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

相关文章

来自专栏算法修养

HDU 1104 Remainder(BFS 同余定理)

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1104 在做这道题目一定要对同余定理有足够的了解,所以对这道...

3226
来自专栏desperate633

LeetCode 121. Best Time to Buy and Sell Stock题目Solution

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例 给出一...

573
来自专栏新智元

【看图识算法】这是你见过最简单的 “算法说明书”

【新智元导读】像阅读宜家的安装说明书一样学习算法,是怎样的体验?不伦瑞克工业大学的三名研究者制作了这份“算法说明书”,简明传神地解释了一些基本算法,一起来看图说...

3418
来自专栏落影的专栏

程序员进阶之算法练习(二十三)

前言 趁着8月还没结束,更新一篇算法练习。 正文 1. Alyona and mex 题目链接 题目大意: mex()定义:mex(arr)是 数组arr的...

3887
来自专栏小樱的经验随笔

51Nod 1632 B君的连通(递归,快速幂)

1632 B君的连通 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 B国拥有n个城市,其交通系统呈树状结构,即任意两个城市...

2397
来自专栏专知

【 关关的刷题日记53】 Leetcode 100. Same Tree

关关的刷题日记53 – Leetcode 100. Same Tree 题目 Given two binary trees, write a function ...

3157
来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

702
来自专栏落影的专栏

程序员进阶之算法练习(五)

前言 这次的题目质量非常高,除了第一道签到题之外都是很不错的想法题,值得学习。 几乎所有的程序员都能做A题; 思维缜密的程序员可以做B题; 数学还没还给老师的能...

3449
来自专栏小樱的经验随笔

DFS中的奇偶剪枝学习笔记

奇偶剪枝学习笔记 描述 现假设起点为(sx,sy),终点为(ex,ey),给定t步恰好走到终点, s | ...

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

P2658 汽车拉力比赛

题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

2568

扫码关注云+社区