面试——经典问题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 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

洛谷讲课手稿

Hello大家好,我是洛谷的HansBug。首先自我介绍下,我现在在北京航空航天大学,计算机科学与技术专业读大二,我参加过2013-2015年的提高组NOIP和...

3074
来自专栏程序员互动联盟

【入门指导】学C语言一段时间了,还是一头雾水该咋办?

学C了一头雾水该怎么办?最简单的方法就是你再学一遍呗。俗话说熟能生巧,铁杵也能磨成针。 但是一味的为学而学,这个好像没什么卵用。为什么学了还是一头雾水,重点就在...

3527
来自专栏区块链大本营

漏洞连载|浮点与精度处理不当的那些事儿

“言治骨角者,既切之而复磋之;治玉石者,既琢之而复磨之,治之已精,而益求其精也。”——宋·朱熹

961
来自专栏ACM小冰成长之路

HDU-6010-Daylight Saving Time

ACM模版 描述 ? 题解 这个题的难点在于题目不好懂,只要读懂了题目,细心一些的人都能做出来。 大致的思路是先预处理出来每年的两个时间节点,也就是每年三月份的...

1879
来自专栏非著名程序员

优秀程序员眼中的整洁代码

有多少程序员,就有多少定义。所以我只询问了一些非常知名且经验丰富的程序员。 ? Bjarne Stroustrup,C++ 语言发明者,C++ Programm...

2007
来自专栏专知

【关关的刷题日记61】Leetcode 102. Binary Tree Level Order Traversal

关关的刷题日记61 – Leetcode 102. Binary Tree Level Order Traversal 题目 ? 题目的意思是让我们按照二叉树每...

2859
来自专栏ThoughtWorks

别忙着撒欢儿了,送你一本《前端函数式攻城指南》可好?

今日推荐 今天推荐欧阳继超老师的新书——《前端函数式攻城指南》,本书获CrossEye重磅推荐,致力于教你用JavaScript编写出优雅的函数式代码,以不一样...

2707
来自专栏落影的专栏

程序员进阶之算法练习(十一)有感而发

前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

35210
来自专栏非著名程序员

七夕节,程序员特有的表白方式!

以上这首告白书,来自于网络,我只是找到了这首程序员的告白诗,最早的时间出现在 2009 年 1 月 5 日,不知道作者是谁。(侵删)

871
来自专栏CSDN技术头条

那些必读的数据库领域论文

之前林仕鼎曾整理过系统架构领域的学习资料,这几天Spark核心团队成员辛湜(Reynold Xin)公开了他整理的一份数据库学习资料列表,Hacker News...

24610

扫码关注云+社区