若干數據結構 && 算法面試題【一】（更新完畢）

一、兩個棧實現一個隊列

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

二、實現一個棧

要求：實現一個棧，要求實現Push（出棧）、Pop（入棧）、Min（返回最小值的操作）的時間復雜度為O(1)

為了在O（1）時間內取到棧內元素的最小值，顯然遍歷是行不通的。

我們需要在入棧和出棧的操作中記錄最小值。

如果用一個變量（假設叫m）在入棧時記錄并保存最小值，假如這個最小的元素出棧。

比如：

入棧元素分別為： 4 3 2 1

這時m保存的最小值為 1

但一旦將值為1的元素彈出，那么棧中實際最小的元素為2，但m的值仍為1.

因此我們還需要一個棧_stack.

每當入棧時，如果判斷出當前元素為最小值，則將這個元素在壓入我們實現的棧Stack的同時，也壓入_stack中。

值得注意的是，必須考慮到最小元素可能重復的情況（比如 4 3 2 1 1 1）因此判斷的時候需要用 ">="操作符而不是 ">" (見代碼15行中的注釋)

出棧時，判斷若出棧元素為當前最小值，則在2個棧中都將該元素彈出。

具體代碼如下：

template<class T>
class Stack
{
public:
	Stack()
		:_sz(0)
	{}
	void Push(const T &data)
	{
		if (_sz == 0)
		{
			_min = data;
			_stack.push(_min);
		}
		if (_min >= data)              //最小元素可能重復的情況
		{
			_min = data;
			_stack.push(_min);
		}
		_arr[_sz++] = data;
	}
	void Pop()
	{
		if (_arr[_sz - 1] == _min)
		{
			_stack.pop();
			_min = _stack.top();
		}
		--_sz;
	}
	void Print()
	{
		for (int i = 0; i < _sz; i++)
		{
			cout << _arr[i] << " ";
		}
		cout << endl;
	}
	T &Min()
	{
		return _min;
	}

protected:
	T _arr[100];
	int _sz;
	int _min;
	stack<int> _stack;
};

三、兩個隊列實現一個棧

(待續··)

四、元素出棧入棧順序的合法性

元素出棧、入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,2,1）

(待續··)

五、一個數組實現兩個棧

(待續··)

六、找出一個字符串中第一次只出現1次的元素，要求時間復雜度為O（N）

代碼：

https://github.com/HonestFox/BrushQuestion/edit/master/2_%E8%8E%B7%E5%8F%96%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E5%AD%97%E7%AC%A6.cpp

七、滑動窗口的最大值

    給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。

    例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 

    針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

全部代碼：https://github.com/HonestFox/BrushQuestion/blob/master/1_%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.c

八、獲取第一個只出現一次的字符

題目描述

請實現一個函數用來找出字符流中第一個只出現一次的字符。例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"。當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"。 

輸出描述:

如果當前字符流沒有存在出現一次的字符，返回#字符。

全部代碼：

https://github.com/HonestFox/BrushQuestion/edit/master/2_%E8%8E%B7%E5%8F%96%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E5%AD%97%E7%AC%A6.cpp

九、有序鏈表刪除重復的元素

題目描述

在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

全部代碼：

https://github.com/HonestFox/BrushQuestion/blob/master/3_%E5%88%A0%E9%99%A4%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0.cpp

十、數組中重復的數據

題目描述

在一個長度為n的數組里的所有數字都在0到n-1的范圍內。

數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。

請找出數組中任意一個重復的數字。 

例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那么對應的輸出是重復的數字2或者3。

全部代碼：

https://github.com/HonestFox/BrushQuestion/blob/master/3_%E5%88%A0%E9%99%A4%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0.cpp

這里有兩種實現方式

首先是第一種方法：

bool duplicate(int numbers[], int length, int* duplication)
{
	const int MAXSIZE = 65535;
	assert(numbers);
	if (length <= 1)
	{
		return false;
	}
	int NumBox[MAXSIZE] = { 0 };
	for (int i = 0 ; i < length; i++)
	{
		++NumBox[numbers[i]];
	}
	for (int i = 0; i < length; i++)
	{
		if(NumBox[numbers[i]] > 1)
		{
			*duplication = numbers[i];
			return true;
		}
	}
	return false;
}

這里的解決思路是，開辟一個較大的數組NumBox 初始化所有元素為0

這個NumBox 表示所有元素出現的個數。

將當前數組遍歷，

每次訪問到一個值，將以這個值為NumBox下標的元素加1

舉個例子，

比如說 numbers為[1, 2, 1, 3]

遍歷完后，NumBox就變成了[0, 2, 1, 1, 0, 0 ......]

這里面表示，NumBox[0] = 0 ,即 numbers數組中 0 出現了 0 次

NumBox[1] = 2， 即number數組中 1 出現了 2次 

......

依此類推

然后再通過判斷NumBox中是否有大于1的元素，就能判斷出numbers數組中是否有出現過多次的元素了。

這里注意，為了減少程序的執行步驟，這一步也不是遍歷整個NumBox，而是以numbers中的元素為下標遍歷一遍即可

以上為第一種實現方式，注意在定義NumBox的時候，要特別注意給它分配的長度。這里我給它分配的長度為65535，但其實是不夠的。

考慮到int型變量在32位操作系統中值的范圍為-2147483648－－2147483647，理論上為了確保程序的正常運行，我們應給NumBox分配一段極大的長度。

所以，第一種方法會占用很多內存空間，因此還有一種巧妙的實現方式，不需要定義像NumBox這樣的輔助數組，代碼如下：

//最優方案： 由于題目已經告訴了數組中最大的元素小于length 因此可以這樣寫
//                  時間復雜度為O(N)  且不需要開辟多余的輔助數組
bool duplicate_best(int numbers[], int length, int* duplication)
{
	assert(numbers);
	if (length <= 1)
	{
		return false;
	}
	for (int i = 0; i < length; i++)
	{
		int index = numbers[i];
		
		if (index >= length)
		{
			index -= length;
		}
		if (numbers[index] >= length)
		{
			*duplication = index;
			return true;
		}
		numbers[index] += length;
	}
	return false;
}

依然是遍歷numbers并將每次訪問到的元素作為下標。

然后，每次訪問到一個元素，將這個元素 += length，保證這個元素大于length

這樣，當再次訪問到相同的元素時，會判斷 numbers中以這個元素作下標的元素的值大于length，

這就表示這個元素在前面已經出現過了

舉個例子

numbers 為 [1, 2, 1, 3]   length 為 4

訪問1后:  numbers為 [1, 6, 1, 3]

訪問2后:  numbers為 [1, 6, 5, 3]

然后再次訪問1: (這里numbers[1]已經變成了6,要減去length，讓他表示為最開始的number[1])

會發現 numbers[1]為 6 , 大于length 

因此可以判斷出，元素 1 之前出現過。返回true

十一、二維數組元素的查找

題目描述

在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

輸入描述:

array： 待查找的二維數組

target：查找的數字

輸出描述:

查找到返回true，查找不到返回false

全部代碼：

https://github.com/HonestFox/BrushQuestion/blob/master/5_%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E6%9C%80%E5%A4%A7%E5%80%BC.cpp

傳統的方法是將數組完整地遍歷一遍

這里我的思路是，比如一個二維數組如下

1 2 3

5 7 8

6 8 9

先判斷第1行最后一個元素。

如果要查找的元素比這個元素小，則可以排除該元素所在列

如果要查找的元素比這個元素大，則可以排除該元素所在行。

舉個例子： 查找 6

由于3比6小，因此可以排除第一行，此時查找范圍變為

5 7 8

6 8 9

然后8比6排除第3列，查找范圍變為

5 7

6 8

……

依此類推即可

十二、替換空格

題目描述

請實現一個函數，將一個字符串中的空格替換成“%20”。例如，當字符串為We Are Happy.則經過替換之后的字符串為We%20Are%20Happy。

代碼：

https://github.com/HonestFox/BrushQuestion/blob/master/6_%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC

十三、逆序打印鏈表（棧和遞歸兩種方法）

題目描述

輸入一個鏈表，從尾到頭打印鏈表每個節點的值。

輸入描述:

輸入為鏈表的表頭

輸出描述:

輸出為需要打印的“新鏈表”的表頭

代碼：

https://github.com/HonestFox/BrushQuestion/blob/master/7_%E9%80%86%E5%BA%8F%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8