stack的基本操作
• s.size()：返回栈中的元素数量
• s.empty()：判断栈是否为空，返回true或false
• s.push(元素)：返回对栈顶部“元素”的可变（可修改）引用
• s.pop()：删除栈顶元素，类型为void，但并不返回被删除的元素
• s.top()：返回栈顶，不删除
• s1==s2：若成立，表明s1中的每个元素都等于s2的对应元素，返回true或是false
题目1：用两个栈实现队列
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：比较简单，两个栈s1，s2 push的时候就往s1里push，pop的时候，先把s1中的元素全部push到s2，再pop就是队列顺序。这个题也可以描述为如何让栈逆序输出
class Solution
{
public:
void push(int node) {
stack1.push(node) ;
} int pop() {
while(!stack1.empty()){
stack2.push(stack1.top()) ;
stack1.pop();
}
int res = stack2.top() ;
stack2.pop() ;
while(!stack2.empty()){
stack1.push(stack2.top()) ;
stack2.pop();
}
return res ;
} private:
stack<int> stack1;
stack<int> stack2;
};
题目2：滑动窗口最大值
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
思路：这个题O（n*k）很简单，但是要O（n）就有说法了，o（n）的方法是双向队列
先看我的比较挫的版本，用了两个队列：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
queue<int> q ;
deque<int> qmin ;
vector<int> ans ;
if(nums.size()==||k==){
return ans ;
}
for(int i=;i<k;i++){
if(qmin.empty()){
qmin.push_back(nums[i]) ;
}else{
while(!qmin.empty()&&qmin.back()<nums[i]) qmin.pop_back();
qmin.push_back(nums[i]) ;
}
q.push(nums[i]) ;
}
ans.push_back(qmin.front()) ;
for(int i=k;i<nums.size();i++){
if(qmin.front()==q.front()){
qmin.pop_front() ;
}
q.pop() ;
q.push(nums[i]) ;
while(!qmin.empty()&&qmin.back()<nums[i]) qmin.pop_back();
qmin.push_back(nums[i]) ;
ans.push_back(qmin.front()) ;
}
return ans ;
}
};
再看网上大神的版本：一个双端队列，代码也比我简洁。。。
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
deque<int> qmin ;
vector<int> ans ;
int k = size ;
if(num.size()==||size==){
return ans ;
}
for(int i=;i<num.size();i++){
// 每当新数进来时，如果发现队列头部的数的下标，是窗口最左边数的下标，则扔掉
if(!qmin.empty() && qmin.front() == i - k) qmin.pop_front();
// 把队列尾部所有比新数小的都扔掉，保证队列是降序的
while(!qmin.empty() && num[qmin.back()] < num[i]) qmin.pop_back() ;
// 加入新数
qmin.push_back(i) ;
// 队列头部就是该窗口内第一大的
if((i + ) >= (int)k) ans.push_back(num[qmin.front()]);
}
return ans ;
}
};
题目3：数独
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。 - 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
思路：搜索的题目，在能填数的位置先填一个数，然后判断合法性，如果合法就从该状态下再填下一个数。
本来以为要用A*，结果发现直接搜也没有超时，还有原题目是void函数，没有返回真的难受，搜索的题如果递归函数没有返回那怎么知道找到了没啊。
最后发现别人强行把示例的函数改成了bool型，然后可以过。
最后复习一下个位数的int-》char就是num+'0',char->int就是str-‘0’
class Solution {
public:
bool checkIsLeagel(vector<vector<char>>& board,int x,int y){
for(int i=;i<;i++){
if(i!=x&&board[x][y]==board[i][y]){
return false ;
}
if(i!=y&&board[x][y]==board[x][i]){
return false ;
}
}
for(int i=*(x/);i<*(x/+);i++){
for(int j=*(y/);j<*(y/+);j++){
if(x!=i&&y!=j&&board[x][y]==board[i][j]){
return false ;
}
}
}
return true ;
}
bool solveSudoku(vector<vector<char>>& board){
for(int i=;i<;i++){
for(int j=;j<;j++){
if(board[i][j]=='.'){
for(int k=;k<=;k++){
board[i][j] = k + '' ;
if(checkIsLeagel(board,i,j)&&solveSudoku(board)){
return true ;
}
board[i][j] = '.' ;
}
return false ;
}
}
}
return true ;
}
};
ps:记录两个数据结构
小顶堆和大顶堆（优先队列）:
priority_queue<int, vector<int>, less<int>> maxHeap; //存储小的值，值越大，优先级越高
priority_queue<int, vector<int>, greater<int>> minHeap; //存储大的值，值越小，优先级越高
双向队列:- deq[ ]：用来访问双向队列中单个的元素。
- deq.front()：返回第一个元素的引用。
- deq.back()：返回最后一个元素的引用。
- deq.push_front(x)：把元素x插入到双向队列的头部。
- deq.pop_front()：弹出双向队列的第一个元素。
- deq.push_back(x)：把元素x插入到双向队列的尾部。
- deq.pop_back()：弹出双向队列的最后一个元素。
deque的一些特点
- 支持随机访问，即支持[ ]以及at()，但是性能没有vector好。
- 可以在内部进行插入和删除操作，但性能不及list。
- deque两端都能够快速插入和删除元素，而vector只能在尾端进行。
- deque的元素存取和迭代器操作会稍微慢一些，因为deque的内部结构会多一个间接过程。
- deque迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。
- deque可以包含更多的元素，其max_size可能更大，因为不止使用一块内存。
- deque不支持对容量和内存分配时机的控制。
- 在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显示不需要复制所有元素。
- deque的内存区块不再被使用时，会被释放，deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。
- deque不提供容量操作：capacity()和reverse()，但是vector可以。