若干数据结构 && 算法面试题【二】 （更新完毕）
这是我的第二个面试题汇总。想看之前的内容，请移步：
http://zhweizhi.blog.51cto.com/10800691/1763237
（若干数据结构 && 算法面试题【一】（更新完毕））
http://zhweizhi.blog.51cto.com/10800691/1787562
（若干数据结构 && 算法面试题【三】（更新中））
一、跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
f(n) = (最后一次跳一级台阶有多少种方法) + (最后一次跳两级台阶有多少种方法)
即：
f(n) = f(n - 1) + f(n - 2)
classSolution{public:intjumpFloor(intnumber){if(number<=1){returnnumber;}intfirst=1;intsecond=1;while(--number){inttmp=second;second+=first;first=tmp;}returnsecond;}};
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/13_%E8%B7%B3%E5%8F%B0%E9%98%B6
二、变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路： 跳上n级台阶的方法 = (最后一次跳上一级) + (最后一次跳上两级) + ...... + (最后一次跳上n级)
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/14_%E5%8F%98%E6%80%81%E8%B7%B3%E5%8F%B0%E9%98%B6
三、矩形覆盖
题目描述：
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/15_%E7%9F%A9%E5%BD%A2%E8%A6%86%E7%9B%96
四、二进制中1的个数
题目描述：
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
方法1：
intNumberOf1(intn){intcur=0x00000001;intcount=0;for(inti=0;i<32;i++){if((n&cur)!=0){count++;}cur=cur<<1;}returncount;}
方法2（最佳）：
//最优解intNumberOf1Best(intn){intcount=0;while(n!=0){++count;n=(n-1)&n;}returncount;}
五、求数值的整数次方
题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/17_%E6%95%B0%E5%80%BC%E7%9A%84%E6%95%B4%E6%95%B0%E6%AC%A1%E6%96%B9
六、调整数组顺序使奇数位于偶数前面
题目描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/18_%E8%B0%83%E6%95%B4%E6%95%B0%E7%BB%84%E9%A1%BA%E5%BA%8F%E4%BD%BF%E5%A5%87%E6%95%B0%E4%BD%8D%E4%BA%8E%E5%81%B6%E6%95%B0%E5%89%8D%E9%9D%A2
七、单链表的倒数第K个结点
通常有两种思路：
1、用2个指针，一前一后，相距为k， 当前面的指针访问到链表尾部时，另一个指针指向的就是倒数第K个结点。
2、遍历一次，每次将访问到的结点的地址压入一个栈中，（为什么存放地址呢？因为如果元素的类型比较大，那么相比存放元素本身，开销比较小）然后对这个栈进行弹出K - 1 次，这时栈顶的元素就是我们要的倒数第K个结点的地址。
思路都比较清晰，这里我采用的是第二种方法
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/19_%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACk%E4%B8%AA%E7%BB%93%E7%82%B9
八、反转单链表
思路：
遍历，每次遍历到的元素加到前一个元素的后面
完整代码：
https://github.com/HonestFox/BrushQuestion/blob/master/20_%E5%8F%8D%E8%BD%AC%E5%8D%95%E9%93%BE%E8%A1%A8
八、合并有序单链表
代码：
ListNode*Merge(ListNode*pHead1,ListNode*pHead2){if(pHead1==NULL&&pHead2==NULL){returnNULL;}if(pHead1==NULL){returnpHead2;}if(pHead2==NULL){returnpHead1;}ListNode*cur1=pHead1;ListNode*cur2=pHead2;ListNode*NewNode=NULL;if(cur1->val<=cur2->val){NewNode=cur1;cur1=cur1->next;}else{NewNode=cur2;cur2=cur2->next;}ListNode*NewHead=NewNode;while(cur1!=NULL&&cur2!=NULL){if(cur1->val<=cur2->val){NewNode->next=cur1;NewNode=NewNode->next;cur1=cur1->next;}else{NewNode->next=cur2;NewNode=NewNode->next;cur2=cur2->next;}}if(cur1!=NULL){NewNode->next=cur1;}elseif(cur2!=NULL){NewNode->next=cur2;}returnNewHead;}
github连接：（这次贴的代码已经比较完整了）
https://github.com/HonestFox/BrushQuestion/blob/master/21_%E5%90%88%E5%B9%B6%E6%9C%89%E5%BA%8F%E5%8D%95%E9%93%BE%E8%A1%A8
（！儿童节快乐！）
九、二叉树的镜像
题目描述:
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
1
/ \
2 3
/ \ / \
4 5 6 7
镜像二叉树
1
/ \
3 2
/ \ / \
7 6 5 4
思路：
比较简单，利用好递归的思想就好。
代码：
voidMirror(TreeNode*pRoot){if(pRoot==NULL){return;}_Mirror(pRoot);}protected:void_Mirror(TreeNode*pRoot){if(pRoot==NULL){return;}if(pRoot->left==NULL&&pRoot->right==NULL){return;}swap(pRoot->left,pRoot->right);_Mirror(pRoot->left);_Mirror(pRoot->right);}
github连接：
https://github.com/HonestFox/BrushQuestion/commit/8548f4e9704045be0ae0530a4c45a91b561c9281
十、顺时针打印矩阵
题目描述:
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
例如，如果输入如下矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
代码：
vector<int>printMatrix(vector<vector<int>>matrix){intmax_line=matrix.size();intmax_col=matrix[0].size();intsize=max_line*max_col;intcount=0;intmin_line=0;intmin_col=0;intcur_line=0;intcur_col=0;vector<int>ret;while(count<size){//横，从左向右for(cur_col;cur_col<max_col;++cur_col){ret.push_back(matrix[cur_line][cur_col]);count++;}cur_col=max_col-1;cur_line=min_line+1;min_line++;//纵，从上到下for(cur_line;cur_line<max_line;cur_line++){ret.push_back(matrix[cur_line][cur_col]);count++;}if(count>=size)//这里需要判断一下{returnret;}cur_col=max_col-2;cur_line=max_line-1;max_col--;//横，从右到左for(cur_col;cur_col>=min_col;cur_col--){ret.push_back(matrix[cur_line][cur_col]);count++;}cur_col=min_col;cur_line=max_line-2;max_line--;//纵，从下到上for(cur_line;cur_line>=min_line;cur_line--){ret.push_back(matrix[cur_line][cur_col]);count++;}cur_col=min_col+1;cur_line=min_line;min_col++;}returnret;}
github连接：
https://github.com/HonestFox/BrushQuestion/blob/master/24_%E9%A1%BA%E6%97%B6%E9%92%88%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5
十一、包含min函数的栈
题目描述:
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
（其实就是要求设计一个栈，能够实现在O(1)时间复杂度内找到最小的元素）
思路：
必须包含两个stack类型的成员变量：
其中一个存放数据(_Data)
另外一个存放最小的元素(_MinData)
新元素入栈时：
当_MinData为空，或新元素的值小于_MinData栈顶的元素时，将新元素入栈_MinData
出栈时：
当_MinData的栈顶元素是要出栈的元素是（即是_Data的栈顶元素时），
将该元素从_MinData弹出
这样设计出来的栈，_MinData的栈顶元素始终是当前栈中存放的最小元素
代码：
classSolution{public:voidpush(intvalue){_Data.push(value);if(_MinData.empty()||value<_MinData.top()){_MinData.push(value);}}voidpop(){if(_Data.top()==_MinData.top()){_MinData.pop();}_Data.pop();}inttop(){return_Data.top();}intmin(){return_MinData.top();}protected:stack<int>_Data;stack<int>_MinData;};
github:
https://github.com/HonestFox/BrushQuestion/blob/master/25_%E5%8C%85%E5%90%ABmin%E5%87%BD%E6%95%B0%E7%9A%84%E6%A0%88
十二、从上到下访问二叉树（层序遍历）
代码：
vector<int>PrintFromTopToBottom(TreeNode*root){vector<int>ret;if(root==NULL){returnret;}if(root->left==NULL&&root->right==NULL){cout<<root->val<<endl;ret.push_back(root->val);returnret;}vector<TreeNode*>box;TreeNode*cur=root;TreeNode*prev=cur;while(ret.empty()||!box.empty()){if(!box.empty()){cur=box.front();box.erase(box.begin());}cout<<cur->val<<"";ret.push_back(cur->val);if(cur->left){//cout<<cur->left->val<<"";box.push_back(cur->left);}if(cur->right){//cout<<cur->right->val<<"";box.push_back(cur->right);}}returnret;}
github：
https://github.com/HonestFox/BrushQuestion/blob/master/27_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86
十二、复杂链表的复制
题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
代码：
RandomListNode*Clone(RandomListNode*pHead){if(pHead==NULL){returnNULL;}RandomListNode*cur=pHead;while(cur){RandomListNode*tmp=cur->next;RandomListNode*NewNode=newRandomListNode(cur->label);cur->next=NewNode;NewNode->next=tmp;cur=tmp;}cur=pHead;while(cur){RandomListNode*pos=cur->next;if(cur->random){pos->random=(cur->random)->next;}cur=pos->next;}cur=pHead;RandomListNode*cur1=cur->next;RandomListNode*NewHead=cur1;while(cur->next->next!=NULL){cur->next=cur->next->next;cur=cur->next;cur1->next=cur1->next->next;cur1=cur1->next;}returnNewHead;}
github:
https://github.com/HonestFox/BrushQuestion/blob/master/28_%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6
十三、数组中出现次数超过一半的数据
题目描述：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：
用哈希表的思想
代码：
intMoreThanHalfNum_Solution(vector<int>numbers){if(numbers.empty()){return0;}intsz=numbers.size();vector<int>HashList;HashList.resize(numbers[0]+1);for(inti=0;i<sz;++i){if(numbers[i]+1>HashList.size()){HashList.resize(numbers[i]+1);}++HashList[numbers[i]];if(HashList[numbers[i]]>sz/2){returnnumbers[i];}}return0;}
github：
https://github.com/HonestFox/BrushQuestion/blob/master/29_%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E6%AC%A1%E6%95%B0%E8%B6%85%E8%BF%87%E4%B8%80%E5%8D%8A%E7%9A%84%E6%95%B0%E5%AD%97
十四、最小的K个数
题目描述:
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
代码：
vector<int>GetLeastNumbers_Solution(vector<int>input,intk){vector<int>HashList;vector<int>Ret;if(k>input.size()){returnRet;}for(size_ti=0;i<input.size();++i){if(HashList.size()<input[i]+1){HashList.resize(input[i]+1);}++HashList[input[i]];}for(size_ti=0;i<HashList.size();++i){while(HashList[i]--){Ret.push_back(i);k--;if(k==0){returnRet;}}}returnRet;}
github：
https://github.com/HonestFox/BrushQuestion/blob/master/30_%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
