OJ每日练习（9）

Posted on | In

（最近在写Json解析器，刷题的时间有所减少，今天只有五道剑指offer）

题目名称

  1. 对称的二叉树（剑指offer #28）
  2. 顺时针打印矩阵(剑指offer #29)
  3. 包含min函数的栈（剑指offer #30）
  4. 栈混洗甄别（剑指offer #31）
  5. 树的层次遍历（剑指offer #32）

对称二叉树

解题思路

递归，若root的左右子均存在，判断其值是否相等，再判断left->right与right->left是否相等 && left->left与right->right是否相等。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSymmetrical(TreeNode* root){
      if(!root)
          return true;
      return isS(root->left,root->right);
    }
    
    bool isS(TreeNode* left,TreeNode* right){
        if(!left && !right)
            return true;
        if(!left || !right)
            return false;
        return left->val == right->val && isS(left->left,right->right) && isS(left->right,right->left);
    }
};

顺时针打印矩阵

解题思路

设立好四个边界，依次遍历即可

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.size()==0||matrix[0].size()==0)
            return res;
        int top=0,bottom=matrix.size()-1;
        int left=0,right=matrix[0].size()-1;
        int n=(bottom+1)*(right+1);
        res.resize(n,0);
        int count=0;
        while(true){
            for(int i=left;i<=right;++i) res[count++]=matrix[top][i];
            ++top;
            if(count==n) break;
            for(int i=top;i<=bottom;++i) res[count++]=matrix[i][right];
            --right;
            if(count==n) break;
            for(int i=right;i>=left;--i) res[count++]=matrix[bottom][i];
            --bottom;
            if(count==n) break;
            for(int i=bottom;i>=top;--i) res[count++]=matrix[i][left];
            ++left;
            if(count==n) break;
        }
        return res;
    }
};

包含min的栈

解题思路

用两个栈substack与lastmin和一个私有data membermin实现这一数据结构。初始化时令min=INT_MAX。当执行pop操作时，若substack栈顶元素为min，令min=lastmin.top，pop lastmin,否则pop substack。当执行push操作时，若当前元素小于min，min等于当前元素，push进入lastmin，否则push入substacck。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void push(int value) {
        if(value<minValue){
            minValue=value;
            lastmin.push(value);
        }
        substack.push(value);
    }
    void pop() {
        if(substack.top()==minValue){
            lastmin.pop();
            minValue=lastmin.top();
        }
        substack.pop();
    }
    int top() {
        return substack.top();
    }
    int min() {
        return minValue;
    }
private:
    stack<int> substack,lastmin;
    int minValue=INT_MAX;
};

栈混洗甄别

解题思路

用一个辅助栈,若栈为空或栈顶元素与对应元素不相等，一直入栈，若某时刻无法入栈则返回false。若栈顶元素与当前相等则出栈，执行下一次比对。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> temp;
        auto i=pushV.cbegin();
        for(auto j=popV.cbegin();j!=popV.cend();++j){
            while(temp.empty() || temp.top()!=*j)
                if(i==pushV.cend())
                    return false;
                else temp.push(*i++);
            temp.pop();
        }
        return true;
    }
};

树的层次遍历

解题思路

层次遍历即为BFS，记得使用队列。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        if(!root)
            return vector<int>();
        queue<TreeNode*> que_aux;
        vector<int> res;
        que_aux.push(root);
        while(!que_aux.empty()){
            TreeNode* temp = que_aux.front();
            res.push_back(temp->val);
            if(temp->left) que_aux.push(temp->left);
            if(temp->right) que_aux.push(temp->right);
            que_aux.pop();
        }
        return res;
    }
};