面试——经典问题1

1、阶梯问题

问题描述:一个阶梯有n个级,一个人要走完这个阶梯,一步可以走一级或两级,问:共有多少个方案?

解决思路:当n=1时候,只有一种走法,当n=2时候有3种走法;那么n=3时候呢?到第三层的走法是到第一层的走法加上到第二层的走法所以显然这是个经典的递归问题。

  因此有a1=1,a2=2,an= an-1 + an-2,其中n>2;

方法1:

  设斐波那契数列的通项为An,An = (p^n - q^n)/√5,其中p = (√5 - 1)/2,q = (√5 + 1)/2

方法2:

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int Fibonacci(int n)
 5 {
 6     if(n==1)
 7         return 1;
 8     else if(n==2)
 9         return 2;
10     else
11         return ( Fibonacci(n-1)+Fibonacci(n-2) );
12 }
13 
14 int main()
15 {
16     int result=0;
17     for(int i=1;i<=10;i++)
18     {
19         result=Fibonacci(i);
20         cout<<"result="<<result<<endl;
21     }
22     return 0;
23 }

执行结果:

方法3:当要求解的n很大的时候,递归耗时很大,因为其中存在很多重复计算的问题,所以采用动态规划,记录计算值,以减少耗时;

 1 #include<iostream>
 2 using namespace std;
 3 
 4 #define N 11
 5 int main()
 6 {
 7     int i;
 8     int A[N] = {0,1,2};
 9     for(i=3;i<N;i++)
10     {
11         A[i] = A[i-1] + A[i-2];
12         cout<<"result="<<A[i]<<endl;
13     }
14     return 0;
15 }

执行结果:

问题延伸:一步可以走一级或两级或者三级,问:共有多少个方案?

  则有a1=1,a2=2,a3=4,an= an-1 + an-2 + an-3,其中n>3

2、不通过比较,找出两个数的最大值

一旦涉及到不用比较找最大值,一般只能通过位运算来实现

方法一:max = a - ( (a-b) & ( (a-b)>>31 ) )

  如果a > b,则后面部分将会出现(a - b)&(全0),即实现max = a - 0;

  如果a < b,则后面部分将会出现(a - b)&(全1),即实现max = a - (a - b) ;

方法二:max = ( (a+b) + |a-b| ) / 2

  加上 |a-b| 实际上是为了加上a与b的差值,( (a+b) + |a-b| )是想获得最大数的两倍

3、字符串反转

只需要遍历数组的一半就可以实现

 1 void StrReverse(string &s)
 2 {
 3     int i,len = s.length();
 4     char temp;
 5     for(i=0;i<len/2;i++)
 6     {
 7         temp = s[i];
 8         s[i] = s[len-i-1];
 9         s[len-i-1] = temp;
10     }
11 }

4、不用循环反转字符串

不能用到循环就只能——递归实现

 1 string Reverse(string s,int index)
 2 {
 3     if(index==0)
 4         return s.substr(0,1);
 5     return s.substr(index,1) + "" + Reverse(s,index-1);
 6 }
 7 int main()
 8 {
 9     string s;
10     cin>>s;
11     string str_test = Reverse(s,s.length()-1);
12     cout<<str_test<<endl;
13     return 0;
14 }

5、十度好友

问题描述:在社交网络中,如果A、B是好友,B、C是好友,且A、C不是好友,则C成为A的二度好友;同理定义十度好友;若给定一张社交网络图,求A的所有十度好友;

解决思路:两种方式求解

(1)想求十度好友,很容易想到的是利用DFS,把A节点作为根部,用DFS搜索到深度为十的所有节点;

  还有一个细节问题,因为网络是复杂的,从一个结点到另外一个结点的路径不止一条,即D可能是A的三度结点,也可能是A的8度结点,这时应该以三度结点为准;

  因此,如果利用DFS解决问题,需要对遍历过的结点做标记,并且该结点度数信息应该更新为更小的值;

(2)利用BFS解决,总体思路如下:

 1 把A放在queue_1里,设置degree = 0;
 2 while(degree != 0 && !queue_1.empty() )
 3 {
 4     遍历queue_1里所有元素
 5   {
 6         if(queue_1.element的邻居结点没有被访问过)
 7     {
 8             邻居结点放入queue_2中;
 9       从queue_1中删除queue_1.element;
10     }
11   }
12   把queue_2中的所有元素放入queue_1中;
13     degree++;
14 }
15 输出queue_1里的所有元素,即为A的十度好友;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2017.10.1解题报告

---- 预计分数:60+50+0=110 实际分数:60+81+0=144 全场rank13?全校rank1?貌似题很难啊23333 ---- T1...

3699
来自专栏数据派THU

Python能让你上天?带你挖掘隐藏彩蛋~(附代码)

4904
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

2027
来自专栏追不上乌龟的兔子

[奇怪但有用的数据结构]并查集Union Find

严格来讲并查集并不是一个数据结构,而是一个算法,毕竟其英文名直译是联合查找,但作为一个系列,还是当做数据结构讲了。

8367
来自专栏青青天空树

2018-母牛的故事

 有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?

3492
来自专栏数据结构与算法

BZOJ2152: 聪聪可可(点分治)

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

1003
来自专栏HansBug's Lab

1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2917
来自专栏HansBug's Lab

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路 Time Limit: 5 Sec  Memory L...

3366
来自专栏技术博客

设计模式之前奏(UML类图)

本人菜菜一个,最近一直在博客园游走闲逛,看到了各种技术,各种各种……。便看到了大话设计模式这本书,下了电子版的看了看第一章,感觉相当不错,不仅通俗易懂,而且与实...

2283
来自专栏牛客网

宜信大数据中心java研发岗面经

在我小时候,我极力装得像个大人,当我已经不再是小孩的时候,我又希望像个孩子。——列夫·托尔斯泰

1532

扫码关注云+社区

领取腾讯云代金券