Day25 2023.2.7 模拟（中等）

剑指Offer 29. 顺时针打印矩阵

自己实现

虽然不知道今天的这个模拟是什么意思，但就先暴力做吧

直接暴力遍历

但是想了一下，如果是用暴力遍历的话，一个是对于角落的转换的处理（即转换后的遍历不能从角落那个值开始，需要处理一下）会比较麻烦；另一个是到最后怎么判断结束了呢？这个可能就要另开一个标记数组，就麻烦了，所以看了看题解，什么是模拟

题解

模拟其实没有什么特殊的含义……但是题解的做法是很好的

核心就是在于设置了四边边界，通过边界来控制遍历。即，每一边边界都是还未输出的边界，那么当上边界大于下边界，左边界大于右边界时就break

代码如下：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size()==0)return {};
        vector<int> res;
        int b=matrix.size()-1;
        int r=matrix[0].size()-1;
        int t=0;
        int l=0;
        while(1){
            for(int i=l;i<=r;i++)res.push_back(matrix[t][i]);
            if(++t>b)break;
            for(int i=t;i<=b;i++)res.push_back(matrix[i][r]);
            if(--r<l)break;
            for(int i=r;i>=l;i--)res.push_back(matrix[b][i]);
            if(--b<t)break;
            for(int i=b;i>=t;i--)res.push_back(matrix[i][l]);
            if(++l>r)break;
        }
        return res;
    }
};

代码表现

hint

• 边界用在二维数组倒确实挺常见的，主要就是这个退出条件要把握好

剑指Offer 31. 栈的压入、弹出序列

自己实现

这个题目就是去模拟这个压栈出栈过程。具体思路是根据出栈序列来判断，一个个判断出栈序列的数

• 如果在之前已经入栈了这个数并且这个数不在栈顶，那就返回false（当然，这个好像只针对入栈序列里面没有重复数字的情况）
• 如果还没有入栈，那就继续入栈直到入栈了这个数字为止。

然后再判断下一个出栈序列中的数字

这个题目是自己做出来的，时间复杂度也还不错！

代码如下

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(popped.size()==0)return true;
        vector<int> stack;
        set<int> s;
        int pos_push=0;
        for(int num:popped){
            if(s.find(num)!=s.end()){
                if(num==stack[stack.size()-1]){
                    stack.pop_back();
                    s.erase(s.find(num));
                }
                else{
                    return false;
                }
            }
            else{
                while(pos_push<pushed.size() && num!=pushed[pos_push]){
                    stack.push_back(pushed[pos_push]);
                    s.insert(pushed[pos_push]);
                    pos_push++;
                }
                if(pos_push>=pushed.size())return false;
                if(num==pushed[pos_push]){
                    pos_push++;
                    continue;
                }
            }
        }
        return true;
    }
};

代码表现

题解

题解思路和我一样！都是实实在在地去根据每个出栈元素模拟这个过程！

只是K神的代码简洁好多……

代码(Java)如下：

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

代码表现

只是时间表现好像没有我那个好，可能是我的判断里面判断了是否在很早之前就被入栈了，若是则直接返回false。取长补短吧

hint

• 像这种过程性比较强的题目就是去实实在在地模拟过程就好，反而思路会很顺，至少能帮自己理清思路