若干数据结构 && 算法面试题【二】 （更新完毕）

这是我的第二个面试题汇总。想看之前的内容，请移步：

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)

class Solution {public:        int jumpFloor(int number)         {                if (number <= 1)                {                        return number;                }                int first = 1;                int second = 1;                while (--number)                {                        int tmp = second;                        second += first;                        first = tmp;                }                return second;        }};

完整代码：

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：

int  NumberOf1(int n)        {                int cur = 0x00000001;                int count = 0;                for (int i = 0; i < 32; i++)                {                        if ( (n & cur) != 0)                        {                                count++;                        }                        cur = cur << 1;                }                return count;        }

方法2（最佳）：

     //最优解        int NumberOf1Best(int n)        {                int count = 0;                while (n != 0)                {                        ++count;                        n = (n - 1) & n;                }                return count;        }

五、求数值的整数次方

题目描述：

给定一个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)                {                        return NULL;                }                if (pHead1 == NULL)                {                        return pHead2;                }                if (pHead2 == NULL)                {                        return pHead1;                }                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;                }                else if (cur2 != NULL)                {                        NewNode->next = cur2;                }                return NewHead;        }

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

思路：

比较简单，利用好递归的思想就好。

代码：

void Mirror(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 printMatrix(vector > matrix)  {  int max_line = matrix.size();  int max_col = matrix[0].size();  int size = max_line * max_col;  int count = 0;  int min_line = 0;  int min_col = 0;  int cur_line = 0;  int cur_col = 0;  vector 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)  //这里需要判断一下   {    return ret;   }   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++;  }  return ret; }

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的栈顶元素始终是当前栈中存放的最小元素

代码：

class Solution{public: void push(int value) {  _Data.push(value);  if (_MinData.empty() || value < _MinData.top())  {   _MinData.push(value);  } } void pop()  {  if (_Data.top() == _MinData.top())  {   _MinData.pop();  }  _Data.pop(); } int top()  {  return _Data.top(); } int min()  {  return _MinData.top(); }protected: stack _Data; stack _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 PrintFromTopToBottom(TreeNode *root) {  vector ret;  if (root == NULL)  {   return ret;  }  if (root->left == NULL && root->right == NULL)  {   cout << root->val << endl;   ret.push_back(root->val);   return ret;  }  vector 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);   }  }  return ret; }

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)  {   return NULL;  }  RandomListNode *cur = pHead;  while (cur)  {   RandomListNode *tmp = cur->next;   RandomListNode *NewNode = new RandomListNode(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;  }  return NewHead; }

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。

思路：

用哈希表的思想

代码：

int MoreThanHalfNum_Solution(vector numbers)         {                if (numbers.empty())                {                        return 0;                }                int sz = numbers.size();                vector HashList;                HashList.resize(numbers[0] + 1);                for (int i = 0; i < sz; ++i)                {                        if (numbers[i] + 1 > HashList.size())                        {                                HashList.resize(numbers[i] + 1);                        }                        ++HashList[numbers[i]];                        if (HashList[numbers[i]] > sz / 2)                        {                                return numbers[i];                        }                }                return 0;        }

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 GetLeastNumbers_Solution(vector input, int k)         {                vector HashList;                vector Ret;                if (k > input.size())                {                        return Ret;                }                for (size_t i = 0; i < input.size(); ++i)                {                        if (HashList.size() < input[i] + 1)                        {                                HashList.resize(input[i] + 1);                        }                        ++HashList[input[i]];                }                for (size_t i = 0; i < HashList.size(); ++i)                {                        while (HashList[i]--)                        {                                Ret.push_back(i);                                k--;                                if (k == 0)                                {                                        return Ret;                                }                        }                }                return Ret;        }

github：

https://github.com/HonestFox/BrushQuestion/blob/master/30_%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0