[数据结构与算法]LeetCode - 4

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        if(!len) return 0;

        vector<int> lmax(len);
        lmax[0] = height[0];  //记录当前位置左侧最高值
        for(int i = 1; i < len; i ++){
            lmax[i] = max(lmax[i-1], height[i]);
        }

        vector<int> rmax(len+5);
        rmax[len-1] = height[len-1];  //记录当前位置右侧最高值
        for(int i = len-2; ~i; i --){
            rmax[i] = max(rmax[i+1], height[i]);
        }
        int ans = 0;
        for(int i = 0; i < len; i ++){
            ans += min(lmax[i], rmax[i])-height[i];
        }
        return ans;
    }
};

?

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        set<char> st;  //set判重
        int ans = 0, l = 0, r = -1, len = s.size();
        while(l<len){ //枚举左指针
            if(l) st.erase(s[l-1]); //左指针右移，重置set
            while(r+1<len&&!st.count(s[r+1])){
                st.insert(s[++r]); //移动右指针找到第一次出现重复的边界
            }
            ans = max(ans, r-l+1); //更新答案
            l ++;
        }
        return ans;
    }
};

?

class Solution {
public:
    int candy(vector<int>& ratings) {
        map<int, int> mp;
        int n = ratings.size();
        for(int i = 0; i < n; i ++){  //先处理出右规则的值
            if(i&&ratings[i]>ratings[i-1]) mp[i] = mp[i-1]+1;
            else mp[i] = 1;
        }
        int tmp = 0, ans = 0; //tmp临时存储左规则的值
        for(int i = n-1; ~i; i --){
            if(i<n-1&&ratings[i]>ratings[i+1]) tmp ++;
            else tmp = 1;
            ans += max(mp[i], tmp); //取值为满足两侧规则的最大值
        }
        return ans;
    }
};

?

?

class Solution {
public:
    void postorder(TreeNode* root, vector<int> &res){
        if(root==nullptr) return;
        res.push_back(root->val); //先序
        postorder(root->left, res);
        // res.push_back(root->val); //中序
        postorder(root->right, res);
        // res.push_back(root->val); //后序
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        postorder(root, ans);
        return ans;
    }
};

?

?

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);  //弹入根节点
        while(!q.empty()){
            int sz = q.size(); //记录当前层次的节点数量
            ans.push_back(vector<int>()); //弹入ans的新一层
            for(int i = 1; i <= sz; i ++){ //进入下一层次的遍历
                auto frt = q.front(); q.pop();
                ans.back().push_back(frt->val); //ans记录当前节点值
                if(frt->left) q.push(frt->left);  //先弹入左节点
                if(frt->right) q.push(frt->right); //再弹入右节点
            }
        }
        return ans;
    }
};

?