這是我的第二個(gè)面試題匯總。想看之前的內(nèi)容，請(qǐng)移步：

在荔浦等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作定制制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,成都全網(wǎng)營(yíng)銷推廣,外貿(mào)營(yíng)銷網(wǎng)站建設(shè),荔浦網(wǎng)站建設(shè)費(fèi)用合理。

http://zhweizhi.blog.51cto.com/10800691/1763237

（若干數(shù)據(jù)結(jié)構(gòu) && 算法面試題【一】（更新完畢））

http://zhweizhi.blog.51cto.com/10800691/1787562

（若干數(shù)據(jù)結(jié)構(gòu) && 算法面試題【三】（更新中））

一、跳臺(tái)階

題目描述

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

f(n) = (最后一次跳一級(jí)臺(tái)階有多少種方法) + (最后一次跳兩級(jí)臺(tái)階有多少種方法)

即：

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

二、變態(tài)跳臺(tái)階

題目描述

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

思路： 跳上n級(jí)臺(tái)階的方法 = (最后一次跳上一級(jí)) + (最后一次跳上兩級(jí)) + ...... + (最后一次跳上n級(jí))

完整代碼：

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的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

完整代碼：

https://github.com/HonestFox/BrushQuestion/blob/master/15_%E7%9F%A9%E5%BD%A2%E8%A6%86%E7%9B%96

四、二進(jìn)制中1的個(gè)數(shù)

題目描述：

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

方法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（最佳）：

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

五、求數(shù)值的整數(shù)次方

題目描述：

給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)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

六、調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

題目描述：

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

完整代碼：

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

七、單鏈表的倒數(shù)第K個(gè)結(jié)點(diǎn)

通常有兩種思路：

1、用2個(gè)指針，一前一后，相距為k， 當(dāng)前面的指針訪問(wèn)到鏈表尾部時(shí)，另一個(gè)指針指向的就是倒數(shù)第K個(gè)結(jié)點(diǎn)。

2、遍歷一次，每次將訪問(wèn)到的結(jié)點(diǎn)的地址壓入一個(gè)棧中，（為什么存放地址呢？因?yàn)槿绻氐念愋捅容^大，那么相比存放元素本身，開銷比較小）然后對(duì)這個(gè)棧進(jìn)行彈出K - 1 次，這時(shí)棧頂?shù)脑鼐褪俏覀円牡箶?shù)第K個(gè)結(jié)點(diǎn)的地址。

思路都比較清晰，這里我采用的是第二種方法

完整代碼：

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

八、反轉(zhuǎn)單鏈表

思路：

遍歷，每次遍歷到的元素加到前一個(gè)元素的后面

完整代碼：

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連接：（這次貼的代碼已經(jīng)比較完整了）

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

（！兒童節(jié)快樂(lè)?。?/p>

九、二叉樹的鏡像

題目描述:
操作給定的二叉樹，將其變換為源二叉樹的鏡像。
輸入描述:
二叉樹的鏡像定義：源二叉樹
         1
        /  \
       2   3
      / \  / \
     4  5 6 7
     鏡像二叉樹
         1
        /  \
       3   2
      / \  / \
     7 6 5  4

思路：

比較簡(jiǎn)單，利用好遞歸的思想就好。

代碼：

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

十、順時(shí)針打印矩陣

題目描述:
輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，
例如，如果輸入如下矩陣：
 1   2   3   4
 5   6   7   8
 9  10 11 12
 13 14 15 16
則依次打印出數(shù)字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函數(shù)的棧

題目描述:
定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。

（其實(shí)就是要求設(shè)計(jì)一個(gè)棧，能夠?qū)崿F(xiàn)在O(1)時(shí)間復(fù)雜度內(nèi)找到最小的元素）

思路：

必須包含兩個(gè)stack類型的成員變量：

   其中一個(gè)存放數(shù)據(jù)(_Data)

   另外一個(gè)存放最小的元素(_MinData)

新元素入棧時(shí)：

   當(dāng)_MinData為空，或新元素的值小于_MinData棧頂?shù)脑貢r(shí)，將新元素入棧_MinData

出棧時(shí)：

   當(dāng)_MinData的棧頂元素是要出棧的元素是（即是_Data的棧頂元素時(shí)），

   將該元素從_MinData彈出

這樣設(shè)計(jì)出來(lái)的棧，_MinData的棧頂元素始終是當(dāng)前棧中存放的最小元素

代碼：

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

十二、從上到下訪問(wèn)二叉樹（層序遍歷）

代碼：

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

十二、復(fù)雜鏈表的復(fù)制

題目描述：
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)）。

代碼：

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

十三、數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)據(jù)

題目描述：

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出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個(gè)數(shù)

題目描述:

輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

網(wǎng)頁(yè)題目：若干數(shù)據(jù)結(jié)構(gòu)&&算法面試題【二】（更新完畢）-創(chuàng)新互聯(lián)
文章起源：http://weahome.cn/article/jogdj.html