1) 逆序输出字符串 输入：abcdefg 输出：gfedcba ~~~ #include<iostream> using namespace std; void reversePrint(const char* str, int n){ if(n == strlen(str)) return; reversePrint(str, n + 1); cout<<str[n]; } int main(){ char *str = "abcdefg"; reversePrint(str, 0); return 0; } ~~~ 2)用递归求数组的最大值 输入：1，3，4，8，2 输出：8 ~~~ int maxElement(int A[], int n){ if(n == 0) return A[0]; return max(maxElement(A, n-1), A[n]); } ~~~

输入：两个序列A、B，A作栈的push序列，判断B是否可能是A的pop序列。 ~~~ #include<iostream> #include<stack> using namespace std; bool solution(const int* apush, const int* apop, int len){ if(len < 1) return false; int i = 0, j = 0; stack<int> stack; while(j < len || !stack.empty()){ if(i < len){ if(apush[i] != apop[j]) stack.push(apush[i++]); else i++, j++; } while(!stack.empty() && stack.top() == apop[j]) stack.pop(), j++; if(i == len && !stack.empty()) break; } return stack.empty() && j == len; } int main(){ int aPush[5] = {1, 2, 3, 4, 5}; int aPop[5] = {4, 3, 5, 2, 1}; cout<<solution(aPush, aPop, 5); return 0; } //output: 1 ~~~

听过一些小伙伴被问到一个问题，题目就是： 给你一个字符串，还有这些字符串出现的权重，让你随机生成字符串，并且字符的权重越高，出现的概率越大。 分析： 假设有三个字符：a , b ,c ，它们的权重分别是2，3，5。我们要生成的字符串中的字符必须是这三个字符之一，因为但是权重不同，a，b，c分别占总权重的比例是：20%，30%，50%，这也是它们生成的概率，概率都出来了，那就得根据概率多的，命中的概率越多，于是，来分配一个数字区间[1,10]，然后按照出现的概率来分每个字母占用的子区间，概率高的，占用的就越高，可以这样分配：a-[1,2] , b-[3,5]，c-[6,10],我们用rand()来生成一个随机数，如果生成的数不是[1,10]之内的，就丢弃掉，这样就可以使在[1,10]之间生成每个数的概率都是一样的，然后根据每次生成的数字去找属于哪个字符的，就选用哪个字符。伪代码如下： ~~~ def procedure: a<-[1,2], b<-[3,5], c<-[6,10] num <-rand() if num in [1, 10]: if num in [1, 2]: return a else if num in [3, 5]: return b else return c else return procedure ~~~

[leetcode](https://oj.leetcode.com/problems/same-tree/) 一道判断两棵树是否相同的题： Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. 直接写递归了，代码行数非常少 ~~~ /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { if(p == NULL && q == NULL)return true; if(p == NULL && q != NULL)return false; if(p != NULL && q == NULL)return false; if(p->val == q->val)return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); else return false; } }; ~~~ 也可以用队列对两棵二叉树层次遍历，在遍历的同时判断节点是否相同。

求最大公约数哪个强，果断GCD，非递归版本和递归版本如下： ~~~ #include<iostream> using namespace std; int gcd(int a, int b){ //非递归版本 int big = max(a, b); int small = min(a, b); int temp; while(small != 0 ){ temp = big % small; big = small; small = temp; } return big; } int gcd_(int a, int b){//递归版本 int big = max(a, b); int small = min(a, b); int temp = big % small; return temp == 0 ? small : gcd_(small, temp); } int main(){ int a = 34, b = 8; cout<<gcd(a, b)<<endl; cout<<gcd_(a, b)<<endl; return 0; } //output: // 2 // 2 ~~~

经过上次去面试，[面试官要求实现strstr()](http://blog.csdn.net/kamsau/article/details/39352061)，当场就蒙了。这个题目是模式匹配问题，《算法导论》里列出了几种字符串匹配算法： 朴素算法 |  Rabin-Karp | 有限自动机算法 | Knuth-Morris-Pratt (KMP)  各种方法都有自己的优缺点，我觉得，还有一些方法可以参考： 1）比如像求最长公共子串那样，用动态规划，最后判断最长公共子串的最大值是不是模式串的长度，不过，这有点绕。 2）用后缀数组，这个也有点绕，实现起来也有点麻烦，就不说了。 个人觉得，还是KMP好，KMP该怎么写呢，立马抄起书《数据结构（C语言版）》，看了一下，感觉，KMP实现起来，代码是很少的，效率还算可以了，实现的过程中，难就难在如何构造next[] 数组，以及如何理解next[]，对避免指针无效回退的作用。看了一个上午，总算是明白了。现就贴下代码，做下笔记。 ~~~ #include<iostream> using namespace std; void get_next(const char* s, int* next){ int i = 0, j = -1; next[0] = -1; int len = strlen(s); while(i < len){ if(j == -1 || s[i] == s[j]){ ++i, ++j; if(s[i] != s[j]) next[i] = j; else next[i] = next[j]; } else j = next[j]; } } int KMP_strstr(const char* s, const char* p){ int i = 0, j = 0; int len_s = strlen(s), len_p = strlen(p); int* next = new int[len_p]; get_next(s, next); while(i < len_s && j < len_p){ if(j == -1 || s[i] == p[j]) ++i, ++j; else j = next[j]; } delete []next; if(j == len_p) return i - len_p; else return -1; } int main(){ const int len = 6; const char *s = "abaabc"; cout<<KMP_strstr("aaabbabaabcaad", s); return 0; }//output: 5 ~~~

Implement pow(x, n).题目在[这里](https://oj.leetcode.com/problems/powx-n/)，二分解法如下： ~~~ class Solution { public: double pow(double x, int n) { double ans; if(n < 0){ ans = power(x, -n); return (double)1 / ans; }else{ return power(x, n); } } double power(double x, int n) { double ans; if(n == 0) ans=1; else { ans=power(x*x, n/2); if(n%2==1) ans*=x; } return ans; } }; ~~~     还可以这么写： ~~~ class Solution { public: double pow(double x, int n) { double ans; if(n < 0) return (double)1 / power(x, -n); else return power(x, n); } double power(double a, int n) { double ans = 1; while(n > 0){ if(n&1) ans *= a; a *= a; n >>= 1; } return ans; } }; ~~~

Given a string s consists of upper/lower-case alphabets and empty space characters `' '`, return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only. For example,  Given s = `"Hello World"`, return `5`. ~~~ class Solution { public: int lengthOfLastWord(const char *s) { int ans = 0, prev = 0; bool space = false; for(int i = 0; s[i] != NULL; ++i){ if(s[i] == ' ') { if(space == false)prev = ans, ans = 0, space = true; else continue; }else ans++, space = false; } if(ans == 0) return prev; return ans; } }; ~~~    

题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。 在[这里](http://zhedahht.blog.163.com/blog/static/25411174200731844235261/)看到这道面试题，思路是： 1）每次可以跳1级，也可以跳2级，如果当前只有1级台阶，那么就只有一次跳法；如果当前只有2级台阶，就有2种跳法（一种是每次跳1级，跳2次；另一种是一次跳2级，就跳完），也即 f(1) = 1; f(2) = 2。 2）假设有n级台阶要跳，如果最后一步是跳1级，那么剩下的就只有前面的n-1级台阶的步数了；如果最后一步是跳2级，那么剩下的就是前面n-2级台阶的步数了。总结两种情况，得出状态转移方程： f（n) = f(n-1) + f(n-2)。 经过上面的过程，可以写出这样的代码：    ~~~ int jumpstep(int n){ if(n == 1 || n == 2) return n; else return jumpstep(n-1) + jumpstep(n-2); } ~~~ 代码行数很少了，但是效率很低，因为有很多重复计算，于是，想出了另一个： ~~~ int jumpstep2(int n){ if(n == 1 || n ==2) return n; int *a = new int[n+1]; a[1] = 1; a[2] = 2; for(int i = 3; i <= n ; ++i){ a[i] = a[i-1] + a[i-2]; } int ret = a[n]; delete []a; return ret; } ~~~ 用一个表了记录计算结果。接着，来粗劣测试一下这两种方法的运行时间。上测试代码： ~~~ #include<iostream> #include<time.h> using namespace std; int jumpstep2(int n){ if(n == 1 || n ==2) return n; int *a = new int[n+1]; a[1] = 1; a[2] = 2; for(int i = 3; i <= n ; ++i){ a[i] = a[i-1] + a[i-2]; } int ret = a[n]; delete []a; return ret; } int jumpstep(int n){ if(n == 1 || n == 2) return n; else return jumpstep(n-1) + jumpstep(n-2); } void test_time(int (*func)(int), int n){ long bTime = clock(); cout<<"-----------------------------------"<<endl; cout<<"result is: "<<func(n)<<endl; long eTime = clock(); cout<<"cost time: "<<(eTime - bTime)<<"ms"<<endl; } void test(){ int n; cout<<"input n to test: "; cin>>n; test_time(jumpstep, n); test_time(jumpstep2, n); } int main(){ test(); return 0; } ~~~ 运行结果如图：     统计为如下表：  当n = 50的时候，递归版本非常慢，等了好久都没出结果，于是干脆不等了。 当n比较大时，非递归版本运行速度比较高。 参考： [http://zhedahht.blog.163.com/blog/static/25411174200731844235261/](http://zhedahht.blog.163.com/blog/static/25411174200731844235261/)

之前去面试遇到了这个问题，题目：找出无序数组中第二大的数字。 定睛一看，好简单，一次遍历就可以找出第二大的数字，不过，这样写没有什么特别之处，因为实在是太简单了。自己仔细想想起了之前做过的题，看看有没有什么类似的。于是，想起了之前在网上看到的一道面试题：找出无序数组中最小的k个数。 要找出最小的k个数，可以用快速选择算法，只要在快速排序之后，枢纽刚好是第k+1个数，那么，他左边的数，刚好就是最小的k个数。要找出无序数组中第二大的数字，可以这样转换： 0）假设数组中有n个元素，a1~an，而我们要求第k大的数字，就相当于求排序后的第m = n - k + 1个数字。 1）假设一次快速排序之后，如果枢纽的是第x个（1~n）。 2）如果x = m，则这个枢纽ax就是我们要求的第k大的数字，结束；如果x < m，则对a0 ~ ax-1进行一次快速排序，重复第2）步；如果x > m，则对ax+1 ~ an 进行一次快速排序，重复第2）步。 快速选择的代码如下： ~~~ //a[] - 要排序的数组 //b - 要排序的子区间的开始索引 //e - 要排序的子区间的结束索引 //k - 求出排序后第k个数 int quickselect(int a[], int b, int e, int k){ int i = b ; int j = e + 1; int x = a[i]; while(true){ while(a[++i] < x && i < j); while(a[--j] > x); if(i >= j) break; else swap(a[i], a[j]); } a[b] = a[j]; a[j] = x; if(k - 1 == j) return a[j]; else if(k - 1 > j) return quickselect(a, j + 1, e, k); else return quickselect(a, b, j - 1, k); } ~~~ 总结：快速选择可以用于这类面试题： 1）求出无序数组中第k大的数 2）求出无序数组中最大/小的k个数

最近在[这里](http://zhedahht.blog.163.com/blog/static/254111742007228357325/)看到一道面试题，看了题目和作者的解答后，感觉真是强大。 题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树  则打印出两条路径：10, 12和10, 5, 7。 二元树结点的数据结构定义为： ~~~ struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node }; ~~~ 作者的解答为： ~~~ /////////////////////////////////////////////////////////////////////// // Find paths whose sum equal to expected sum /////////////////////////////////////////////////////////////////////// void FindPath ( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum, // the expected sum std::vector<int>& path, // a path from root to current node int& currentSum // the sum of path ) { if(!pTreeNode) return; currentSum += pTreeNode->m_nValue; path.push_back(pTreeNode->m_nValue); // if the node is a leaf, and the sum is same as pre-defined, // the path is what we want. print the path bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight); if(currentSum == expectedSum && isLeaf) { std::vector<int>::iterator iter = path.begin(); for(; iter != path.end(); ++ iter) std::cout << *iter << '\t'; std::cout << std::endl; } // if the node is not a leaf, goto its children if(pTreeNode->m_pLeft) FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum); if(pTreeNode->m_pRight) FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum); // when we finish visiting a node and return to its parent node, // we should delete this node from the path and // minus the node's value from the current sum currentSum -= pTreeNode->m_nValue; path.pop_back(); } ~~~ 仔细看代码，你会发现，这种方法遍历了解空间树，所有的叶子节点都会访问到， 如果二叉树是这样的呢：  按照这种方法，20的两个孩子都会访问到，但是，这在做无用功，因为，题目要求的是从根节点到叶子节点的路径和为22，当访问到20的时候，路径和已是30了（大于22），再访问20的孩子，路径和也会大于22，这样就没有必要再访问20的孩子了。 所以，应该避免这种无效搜索，在遍历每个节点的时候，先判断路径和是否大于目标值，如果大于的话，则不要遍历该节点的孩子，并且回溯。 优化后的代码为： ~~~ void FindPath( BinaryTreeNode* pTreeNode, // a node of binary tree int expectedSum, // the expected sum std::vector<int>& path, // a path from root to current node int& currentSum // the sum of path ) { if(!pTreeNode) return; currentSum += pTreeNode->m_nValue; if(currentSum > expectedSum){ //判断路径和是否会超出目标值，超出则回溯 currentSum -= pTreeNode->m_nValue; return; } path.push_back(pTreeNode->m_nValue); // if the node is a leaf, and the sum is same as pre-defined, // the path is what we want. print the path bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight); if(currentSum == expectedSum && isLeaf) { std::vector<int>::iterator iter = path.begin(); for(; iter != path.end(); ++ iter) std::cout << *iter << '\t'; std::cout << std::endl; } // if the node is not a leaf, goto its children if(pTreeNode->m_pLeft) FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum); if(pTreeNode->m_pRight) FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum); // when we finish visiting a node and return to its parent node, // we should delete this node from the path and // minus the node's value from the current sum currentSum -= pTreeNode->m_nValue; path.pop_back(); } ~~~ 在原来的代码里增加了如下代码： ~~~ if(currentSum > expectedSum){ //判断路径和是否会超出目标值，超出则回溯 currentSum -= pTreeNode->m_nValue; return; } ~~~ 剪去无效的子树，避免无效搜素，提高效率。 参考：[http://zhedahht.blog.163.com/blog/static/254111742007228357325/](http://zhedahht.blog.163.com/blog/static/254111742007228357325/)

> 原文出处：[一起做过的面试题](http://blog.csdn.net/column/details/noodles.html) 作者：[kamsau](http://blog.csdn.net/kamsau) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 一起做过的面试题 > 面试中经常出现的算法编程题