「leetcode刷题」两天冲刺挑战(100题)

​ 时间: 2021-08-23 21:14:55—->2021-08-26 10:43:12

​ 完结撒花

1 | 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        ListNode* pre = nullptr, *nex = nullptr;
        while (head != nullptr) {
            nex = head->next, head->next = pre, pre = head, head = nex;
        }
        return pre;
    }
};

2 | 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // set记录字符出现
        unordered_set<char> st;
        int ans = 0;
        for (int r = 0, l = 0; r < s.size(); ++r) {
            // 如果发现set中已经含有当前字符
            if (st.count(s[r])) {
                while (s[r] != s[l]) st.erase(s[l++]); // 这里没必要考虑l和r相遇, 因为移动到r自然就退出了
                // 现在 s[r] == s[l]还需要将s[l]删除
                st.erase(s[l++]);
            }
            // 最后将s[r]插入
            st.insert(s[r]);
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

3 | LRU 缓存机制

note:

自己写链表还是太麻烦了

一定要记得将「移动到头部」方法提取出来, 因为在get和put中都需要用, 一共用三次, 而链表的移动一定要考虑清楚, 步骤不要写丢了

https://leetcode-cn.com/problems/lru-cache/

  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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// LRU缓存
// 需要随机删除链表, 需要用到哈希表(unordered_map)
// 随机删除链表必须使用双向链表: 
// 方法1. 自己实现双向链表 方法2. 利用stl中的list
// 考虑使用方法1

struct double_list {
    int key, value; // 保存键值对
    double_list* next, *prev; // 前驱与后继
    double_list():  // 成员初始化表
        key(0),
        value(0),
        prev(nullptr),
        next(nullptr) {}
};

class LRUCache {
public:
    unordered_map<int, double_list*> hmap; // 记录键与链表结点的对应关系
    double_list* head, *tail; // 链表的头尾
    int sz; // 当前容量
    int thresh; // 最大容量
    LRUCache(int capacity): thresh(capacity), sz(0) {
        // 虚拟头和虚拟尾
        head = new double_list();
        tail = new double_list(); 
        head->next = tail, tail->prev = head; // 链接首尾
    }
    
    // 抽离出移动到头部这个方法
    void add_head (double_list* now) {
        // 先删除
        if (now->next && now->prev) {
            now->next->prev = now->prev;
            now->prev->next = now->next;
        }
        // 再添加
        now->next = head->next;
        head->next->prev = now;
        now->prev = head;
        head->next = now;
 }

    // 作用:
    // 如果key存在, 将其移动到链表首部并且返回value
    // 如果key不存在, 返回-1
    int get(int key) {
        if (!hmap.count(key)) {
            return -1;
        } else {
            double_list* now = hmap[key];
            add_head(now);
            return now->value;
        }
    }
    
    // 作用:
    // 如果key存在, 移动到链表首部并且更新值
    // 如果key不存在, 在链表首部插入值并且更新哈希表
    void put(int key, int value) {
        if (!hmap.count(key)) {
            ++sz;
            double_list* now = new double_list();
            // value和key都要加入, 为了方便删除
            now->value = value;
            now->key = key;
            add_head(now);
            hmap[key] = now; // 加入到哈希表
            // 超过上限, 删除链表尾部
            if (sz > thresh) {
                --sz;
                double_list* pre = tail->prev;
                tail->prev = tail->prev->prev;
                pre->prev->next = tail;
                hmap.erase(pre->key);
                delete pre;
            }
        } else {
            double_list* now = hmap[key];
            now->value = value; // 更新value
            add_head(now);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
  1. 使用list
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
class LRUCache {
public:
    int sz; // 上限, 目前大小可以用cache.size()判断
    unordered_map<int, list<pair<int, int>>::iterator> hmap;
    list<pair<int, int>> cache;
    
    // splice用法:
    // void splice( const_iterator pos, list& other, const_iterator it );
    // void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);
    LRUCache(int capacity): sz(capacity) {}
    
    int get(int key) {
        if (hmap.count(key)) {
            cache.splice(cache.begin(), cache, hmap[key]);
            return hmap[key]->second;
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if (!hmap.count(key)) {
            cache.emplace_front(key, value); // 在首部添加
            hmap[key] = cache.begin();
            if (cache.size() > sz) { // 大于了
                hmap.erase(cache.back().first);
                cache.pop_back();
            }
        } else {
            hmap[key]->second = value;
            cache.splice(cache.begin(), cache, hmap[key]);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

4 | 数组中的第K个最大元素

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

note:

此题考查的点:

  1. 快速排序 (复杂度为O(N)) => 如何证明?
  2. 堆排序 (复杂度O(NlogN))

堆排序写法:

    堆排序 + 删除k次最顶端元素: 
    堆排的方法: 

    1. 从 N / 2开始每次sink建立大顶堆
    2. 删除最顶端元素方法: 将最顶端和最后一个交换后sink一次
    总复杂度: O(nlogn)

快速排序写法

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        random_shuffle(nums.begin(), nums.end());
        int n = nums.size();
        return select(nums, 0, n, n - k); // 第k大值是倒数第n - k个
    }
    int select (vector<int>& nums, int l, int r, int k) {
        int idx = partition(nums, l, r); // 分割
        if (idx == k) return nums[idx];
        return idx < k ? select(nums, idx + 1, r, k) : select(nums, l, idx, k); // 左闭右开
    }
    int partition(vector<int>& nums, int l, int r) {
        int i = l, j = r;
        int x = nums[l]; // 哨兵
        while (i < j) {
            while (j > i && nums[--j] > x);
            while (j > i && nums[++i] < x);
            swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[i]);
        return i;
    }
};

自建大顶堆, k次删除

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
class Solution {
public:
    /* 
        堆排序 + 删除k次最顶端元素: 
        堆排的方法: 
        1. 从 N / 2开始每次sink建立大顶堆
        2. 删除最顶端元素方法: 将最顶端和最后一个交换后sink一次
        总复杂度: O(nlogn)
    */

    void sink (vector<int>& x, int k, int n) {
        while ((k << 1) <= n) {
            int j = k << 1;
            if (j < n && x[j] < x[j + 1]) ++j; // 选择叶子中较大者
            if (x[k] >= x[j]) break; // 因为sink是自下而上进行的, 因此任何时刻k的儿子们都是大顶堆
            swap(x[k], x[j]);
            k = j;
        }
    }

    // 建立大顶堆
    void build (vector<int>& x, int n) {
        for (int k = n >> 1; k >= 1; --k) {
            sink(x, k, n);
        }
    }

    // 进行k - 1次`pop`操作, 然后返回堆顶
    int select (vector<int>& x, int k, int n) {
        k--;
        while (k--) {
            swap(x[n], x[1]);
            x.pop_back();
            sink(x, 1, --n); // 将第一个下沉到底部
        }
        return x[1];
    }
    int findKthLargest(vector<int>& nums, int k) {
        // 就不能从1开始嘛!
        nums.insert(nums.begin(), 0);
        int n = nums.size() - 1;
        // 构造大顶堆
        build(nums, n);
        // 选择第k大
        return select(nums, k, n);
    }
};

5 | K 个一组翻转链表

寻觅的最简单的一种写法

变量定义个数: (prev, nex, tail, now)共四个

其中prev和now用于遍历和调换顺序

tail和head用于控制头尾

最后head指向「尾部」! prev指向「头部」! now和tail指向「下一组的头部」

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

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
/**
 * 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* reverseKGroup(ListNode* head, int k) {
        if (!head) return head;
        ListNode* tail = head;
        for (int i = 0; i < k; ++i) {
            if (!tail) return head; // 这里不能调换顺序, tail是可以最后一次跑到空的!!
            tail = tail->next;
        }
        ListNode* now = head;
        ListNode* prev = tail, *nex = nullptr;
        while (now != tail) {
            nex = now->next, now->next = prev, prev = now, now = nex;
        }
        // 目前反转后头部为: prev, 尾部为: head
        head->next = reverseKGroup(tail, k);
        return prev;
    } 
};

6 | 排序数组

https://leetcode-cn.com/problems/sort-an-array/

快速排序

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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int l = 0, r = nums.size();
        random_shuffle(nums.begin(), nums.end());
        quick_sort(nums, l, r);
        return nums;
    }
    void quick_sort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int idx = partition(nums, l, r);
        quick_sort(nums, l, idx);
        quick_sort(nums, idx + 1, r);
    }
    int partition (vector<int>& nums, int l, int r) {
        int i = l, j = r;
        int x = nums[l];
        while (i < j) {
            while (j > i && nums[--j] > x);
            while (j > i && nums[++i] < x);
            swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[l]);
        return i;
    }
};

归并排序

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
class Solution {
public:
    vector<int> aux; // 辅助数组
    // 归并排序
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        aux = nums;
        int l = 0, r = nums.size();
        merge_sort(nums, l, r - 1);
        return nums;
    }
    void merge_sort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        // 左半边排序
        merge_sort(nums, l, mid);
        // 右半边排序
        merge_sort(nums, mid + 1, r);
        // 归并
        merge(nums, l, mid, r);
    }
    // 将l，r这一段归并
    void merge(vector<int>&nums, int l, int mid, int r) {
        int p1 = l, p2 = mid + 1, k = l;
        while (p1 <= mid && p2 <= r) {
            if (nums[p1] < nums[p2]) {
                aux[k++] = nums[p1++];
            } else {
                aux[k++] = nums[p2++];
            }
        }
        // 将剩余部分链接上
        while (p1 <= mid) aux[k++] = nums[p1++];
        while (p2 <= r) aux[k++] = nums[p2++];
        // 将aux复制回nums
        for (int i = l; i <= r; ++i) {
            nums[i] = aux[i];
        }
    }

};

堆排序

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
class Solution {
public:
    // 堆排序
    // (起点为0) ==> 左边为2 * k + 1, 右边为 2 * k + 2
    void sink (vector<int>& nums, int k, int n) {
        while (k * 2 + 1 < n) {
            int left = k * 2 + 1;
            int right = k * 2 + 2;
            int choice = left;
            if (left < n - 1 && nums[right] > nums[left]) choice = right;
            if (nums[choice] <= nums[k]) break;
            swap(nums[choice], nums[k]);
            k = choice;
        }
    }

    void build(vector<int>& nums, int n) {
        for (int i = n / 2; i >= 0; --i) {
            sink(nums, i, n);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        // 不从1开始试试
        int n = nums.size();
        build(nums, n);
        // 排序
        int k = n - 1;
        // 大小为n的数组维护(n - 1)次
        for (int i = 0; i < n - 1; ++i) {
            swap(nums[0], nums[k]); // 将堆顶和堆尾交换
            sink(nums, 0, k--); // 维护堆
        }
        return nums;
    }
};

7 | 两数之和

https://leetcode-cn.com/problems/two-sum/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hmap;
        int k = 0;
        for (auto i : nums) {
            if (hmap.count(target - i)) return {k, hmap[target - i]};
            else hmap[i] = k++;
        }
        return {};
    }
};

8 | 三数之和

https://leetcode-cn.com/problems/3sum/submissions/

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans; // 答案数组
        sort(nums.begin(), nums.end());
        int n = nums.size();
        // 左边
        for (int l = 0; l < n - 2; ++l) { 
            if (l != 0 && nums[l] == nums[l - 1]) continue; // 去重, 这样找到的一定重复(开头相同)
            int r = n - 1, k = l + 1; // 内部使用双指针找target即可
            int target = -nums[l]; // 加起来 == target
            while (k < r) {
                int cur = nums[k] + nums[r]; // 加起来的和
                // 升序
                if (cur > target) {
                    --r;
                } else if (cur < target) {
                    ++k;
                } else if (cur == target) {
                    // 判断右边界是否重复
                    if (r == n - 1 || nums[r] != nums[r + 1]) 
                        ans.push_back({nums[l], nums[k], nums[r]}); // 加入答案
                    ++k, --r; // 放外面
                }
            }
        }
        return ans;
    }
};

9 | 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 子数组(连续)
        // t代表的含义是 (以上一位置结尾的「最大子序和」)
        int ans = INT_MIN, t = 0;
        for (auto i : nums) {
            t = max(t + i, i);
            ans = max(ans, t);
        }
        return ans;
    }
};

10 | 合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/

减少特判是增加可读性的必要条件

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
/**
 * 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* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0, l1);
        ListNode* now = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                now->next = l1;
                l1 = l1->next;
            } else {
                now->next = l2;
                l2 = l2->next;
            }
            now = now->next;
        }
        if (l1) now->next = l1;
        else now->next = l2;
        return dummy->next;
    }
};

11 | 环形链表

只需要判断fast是否到达null即可, 因为fast走的快

https://leetcode-cn.com/problems/linked-list-cycle/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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) return false;
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }    
        return false;
    }
};

12 | 相交链表

因为最后不管是否相交总会走到空, 故无需特判

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1 = headA, *p2 = headB;
        while (p1 != p2) {
            p1 = p1 == nullptr ? headB : p1->next;
            p2 = p2 == nullptr ? headA : p2->next;
        }
        return p1;
    }
};

13 | 二叉树的锯齿形层序遍历

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

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
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        // 广搜每层反向就可以了
        if (!root) return {};
        int flag = true;
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            flag = !flag;
            vector<int> now;
            int sz = q.size();
            while (sz--) {
                auto k = q.front(); q.pop();
                now.push_back(k->val);
                if (k->left) q.push(k->left);
                if (k->right) q.push(k->right);
            }
            if (flag) reverse(now.begin(), now.end());
            ans.push_back(now);
        }
        return ans;
    }
};

14 | 二叉树的层序遍历

上一题的简化版

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

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
/**
 * 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) {
        if (!root) return {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            vector<int> now;
            int sz = q.size();
            while (sz--) {
                auto k = q.front(); q.pop();
                now.push_back(k->val);
                if (k->left) q.push(k->left);
                if (k->right) q.push(k->right);
            }
            ans.push_back(now);
        }
        return ans;
    }
};

15 | 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minn = INT_MAX >> 1;
        int ans = 0;
        for (auto i : prices) {
            ans = max(ans, i - minn);
            minn = min(minn, i);
        }
        return ans;
    }
};

16 | 有效的括号

https://leetcode-cn.com/problems/valid-parentheses/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> hmap = {{']', '['}, {')', '('}, {'}', '{'}};
        stack<char> stk;
        for (auto i : s) {
            // 右括号
            if (hmap.count(i)) {
                if (stk.empty()) return false;
                auto now = stk.top(); stk.pop();
                if (now != hmap[i]) return false;
            } else {
                stk.push(i);
            }
        }           
        return stk.empty();
    }
};

17 | 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k = m + n - 1; // 指向合并后的尾部
        --m, --n; // 指向两个数组最后一个
        while (m >= 0 && n >= 0) {
            nums1[k--] = nums2[n] > nums1[m] ? nums2[n--] : nums1[m--];
        }
        // 如果nums2先空, nums1前面本身就是nums1不用管
        // 如果nums1先空, 需要把nums2放到nums1前面
        while (n >= 0) {
            nums1[k--] = nums2[n--];
        }
    }
};

18 | 字符串相加

https://leetcode-cn.com/problems/add-strings/

模拟竖式加法后逆序

减少特判! 和T37「两数相加」的实现方法基本是一致的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string addStrings(string nums1, string nums2) {
        int carry = 0;
        string res;
        int p1 = nums1.size() - 1, p2 = nums2.size() - 1;
        // 还有加法的三种情况
        while (p1 >= 0 || p2 >= 0 || carry) {
            int a = 0, b = 0;
            if (p1 >= 0) a = nums1[p1--] - '0';
            if (p2 >= 0) b = nums2[p2--] - '0';
            res += (a + b + carry) % 10 + '0';
            carry = (a + b + carry) / 10;
        } 
        // 倒序
        reverse(res.begin(), res.end());
        return res;
    }
};

19 | 二叉树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

  1. 自底向上
  2. 不用担心重复更新res的问题, 因为res更新的情况仅仅只会出现一次
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
/**
 * 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:
    TreeNode* res;

    // 1. 检查是否自己 + 左边 | 右边
    // 2. 检查是否 左边 & 右边
    bool check (TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return false;
        // 以左儿子为根的树是否包含 p | q
        bool lflag = check(root->left, p, q);
        // 以右儿子为根的树是否包含 p | q
        bool rflag = check(root->right, p, q);
        if (lflag && rflag || (lflag || rflag) && (root == p || root == q)) {
            res = root;
            return true;
        }
        return lflag || rflag || root == p || root == q;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        check(root, p, q);
        return res;    
    }
};

20 | 环形链表2

https://leetcode-cn.com/problems/linked-list-cycle-ii/

需要利用的条件:

  1. 快指针走的是满指针2倍速
  2. 快指针比慢指针多走n圈
  3. 然后写出公式, 考虑a和c的关系

对快慢指针进行分析:

当快慢指针相遇时:

快指针走了: a + b + n * circle

慢指针走了: a + b

令 c = circle - b ==> b + c = circle

又已知快指针是满指针的两倍: 即: a + b = n * circle

由 a + b = n * circle 和 b + c = circle

相减得到a - c = (n - 1) * circle

即a - c是circle的整数倍

那么当快慢指针相遇时候, 让一个指针从起点开始和慢指针一起走, 当他走到a时候, 慢指针走了 c + k圈, 最后会在起点相遇

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(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // 本题考查数学知识
    // 对快慢指针进行分析: 
    // 当快慢指针相遇时: 
    // 快指针走了: a + b + n * circle
    // 慢指针走了: a + b
    // 令 c = circle - b ==> b + c = circle
    // 又已知快指针是满指针的两倍: 即: a + b = n * circle
    // 由 a + b = n * circle 和 b + c = circle
    // 相减得到a - c = (n - 1) * circle
    // 即a - c是circle的整数倍
    // 那么当快慢指针相遇时候, 让一个指针从起点开始和慢指针一起走, 当他走到a时候, 慢指针走了 c + k圈, 最后会在起点相遇
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next; 
            slow = slow->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next) return nullptr;
        ListNode* p = head;
        while (p != slow) {
            slow = slow->next;
            p = p->next;
        }
        return slow;
    }
};

21 | 搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 二分的基础上加入分类讨论的思想
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] == target) return mid;
            if (nums[mid] >= nums[0]) {
                // [0, mid)
                if (target >= nums[0] && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else { 
                if (target > nums[mid] && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }    
        return -1;
    }
};

22 | 全排列

https://leetcode-cn.com/problems/permutations/

利用标记数组的写法 (可以保证字典序):

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
class Solution {
public:
//  dfs填充
    vector<int> vis;
    int n;
    vector<vector<int>> ans;

    void dfs (int k, vector<int> now, vector<int>& nums) {
        if (k == n) {
            ans.push_back(now);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                vis[i] = 1;
                now.push_back(nums[i]);
                dfs(k + 1, now, nums);
                now.pop_back();
                vis[i] = 0;
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        vis.resize(n, 0);
        vector<int> now;
        dfs(0, now, nums);
        return ans;
    }
};

利用交换的写法, 减少了空间复杂度: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    // swap的写法 
    vector<vector<int>> ans;
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        dfs(nums, 0, n);
        return ans;
    }
    void dfs(vector<int>& nums, int now, int n) {
        if (now == n) {
            ans.push_back(nums);
            return;
        }
        for (int i = now; i < n; ++i) {
            swap(nums[now], nums[i]);
            dfs(nums, now + 1, n);
            swap(nums[now], nums[i]);
        }
    }
};

23 | 二分查找

https://leetcode-cn.com/problems/binary-search/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 左闭右开
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return -1;
    }
};

24 | 螺旋矩阵

https://leetcode-cn.com/problems/spiral-matrix/submissions/

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // 收缩上写下左右边界
        if (matrix.empty()) return {};
        int n = matrix.size(), m = matrix[0].size();
        int left = 0, right = m - 1, top = 0, bottom = n - 1;
        vector<int> ans;
        while (1) {
            for (int i = left; i <= right; ++i) {
                ans.push_back(matrix[top][i]);
            }
            if (++top > bottom) break; // 等于的时候还需要遍历一次bottom所以是 > 时候break
            for (int i = top; i <= bottom; ++i) {
                ans.push_back(matrix[i][right]);
            }            
            if (--right < left) break;
            for (int i = right; i >= left; --i) {
                ans.push_back(matrix[bottom][i]);
            }
            if (--bottom < top) break;
            for (int i = bottom; i >= top; --i) {
                ans.push_back(matrix[i][left]);
            }
            if (++left > right) break;
        }
        return ans; 
    }
};

25 | 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/

方案1: 动态规划 (注意考虑长度为1和长度为2的作为初始化)

初始化: dp[i][i]和dp[i][i + 1]

转移: dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]

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
class Solution {
public:
    // 方法1. 动态规划
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int> (n, 0));
        // 状态转移方程:
        // dp[i][j] 表示 s[i..j]为回文串
        // dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]
        // 初始化: 
        // dp[i][i] = 1;   光这个不行, 相邻的情况无法覆盖到
        // dp[i][i + 1] = s[i] == s[i + 1];
        int ans = 1, idx = 0; // 记录长度和起始位置
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
            if (i != n - 1 && s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                ans = 2;
                idx = i;
            }
        }
        // 递推是从小往大, 所以第一层枚举字符串长度
        for (int len = 2; len <= n; ++len) {
            // 左
            for (int i = 0; i < n; ++i) { 
                int j = i + len - 1;
                if (j >= n) break;
                if (dp[i + 1][j - 1] && (s[i] == s[j])) {
                    dp[i][j] = 1;
                    if (j - i + 1 > ans) {
                        ans = j - i + 1;
                        idx = i;
                    }
                }
            }
        }
        return s.substr(idx, ans);
    }
};

方案2. 中心扩展(trick很多, 建议熟记!!)

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
class Solution {
public:
    // 中心扩展
    // 非常精妙的check, 同时处理了: {奇数情况, 偶数情况, 越界情况} 并且无需特判
    int check (string s, int l, int r) {
        while (l >= 0 && r <= s.size() - 1 && s[l] == s[r]) {
            --l, ++r;
        }
        // 结束位置是字符串边界之外的地方
        return r - l - 1;
    }
    string longestPalindrome(string s) {
        int start = 0, len = 1;
        for (int i = 0; i < s.size(); ++i) {
            int now_len = max(check(s, i, i), check(s, i, i + 1));
            if (now_len > len) {
                // 奇数情况: xxyxx (i = 2, now_len = 5) => start = i - (now_len - 1) / 2;
                // 偶数情况: xxyyxx (i = 2, now_len = 6) => start = i - (now_len - 1) / 2;
                start = i - (now_len - 1) / 2;
                len = now_len;
            }
        }
        return s.substr(start, len);
    }
};

26 | 岛屿数量

这里卡了一会, 注意bfs标记的时候要立即标记不要取出队列以后再标记

https://leetcode-cn.com/problems/number-of-islands/

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

class Solution {
public:
//  方法: 典型BFS计数
    vector<int> dir = {-1, 0, 1, 0, -1};
    void bfs (int i, int j, vector<vector<char>>& grid) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        grid[i][j] = '3';
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; ++k) {
                int nx = x + dir[k], ny = y + dir[k + 1];
                if (nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size() || grid[nx][ny] != '1') continue; 
                if (grid[nx][ny] == '1') {
                    grid[nx][ny] = '3'; 
                    q.emplace(nx, ny);
                } 
            }
        }
    };
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    ++ans;
                    bfs(i, j, grid);
                }
            }
        }
        return ans;
    }
};

27 | 接雨水

https://leetcode-cn.com/problems/trapping-rain-water/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    // 双指针保存左右最大值, 不断更新
    int trap(vector<int>& height) {
        int n = height.size();
        int leftmax = height[0], rightmax = height[n - 1];
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            //可以接两边 最高的的更小值 那么多水
            if (leftmax < rightmax) {
                ans += max(leftmax - height[l], 0);
                leftmax = max(leftmax, height[l++]);
            } else {
                ans += max(rightmax - height[r], 0);
                rightmax = max(rightmax, height[r--]);
            }
        }
        return ans;
    }
};

28 | 最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/

  1. 动态规划解法: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    // 这题我可太熟了
    // 1. 动态规划 O(n ^ 2)
    // 2. 贪心 O(nlogn)
    // 动态规划解法
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        // dp[i] = max(dp[i], dp[j] + 1);
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    ans = max(ans, dp[i]);
                }
            }
        }
        return ans;
    }
};
  1. 贪心解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    // 这题我可太熟了
    // 1. 动态规划 O(n ^ 2)
    // 2. 贪心 O(nlogn)
    // 贪心解法
    int lengthOfLIS(vector<int>& nums) {
        vector<int> res;
        for (auto i : nums) {
            if (res.empty() || i > res.back()) res.push_back(i);
            else {
                auto it = lower_bound(res.begin(), res.end(), i);
                *it = i;
            }
        }
        return res.size();
    }
};

29 | 反转链表2

所有链表反转类的题目基本类似

https://leetcode-cn.com/problems/reverse-linked-list-ii/submissions/

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
/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        if (!head) return head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* slow = dummy, *fast = dummy;
        for (int i = 0; i < right - left + 1; ++i) {
            fast = fast->next;
        }
        for (int i = 1; i < left; ++i) {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* tail = fast->next, *before = slow;
        ListNode* prev = tail, *nex = nullptr;
        slow = slow->next;
        while (slow != tail) {
            nex = slow->next, slow->next = prev, prev = slow, slow = nex;
        }
        before->next = prev;
        return dummy->next;
    }
};

30 | 用栈实现队列

核心: 仅当有peek操作并且stk2为空的时候才将stk1中的内容放入stk2中

https://leetcode-cn.com/problems/implement-queue-using-stacks/

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
class MyQueue {
private:
    stack<int> stk1, stk2;
public:
    /** Initialize your data structure here. */
    // 核心思想: 仅当有peek操作并且stk2为空的时候才将stk1中的内容放入stk2中
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stk1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x = peek();
        stk2.pop();
        return x;
    }
    
    /** Get the front element. */
    int peek() {
        if (stk2.size()) return stk2.top();
        while (stk1.size()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        return stk2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk1.empty() && stk2.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

31 | 二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

迭代写法 (morris暂时抛弃)

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 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> ans;
        stack<TreeNode*> stk;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top(); stk.pop();
            ans.push_back(root->val);
            root = root->right;
        }
        return ans;
    }
};

32 | 二叉树的右视图

bfs层序, 每次保存最后一个结点

https://leetcode-cn.com/problems/binary-tree-right-side-view/submissions/

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
/**
 * 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> rightSideView(TreeNode* root) {
        // 利用bfs每次保存最后一个结点
        vector<int> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int sz = q.size();
            TreeNode* t = nullptr;
            for (int i = 0; i < sz; ++i) {
                auto now = q.front();
                q.pop();
                t = now;
                if (now->left) q.push(now->left);
                if (now->right) q.push(now->right);
            }
            ans.push_back(t->val);
        }
        return ans;
    }
};

33 | 爬楼梯

基本递推

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1, dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] += dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

优化空间

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        int ans = 1;
        for (int i = 2; i <= n; ++i) {
            ans = a + b;
            a = b;
            b = ans;
        }
        return ans;
    }
};

34 | 合并k个排序链表

https://leetcode-cn.com/problems/merge-k-sorted-lists/

归并排序优化空间

次数没变(k - 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
/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        return merge_list(lists, 0, n - 1);
    }
    ListNode* merge_list(vector<ListNode*>& lists, int l, int r) {
        if (l > r) return nullptr;
        if (l == r) return lists[r];
        int mid = l + r >> 1;
        ListNode* l1 = merge_list(lists, l, mid);
        ListNode* l2 = merge_list(lists, mid + 1, r);
        return merge(l1, l2);
    }
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0, nullptr);
        ListNode* now = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                now->next = l1;
                l1 = l1->next;
            } else {
                now->next = l2;
                l2 = l2->next;
            }
            now = now->next;
        }
        if (l1) now->next = l1;
        if (l2) now->next = l2;
        return dummy->next;
    }

};

优先队列写法

(不要一次性保存所有结点, 可以优化空间复杂度为O(k))

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
/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        // 优先队列的写法
        priority_queue<pair<int, ListNode*>> q;
        for (auto i : lists) {
            if (i)
                q.emplace(-i->val, i); // 小的在上
        }
        ListNode* dummy = new ListNode(0, nullptr);
        ListNode* tail = dummy;
        while (q.size()) {
            auto [v, now] = q.top(); q.pop();
            tail->next = now;
            tail = tail->next;
            if (now->next) q.emplace(-now->next->val, now->next);
        }
        return dummy->next;
    }
};

35 | 链表中倒数第k个节点

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* slow = head, *fast = head;
        for (int i = 0; i < k; ++i) fast = fast->next;
        while (fast) {
            fast = fast->next, slow = slow->next;
        }
        return slow;
    }
};

36 | x的平方根

https://leetcode-cn.com/problems/sqrtx/submissions/

二分查找

注意爆int的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    // 二分
    int mySqrt(int x) {
        long long l = 0, r = (long long)x + 1;
        while (l < r) {
            long long mid = (l + r) >> 1;
            if (mid * mid <= x) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return r - 1;
    }
};

37 | 两数相加

https://leetcode-cn.com/problems/add-two-numbers/

减少特判! 和T18「字符串相加」的实现方法基本是一致的。

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
/**
 * 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* dummy = new ListNode(0, nullptr);
        ListNode* now = dummy;
        int carry = 0;
        while (l1 || l2 || carry) {
            int a = 0, b = 0;
            if (l1) {
                a += l1->val, l1 = l1->next;
            }
            if (l2) {
                b += l2->val, l2 = l2->next;
            }
            int res = a + b + carry;
            carry = res / 10;
            ListNode* new_node = new ListNode(res % 10, nullptr);
            now->next = new_node;
            now = now->next;
        }
        return dummy->next;
    }
};

38 | 删除链表的倒数第 N 个结点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

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
/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        // 快慢指针的基本用法
        ListNode* dummy = new ListNode(0, head);
        ListNode *slow = dummy, *fast = dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        while (fast->next) {
            fast = fast->next, slow = slow->next;
        }
        // 删除slow->next
        slow->next = slow->next->next;
        return dummy->next;
    }
};

39 | 字符串转整数

https://leetcode-cn.com/problems/string-to-integer-atoi/

小细节比较多

  1. 前导0
  2. 正负号
  3. 忽略其他部分
  4. 判断是否溢出 (简便方法直接上long long)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int myAtoi(string s) {
        int p = 0, len = s.size();
        long long ans = 0;
        // 去除前导0
        while (p < len && s[p] == ' ') ++p;
        if (p >= len) return 0; // ?有这种情况吗
        // 判断正负号
        bool neg = false;
        if (s[p] == '-') neg = true, ++p;
        else if (s[p] == '+') ++p;
        // 处理数字部分, 注意忽略其他部分
        while (p < len && s[p] >= '0' && s[p] <= '9') {
            long long cur = s[p++] - '0'; // 当前数位
            if (neg) cur = -cur;
            ans = ans * 10 + cur;
            if (ans > INT_MAX) return INT_MAX;
            if (ans < INT_MIN) return INT_MIN;
        }
        return static_cast<int>(ans);
    }
};

40 | 重排链表

https://leetcode-cn.com/problems/reorder-list/

本题有两种做法:

  1. 双端队列
  2. 原地

双端队列很简单, 这里只记录原地的写法:

  1. 快慢指针找到链表中点将链表分开
  2. 反转后面的链表
  3. 按顺序合并链表

坑点:

  1. 快慢指针奇偶考虑清楚
  2. 分开后记得将l1末尾指向null
  3. 按顺序合并链表考虑l1和l2长度相等, 或者l1长度比l2多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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * 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:
    void reorderList(ListNode* head) {
        // 这题可以原地做吗??
        // 不用原地的方法很简单, 就是压到deque中就可以
        // 可以寻找中点, 然后左右半边合并?
        // 考虑下奇数和偶数的情况:
        // 奇数 1->2->3  ==>  1->2 和 3 
        // 偶数 1->2->3->4 ==>  1->2 和 3->4 (3->4逆序变为4->3)
        // 即奇数左半边比右半边多一个
        if (!head) return;
        ListNode* l1 = head;
        ListNode* mid = split_list(head);
        ListNode* l2 = mid->next;
        mid->next = nullptr;
//         cout << l1->val << ' ' << l2->val << endl;
        l2 = reverse_list(l2);
        // cout << l2->val << endl;
        merge(l1, l2);
    }

    // return: 切断后第二个链表的头结点
    ListNode* split_list(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    // return: 反转后链表的头节点
    ListNode* reverse_list(ListNode* head) {
        // 反转链表
        if (!head) return head;
        ListNode* pre = nullptr, *nex;
        while (head != nullptr) {
            nex = head->next, head->next = pre, pre = head, head = nex;
        }
        return pre;
    }

    // return: 按顺序合并的两个链表
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0, nullptr);
        ListNode* cur = dummy;
        // l1的长度 == l2 / l2 + 1
        while (l1 && l2) {
            cur->next = l1;
            l1 = l1->next;
            cur = cur->next;
            cur->next = l2;
            l2 = l2->next;
            cur = cur->next;
        }
        // 考虑到l1可能剩一个, 得接上
        if (l1) cur->next = l1;
        return dummy->next;
    }
};

41 | 合并区间

https://leetcode-cn.com/problems/merge-intervals/submissions/

画个数组想想就出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;
        int left = intervals[0][0], right = intervals[0][1];
        for (auto inter : intervals) {
            int l = inter[0], r = inter[1];
            if (right < l) {
                ans.push_back({left, right});
                left = inter[0], right = inter[1];
            } else {
                right = max(right, r);
            }
        }
        ans.push_back({left, right}); // 最后多push一次
        return ans;
    }
};

42 | 二叉树的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

43 | 反转字符串里的单词

https://leetcode-cn.com/problems/reverse-words-in-a-string/

非O(1)写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
// 非O(1)写法
    string reverseWords(string s) {
        stringstream ss(s);
        vector<string> ans;
        string x;
        while (ss >> x) {
            ans.push_back(x);
        }
        string res = "";
        reverse(ans.begin(), ans.end());
        for (auto i : ans) {
            res += i + " ";
        }
        res.pop_back(); // 去除最后空格
        return res;
    }
};

O(1)写法

由于包含多个空格, 需要一个写指针记录写的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string reverseWords(string s) {
        // O(1)解法
        // 思路: 首先反转整个字符串, 然后指针搞搞搞反转每一个空格分割的单词
        // 由于包含多个空格, 故需要用一个写指针
        int n = s.size();
        reverse(s.begin(), s.end());
        int p = 0;
        for (int l = 0; l < n; ++l) {
            if (s[l] != ' ') {
                if (p != 0) s[p++] =  ' ';
                int r = l;
                while (r < n && s[r] != ' ') s[p++] = s[r++];
                int len = r - l;
                reverse(s.begin() + p - len, s.begin() + p);
                l = r;
            }
        }
        s.erase(s.begin() + p, s.end()); // 删除后面的一众空格
        return s;
    }
};

44 | 平衡二叉树

https://leetcode-cn.com/problems/balanced-binary-tree/

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
/**
 * 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 flag = true;
    bool isBalanced(TreeNode* root) {
        // 基本思路:
        // 暴力的解法是对每个结点求深度, 但是没必要, 重复求了很多次
        // 应该自底向上
        // 判断自己是否是平衡二叉树, 再向上返回高度
        check(root);
        return flag;
    }
    int check (TreeNode* root) {
        if (!root) return 0;
        int right_depth = check(root->right), left_depth = check(root->left);
        if (!flag) return -1; // 剪枝
        if (abs(right_depth - left_depth) > 1) flag = false;
        return max(left_depth, right_depth) + 1;
    }
};

45 | 二叉树的前序遍历

一样只写递归版本

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
/**
 * 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> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                ans.push_back(root->val);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            root = root->right;
        }
        return ans;
    }
};

46 | 二叉树中的最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/submissions/

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
/**
 * 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:
    int ans = INT_MIN; // 全局ans
    int maxPathSum(TreeNode* root) {
        // 感觉和那个平衡二叉树的题很像
        // 递归的时候可以自底向下, 维护一个全局的答案, 再分别向上更新自己的值
        check(root);
        return ans;
    }
    int check(TreeNode* root) {
        if (!root) return 0;
        int l = check(root->left);
        int r = check(root->right);
        // l, r可以选或者不选
        l = max(0, l), r = max(0, r);
        ans = max(ans, l + r + root->val);
        // 向上返回左边或右边 + 当前节点的最大路径
        return max(l, r) + root->val; 
    }
};

47 | 路径总和2

https://leetcode-cn.com/problems/path-sum-ii/submissions/

减弱版为:「64. 路经总和」(不需要记录路径)

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 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>> ans;
    int target;

    void dfs(TreeNode* root, vector<int>& cur, int sum) {
        if (!root) return;
        cur.push_back(root->val);
        sum += root->val;
        // 叶子
        if (!root->right && !root->left && target == sum) {
            ans.push_back(cur);
        }
        dfs(root->left, cur, sum);
        dfs(root->right, cur, sum);
        cur.pop_back(); // 回来的时候pop掉
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        // 基本的深搜
        target = targetSum;
        vector<int> now;
        dfs(root, now, 0);
        return ans;
    }
};

48 | 下一个排列

https://leetcode-cn.com/problems/next-permutation/submissions/

(官方题解好像要短点, 思路是一样的)

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        // 这题其实是一个思维题
        // 1. 从后向前找到 nums[k] < nums[k + 1], k就是要处理的标志点
        // 2. 在[k, n - 1] (一个降序排列) 中找到大于nums[k]的最小值与k交换
        // 3. 将[k + 1, n - 1] 这一段反序
        int n = nums.size();
        bool flag = false;
        for (int k = n - 2; k >= 0; --k) {
            if (nums[k] < nums[k + 1]) {
                flag = true;
                for (int j = n - 1; j > k; --j) {
                    if (nums[j] > nums[k]) {
                        swap(nums[j], nums[k]);
                        reverse(nums.begin() + k + 1, nums.end());
                        break;
                    }
                }
            }
            if (flag) return;
        }
        if (!flag) reverse(nums.begin(), nums.end());
    }
};

49 | 从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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 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:
// 后序 / 前序 指示根节点
// 中序用于分治造树
// 1. 哈希表将中序的结点和序号一一对应方便分治 (inorder中)
// 2. 全局指针指示目前处理到的根节点 (preorder中)
    int ptr = 0, n = 0;
    unordered_map<int, int> idx;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        n = preorder.size();
        for (int i = 0; i < n; ++i) {
            idx[inorder[i]] = i;
        }
        return build(0, n - 1, preorder, inorder);
    }
    TreeNode* build (int left, int right, vector<int>& preorder, vector<int>& inorder) {
        if (left > right) return nullptr;
        int now = preorder[ptr++]; // 当前根结点值
        TreeNode* node = new TreeNode(now);
        int mid = idx[now];
        node->left = build(left, mid - 1, preorder, inorder);
        node->right = build(mid + 1, right, preorder, inorder);
        return node; 
    }
};

50 | 排序链表

自顶向下归并排序

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
/**
 * 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* sortList(ListNode* head) {
        // 归并排序
        if (!head) return head;
        ListNode* t = head;
        while (t->next) t = t->next;
        return sortList(head, t);  // 头, 尾    
    }
    // 找到中点 (偶数在中左, 奇数在中)
    ListNode* find_mid (ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == tail) return head;
        ListNode* mid = find_mid(head);
        ListNode* nex = mid->next;
        mid->next = nullptr; // 置空很重要
        return merge(sortList(head, mid), sortList(nex, tail));
    }
    ListNode* merge(ListNode *l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0, nullptr), *now = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                now->next = l1;
                l1 = l1->next;
            } else {
                now->next = l2;
                l2 = l2->next;
            }
            now = now->next;
        }
        if (l1) now->next = l1;
        if (l2) now->next = l2;
        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
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
64
/**
 * 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* sortList(ListNode* head) {
        if (!head) return head;
        int length = 0;
        // 统计长度
        ListNode* tmp = head;
        while (tmp) tmp = tmp->next, ++length;
        // 自底向上, 从长度1开始, 每次 x2开始归并
        ListNode* dummy = new ListNode(0, head); // 第一次指向head
        for (int len = 1; len < length; len <<= 1) {
            ListNode* prev = dummy, *now = dummy->next; // now指向归并后第一个
            while (now) {
                ListNode* left = now;
                for (int i = 0; i < len - 1 && now->next; ++i) {
                    now = now->next;
                }
                ListNode* right = now->next;
                now->next = nullptr;
                // 第一段就是left开头的
                now = right;
                // 再获取第二段, 方法一致
                for (int i = 0; i < len - 1 && now && now->next; ++i) {
                    now = now->next;
                }
                // 剩余的链表取决于now->next现在是否指向空
                ListNode* remain = now ? now->next : nullptr;
                if (now) now->next = nullptr;
                // 将left和right这两个链表归并了
                prev->next = merge(left, right);
                while (prev->next) prev = prev->next; // 将prev移动到归并后的链表末尾
                now = remain;
            }
        }
        return dummy->next;
    }
    ListNode* merge(ListNode *l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0, nullptr), *now = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                now->next = l1;
                l1 = l1->next;
            } else {
                now->next = l2;
                l2 = l2->next;
            }
            now = now->next;
        }
        if (l1) now->next = l1;
        if (l2) now->next = l2;
        return dummy->next;
    }
};

51 | 求根节点到叶节点数字之和

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

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
/**
 * 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:
    int sum = 0;
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return sum;
    }
    // 自上而下dfs
    void dfs(TreeNode* root, int now) {
        if (!root) return;
        now = now * 10 + root->val;
        if (!root->left && !root->right) {
            sum += now;
        }
        dfs(root->left, now);
        dfs(root->right, now); 
    }
};

52 | 用 Rand7() 实现 Rand10()

https://leetcode-cn.com/problems/implement-rand10-using-rand7/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    // 拒绝采样思路:
    // rand7()生成 1~7 之间的随机数
    // 如果使用(rand7() - 1) * 7生成的就是 0, 7, 14, 21, 28, 35, 42 这些数
    // 如果使用(rand7() - 1) * 7 + rand7()生成得就是 1~49 得随机数
    // 取1~40之间的40个数, (x - 1) % 10 + 1就是1 ~ 10的随机数
    int rand10() {
        int res;
        do {
            res = (rand7() - 1) * 7 + rand7();
        } while (res > 40);
        return (res - 1) % 10 + 1;
    }
};

53 | 编辑距离

https://leetcode-cn.com/problems/edit-distance/

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
class Solution {
public:
    // 首先想到的思路: 暴力检查所有操作, 取最小 ----> 不现实
    // 观察发现对word1和word2的操作本质上是相同的
    // 插入和删除互为相反, 而替换是同质的
    // 故只需要将操作转化为对word1的操作就可以了
    // 对于两个字符串, 如最长公共子串这样的问题, 考虑使用dp[i][j], 每一维度分别对应一个字符串来进行比较
    // 如果用dp, 如何定义状态转移?
    // 假设dp[i][j]表示word1的前i - 1个字符和word2的前j - 1个字符的编辑距离

    // 状态转移: 
    // 如果word1[i - 1] == word2[j - 1] ==> dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]) + 1)
    // 如果word1[i - 1] != wrod2[j - 1] ==> dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

    // 可以归到上面
    // 如果word1[i - 1] && (j >= word2.size()) ==> dp[i][word2.size() - 1] = dp[i - 1][word2.size() - 1] + 1
    // 如果(i >= word1.size()) && word2[j - 1] ==> dp[word1.size() - 1][j] = dp[word1.size() - 1][j - 1] + 1

    // 初始化:
    // 对空串情况进行初始化

    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));
        for (int i = 0; i <= n; ++i) dp[i][0] = i;
        for (int j = 0; j <= m; ++j) dp[0][j] = j;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int a = dp[i - 1][j - 1], b = dp[i - 1][j], c = dp[i][j - 1];
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = min(a, min(b, c) + 1);
                } else {
                    dp[i][j] = min(a, min(b, c)) + 1;
                }
            }
        }
        return dp[n][m]; 
    }
};

54 | 寻找两个正序数组的中位数

这题起码再做3遍

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
class Solution {
public:
    // 勇敢牛牛, 不怕困难, 抄一遍, 记得牢
    int find_kth_element (vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        // 两个数组分别取 nums[k / 2 - 1]的最小值, 我们要找第k小的, 而二者较小值之前最多只有 2 * (k / 2 - 1) = k - 2个比它小的
        // 指示查找边界
        int idx1 = 0, idx2 = 0;
        while (1) {
            // 边界条件1. 其中一个数组为空
            if (idx1 == n) {
                return nums2[idx2 + k - 1];
            }
            if (idx2 == m) {
                return nums1[idx1 + k - 1];
            }
            // 边界条件2. k就是1, 那么直接返回更小的那一个
            if (k == 1) {
                return min(nums1[idx1], nums2[idx2]);
            }
            // 防止越界
            int new_idx1 = min(idx1 + k / 2 - 1, n - 1);
            int new_idx2 = min(idx2 + k / 2 - 1, m - 1); 
            int p1 = nums1[new_idx1], p2 = nums2[new_idx2];
            if (p1 <= p2) {
                k -= new_idx1 - idx1 + 1; // 减去排除数的个数
                idx1 = new_idx1 + 1;
            } else {
                k -= new_idx2 - idx2 + 1;
                idx2 = new_idx2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();
        // 如果是奇数, 找第 len / 2 + 1小的
        // 如果是偶数, 找第 len / 2和len / 2 + 1小的 相加 / 2
        if (len & 1) {
            return static_cast<double> (find_kth_element(nums1, nums2, len / 2 + 1));
        } else { 
            double left = static_cast<double> (find_kth_element(nums1, nums2, len / 2 + 1));
            double right = static_cast<double> (find_kth_element(nums1, nums2, len / 2));
            return (left + right) / 2.000; 
        }
    }
};

55 | 最小覆盖子串

经典滑动窗口, 注意两个哈希表的用途

这里c在第一次找到后就不变了, 之后一直靠j维护count和source的冗余关系来维持窗口

https://leetcode-cn.com/problems/minimum-window-substring/submissions/

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
class Solution {
public:
// 滑窗吧..
// 用哈希表记录字符出现情况
    unordered_map<char, int> count, source; // 一个是当前动态的, 一个是统计静态的

    string minWindow(string s, string t) {
        // 统计t的字符数
        for (auto i : t) source[i]++;
        string ans;
        int c = 0; // 统计有多少个字符
        // i, j分别为右, 左指针
        for (int i = 0, j = 0; i < s.size(); ++i) {
            ++count[s[i]];
            if (count[s[i]] <= source[s[i]]) c++; // 统计包含的个数
            while (j <= i && count[s[j]] > source[s[j]]) --count[s[j++]]; // 收缩左边界, 这时候c的值不会减, 因为收缩的都是多余的
            // 统计个数刚好为
            if (c == t.size()) {
                int len = i - j + 1;
                if (ans.empty() || len < ans.size()) {
                    ans = s.substr(j, len);
                }
            }
        }
        return ans;
    }
};

56 | 删除链表中的重复元素2

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

是「74 | 删除排序链表中的重复元素」的加强版

用一个指在now前面的指针跑重复元素即可

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) {
        if (!head) return head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* now = dummy;
        while (now->next && now->next->next) {
            ListNode* p = now->next;
            if (p->val == p->next->val) {
                while (p->next && p->val == p->next->val) p = p->next;
                now->next = p->next;
            } else {
                now = now->next;
            }
        }
        return dummy->next;
    }
};

57 | 缺失的第一个正数

https://leetcode-cn.com/problems/first-missing-positive/

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
class Solution {
public:
    // 常数级别额外空间..
    // 首先
    // 性质1. 最小正整数不会超过 nums.size() ==> 要在nums数组里一通操作    
    // 如果额外空间为N, 可以对这个空间进行标记, 然后遍历的第一个未标记就是答案
    // 那么可以考虑将标记标在原数组上
    // 但是如果进行了标记, 那么数就被覆盖了, 答案会不对
    // 如何进行标记还保留原始数据?
    // 考虑到我们用到的数是(0, 正无穷], 那么将数据标记为负数不就可以保留数据并且标记两个效果吗
    // 需要考虑一个特殊情况: 如果一个数本来就是负数, 那么标记会将它变为正数, 但实际上它不应该被包含, 特判一下? 不可, 需要预处理
    // 为了防止重复标记, 标记的时候需要用绝对值
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        // 第一次遍历预处理负数
        for (auto& i : nums) {
            if (i <= 0) i = n + 1;
        }
        // 第二遍
        for (auto& i : nums) {
            int k = abs(i);
            if (k <= n) nums[k - 1] = -abs(nums[k - 1]);
        }
        // 求答案
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

58 | 滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/submissions/

单调队列 => 双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 用双端队列维护一个单调递减
        deque<int> q;
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            // 先弹
            while (i - k + 1 >= 0 && q.size() && q.front() < i - k + 1) {
                q.pop_front();
            }
            // 再压
            while (q.size() && nums[i] > nums[q.back()]) q.pop_back();
            q.push_back(i);
            // 返回队列首部就是目前的最大值
            if (i >= k - 1) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

59 | 二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/

和那个二叉树最大路径和基本一致, 为啥这题是简单那题是困难?

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
/**
 * 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:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;        
    }
    int dfs (TreeNode* root) {
        if (!root) return 0;
        int l = dfs(root->left), r = dfs(root->right);
        ans = max(ans, l + r);
        return max(l, r) + 1; // 向上返回的是深度
    }
};

60 | 最小栈

两个栈, 保存最小值的栈「同步更新」

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
class MinStack {
public:
    /** initialize your data structure here. */
    // 直接两个栈
    stack<int> stk, min_stk;
    MinStack() {

    }
    
    void push(int val) {
        stk.push(val);
        if (min_stk.empty() || val < min_stk.top()) min_stk.push(val);
        else min_stk.push(min_stk.top());
    }
    
    void pop() {
        stk.pop();
        min_stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return min_stk.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

61 | 最长重复子数组

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    static const int N = 1005;
    int dp[N][N];
    // 复杂度O(N^2)
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        // dp[i][j]表示以i - 1, j - 1结尾的最长公共子数组长度
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
};

滑动窗口

理解下两种偏移方式

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
class Solution {
public:
    // 滑动窗口解法

    int count (vector<int>& nums1, vector<int>& nums2, int offset1, int offset2, int len) {
        int cnt = 0, ans = 0;
        for (int i = 0; i < len; ++i) {
            if (nums1[offset1 + i] == nums2[offset2 + i]) {
                ++cnt;
            }
            else {
                cnt = 0;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }

    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        int ans = 0;
        // nums2相对于nums1偏移量
        for (int i = 0; i < n; ++i) {
            int len = min(n - i, m);
            ans = max(ans, count(nums1, nums2, i, 0, len));
        }
        for (int i = 0; i < m; ++i) {
            int len = min(m - i, n);
            ans = max(ans, count(nums1, nums2, 0, i, len));
        }
        return ans;
    }
};

62 | 最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/

动态规划, 注意子序列和子数组不同

子数组的dp[i][j]表示的是以i, j结尾的

子序列的dp[i][j]表示的是前i个, 前j个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    static const int N = 1005;
    int dp[N][N];
    int longestCommonSubsequence(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        // dp[i][j]表示s1前i个字符和s2前j个字符的最长公共子序列
        // state transition: --> dp[i][j] = max(max(dp[i - 1][j], dp[i - 1][j]), s1[i] == s2[j] ? dp[i - 1][j - 1] + 1, dp[i - 1][j - 1]);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (s1[i - 1] == s2[j - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        return dp[n][m];
    }
};

63 | 回文链表

https://leetcode-cn.com/problems/palindrome-linked-list/

  1. 快慢指针找中点
  2. 反转后面链表
  3. 挨个比对(以后面链表为边界, 前面长度可能会比后面多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
/**
 * 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:
    bool isPalindrome(ListNode* head) {
        // 找中点, 切断, 反向, 比对
        if (!head) return false;
        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* head2 = slow->next;
        slow->next = nullptr;
        // cout << head2->val << endl;
        auto reverse_list = [](ListNode* h) {
            ListNode* nex = nullptr, *prev = nullptr;
            while (h) {
                nex = h->next, h->next = prev, prev = h, h = nex;
            }
            return prev;
        };
        head2 = reverse_list(head2);
        while (head2) {
            if (head->val != head2->val) return false;
            head = head->next, head2 = head2->next;
        }
        return true;
    }
};

64 | 路经总和

https://leetcode-cn.com/problems/path-sum/

加强版为「47. 路经总和2」

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
/**
 * 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 flag = false;
    int tar;
    void dfs(TreeNode* root, int sum) {
        if (!root) return;
        sum += root->val;
        if (!root->left && !root->right) {
            if (sum == tar) {
                flag = true;
            }
            return;
        }
        dfs(root->left, sum), dfs(root->right, sum);
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        tar = targetSum;
        dfs(root, 0);
        return flag;
    }
};

65 | 多数元素

https://leetcode-cn.com/problems/majority-element/submissions/

摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 3;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};

66 | 验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/

中序遍历递归

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
/**
 * 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:
    // 首先二叉搜索树一个性质: 中序遍历就是递增序列
    // 保存中序遍历上一个元素, 比较每一个元素是否相同即可
    long long pre = LLONG_MIN;
    bool flag = true;
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        if (root->val <= pre) {
            flag = false;
            return;
        }
        pre = root->val;
        dfs(root->right);
    }
    bool isValidBST(TreeNode* root) {
        dfs(root);
        return flag;
    }
};

中序遍历迭代

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
/**
 * 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) {
        stack<TreeNode*> stk;
        long long pre = LLONG_MIN;
        while (root || stk.size()) {
            while (root) {
                stk.push(root); 
                root = root->left;
            }
            root = stk.top(); stk.pop();
            if (root->val <= pre) return false;
            pre = root->val;
            root = root->right;
        }
        return true;
    }
};

67 | 旋转图像

暴力的做法:

第一行 放到 最后一列

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> help(n, vector(n, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                help[j][n - 1 - i] = matrix[i][j];
            }
        }
        matrix = move(help);
    }
};

反转的做法:

  1. 上下翻转
  2. 沿主对角线翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 这题我记得以前有一个贼有趣的图
        // 就是把一个蛋黄派反转...
        // 3/2 = 1, 4/2 = 2
        int n = matrix.size();
        // 上下翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - 1 - i][j]);
            }
        }        
        // 对角线
        // 对于上三角m[i][j]关于主对角线对称是m[j][i]
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

68 | 对称二叉树

https://leetcode-cn.com/problems/symmetric-tree/submissions/

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 check(TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;
        if (a && !b || !a && b) return false;
        return (a->val == b->val && check(a->left, b->right) && check(a->right, b->left));
    }
    bool isSymmetric(TreeNode* root) {  
        return check(root, root);
    }
};

迭代写法

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
/**
 * 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 check(TreeNode* a, TreeNode* b) {
        queue<TreeNode*> q;
        q.push(a), q.push(b);
        while (q.size()) {
            auto u = q.front(); q.pop();
            auto v = q.front(); q.pop();
            if (!u && !v) continue;
            if (!u && v || !v && u) return false;
            if (u->val != v->val) return false;
            q.push(u->left), q.push(v->right);
            q.push(u->right), q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

69 | 子集

二进制枚举法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // 二进制枚举
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < (1 << n); ++i) {
            vector<int> now;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    now.push_back(nums[j]);
                }
            }
            ans.push_back(now);
        }
        return ans;
    }
};

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> cur;
    void dfs(vector<int>& nums, int now) {
        if (now == nums.size()) {
            ans.push_back(cur);
            return;
        }
        cur.push_back(nums[now]);
        dfs(nums, now + 1);
        cur.pop_back();
        dfs(nums, now + 1);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

70 | 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        TreeNode* tmp = root->left;
        root->left = root->right, root->right = tmp;
        invertTree(root->left), invertTree(root->right);
        return root;
    }
};

71 | 复原ip地址

回溯

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
class Solution {
public:
    vector<string> ans;
    vector<string> restoreIpAddresses(string s) {
        if (s.size() > 12) return {};
        dfs(s, "", 0);
        return ans;
    }

    void dfs(string& s, string cur, int start) {
        if (cur.size() == s.size() + 3) {
            if (start == s.size()) ans.push_back(cur);
            return;
        }
        string now = "";
        for (int i = start; i < min((int)s.size(), start + 3); ++i) {
            now += s[i];
            if (valid(now)) {
                dfs(s, cur.size() ? cur + "." + now : now, i + 1);
            }
        }
    }
    bool valid (string& x) {
        if (x.size() < 1 || x.size() > 3) return false;
        if (x.size() > 1 && x[0] == '0') return false;
        int num = stoi(x);
        return num >= 0 && num <= 255;
    };
};

72 | 零钱兑换

典型的完全背包问题 (物品可以选择无数次)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    // 硬币的体积 ==> 1
    // 硬币的价值 ==> coins[i]
    // 硬币可重复次数 ==> 无限次
    // 完全背包问题
    const int inf = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, inf); 
        dp[0] = 0;
        for (int i = 0; i <= amount; ++i) {
            for (auto j : coins) {
                if (i - j >= 0) {
                    dp[i] = min(dp[i], dp[i - j] + 1);
                }
            }
        }
        return dp[amount] == inf ? -1 : dp[amount];
    }
};

关于背包

  • 背包问题

关于初始化:

恰好装满 ==> dp[i] = inf

小于等于 ==> dp[i] = 0

0-1背包

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int f[1005];

int w[1005], v[1005];

int main () {
 int N, V;
 cin >> N >> V;
 for (int i = 0; i < N; ++i) {
     cin >> v[i] >> w[i];
 }
 for (int i = 0; i < N; ++i) {
     for (int j = V; j >= v[i]; --j) {
         f[j] = max(f[j], f[j - v[i]] + w[i]);
     }
 }
 cout << f[V] << endl;
 return 0;
}

完全背包和0-1背包相比仅仅是第二层循环的顺序改了

完全背包

有 N 件物品和一个容量是 V的背包。每种物品都有无限件可用。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int f[1005];

int v[1005], w[1005];

int main () {
 int N, V;
 cin >> N >> V;
 for (int i = 0; i < N; ++i) {
     cin >> v[i]  >> w[i];
 }
 for (int j = 0; j <= V; ++j) {
     for (int i = 0; i < N; ++i) {
         if (j - v[i] >= 0) {
             f[j] = max(f[j], f[j - v[i]] + w[i]);
         }
     }
 }
 cout << f[V] << endl;
 return 0;
}

多重背包

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int f[1005];

int s[1005], v[1005], w[1005];

int main () {
 int N, V;
 cin >> N >> V;
 for (int i = 0; i < N; ++i) {
     cin >> v[i] >> w[i] >> s[i]; 
 }
 for (int i = 0; i < N; ++i) {
     for (int j = V; j >= 0; --j) {
         for (int k = 1; k <= s[i] && k * v[i] <= j; ++k) {
             f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
         }
     }
 }
 cout << f[V] << endl;
 return 0;
}

多重背包+二进制优化

题目同上, 但是由于多重背包复杂度N V S, 当数量比较大时会超, 故采用二进制优化的方式将多重背包转化成01背包的问题

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
int f[N];

int main () {
 int nn, V;
 int v, w, s;
 cin >> nn >> V;
 vector<pair<int, int>> all;
 for (int i = 0; i < nn; ++i) {
     cin >> v >> w >> s;
     for (int k = 1; k <= s; k <<= 1) {
         s -= k;
         all.emplace_back(v * k, w * k);
     }
     if (s > 0) {
         all.emplace_back(v * s, w * s);
     }
 }
 for (auto& [v, w] : all) {
     for (int j = V; j - v >= 0; --j) {
         f[j] = max(f[j], f[j - v] + w);
     }   
 }
 cout << f[V] << endl;
 return 0;
}

混合背包

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

  • 第一类物品只能用1次（01背包）；
  • 第二类物品可以用无限次（完全背包）；
  • 第三类物品最多只能用 si次（多重背包）；

每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

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
#include<bits/stdc++.h>
using namespace std;

vector<tuple<int, int, int>> all; // t, v, w
int f[1005];

int main()
{
    int N, V;
    cin >> N >> V;
    for (int i = 0; i < N; ++i) {
        int v, w, t;
        cin >> v >> w >> t;
        if (t == -1) { // 01背包
            all.emplace_back(0, v, w);
        } else if (t == 0) { // 完全背包
            all.emplace_back(-1, v, w);
        } else { // 多重背包
            for (int k = 1; k <= t; k <<= 1) {
                t -= k;
                all.emplace_back(0, v * k, w * k);
            }
            if (t > 0) {
                all.emplace_back(0, v * t, w * t);
            }
        }
    }
    for (auto& [t, v, w] : all) {
        if (t == 0) {
            for (int i = V; i - v >= 0; --i) {
                f[i] = max(f[i], f[i - v] + w);
            }
        } else if (t == -1) {
            for (int i = v; i <= V; ++i) {
                f[i] = max(f[i], f[i - v] + w);
            }
        }
    }
    cout << f[V] << endl;
    return 0;
}

二维费用背包

就是把0-1背包的限制条件扩展到了二维, 思路是一致的

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。

输出最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int f[maxn][maxn];

int main () {
 int N, V, M;
 cin >> N >> V >> M;
 int v, m, w;
 for (int i = 0; i < N; ++i) {
     cin >> v >> m >> w;
     for (int i = V; i - v >= 0; --i) {
         for (int j = M; j - m >= 0; --j) {
             f[i][j] = max(f[i][j], f[i - v][j - m] + w);
         }
     }
 }
 cout << f[V][M];
 return 0;
}

分组背包问题

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

int f[105], v[105], w[105];

int main () {
 int N, V;
 cin >> N >> V;
 int s;
 while (N--) {
     cin >> s;
     for (int i = 0; i < s; ++i) {
         cin >> v[i] >> w[i];
     }
     for (int i = V; i >= 0; --i) {
         for (int j = 0; j < s; ++j) {
             if (i - v[j] >= 0)
                 f[i] = max(f[i], f[i - v[j]] + w[j]);
         }
     }
 }
 cout << f[V] << endl;
 return 0;
}

73 | 在排序数组中查找元素的第一个和最后一个位置

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 二分
        // 实质是: lower_bound - 1 - lower_bound
        // 自己实现一个
        int n = nums.size();
        int l = 0, r = n;
        // 实现upper_bound
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int up = r;
        l = 0, r = n;
        // 实现lower_bound
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int lo = r;
        if (up > lo) return {lo, up - 1};
        else return {-1, -1}; 
    }
};

74 | 删除排序链表中的重复元素

是「56 | 删除链表中的重复元素2」的简化版

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
/**
 * 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) {
        if (!head) return head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* now = dummy;
        while (now->next) {
            ListNode* p = now->next;
            if (p->next && p->val == p->next->val) {
                while (p->next && p->val == p->next->val) {
                    p = p->next;
                }
            }
            now->next = p;
            now = now->next;
        }
        return dummy->next;
    }
};

75 | 比较版本号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int compareVersion(string version1, string version2) {
        // 双指针比较
        int num1 = 0, num2 = 0;
        int n1 = version1.size(), n2 = version2.size();
        int p1 = 0, p2 = 0;
        while (p1 < n1 || p2 < n2) {
            int t1 = 0, t2 = 0; // 存这一段的结果
            while (p1 < n1 && version1[p1] != '.') {
                t1 = t1 * 10 + version1[p1++] - '0';
            }
            ++p1;
            while (p2 < n2 && version2[p2] != '.') {
                t2 = t2 * 10 + version2[p2++] - '0';
            }
            ++p2;
            if (t1 != t2) {
                return t1 < t2 ? -1 : 1;
            }
        }
        return 0;
    }
};

76 | 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // 只能dp了
        // 由于只从左边或者上面转移
        int n = grid.size(), m = grid[0].size();
        vector<int> dp(m, INT_MAX);
        dp[0] = grid[0][0];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i != 0) dp[j] += grid[i][j];
                if (j != 0) dp[j] = min(dp[j], dp[j - 1] + grid[i][j]);
            }
        }
        return dp[m - 1];
    }
};

77 | 只出现一次的数字

https://leetcode-cn.com/problems/single-number/

1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto& i : nums) ans ^= i;
        return ans;
    }
};

78 | 括号生成

https://leetcode-cn.com/problems/generate-parentheses/

二进制枚举, 无优化, 铁暴力

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
class Solution {
public:
    bool check (string s) {
        int cnt = 0;
        for (auto& i : s) {
            if (i == '(') ++cnt;
            if (i == ')') {
                if (cnt <= 0) return false;
                --cnt;
            }
        }
        return cnt == 0;
    }
    vector<string> generateParenthesis(int n) {
        // 二进制枚举, 检查序列是否可靠
        n <<= 1;
        vector<string> ans;
        for (int i = 0; i < (1 << n); ++i) {
            string now = "";
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    now += '(';
                } else {
                    now += ')';
                }
            }
            if (check(now)) ans.push_back(now);
        }
        return ans;
    }
};

回溯带优化

  1. 左 + 右 = n终止
  2. 右 > 左 break
  3. 左 = 右 放左
  4. 左 > 右 放左, 右

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> ans;
    vector<string> generateParenthesis(int n) {
        dfs("", n, 0, 0);
        return ans;
    }
    void dfs(string now, int n, int l, int r) {
        if (l + r == n * 2) {
            if (l == r)
                ans.push_back(now); 
            return;
        }
        if (r > l) return;
        if (r <= l) dfs(now + '(', n, l + 1, r);
        dfs(now + ')', n, l, r + 1);
    }
};

79 |寻找旋转排序数组中的最小值

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

这个二分不太正常，既没有左闭右开，右边界又没有收缩到n - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMin(vector<int>& nums) {
        // 一样使用二分
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[n - 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }   
        return nums[r]; 
    }
};

80 | 组合总和

https://leetcode-cn.com/problems/combination-sum/

一开始想的方法是枚举每个数被选取(1, 2, 3, … k)次, 直到sum + k * now >= target

但注意到这样会让now有很多份, 因为无法及时pop掉

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
class Solution {
public:
    vector<vector<int>> ans;
    void dfs (int idx, vector<int>& candidates, int target, vector<int> now, int sum) {
        if (sum == target) {
            ans.push_back(now);
            return;
        }
        if (idx >= candidates.size() || sum > target) return;
        // 枚举选0, 1, ...k次(k *)
        int k = 0;
        while (k * candidates[idx] + sum <= target) {
            if (k) now.push_back(candidates[idx]);
            dfs(idx + 1, candidates, target, now, sum + k * candidates[idx]);
            ++k;
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // dfs 枚举每一个数被选到他大于target
        vector<int> now;
        dfs(0, candidates, target, now, 0);
        return ans;
    }
};

考虑到可以直接不进行下标递增的选取, 在原地表示(跳过或者不跳过), 可以优化空间

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
class Solution {
public:
    vector<vector<int>> ans;
    void dfs (int idx, vector<int>& candidates, int target, vector<int>& now) {
        if (idx >= candidates.size()) return;
        if (target == 0) {
            ans.push_back(now);
            return;
        }
        // jump 
        dfs(idx + 1, candidates, target, now);
        // select
        if (target - candidates[idx] >= 0) {
            now.push_back(candidates[idx]);
            dfs(idx, candidates, target - candidates[idx], now);
            now.pop_back(); // 回溯
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> now;
        dfs(0, candidates, target, now);
        return ans;
    }
};

81 | 字符串相乘

https://leetcode-cn.com/problems/multiply-strings/

直接用数组保存, 然后对数组进行「竖式加法」

相当于模拟乘法竖式的时候将乘法时候的「进位」保留了, 最后相加时候一起进位

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
class Solution {
public:
    // 本方法: 
    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int n = num1.size(), m = num2.size();
        vector<int> c (n + m, 0);
        int carry = 0;
        // 模拟列竖式的过程 (不完全是)
        for (int i = 0; i < n; ++i) {
            int a = num1[i] - '0';
            for (int j = 0; j < m; ++j) {
                int b = num2[j] - '0';
                c[i + j] += a * b;
            }
        }
        for (int i = 0, t = 0; i < n + m; ++i) {
            t += c[i];
            c[i] = t % 10;
            t /= 10;
        }
        // 去除前面的0
        while (c.size() > 1 && c.back() == 0) c.pop_back();
        string ans;
        for (int i = c.size() - 1; i >= 0; --i) {
            ans += (c[i] + '0');
        }
        return ans;
    }
};

82 | 调整数组顺序使奇数位于偶数前面

https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        // 双指针
        int p1 = 0, p2 = nums.size() - 1;
        // 左边找到第一个偶数, 右边找到第一个奇数, 交换
        while (p1 < p2) {
            while (p1 < p2 && nums[p1] % 2 == 1) ++p1;
            while (p1 < p2 && nums[p2] % 2 == 0) --p2;
            if (p1 < p2)
                swap(nums[p1], nums[p2]);
        }
        return nums;
    }
};

83 | 二叉树的后序遍历

假的后序, 真的前序写法:

前序 中->右->左

翻转后成为左->右->中即为后序

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
/**
 * 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) {
        // 左->右->中为后序
        // 可以先 中->右->左, 然后结果reverse
        stack<TreeNode*> stk;
        vector<int> ans;
        while (root || stk.size()) {
            while (root) {
                ans.push_back(root->val);
                stk.push(root);
                root = root->right;
            }
            root = stk.top();
            stk.pop();
            root = root->left; 
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

真的后序写法(需要记录前一个结点, 防止重复访问右边)

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 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) {
        stack<TreeNode*> stk;
        vector<int> ans;
        TreeNode* prev = nullptr;
        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            // 没有右边或者就是从右边上来的
            if (!root->right || root->right == prev) {
                ans.push_back(root->val);
                prev = root;
                root = nullptr; // 不能再访问左节点了
            } else {
                stk.push(root); // 有右边则当前还得入栈, 因为先右再中
                root = root->right;
            }
        }
        return ans;
    }
};

84 | 对角线遍历

做这种题最重要的是:

  1. 找规律
  2. 充分讨论边界情况
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
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        // 真有你的
        /*
            找规律:

            注意左下(+1, -1)和右上移动(-1, +1)不会改变当前(行 + 列)的和, 即判断方式为行 + 列的和
            if (行 + 列)是偶数, 就是右上, 是奇数就是左下

            左下 = [1, -1]
            如果在最后一行 => 向右 [0, 1]  (先判断行, 防止在左下角的时候向下则越界)
            如果在第一列 => 向下 [1, 0]
            
            右上 = [-1, 1]
            如果在最后一列 => 向下 [1, 0]   (先判断列, 防止在右上角时候向右则越界)
            如果在第一行 => 向右 [0, 1]
        */
        vector<int> ans;
        int row = mat.size(), col = mat[0].size();
        int all = row * col; // 元素个数
        int x = 0, y = 0;
        for (int i = 0; i < all; ++i) {
            ans.push_back(mat[x][y]);
            // 右上
            if ((x + y) % 2 == 0) {
                if (y == col - 1) ++x; // 最后一列
                else if (x == 0) ++y; // 第一行
                else --x, ++y; // 正常右上
            } else {
                if (x == row - 1) ++y;
                else if (y == 0) ++x;
                else ++x, --y;
            }
        }
        return ans;
    }
};

85 | 斐波那契数列

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int fib(int n) {
        int a = 0, b = 1;
        int mod = (int) 1e9 + 7;
        if (n == 0) return a;
        if (n == 1) return b;
        int ans = 0;
        for (int i = 2; i <= n; ++i) {
            ans = a + b;
            ans %= mod;
            a = b, b = ans;
        }
        return ans;
    }
};

86 | 复制带随机指针的链表

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    unordered_map<Node*, Node*> mem; // 记录旧链表和新链表的对应关系
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        if (!mem.count(head)) {
            // 没有对应的就新建
            Node* new_node = new Node(head->val);
            mem[head] = new_node;
            new_node->next = copyRandomList(head->next);
            new_node->random = copyRandomList(head->random);
        }
        return mem[head];
    }
};

87 | 买卖股票的最佳时机2

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

由于不限交易次数, 我们将所有上升段统计即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // O(N)复杂度的dp
        // 发现一件事: 那就是第二天就卖永远不会亏
        // 我们跳过所有的下降段, 只收获上升段得到的值
        int ans = 0;
        for (int i = 1; i < prices.size(); ++i) {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

dp的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // dp的写法
        // dp[i][0] 表示 第i天没股票的最大收获
        // dp[i][1] 表示 第i天有股票的最大收获
        // 滚动数组优化
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.size() - 1][0];
    }
};

加上滚动数组优化的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // dp的写法
        // dp[i][0] 表示 第i天没股票的最大收获
        // dp[i][1] 表示 第i天有股票的最大收获
        // 滚动数组优化
        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i & 1][0] = max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]);
            dp[i & 1][1] = max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]);
        }
        return dp[(prices.size() - 1) & 1][0];
    }
};

88 | 数组中的逆序对

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

归并排序求逆序对

这题还有个树状数组的解法, 但是面试肯定不会问, 就不写了

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
class Solution {
public:

    int ans = 0;
    vector<int> aux;
    void count(vector<int>& nums, int l, int mid, int r) {
        int p1 = l, p2 = mid + 1;
        int k = p1;
        while (p1 <= mid && p2 <= r) {
            if (nums[p1] <= nums[p2]) { // 这里是小于等于, 不能搞成小于了!!
                aux[k++] = nums[p1++];
            } else {
                aux[k++] = nums[p2++];
                ans += (mid - p1 + 1);
            }
        }
        while (p1 <= mid) aux[k++] = nums[p1++]; //?
        while (p2 <= r) aux[k++] = nums[p2++];
        for (int i = l; i <= r; ++i) nums[i] = aux[i];
    }
    void merge_count(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        merge_count(nums, l, mid);
        merge_count(nums, mid + 1, r);
        count(nums, l, mid, r);
    }
    int reversePairs(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        aux.resize(nums.size());
        merge_count(nums, l, r);
        return ans;
    }
};

89 | 单词搜索

https://leetcode-cn.com/problems/word-search/

爆搜回溯

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
class Solution {
public:
    vector<int> dir = {-1, 0, 1, 0, -1};
    vector<vector<int>> vis;
    bool dfs(int x, int y, int k, string s, vector<vector<char>>& board) {
        if (board[x][y] != s[k]) return false;
        if (k == s.size() - 1) return true; // 找到了
        vis[x][y] = true;
        bool f = false;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dir[i], ny = y + dir[i + 1];
            if (nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size() || vis[nx][ny]) continue;
            f = dfs(nx, ny, k + 1, s, board); // 找到一个就可
            if (f) return true;
        }
        vis[x][y] = false; // 记得取消标记, 别的路还要搜呢
        return f; 
    }
    bool exist(vector<vector<char>>& board, string word) {
        // 典型的dfs
        // 找到所有前缀搜一遍就行了
        int n = board.size(), m = board[0].size();
        vis.resize(n, vector<int> (m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (board[i][j] == word[0]) {
                    vis.assign(n, vector<int> (m, 0));
                    if (dfs(i, j, 0, word, board)) return true;
                }
            }
        }
        return false;
    }
};

90 | 长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 滑动窗口
        int sum = 0;
        int ans = INT_MAX;
        for (int r = 0, l = 0; r < nums.size(); ++r) {
            sum += nums[r];
            while (sum >= target) {
                ans = min(ans, r - l + 1);
                sum -= nums[l++];
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

91 | 整数反转

https://leetcode-cn.com/problems/reverse-integer/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int reverse(int x) {
        // ans = ans * 10 + x % 10; x /= 10;
        // 如何判断ans是否溢出呢?
        // 知道x的第一位只有可能是1 / 2开头 (INT_MAX = 24xxx)
        // 故在判断最后一位的时候只需要 将 ans 和 INT_MAX / 10对比, 
        // ans * 10 + x > INT_MAX得条件是 (ans * 10 + x > (INT_MAX // 10) * 10 + 7)
        // 而 x < 7 (x <= 2)
        // 意思只需要ans * 10 > INT_MAX // 10即可
        int ans = 0;
        while (x) {
            if (ans < INT_MIN / 10 || ans > INT_MAX / 10) {
                return 0;
            }
            ans = ans * 10 + x % 10, x /= 10;
        }
        return ans;
    }
};

92 | 螺旋矩阵2

https://leetcode-cn.com/problems/spiral-matrix-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int top = 0, bottom = n - 1, left = 0, right = n - 1, now = 1;
        vector<vector<int>> g (n, vector<int>(n, 0));
        while (1) {
            for (int i = left; i <= right; ++i) g[top][i] = now++;
            if (++top > bottom) return g;
            for (int i = top; i <= bottom; ++i) g[i][right] = now++;
            if (--right < left) return g;
            for (int i = right; i >= left; --i) g[bottom][i] = now++;
            if (--bottom < top) return g;
            for (int i = bottom; i >= top; --i) g[i][left] = now++;
            if (++left > right) return g;
        }        
        return g;
    }
};

93 | 最长有效括号

https://leetcode-cn.com/problems/longest-valid-parentheses/

栈得做法, 很巧妙

栈中(底部)保存得是「最后一个失配的右括号的下标」, 栈其他保存的是各个未匹配的左括号的下标

一旦产生括号匹配就先将匹配的左括号弹出, 再更新ans

边界条件是stk.push(-1), 先将栈中压入-1, 保证每个右括号到来时都可以更新ans

当栈为空时, 表示出现了)), 这时候更新栈底失配右括号的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk; stk.push(-1);
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                stk.push(i);
            } else if (s[i] == ')') {
                stk.pop();
                if (!stk.empty()) {
                    ans = max(ans, i - stk.top());
                } else {
                    stk.push(i);
                }
            }
        }
        return ans;
    }
};

94 | 搜索二维矩阵2

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

将矩阵以右上角为根看成一颗二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 注意到以右上角开头的元素对应一个二叉搜索树
        // 这样就好办了
        int n = matrix.size(), m = matrix[0].size();
        int x = 0, y = m - 1;
        while (x >= 0 && x < n && y >= 0 && y < m) {
            if (matrix[x][y] == target) return true;
            // 搜索左子树
            if (matrix[x][y] > target) {
                --y;
            } else { // 搜索右子树
                ++x;
            }
        }
        return false;
    }
};

95 | 最大正方形

https://leetcode-cn.com/problems/maximal-square/

动态规划: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int dp[310][310];
    int maximalSquare(vector<vector<char>>& mat) {
        memset(dp, 0, sizeof dp);
        // 动态规划
        // dp[i][j] = k表示以i, j为左下角的最大正方形的边长为k
        // 状态转移: if (m[i][j] == '1') dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        int n = mat.size(), m = mat[0].size();
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (mat[i - 1][j - 1] == '1') {
                    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    ans = max(ans, dp[i][j] * dp[i][j]);
                }
            }
        }
        return ans;
    }
};

96 | 最长连续序列

https://leetcode-cn.com/problems/longest-consecutive-sequence/

记录就是桶排后中心扩展, 只是由于数据量大, 不能直接用数组模拟, 需要用哈希表

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
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 必然的动态规划
        // 要求时间没要求空间 
        // 居然也没要求顺序
        // 桶排的话数据量略大
        // 哈希吧
        int ans = 0;
        unordered_set<int> hmap;
        for (auto i : nums) {
            hmap.insert(i);
        }
        while (hmap.size()) {
            int now = *hmap.begin();
            hmap.erase(now);
            // 左右扩展?
            int next = now + 1, prev = now - 1;
            while (hmap.count(next)) {
                hmap.erase(next);
                next++;
            }
            while (hmap.count(prev)) {
                hmap.erase(prev);
                prev--;
            }
            ans = max(ans, next - prev - 1);
        }
        return ans;
    }
};

97 | 验证IP地址

https://leetcode-cn.com/problems/validate-ip-address/

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
class Solution {
public:
    // 将s分割成以spliter为分隔符的n份
    vector<string> split(string s, string spliter) {
        vector<string> ans;
        int it;
        int len =spliter.size();
        while ((it = s.find(spliter)) && it != s.npos) {
            ans.push_back(s.substr(0, it));
            s = s.substr(it + len);
        }    
        ans.push_back(s);
        return ans;
    }

    // 检查: 长度, 整数范围, 是否有其他字符
    bool check_ipv4 (string s) {
        vector<string> ss = split(s, ".");
        // 检查是否是4份
        if (ss.size() != 4) return false;
        for (string& str : ss) {
            if (str.empty() || str.size() > 3 || str.size() != 1 && str[0] == '0') return false;
            for (auto i : str) if (!isdigit(i)) return false;
            if (stoi(str) < 0 || stoi(str) > 255) return false;
        }
        return true;
    }

    // 这里的ipv6时不带简写的
    bool check_ipv6 (string s) {
        vector<string> ss = split(s, ":");
        // 检查是否是8份
        if (ss.size() != 8) return false;
        for (string& str : ss) {
            if (str.empty()) return false;
            // i是数字或者a ~ f A ~ F
            for (auto i : str) {
                if (! (isdigit(i) || (i >= 'a' && i <= 'f') || (i >= 'A' && i <= 'F'))) return false;
            }
            if (str.size() == 0 || str.size() > 4) return false;
        }
        return true;
    }

    string validIPAddress(string IP) {
        return check_ipv4(IP) ? "IPv4" : check_ipv6(IP) ? "IPv6" : "Neither"; 
    }
};

98 | 二叉树的完全性检验

二叉树(从1开始标记) 左边 2 x, 右边2 x + 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
/**
 * 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 isCompleteTree(TreeNode* root) {
        // 标记法 + 层序
        if (!root) return true;
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 1);
        int cnt = 1;
        while (q.size()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                auto [now, idx] = q.front(); q.pop();
                if (idx != cnt++) return false;
                if (now->left) q.emplace(now->left, idx * 2);
                if (now->right) q.emplace(now->right, idx * 2 + 1);
            }            
        }
        return true;
    }
};

99 | 二叉搜索树与完全链表

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    // 最后head指向第一个, prev指向最后一个
    Node* prev = nullptr, *head = nullptr;
    void dfs(Node* root) {
        if (!root) return;
        dfs(root->left);
        if (prev) prev->right = root;
        else head = root;
        root->left = prev;
        prev = root;
        dfs(root->right);
    }
    Node* treeToDoublyList(Node* root) {
        if (!root) return root;
        dfs(root);
        prev->right = head, head->left = prev;
        return head;
    }
};

100 | 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int dp[110];
    int uniquePaths(int m, int n) {
        // 递推
        dp[0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j) dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};