头像

George




离线:3天前


活动打卡代码 LeetCode 42. 接雨水

George
1个月前
class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int n = height.size();
        stack<int> stk;

        for(int i = 0; i < n; i++){
            while(stk.size() && height[stk.top()] <= height[i]){
                int cur = stk.top();
                stk.pop();
                if(stk.size())
                    res += (i-stk.top()-1) * ( min(height[i], height[stk.top()]) - height[cur]);
            }
            stk.push(i);
        }

        return res;

    }
};


活动打卡代码 LeetCode 85. 最大矩形

George
1个月前
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if(!n)  return 0;
        int m = matrix[0].size();


        vector<int> heights(m+1);
        heights[m] = -1;

        int res = 0;
        for(int i = 0; i < n; i++){

            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '0')   heights[j] = 0;
                else heights[j]++;        

            stack<int> stk;
            for(int j = 0; j <= m; j++){
                while(stk.size() && heights[j] < heights[stk.top()]){
                    int cur = stk.top();
                    stk.pop();

                    if(stk.size())
                        res = max(res, heights[cur]*(j-stk.top()-1));
                    else  
                        res = max(res, heights[cur]*(j));
                }

                stk.push(j);
            }

        }

        return res;

    }
};


活动打卡代码 LeetCode 85. 最大矩形

George
1个月前
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if(!n)  return 0;
        int m = matrix[0].size();


        vector<int> heights(m+1);
        heights[m] = -1;

        int res = 0;
        for(int i = 0; i < n; i++){

            for(int j = 0; j < m; j++)
                if(matrix[i][j] == '0')   heights[j] = 0;
                else heights[j]++;        

            stack<int> stk;
            for(int j = 0; j <= m; j++){
                while(stk.size() && heights[j] < heights[stk.top()]){
                    int cur = stk.top();
                    stk.pop();

                    if(stk.size())
                        res = max(res, heights[cur]*(j-stk.top()-1));
                    else  
                        res = max(res, heights[cur]*(j));
                }

                stk.push(j);
            }

        }

        return res;

    }
};



George
1个月前
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(-1);
        int res = 0;
        stack<int> stk;


        for(int i = 0; i < heights.size(); i++){
            while(stk.size() && heights[i] < heights[stk.top()]){
                int cur = stk.top();
                stk.pop();

                if(stk.size()){
                    res = max(res, heights[cur]*(i-stk.top()-1));
                }else
                    res = max(res, heights[cur]*i);
            }
            stk.push(i);
        }

        return res;
    }
};


活动打卡代码 LeetCode 5. 最长回文子串

George
1个月前
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        int n = s.size();
        for(int i = 0; i < n; i++){
            int l = i-1, r = i+1;
            while(l>=0 && r<n && s[l]==s[r]) l--, r++;
            if(res.size() < r-l-1) res = s.substr(l+1, r-l-1);

            l = i, r = i+1;
            while(l>=0 && r<n && s[l]==s[r]) l--, r++;
            if(res.size() < r-l-1) res = s.substr(l+1, r-l-1);
        }

        return res;
    }
};



George
1个月前
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> f(n+1, vector<bool>(m+1));
        f[0][0] = true;
        s = ' ' + s;
        p = ' ' + p;
        for(int i = 0; i <= n; i++)
            for(int j = 1; j <= m; j++){
                // if(j+1 <= m && p[j+1]=='*') continue;
                if(p[j] == '*')
                    f[i][j] = i && f[i-1][j] && (s[i]==p[j-1] || p[j-1]=='.') || j-2>=0 && f[i][j-2];
                else
                    f[i][j] = i && f[i-1][j-1] && (s[i]==p[j] || p[j]=='.');
            }

        return f[n][m];
    }
};



George
1个月前

缩小解集+最长下降子序列

class Solution {
public:
    int maxHeight(vector<vector<int>>& w) {
        for(auto a : w) sort(a.begin(), a.end());       // 为了让c最大,作高
        sort(w.begin(), w.end(), greater<vector<int>>());   // 为了让比i大的长方体一定在i的左边

        int n = w.size();
        vector<int> f(n);       // f[i]表示以w[i]为最上面的矩阵的最高高度。

        int res = 0;
        for(int i = 0; i < n; i++){
            f[i] = w[i][2];
            for(int j = 0; j < i; j++){         
                if(w[j][0] >= w[i][0] && w[j][1] >= w[i][1] && w[j][2] >= w[j][2])
                    f[i] = max(f[i], f[j]+w[i][2]);

            }

            res = max(res, f[i]);
        }

        return res;
    }
};


新鲜事 原文

George
1个月前
周末好!打工人



George
1个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(-1);         // sorted list;

        while(head){
            ListNode* p = dummy;
            ListNode* next = head->next;
            while(p->next && p->next->val <= head->val) p = p->next;
            head->next = p->next;
            p->next = head;
            head = next;
        }


        return dummy->next;
    }
};



George
1个月前

根右左 ===》 左右根(后序)

/**
 * 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<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;

        while(root || stk.size()){
            while(root){
                res.push_back(root->val);
                stk.push(root);
                root = root->right;
            }

            root = stk.top()->left;
            stk.pop();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};