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

這是我的第三個面試題匯總。

想看之前的內(nèi)容請移步

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

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

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

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

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

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

另外我的全部刷題代碼都在這里

https://github.com/HonestFox/BrushQuestion

//第四篇啦終于放暑假啦可以安安心心學(xué)習(xí)啦  (●ˇˇ●)

//因?yàn)閯傞_始刷題的時候還沒有接觸過二叉樹，所以只要遇到二叉樹的問題就跳過了

//慢慢的居然積壓了這么多，

//如今題總算快刷完了  接下來的這些問題主要是 二叉樹相關(guān)的面試題了

————————————————————————————————————————

一、帶環(huán)鏈表中環(huán)的入口

題目描述:
一個鏈表中包含環(huán)請找出該鏈表的環(huán)的入口結(jié)點(diǎn)。

分析

    · 首先用兩個指針 Fast 和 SlowFast每次走兩步Slow每次走一步這樣最終這兩個指針會在環(huán)內(nèi)相遇相遇時讓它們停下來;

    · 這時設(shè)Slow走的步數(shù)為s則Fast走的步數(shù)為2s 此外Fast肯定比Slow多走一個環(huán)長 r所以 s = r

    · 設(shè)起點(diǎn)到環(huán)入口點(diǎn)這一段的長度為x    則相遇時Slow在環(huán)內(nèi)走了 r - x,  那么相遇點(diǎn)繼續(xù)走也就是后半部分到環(huán)入口的距離為   r - (r - x) = x   可以看出x剛好也是起點(diǎn)到環(huán)入口的舉例

    · 所以再讓兩個指針分別從pHead 和 相遇點(diǎn)開始每次走一步直到兩個指針相交這時的交點(diǎn)就是環(huán)的入口

    ·

代碼

 ListNode* EntryNodeOfLoop(ListNode* pHead)
 {
  if (pHead == NULL || pHead->next == NULL || pHead->next->next == NULL)
  {
   return NULL;
  }
  if (pHead->next == pHead)
  {
   return pHead;
  }
  ListNode *FastNode = pHead;
  ListNode *SlowNode = pHead;
  while (FastNode != SlowNode || FastNode == pHead)
  {
   FastNode = FastNode->next->next;
   SlowNode = SlowNode->next;
   if (SlowNode == pHead)
   {
    return pHead;;
   }
  }
  ListNode *pos = FastNode;
  ListNode *cur = pHead;
  while (FastNode != cur)
  {
   FastNode = FastNode->next;
   cur = cur->next;
  }
  return cur;
 }

github:

https://github.com/HonestFox/BrushQuestion/blob/master/55_%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3%E7%BB%93%E7%82%B9

二、二叉樹的下一個結(jié)點(diǎn)

題目描述:
給定一個二叉樹和其中的一個結(jié)點(diǎn)請找出中序遍歷順序的下一個結(jié)點(diǎn)并且返回。
注意樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)同時包含指向父結(jié)點(diǎn)的指針。

github:

https://github.com/HonestFox/BrushQuestion/blob/master/56_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%8A%82%E7%82%B9

三、對稱的二叉樹

題目描述
請實(shí)現(xiàn)一個函數(shù)用來判斷一顆二叉樹是不是對稱的。注意如果一個二叉樹同此二叉樹的鏡像是同樣的定義其為對稱的。

github

https://github.com/HonestFox/BrushQuestion/blob/master/57_%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91

四、把二叉樹打印成多行

題目描述
從上到下按層打印二叉樹，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

github：

https://github.com/HonestFox/BrushQuestion/blob/master/58_%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%A0%91%E6%89%93%E5%8D%B0%E6%88%90%E5%A4%9A%E8%A1%8C

五、之字形打印二叉樹

題目描述

請實(shí)現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

github：

https://github.com/HonestFox/BrushQuestion/blob/master/59_%E4%B9%8B%E5%AD%97%E5%BD%A2%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91

六、序列化與反序列化二叉樹

github：

https://github.com/HonestFox/BrushQuestion/blob/master/60_%E5%BA%8F%E5%88%97%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91

七、求二叉樹中兩個節(jié)點(diǎn)最近的公共祖先結(jié)點(diǎn)

struct TreeNode
{
public:
	TreeNode(int val)
		:_val(val)
		, _left(NULL)
		, _right(NULL)
	{}
public:
	int _val;
	TreeNode *_left;
	TreeNode *_right;
};

可以訪問父節(jié)點(diǎn)的話：

  首先，假設(shè)如果這顆二叉樹的結(jié)點(diǎn)可以有指向父節(jié)點(diǎn)的指針，那么問題可以轉(zhuǎn)化為對一顆三叉鏈，給定兩個結(jié)點(diǎn)求他們最近的公共祖先結(jié)點(diǎn)。

   所以，如果對上圖這顆樹的 5結(jié)點(diǎn) 和 8結(jié)點(diǎn)求他們的公共祖先結(jié)點(diǎn)，我們可以獲得他們到根節(jié)點(diǎn)的鏈表形式路徑，并且這兩個鏈表肯定是相交的。它們分別是：   8 -> 4 -> 2 -> 1    以及   5 -> 2 -> 1   

     這樣，問題就轉(zhuǎn)化成：尋找兩個鏈表的第一處交點(diǎn)。

時間復(fù)雜度O(log2(N) * 5)   =  O(log2(N)

如果這棵樹是搜索樹的話：

   我們知道，對于一顆二叉搜索樹的每個結(jié)點(diǎn)都滿足：左子樹的所有結(jié)點(diǎn)的值都小于當(dāng)前結(jié)點(diǎn)，右子樹的所有節(jié)點(diǎn)的值都大于當(dāng)前結(jié)點(diǎn)。 

   因此，如果給定兩個結(jié)點(diǎn)，就可以從根節(jié)點(diǎn)開始，判斷當(dāng)前結(jié)點(diǎn)的值和兩個目標(biāo)節(jié)點(diǎn)的值的大小關(guān)系：

 1、如果當(dāng)前結(jié)點(diǎn)的值比其中一個要找的結(jié)點(diǎn)小，比另一個要找的結(jié)點(diǎn)大，則說明要找的兩個結(jié)點(diǎn)分別在這個結(jié)點(diǎn)的左右子樹中，所以當(dāng)前結(jié)點(diǎn)一定是要找的結(jié)點(diǎn)。

 2、如果當(dāng)前結(jié)點(diǎn)比要找的兩個結(jié)點(diǎn)都大，則說明兩個結(jié)點(diǎn)都在當(dāng)前結(jié)點(diǎn)的左子樹，那么就在左子樹里面繼續(xù)找。

 3、如果當(dāng)前結(jié)點(diǎn)比要找的兩個結(jié)點(diǎn)都小，反之。

現(xiàn)在將這棵樹限制為一顆普通的二叉樹：

   這時，就沒法再利用數(shù)值上的關(guān)系來確定結(jié)點(diǎn)在當(dāng)前結(jié)點(diǎn)的左樹中還是右樹中了...不過，還是可以用這種思路，只不過在確定目標(biāo)節(jié)點(diǎn)的位置時，需要遍歷來找。

    代碼中，我用的實(shí)際上時前序遍歷，對每一個結(jié)點(diǎn) 都可以看成一個單獨(dú)的問題，先判斷當(dāng)前結(jié)點(diǎn)的左結(jié)點(diǎn)和右結(jié)點(diǎn)有沒有要找的結(jié)點(diǎn)，如果有，直接返回當(dāng)前結(jié)點(diǎn)，如果沒有，就在其左子樹和右子樹里繼續(xù)找，如果左子樹和右子樹都找到了，則說明當(dāng)前結(jié)點(diǎn)就是要找的結(jié)點(diǎn)；如果只有其中一側(cè)找到了，則將找到的那一側(cè)的子樹視為一個新的子問題。（都沒找到？）

 具體的代碼實(shí)現(xiàn)如下：

class BinaryTree()
{
public:
    TreeNode* GetNearRoot_2(TreeNode *Node1, TreeNode *Node2)
	{
		return _GetNearRoot_2(_root, Node1, Node2);
	}
protected:
	TreeNode* _GetNearRoot_2(TreeNode *root, TreeNode *Node1, TreeNode *Node2)
	{
		if (root == NULL || Node1 == NULL || Node2 == NULL)
		{
			return NULL;
		}
		if (root->_left == Node1 || root->_right == Node1 || root->_left == Node2 || root->_right == Node2)
		{
			return root;
		}
		TreeNode *pLeft = _GetNearRoot_2(root->_left, Node1, Node2);
		TreeNode *pRight = _GetNearRoot_2(root->_right, Node1, Node2);


		if (pLeft != NULL && pRight != NULL)	//左右都不為空，說明分別在根節(jié)點(diǎn)的 左右 子樹 ，則肯定他們的最近父節(jié)點(diǎn)就是根節(jié)點(diǎn)
		{
			return root;
		}
		else if (pLeft != NULL)
		{
			return pLeft;
		}
		else if (pRight != NULL)
		{
			return pRight;
		}
	}
protected:
    TreeNode *_root;

}

    其實(shí)可以看出，我用遞歸實(shí)現(xiàn)需要注意的就是，找到了以后，要將當(dāng)前結(jié)點(diǎn)傳遞回上層的遞歸，這里我用返回值的方式向上傳遞。

（舉例子說明 --2）

    采用這種方法，思路比較簡單，代碼坑比較多。

    時間復(fù)雜度為 O(N) * O(N)

比較高效的方法：

    其實(shí)，可以觀察到，從根節(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)，都有一條唯一的路徑。因此從根節(jié)點(diǎn)到我們要找的兩個結(jié)點(diǎn)，就有兩條路徑，并且這兩條路徑的起點(diǎn)肯定相同（都是根結(jié)點(diǎn)），那么我們可以在這兩條路徑中找出它們分開的結(jié)點(diǎn)，也就是我們要找的結(jié)點(diǎn)了。

代碼：

class BinaryTree
{
public:
	typedef vector<vector <TreeNode*> > PathVec;

	TreeNode* GetNearRoot_3(TreeNode *Node1, TreeNode *Node2)
	{
		//獲取兩條路徑
		PathVec path;
		path.resize(2);
		path[0] = _GetPath(Node1);
		path[1] = _GetPath(Node2);
		//找開始不同的結(jié)點(diǎn)的前一個結(jié)點(diǎn)
		TreeNode *DifferentNode = _GetDivide(path);
		return DifferentNode;
	}
protected:
	//獲得從根節(jié)點(diǎn)到Node的路徑
	vector<TreeNode*> _GetPath(TreeNode *Node)
	{
		vector<TreeNode*> ret;
		_PrevOrder(_root, Node, ret);
		return ret;
	}
	void _PrevOrder(TreeNode *root, TreeNode *Node, vector<TreeNode*> &ret)
	{
		if (root == NULL)
		{
			return;
		}
		ret.push_back(root);
		if (root == Node)
		{
			return;
		}
		else if (root->_left == NULL && root->_right == NULL)
		{
			ret.pop_back();
			return;
		}
		_PrevOrder(root->_left, Node, ret);
		if (*(ret.end() - 1) == Node)
		{
			return;
		}
		_PrevOrder(root->_right, Node, ret);
		if (*(ret.end() - 1) == Node)
		{
			return;
		}
		ret.pop_back();
	}
	//從路徑中找出分離點(diǎn)
	TreeNode* _GetDivide(PathVec path)
	{
		int i = 0;
		while (i < path[0].size() && i < path[1].size() && (path[0])[i] == (path[1])[i])
		{
			++i;
		}
		if (i > 0 && i == path[0].size() || i == path[1].size()) //如果兩個結(jié)點(diǎn)在同一顆子樹，會出現(xiàn)這種情況
		{
			--i;
		}
		return path[0][i - 1];
	}
protected:
	TreeNode *_root;
};

兩條路徑，并且這兩條路徑的起點(diǎn)肯定相同（都是根結(jié)點(diǎn)），那么我們可以在這兩條路徑中找出它們分開的結(jié)點(diǎn)，也就是我們要找的結(jié)點(diǎn)了。

    時間復(fù)雜度： O(N * 2 + log2(N) * 2) = O(N)

    空間復(fù)雜度： O(log2(N) * 2) = O(log2(N))

github：

https://github.com/HonestFox/BrushQuestion/blob/master/61_%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E6%9C%80%E8%BF%91%E7%9A%84%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%E8%8A%82%E7%82%B9

八、判斷一顆二叉樹是否為平衡二叉樹

github：

https://github.com/HonestFox/BrushQuestion/blob/master/62_%E5%88%A4%E6%96%AD%E4%B8%80%E9%A2%97%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91

九、求二叉樹中最遠(yuǎn)兩個節(jié)點(diǎn)的距離 

github：

https://github.com/HonestFox/BrushQuestion/blob/master/63_%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E6%9C%80%E8%BF%9C%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E8%B7%9D%E7%A6%BB

十、由前序遍歷和中序遍歷重建二叉樹

github：

https://github.com/HonestFox/BrushQuestion/blob/master/64_%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%88STL%EF%BC%89

十一、二叉搜索樹的第k個節(jié)點(diǎn)

github：

https://github.com/HonestFox/BrushQuestion/blob/master/65_%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E7%AC%ACK%E4%B8%AA%E7%BB%93%E7%82%B9

十二、判斷一個序列是否為二叉樹的后序遍歷序列

github：

https://github.com/HonestFox/BrushQuestion/blob/master/66_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97

十三、數(shù)據(jù)流中的中位數(shù)

（8.30恢復(fù)更新 ）

（開學(xué)了  /(ㄒoㄒ)/~~）

題目描述：

如何得到一個數(shù)據(jù)流中的中位數(shù)？

如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。

如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。

分析：

思路1：討論區(qū)都在用堆做，但其實(shí)用哈希的思想也可以做的，只要考慮清楚如下兩點(diǎn)：

1、重復(fù)的數(shù)字怎么處理

2、絕對值相等但符號相反的數(shù)字怎么處理

代碼如下，

#include <iostream>
#include <vector>

using namespace std;

/*
題目描述：
如何得到一個數(shù)據(jù)流中的中位數(shù)？
如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。
如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。
*/


struct Pos
{
	int _count = 0;				 //記錄該位置下標(biāo)對應(yīng)數(shù)據(jù)出現(xiàn)的次數(shù)  （為什么要這個變量？因?yàn)橛锌赡苡兄貜?fù)的數(shù)據(jù)）
	bool _IsExist = false;	 //記錄是否存在
};

class Solution
{
public:
	void Insert(int num)
	{
		if (num < 0)
		{
			num *= -1;
			_Insert(_Nvec, num, -1);
			++_NSize;
		}
		else
		{
			_Insert(_Pvec, num, 1);
			++_PSize;
		}
	}

	double GetMedian()
	{
		int size = _PSize + _NSize;
		int pos = _PSize - _NSize;      //size   pos  奇偶性一定是相同的
		int symbol = 1;
		if (pos < 0)
		{
			symbol = -1;
			pos *= -1;
		}
		double ret = 0;
		if (pos % 2 == 0)		//偶數(shù)
		{
			if (symbol == 1)
			{
				ret = ((double)_GetIndexVal(_Pvec, pos / 2) + (double)_GetIndexVal(_Pvec, pos / 2 - 1)) / 2;
			}
			else
			{
				ret = ((double)_GetIndexVal(_Nvec, pos / 2) + (double)_GetIndexVal(_Nvec, pos / 2 - 1) ) / 2;
			}
		}
		else						//奇數(shù)
		{
			if (symbol == 1)
			{
				ret = _GetIndexVal(_Pvec, pos / 2);
			}
			else
			{
				ret = _GetIndexVal(_Nvec, pos / 2);
			}
		}
		ret *= symbol;
		return ret;
	}

protected:
	void _Insert(vector<Pos> &vec, int num, int symbol = 1)
	{
		//判斷容量
		if (num >= vec.size())
		{
			vec.resize(num * 2 + 1);
		}
		//生成結(jié)點(diǎn)
		Pos pos;
		pos._IsExist = true;
		++pos._count;
		//插入
		vec[num] = pos;
	}

	int _GetIndexVal( vector<Pos> vec, int pos)           //pos表示第幾個元素 
	{
		int index = 0;
		while (pos >= 0)
		{
			while (pos >= 0 && vec[index]._IsExist && vec[index]._count > 0)
			{
				--vec[index]._count;
				--pos;
				if (vec[index]._count == 0)
				{
					vec[index]._IsExist = false;
				}
			}
			if (pos < 0)
			{
				break;
			}
			++index;
		}
		return index;
	}

protected:
	vector<Pos> _Pvec;		//存放正數(shù)的數(shù)組
	vector<Pos> _Nvec;		//存放負(fù)數(shù)的數(shù)組
	int _PSize = 0;						//正數(shù)的數(shù)目
	int _NSize = 0;						//負(fù)數(shù)的數(shù)目
};

int main()
{
	Solution s;
	s.Insert(-1);
	s.Insert(-2);
	s.Insert(-3);
	s.Insert(-4);
	s.Insert(1);
	s.Insert(2);
	double ret = s.GetMedian();
	cout << ret << endl;
	return 0;

}

github： https://github.com/HonestFox/BrushQuestion/blob/master/67_%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0

(9.3恢復(fù)更新)

十四、將功贖罪

github：

https://github.com/HonestFox/BrushQuestion/blob/master/68_%E5%B0%86%E5%8A%9F%E8%B5%8E%E7%BD%AA

十五、矩陣中的路徑

github：

https://github.com/HonestFox/BrushQuestion/blob/master/69_%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84