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

一、两个栈实现一个队列

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