[刷题]LeetCode每日一题[2022.03]

 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
29
30
31
32

// dp[i+1][j+1]: s[0,...,i] 和 t[0,...,j]中的最长公共子串的长度. 故dp[m][n] == m为题意所求
// DP: TC: O(m*n), SC: O(m*n)
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n] == m;
    }
};

// TC: O(m + n), SC: O(1)
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        while (i < s.size() && j < t.size()) {
            if (s[i] == t[j]) ++ i;
            ++ j;
        }
        return i == s.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        vector<int>dp(n, 0);
        int res = 0;
        // 例如 nums = [1, 2, 3, 4]
        // dp[3] = 1, [1, 2, 3]
        // dp[4] = dp[3] + 1([2, 3, 4]). 此时的dp[3]的 Arithmetic Slices是[1, 2, 3, 4]
        for (int i=2; i<n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
            }
            res += dp[i];
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> dp(101, 0); dp[0] = poured;
        for(int row=1; row<=query_row; row++)
            for(int i=row; i>=0; i--)
                dp[i+1] += dp[i] = max(0.0, (dp[i]-1)/2);
        return min(dp[query_glass], 1.0);
    }
};

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// map存储累加和. 时间复杂度O(n+k), SC: O(n*2)  自顶向下 
class Solution {
public:
    int dfs(int num, unordered_map<int, int>& sum, vector<int>& dp) {
        if (num == 0) return 0;
        if (num == 1) {
            return sum[1];
        }
        if (dp[num] != -1) return dp[num];
        dp[num] = max(dfs(num-1, sum, dp), sum[num] + dfs(num-2, sum, dp));
        return dp[num];
    }
    int deleteAndEarn(vector<int>& nums) {
        int max_num = 1e4;
        vector<int> dp(max_num+1, -1);
        unordered_map<int, int> sum(max_num+1); // {i: sum of i} when i equals the element in nums
        for (int& num: nums) {
            sum[num] += num;
        }
        return dfs(max_num, sum, dp);
    }
};

// 改成vectror以后。 DFS+记忆化  时间复杂度O(n+k), SC: O(n)
class Solution {
public:
    int dfs(int num, vector<int>& sum, vector<int>& dp) {
        if (num == 0) return 0;
        if (num == 1) {
            return sum[1];
        }
        if (dp[num] != -1) return dp[num];
        dp[num] = max(dfs(num-1, sum, dp), sum[num] + dfs(num-2, sum, dp));
        return dp[num];
    }
    int deleteAndEarn(vector<int>& nums) {
        int max_num = 1e4;
        vector<int> dp(max_num+1, -1);
        vector<int> sum(max_num+1, 0);
        for (int& num: nums) {
            sum[num] += num;
        }
        return dfs(max_num, sum, dp);
    }
};

// 自底向上 DP
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int max_num = 1e4;
        vector<int> dp(max_num+1, 0);
        vector<int> sum(max_num+1); // {i: sum of i} when i equals the element in nums
        for (int& num: nums) {
            sum[num] += num;
        }
        dp[1] = sum[1], dp[2] = max(sum[1], sum[2]);
        for (int i=3; i<=max_num; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + sum[i]);
        }
        return max(dp[max_num], dp[max_num - 1]);
    }
};

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// 迭代
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1 = list1, *p2 = list2;
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while (p1 && p2) {
            if (p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 ? p1 : p2;
        return dummy->next;
    }
};

// 递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        ListNode *l1 = list1->val < list2->val ? list1 : list2;
        ListNode *l2 = list1->val < list2->val ? list2 : list1;
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        ListNode *slow = head, *fast = slow->next;
        while (fast && fast->next && slow != fast) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow == fast;
    }
};

 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* first = dummy;
        while (first->next && first->next->next) {
            if (first->next->val == first->next->next->val) {
                int val = first->next->val;
                while (first->next && first->next->val == val) {
                    first->next = first->next->next;
                }
            } else {
                first = first->next;
            }
        }
        return dummy->next;
    }
};

 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
29
30
31
32
33
34
35
36
37

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *rl1 = l1, *rl2 = l2;
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        int carry = 0, val;
        while (rl1 || rl2) {
            val = carry;
            if (rl1) {
                val += rl1->val;
                rl1 = rl1->next;
            }
            if (rl2) {
                val += rl2->val;
                rl2 = rl2->next;
            }
            carry = val / 10;
            p->next = new ListNode(val % 10);
            p = p->next;
        }
        if (carry) {
            p->next = new ListNode(carry);
        }
        return dummy->next;
    }
};