头像

Zey

三峡大学




离线:50分钟前


活动打卡代码 LeetCode 321. 拼接最大数

Zey
51分钟前
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            int n = nums1.size(), m = nums2.size();
            vector<int> res(k, INT_MIN);
            for(int i = max(0, k - m); i <= min(k, n); i++){
                auto a = maxArray(nums1, i);
                auto b = maxArray(nums2, k - i);
                auto c = merge(a, b);
                res = max(res, c);
            }
            return res;
    }

    vector<int> merge(vector<int>& a, vector<int>& b){
        vector<int> res;
        while(a.size() && b.size()){
            if(a > b) res.push_back(a[0]), a.erase(a.begin());
            else res.push_back(b[0]), b.erase(b.begin());
        }
        while(a.size()) res.push_back(a[0]), a.erase(a.begin());
        while(b.size()) res.push_back(b[0]), b.erase(b.begin());
        return res;
    }

    vector<int> maxArray(vector<int>&nums, int k){
        int n = nums.size();
        vector<int> res(k);
        for(int i = 0, j = 0; i < n; i++){
            int x = nums[i];
            while(j && res[j-1] < x && j + n - i > k) j--;//这里j + n - i要注意
            if(j < k) res[j++] = x;
        }
        return res;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 100. 相同的树

Zey
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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        if(!p || !q || p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Zey
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:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second, *last = nullptr;
        while(root){
            if(!root->left){
                if(last && last->val > root->val){
                    if(!first) first = last, second = root;
                    second = root;
                }
                last = root;
                root = root->right;
            }
            else{
                auto p = root->left;
                while(p->right && p->right != root) p = p->right;
                if(!p->right) p->right = root, root = root->left;
                else{
                    p->right = nullptr;
                    if(last && last->val > root->val){
                        if(!first) first = last, second = root;
                        second = root;
                    }
                    last = root;
                    root = root->right;
                }
            }
        }
        swap(first->val, second->val); 
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Zey
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:
    bool isValidBST(TreeNode* root) {
        if(!root) return false;
        return dfs(root)[0];
    }

    vector<int> dfs(TreeNode* root){
        vector<int> res({1, root->val, root->val});
        if(root->left){
            auto t = dfs(root->left);
            if(!t[0] || t[2] >= root->val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]);
        }
        if(root->right){
            auto t = dfs(root->right);
            if(!t[0] || t[1] <= root->val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]); 
        }
        return res;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 97. 交错字符串

Zey
1小时前
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size();
        if(s3.size() != n + m) return false;

        s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));

        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= m; j++){
                if(!i && !j) f[i][j] = true;
                if(i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
                if(j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
            }
        }

        return f[n][m];
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Zey
2小时前
class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Zey
2小时前
/**
 * 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<TreeNode*> generateTrees(int n) {
        if(!n) return {};
        return dfs(1, n);
    }
    vector<TreeNode*> dfs(int l, int r){
        if(l > r) return {nullptr};
        vector<TreeNode*> res;
        for(int i = l; i <= r; i++){
            auto left = dfs(l, i - 1), right = dfs(i + 1, r);
            for(auto l : left)
                for(auto r : right){
                    auto root = new TreeNode(i);
                    root->left = l, root->right = r;
                    res.push_back(root);
                }
        }
        return res;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Zey
2小时前
/**
 * 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> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;

        while(root || stk.size()){
            while(root){
                stk.push(root);
                root = root->left;
            }

            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 93. 复原IP地址

Zey
2小时前
class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }

    void dfs(string& s, int u, int k, string path){
        if(u == s.size() && k == 4){
            path.pop_back();//去除最后的点
            res.push_back(path);
            return;
        }
        if(k == 4) return;
        for(int i = u, t = 0; i < s.size(); i++){
            if(i > u && s[u] == '0') break;
            t = t * 10 + s[i] - '0';
            if(t <= 255) dfs(s, i + 1, k + 1, path + to_string(t) + '.');
            else break;
        }
    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 92. 反转链表 II

Zey
3小时前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto p = dummy;
        for(int i = 0; i < m - 1; i++) p = p->next;

        auto b = p->next, c = b->next;
        for(int i = 0; i < n - m; i++){
            auto t = c->next;
            c->next = b;
            b = c, c = t;
        }
        auto t = p->next;
        p->next = b;
        t->next = c;

        return dummy->next;


    }
};
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~