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

一、兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

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

二、實(shí)現(xiàn)一個(gè)棧

要求：實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（出棧）、Pop（入棧）、Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)

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

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

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

比如：

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

這時(shí)m保存的最小值為 1

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

因此我們還需要一個(gè)棧_stack.

每當(dāng)入棧時(shí)，如果判斷出當(dāng)前元素為最小值，則將這個(gè)元素在壓入我們實(shí)現(xiàn)的棧Stack的同時(shí)，也壓入_stack中。

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

出棧時(shí)，判斷若出棧元素為當(dāng)前最小值，則在2個(gè)棧中都將該元素彈出。

具體代碼如下：

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)              //最小元素可能重復(fù)的情況
		{
			_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;
};

三、兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

(待續(xù)··)

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

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

(待續(xù)··)

五、一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧

(待續(xù)··)

六、找出一個(gè)字符串中第一次只出現(xiàn)1次的元素，要求時(shí)間復(fù)雜度為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

七、滑動(dòng)窗口的最大值

    給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。

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

    針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[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

八、獲取第一個(gè)只出現(xiàn)一次的字符

題目描述

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"g"。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"l"。 

輸出描述:

如果當(dāng)前字符流沒(méi)有存在出現(xià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

九、有序鏈表刪除重復(fù)的元素

題目描述

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針。 例如，鏈表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

十、數(shù)組中重復(fù)的數(shù)據(jù)

題目描述

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。

數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。

請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 

例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字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

這里有兩種實(shí)現(xiàn)方式

首先是第一種方法：

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;
}

這里的解決思路是，開(kāi)辟一個(gè)較大的數(shù)組NumBox 初始化所有元素為0

這個(gè)NumBox 表示所有元素出現(xiàn)的個(gè)數(shù)。

將當(dāng)前數(shù)組遍歷，

每次訪問(wèn)到一個(gè)值，將以這個(gè)值為NumBox下標(biāo)的元素加1

舉個(gè)例子，

比如說(shuō) numbers為[1, 2, 1, 3]

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

這里面表示，NumBox[0] = 0 ,即 numbers數(shù)組中 0 出現(xiàn)了 0 次

NumBox[1] = 2， 即number數(shù)組中 1 出現(xiàn)了 2次 

......

依此類推

然后再通過(guò)判斷NumBox中是否有大于1的元素，就能判斷出numbers數(shù)組中是否有出現(xiàn)過(guò)多次的元素了。

這里注意，為了減少程序的執(zhí)行步驟，這一步也不是遍歷整個(gè)NumBox，而是以numbers中的元素為下標(biāo)遍歷一遍即可

以上為第一種實(shí)現(xiàn)方式，注意在定義NumBox的時(shí)候，要特別注意給它分配的長(zhǎng)度。這里我給它分配的長(zhǎng)度為65535，但其實(shí)是不夠的。

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

所以，第一種方法會(huì)占用很多內(nèi)存空間，因此還有一種巧妙的實(shí)現(xiàn)方式，不需要定義像NumBox這樣的輔助數(shù)組，代碼如下：

//最優(yōu)方案： 由于題目已經(jīng)告訴了數(shù)組中最大的元素小于length 因此可以這樣寫(xiě)
//                  時(shí)間復(fù)雜度為O(N)  且不需要開(kāi)辟多余的輔助數(shù)組
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并將每次訪問(wèn)到的元素作為下標(biāo)。

然后，每次訪問(wèn)到一個(gè)元素，將這個(gè)元素 += length，保證這個(gè)元素大于length

這樣，當(dāng)再次訪問(wèn)到相同的元素時(shí)，會(huì)判斷 numbers中以這個(gè)元素作下標(biāo)的元素的值大于length，

這就表示這個(gè)元素在前面已經(jīng)出現(xiàn)過(guò)了

舉個(gè)例子

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

訪問(wèn)1后:  numbers為 [1, 6, 1, 3]

訪問(wèn)2后:  numbers為 [1, 6, 5, 3]

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

會(huì)發(fā)現(xiàn) numbers[1]為 6 , 大于length 

因此可以判斷出，元素 1 之前出現(xiàn)過(guò)。返回true

十一、二維數(shù)組元素的查找

題目描述

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

輸入描述:

array： 待查找的二維數(shù)組

target：查找的數(shù)字

輸出描述:

查找到返回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

傳統(tǒng)的方法是將數(shù)組完整地遍歷一遍

這里我的思路是，比如一個(gè)二維數(shù)組如下

1 2 3

5 7 8

6 8 9

先判斷第1行最后一個(gè)元素。

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

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

舉個(gè)例子： 查找 6

由于3比6小，因此可以排除第一行，此時(shí)查找范圍變?yōu)?/p>

5 7 8

6 8 9

然后8比6排除第3列，查找范圍變?yōu)?/p>

5 7

6 8

……

依此類推即可

十二、替換空格

題目描述

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy。

代碼：

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

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

題目描述

輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。

輸入描述:

輸入為鏈表的表頭

輸出描述:

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

代碼：

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