头像

NeonSean


访客:3066

离线:17小时前


活动打卡代码 LeetCode 27. 移除元素

NeonSean
17小时前
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != val) nums[j++] = nums[i];
        }
        return j;
    }
};



递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == NULL) return {};
        if (root->left) {
            inorderTraversal(root->left);
        }
        res.push_back(root->val);
        if (root->right) {
            inorderTraversal(root->right);
        }
    return res;
    }
};

迭代

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        stack<TreeNode*> stk;
        vector<int> res;
        TreeNode* p = root;
        while (p || !stk.empty()) {
            if (p) {
                stk.push(p);
                p = p->left;
            }else {
                p = stk.top();
                stk.pop();
                res.push_back(p->val);
                p = p->right;
            }
        }
        return res;
    }
};


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

class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }
    void dfs(const string& s, int u, int k, string path) {
        if (u == s.size()) {
            if (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

/**
 * 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) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        ListNode* a = dummy;
        for (int i = 0; i < m - 1; i++) a = a->next;
        ListNode* b = a->next;
        ListNode* c = b->next;
        for (int i = 0; i < n - m; i++) {
            auto t = c->next;
            c->next = b;
            b = c;
            c = t;
        }
        a->next->next = c;
        a->next = b;
        return dummy->next;
    }
};


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

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        else if (p && q && p->val == q->val) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        else return false;
    }
};


活动打卡代码 LeetCode 91. 解码方法

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s[i] >= '1' && s[i] <= '9') f[i] += f[i-1];
            if (i > 1) {
                int t = (s[i-1] - '0') * 10 + (s[i] - '0');
                if (t >= 10 && t <= 26) f[i] += f[i-2];
            }
        }
        return f[n];
    }
};



class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        vector<int> f(n);

        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }
        return res;
    }
};



class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& env) {
        sort(env.begin(), env.end());
        int n = env.size();
        int res = 0;
        vector<int> f(n,1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (env[i][0] > env[j][0] && env[i][1] > env[j][1]) {
                    f[i] = max(f[i], f[j] + 1);
                }      
            }
            res = max(res, f[i]);    
        }
        return res;
    }
};



class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_multiset<int> s;
        vector<int> res;
        for (auto c : nums1) s.insert(c);
        for (auto c : nums2) {
            if (s.count(c)) {
                res.push_back(c);
                s.erase(s.find(c));
            }
        }
        return res;
    }
};



class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s;
        vector<int> res;
        for (int c : nums1) s.insert(c);
        for (int c : nums2) {
            if (s.count(c)) {
                res.push_back(c);
                s.erase(c);
            }
        }
        return res;
    }
};