一、两个栈实现一个队列
成都创新互联执着的坚持网站建设，微信小程序定制开发；我们不会转行，已经持续稳定运营十载。专业的技术，丰富的成功经验和创作思维，提供一站式互联网解决方案，以客户的口碑塑造品牌，携手广大客户，共同发展进步。
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 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 _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
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
当前名称：若干数据结构&&算法面试题【一】（更新完毕）-创新互联
当前URL：
http://cdxtjz.cn/article/ephps.html
