c++刷题（3/100）数独，栈和队列

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可以。

巴特西

c++刷题（3/100）数独，栈和队列

题目描述

题目描述

deque的一些特点

最新文章

热门文章