Code面试1

Updated: at 04:12 PM

🤠Code

1. 背过

1.1. 区间第K大

超时的双指针思路：

  1. 每次取区间rand的一个value，把比value大的数都放在value前面，这个可以通过双指针来实现（l指针把比value大的区域分开）
/**
* 超时版思路
*/
class Solution {
public:
    int findK(vector<int>& nums, int l, int r, int k) {
        int rd = l + rand() % (r - l + 1);
        int val = nums[rd];
        swap(nums[l], nums[rd]);
        int ll = l + 1;
        int rr = l + 1;
        // 双指针维护比val大的区域
        while(rr <= r) {
            if(nums[rr] > val) {
                swap(nums[ll], nums[rr]);
                ll++;
            }
            rr++;
        }
        // ll - 1的位置替换为val，并让当前位置与k比较
        swap(nums[ll - 1], nums[l]);
        int idx = ll - 1;
        if(idx == k) return val;
        else if(idx < k) return findK(nums, idx + 1, r, k);
        else{
            return findK(nums, l, idx - 1, k);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        return findK(nums, 0, nums.size() - 1, k - 1);
    }
};

小根堆思路：维护一个小根堆，固定长度为k，遍历元素，每次只有比堆顶元素大才会加入堆中，最后堆顶元素为第k大

/**
* 小根堆思路
*/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> queue;

        for(int &i : nums) {
            if(queue.size() < k) {
                queue.push(i);
            } else {
                if(i > queue.top()) {
                    queue.pop();
                    queue.push(i);
                }
            }
        }

        return queue.top();
    }
};

1.2. LRU Cache

思路：

  1. Map快速定位 + 双向链表头插法维护最近使用 + size维护当前和capacity的容量
  2. 写两个函数addToHead()和remove()，注意这两个函数要维护size和Map
  3. get()判断如果Map中有则remove() + addToHead()
  4. put()判断如果Map中没有则直接addToHead()，加入以后如果size大于capacity了则remove(tail->prev)。如果Map中没有则remove() + addToHead()
struct Node {
    Node* prev;
    Node* next;
    int key;
    int val;
    Node(int key, int val) : key(key), val(val){}
};

class LRUCache {
public:
    int capacity;
    int size;
    Node* head;
    Node* tail;
    unordered_map<int, Node*> map;

    LRUCache(int capacity) : capacity(capacity), size(0), head(new Node(-1, -1)), tail(new Node(-1, - 1)) {
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if(map.count(key)) {
            Node* node = map[key];
            remove(node);
            addToHead(node);
            return node->val;
        }else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if(!map.count(key)) {
            Node* node = new Node(key, value);
            addToHead(node);
            if(size > capacity) {
                remove(tail->prev);
            }
        } else {
            Node* node = map[key];
            node->val = value;
            remove(node);
            addToHead(node);
        }
        
    }

    void addToHead(Node* node) {
        Node* nn = head->next;
        nn->prev = node;
        node->next = nn;
        head->next = node;
        node->prev = head;
        map[node->key] = node;
        size++;
    }

    void remove(Node* node) {
        Node* nn = node->next;
        Node* pp = node->prev;
        pp->next = nn;
        nn->prev = pp;
        map.erase(node->key);
        size--;
    }
};

/**
 * 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.3. K个一组反转链表

思路：

  1. 先背一个反转链表
  2. [ pre [start end] nxt ]
  3. end是控制遍历的，每次循环k次向后移动都到end处
/**
 * 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) {
        // [ pre [start end] nxt ]
        ListNode* H = new ListNode(-1);
        H->next = head;
        ListNode* end = H;
        ListNode* pre = H;
        while(end->next) {
            for(int i = 0; i < k && end; ++i) {
                end = end->next;
            }
            if(!end) break;
            ListNode* start = pre->next;
            ListNode* nxt = end->next;
            end->next = nullptr;

            pre->next = reverse(start);
            start->next = nxt;

            end = start;
            pre = end;
        }
        return H->next;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* nextp = nullptr;
        while(cur) {
            nextp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nextp;
        }
        return prev;
    }
};

2. 常考算法法

2.1. 排序

2.1.1. 快速排序

思路：控制区间一个rand的val保证其在正确的位置（val前面的一定小于它，后面的一定大于它）

class Solution {
public:
    void Qsort(vector<int> &nums, int l, int r) {
        if(l >= r) return;
        int ll = l;
        int rr = r;
        int val = nums[l + rand() % (r - l + 1)];
        while(ll <= rr) {
            while(ll <= rr && nums[ll] < val) ll++;
            while(ll <= rr && nums[rr] > val) rr--;
            if(ll <= rr) swap(nums[ll++], nums[rr--]);
        }
        Qsort(nums, l, rr);
        Qsort(nums, ll, r);
    }

    vector<int> sortArray(vector<int>& nums) {
        Qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};

2.1.2. 堆排序

思路：

  1. insert()：插入的时候先插入数组最后面，然后逐个跟父节点比较并交换以得到它正确的位置
  2. pop()：弹出heap[0]（堆顶），即让heap数组最后一个替换heap[0]，然后对0位置开始调用heapify[0]
  3. heapify()：从该位置开始，比较左孩子和右孩子，如果比它大则交换，递归。
class Solution {
public:
    class MaxHeap {
        public:
            vector<int> heap;
            void insert(int val) {
                heap.push_back(val);
                int cur = heap.size() - 1;
                while(cur > 0 && heap[cur] > heap[(cur - 1) / 2]) {
                    swap(heap[cur], heap[(cur - 1) / 2]);
                    cur = (cur - 1) / 2;
                }
            }
            int pop() {
                int tmp = heap[0];
                heap[0] = heap.back();
                heap.pop_back(); // 居然有这个函数嘛？
                heapify(0);
                return tmp;
            }
            void heapify(int x) {
                int xl = x * 2 + 1;
                int xr = x * 2 + 2;
                int xx = x;
                if(xl < heap.size() && heap[xl] > heap[xx]) xx = xl;
                if(xr < heap.size() && heap[xr] > heap[xx]) xx = xr;
                if(xx != x) {
                    swap(heap[xx], heap[x]);
                    heapify(xx);
                }
            }
    }; 
    vector<int> sortArray(vector<int>& nums) {
        MaxHeap *mx = new MaxHeap();
        for(auto &x : nums) mx->insert(x);
        for(int i = 0; i < nums.size(); ++i) nums[i] = mx->pop();
        reverse(nums.begin(), nums.end());
        return nums;
    }
};

2.1.3. 归并排序

思路：mid，左边右边排好，然后归并

class Solution {
    void mergeSort(vector<int>& nums, int l, int r) {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int ll = l;
        int rr = mid + 1;
        int cur = l;
        while(ll < mid && rr < r) {
            if(nums[ll] < nums[rr]) st[cur++] = nums[ll++]; 
            else st[cur++] = nums[rr++];
            
        }
        while(ll < mid) st[cur++] = nums[ll++];
        while(rr < mid) st[cur++] = nums[rr++];
    }
public:
    vector<int> st;
    vector<int> sortArray(vector<int> nums) {
        st.resize((int)nums.size(), 0);
        mergeSort(nums, 0, nums.size() - 1);
        return st;
    }
};

3. 链表

3.1. 删除链表中的重复元素

3.1.1. 删除排序链表中的重复元素

用双指针会改变结构，双指针用在数组中会比较好

这题需要在循环中控制cur

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

3.1.2. 删除排序链表中的重复元素II

控制的还是cur，不管I还是II有一点很关键，如果不需要更改cur后面的，就让cur = cur->next。如果需要更改，下一轮还是cur

p是当前的，判断是判断q（p->next）是否是一段重复的开头，是的话全部去掉

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* p = dummy;
        while(p && p->next) {
            ListNode* q = p->next;
            while(q->next && q->next->val == q->val) q = q->next;
            if(p->next == q) p = p->next;
            else p->next = q->next; 
        }
        return dummy->next;
    }
};

3.2. 合并链表

3.2.1. 合并K个升序链表

优先队列维护每个链表的最小的，其他跟合并两个就是一样的了

/**
 * 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(int i = 0; i < lists.size(); ++i) {
            if(lists[i]) {
                q.push(make_pair(-lists[i]->val, lists[i]));
            }
        }
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(!q.empty()) {
            pair<int, ListNode*> pp = q.top();
            ListNode* node = pp.second;
            q.pop();
            cur->next = node;
            cur = cur->next;
            if(node->next) q.push(make_pair(-node->next->val ,node->next));
        }
        return dummy->next;
    }
};

3.2.2. 排序链表

需要注意两个点：什么情况下链表会出现无限递归导致的栈溢出，根据写的双指针移动来确定

这里我是把这种情况单独处理了

/**
 * 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 || !head->next) return head;
        ListNode* p1 = head, *p2 = head;
        if(!head->next->next) {
            p2 = head->next;
        } else {
            while(p2) {
                p2 = p2->next;
                if(!p2) break;
                p2 = p2->next; 
                p1 = p1->next;
            }
        }
        
        ListNode* head1 = p1->next;
        p1->next = nullptr;
        ListNode* h1 = sortList(head);
        ListNode* h2 = sortList(head1);

        ListNode* H = new ListNode(-1);
        ListNode* cur = H;
        while(h1 && h2) {
            if(h1->val < h2->val) {
                cur->next = h1;
                h1 = h1->next;
                cur = cur->next;
            } else {
                cur->next = h2;
                h2 = h2->next;
                cur = cur->next;
            }
        }

        while(h1) {
            cur->next = h1;
            h1 = h1->next;
            cur = cur->next;
        }

        while(h2) {
            cur->next = h2;
            h2 = h2->next;
            cur = cur->next;
        }

        return H->next;

    }
};

3.3. 🌈链表的反转/相交/重排

3.3.1. 反转链表

（迭代）背出来的

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr, *cur = head, *nxt = nullptr;
        while(cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

（递归）：

3.3.2. 🌟两个两两交换链表中的节点

背出来，易错在第一句 if(!head || !head->next)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* nxt = head->next;
        ListNode* nnxt = nxt->next;
        nxt->next = head;
        head->next = swapPairs(nnxt);
        return nxt;
    }
};

3.3.3. K个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

[ pre [start end] nxt ]

记得几个点：1. while(end->next) 2. 如果不够k个的特殊处理

/**
 * 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* reverse(ListNode* head) {
        ListNode* pre = nullptr, *cur = head, *nxt = nullptr;
        while(cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int sum = 0;
        ListNode* cur = head;
        while(cur) {
            cur = cur->next;
            sum++;
        }

        ListNode* H = new ListNode(-1);
        H->next = head;
        ListNode* end = H;
        ListNode* pre = H;
        while(end->next) {
            for(int i = 0; i < k && end; ++i) {
                end = end->next;
            }
            if(!end) break;
            ListNode* nxt = end->next;
            ListNode* start = pre->next;
            end->next = nullptr;

            ListNode* head1 = reverse(start);
            pre->next = head1;
            start->next = nxt;

            pre = end = start;
        }
        return H->next;
    }
};

3.4. 链表模拟

138. 随机链表的复制 - 力扣（LeetCode）

不需要虚拟头节点

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> hash;
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        Node* cur = head;
        while(cur) {
            Node* node = new Node(cur->val);
            hash[cur] = node;
            cur = cur->next;
        }
        cur = head;
        while(cur) {
            hash[cur]->next = hash[cur->next];
            hash[cur]->random = hash[cur->random];
            cur = cur->next;
        }
        return hash[head];
    }
};

4. 二叉树

4.1. 二叉树递归

4.1.1. 对称二叉树

process(root, root)

递归处理比较特殊，传入的是两个

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return process(root, root);
    }

    bool process(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2) return true;
        else if(root1 && root2) {
            if(root1->val != root2->val) return false;
            bool l = process(root1->left, root2->right);
            bool r = process(root1->right, root2->left);
            return l && r;
        } else return false;
    }
};

4.1.2. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return process(nums, 0, nums.size() - 1);
    }

    TreeNode* process(vector<int>& nums, int l, int r) {
        if(l > r) return nullptr;
        int m = l + (r - l) / 2;
        TreeNode* ll = process(nums, l, m - 1);
        TreeNode* rr = process(nums, m + 1, r);
        TreeNode* root = new TreeNode(nums[m]);
        root->left = ll;
        root->right = rr;
        return root;
    }
};

4.2. 二叉树的深度

4.2.1. 🌈二叉树的直径

边数 = 节点数 - 1

class Solution {
public:
    int ans;
    int func(TreeNode* node) {
        if(!node) return 0;
        int left = func(node->left);
        int right = func(node->right);
        int d = left + right;
        ans = max(ans, d);
        return max(left, right) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        func(root);
        return ans;
    }
};

4.3. 二叉树的层序遍历

4.3.1. 二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

/**
 * 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) {
        if(!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;
        while(!q.empty()) {
            int qsize = q.size();
            for(int i = 0 ; i < qsize; ++i) {
                auto n = q.front();
                if(i == qsize - 1) {
                    res.push_back(n->val);
                }
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
            }
        }
        return res;
    }
};

4.3.2. 二叉树的锯齿形层序遍历

相比于层序遍历，只是vector换成了deque，可以push_back也可以push_front，最后把deque转化为vector可以用vector(deque.begin(), deque.end());

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        int idx = 1;
        while(!q.empty()) {
            int size = q.size();
            deque<int> arr;
            for(int i = 0; i < size; ++i) {
                auto n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                if(idx % 2) arr.push_back(n->val);
                else arr.push_front(n->val);
            }
            ans.push_back(vector<int>(arr.begin(), arr.end()));
            idx++;
        }
        return ans; 
    }
};

4.4. 二叉搜索树

4.4.1. 二叉搜索树的第K小节点

二叉搜索树->中序遍历

如果找的是第K小只需要先右后左

class Solution {
public:
    int cnt;
    int ans;
    void dfs(TreeNode* root, int k) {
        if(root->left) dfs(root->left, k);
        if(cnt++ == k) ans = root->val;
        if(root->right) dfs(root->right, k);

    }
    int kthSmallest(TreeNode* root, int k) {
        cnt = 1;
        ans = -1;
        dfs(root, k);
        return ans;
    }
};

4.5. LCA

4.5.1. 二叉树的最近公共祖先

套路

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        else return left ? left : right;
    }
};

4.6. 二叉树模拟

4.6.1. 二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode）

记得先把root左节点保存下来就好了

class Solution {
public:
    TreeNode* cur;
    void flatten(TreeNode* root) {
        cur = new TreeNode(-1);
        dfs(root);  
    }

    void dfs(TreeNode* root) {
        if(!root) return;
        TreeNode* r = root->right;
        TreeNode* l = root->left;
        cur->right = root;
        root->left = nullptr;
        cur = root;
        dfs(l);
        dfs(r); 
    }
};

5. 二分

5.1. 旋转数组

5.1.1. 🌈搜索旋转排序数组

套路还是先找分界点。

用红蓝染色法需要注意的一点是r == n的特殊判断

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = -1;
        int r = n;
        while(l + 1 < r) {
            int mid = (l + r) >> 1;
            if(nums[mid] >= nums[0]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        
        int ll,rr;
        if(target >= nums[0]) {
            ll = -1;
            rr = r;
        } else {
            ll = l;
            rr = n;
        }
        if(r == n) {
            ll = -1;
            rr = n;
        }
        while(ll + 1 < rr) {
            int m = (ll + rr) >> 1;
            if(nums[m] < target) {
                ll = m;
            } else {
                rr = m;
            }
        }
        if(rr == n) return -1;
        return nums[rr] == target ? rr : -1;
    }
};

5.1.2. 寻找旋转排序数组中的最小值I-无重复元素

上一题的简化版，easy

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = -1;
        int r = n;
        while(l + 1 < r) {
            int mid = (l + r) >> 1;
            if(nums[mid] >= nums[0]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if(r == n) {
            return nums[0];
        } else {
            return nums[r];
        }
    }
};

5.1.3. 寻找旋转排序数组中的最小值II-有重复元素

首尾的重复元素会破坏二段性，中间的重复元素

所以只需要一开始把首位重复的元素去掉，就跟第一个题是一样的了

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = -1;
        int r = n - 1;
        while(r > 0 && nums[0] == nums[r]) r--;
        r++;
        n = r;
        while(l + 1 < r) {
            int mid = (l + r) >> 1;
            if(nums[mid] >= nums[0]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if(r == n) {
            return nums[0];
        } else {
            return nums[r];
        }
    }
};

5.2. 答案二分排除

5.3. 二分查找

6. 双指针

6.1. 范围指针（往里面缩单调趋势）

6.1.1. 🌈三数之和

注意去重，更要注意的是每个while都要有l < r

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 i = 0; i < n - 2; ++i) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1;
            int r = n - 1;
            while(l < r) {
                int target = nums[l] + nums[r] + nums[i];
                if(target > 0) {
                    r--;
                    while(l < r && nums[r] == nums[r + 1]) r--;
                } else if(target < 0) {
                    l++;
                    while(l < r && nums[l] == nums[l - 1]) l++;
                } else {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    r--;
                    while(l < r && nums[r] == nums[r + 1]) r--;
                    l++;
                    while(l < r && nums[l] == nums[l - 1]) l++;
                }
            }
        }
        return ans;
    }
};

6.2. 快慢指针类

6.2.1. 🌟移动零

l指针分割两个区域，r指针指向的满足l指针区域则交换

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l = 0;
        int r = 0;
        while(r < nums.size()) {
            if(nums[r] != 0) {
                swap(nums[l], nums[r]);
                l++;
            }
            r++;
        }
    }
};

6.3. 滑动窗口-窗口固定类

6.3.1. 🌟滑动窗口最大值

deque的API: front() back() push_back() push_front() pop_back() pop_front()

每一个新元素加进来就把它前面比它矮的都踢走

在这之前如果deque队首不在窗口中了(nums[i - k] == deque.front())，踢走

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res(n - k + 1, 0);
        deque<int> dq;
        for(int i = 0; i < k; ++i) {
            while(!dq.empty() && dq.back() < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
        }
        res[0] = dq.front();
        for(int i = k; i < n; ++i) {
            if(nums[i - k] == dq.front()) {
                dq.pop_front();
            }
            while(!dq.empty() && dq.back() < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
            res[i - k + 1] = dq.front();
        }
        return res;
    }
};

6.3.2. 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

easy

class Solution {
public:
    bool match(int* cnts, int* cntp) {
        for(int i = 0; i < 26; ++i) {
            if(cntp[i] != cnts[i]) return false;
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        if(s.length() < p.length()) return {};
        vector<int> ans;
        int cnts[26];
        int cntp[26];

        for(int i = 0 ; i < p.length(); ++i) cntp[p[i] - 'a']++;
        int j = 0;
        for(j = 0; j < p.length(); ++j) cnts[s[j] - 'a']++;

        if(match(cnts, cntp)) ans.push_back(0);
        int l = 0;
        for(; j < s.length(); ++j) {
            cnts[s[j] - 'a']++;
            cnts[s[l++] - 'a']--;
            if(match(cnts, cntp)) ans.push_back(l);
        }
        return ans;
    }
};

6.4. 滑动窗口-窗口不固定类

6.4.1. 无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {
public:
    unordered_map<char, int> map;
    int ans;
    int lengthOfLongestSubstring(string s) {
        int l = 0;
        for(int i = 0; i < s.length(); ++i) {
            char c = s[i];
            map[c]++;
            while(map[c] > 1) map[s[l++]]--;
            ans = max(ans, i - l + 1);
        }
        return ans;
    }
};

6.4.2. 最小覆盖子串

LCR 017. 最小覆盖子串 - 力扣（LeetCode）

小技巧，在不满足的时候cnt++，直到cnt = t的长度说明覆盖了

while l右移的时候保持仍保持覆盖条件

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> cnts, cntt;
        string ans;
        for(int i = 0; i < t.length(); ++i) cntt[t[i]]++;

        int l = 0;
        int cnt = 0;
        for(int i = 0; i < s.length(); ++i) {
            cnts[s[i]]++;
            if(cnts[s[i]] <= cntt[s[i]]) cnt++;

            while(cnts[s[l]] > cntt[s[l]]) cnts[s[l++]]--;
            if(cnts[s[i]] >= cntt[s[i]] && cnt == t.length()) {
                if(ans.empty() || ans.length() > i - l + 1) {
                    ans = s.substr(l, i - l + 1);
                }
            }    
        } 
        return ans;
    }
};

7. 数据结构-栈/单调栈

7.1. 单调栈

7.1.1. 🌈柱状图中的最大矩形

注意前后补零化简

注意别忘了往栈里加元素

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxS = 0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> st;
        
        for(int i = 0; i < heights.size(); ++i) {
            while(!st.empty() && heights[st.top()] > heights[i]) {
                int pp = st.top();
                st.pop();
                maxS = max(maxS, (i - st.top() - 1) * heights[pp]);
            }
            st.push(i);
        }

        return maxS;
    }
};

7.1.2. 接雨水

与上一个题的边界的区别

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int ans = 0;
        for(int i = 0; i < height.size(); ++i) {
            while(!st.empty() && height[st.top()] <= height[i]) {
                int t = st.top();
                st.pop();
                if(st.empty()) break;
                ans += (i - st.top() - 1) * (min(height[i], height[st.top()]) - height[t]);
            }
            st.push(i);
        }
        return ans;
    }
};

7.2. 栈模拟

7.2.1. 有效的括号

20. 有效的括号 - 力扣（LeetCode）

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int n = s.length();
        for(int i = 0; i < n; i++) {
            char c = s[i];
            switch(c) {
                case ')': {
                    if(st.empty() || !(st.top() == '(')) return false;
                    st.pop();
                    break;
                }
                case '}': {
                    if(st.empty() || !(st.top() == '{')) return false;
                    st.pop();
                    break;
                }
                case ']': {
                    if(st.empty() || !(st.top() == '[')) return false;
                    st.pop();
                    break;
                }
                default: {
                    st.push(c);
                }
            }

        }
        return st.empty();
    }
};

7.2.2. 字符串解码

394. 字符串解码 - 力扣（LeetCode）

倒着遍历

class Solution {
public:
    string decodeString(string s) {
        stack<string> st;
        int n = s.length();
        for(int i = n - 1; i > -1; ) {
            if(s[i] == '[') {
                string ss = "";
                while(!st.empty()) {
                    string c = st.top();
                    if(c == "]") break;
                    st.pop();
                    ss += c;
                }
                st.pop();
                i--;

                int cnt = 1;
                int num = 0;
                while(i > -1 && s[i] >= '0' && s[i] <= '9') {
                    num += (s[i] - '0') * cnt;
                    cnt *= 10;
                    i--;
                }
                string sss = "";
                for(int j = 0; j < num; ++j) {
                    sss += ss;
                }
                st.push(sss);
            } else {
                st.push(string(1, s[i]));
                i--;
            }
        }
        string res = "";
        while(!st.empty()) {
            res += st.top();
            st.pop();
        }
        return res;
    }
};

7.3. 栈维护性质

7.3.1. 最小栈

最小值的栈记得先push进去一个INT_MAX

class MinStack {
public:
    stack<int> minst;
    stack<int> curst;
    MinStack() {
        minst.push(INT_MAX);
    }
    
    void push(int val) {
        minst.push(min(val, minst.top()));
        curst.push(val);
    }
    
    void pop() {
        if(!curst.empty()) {
            curst.pop();
            minst.pop();
        }
    }
    
    int top() {
        return curst.top();
    }
    
    int getMin() {
        return minst.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();
 */

8. 数据结构-堆

8.1. 堆维护第K

8.1.1. 前K个高频元素

参考第K大元素，只不过用pair多了一个频率

class Solution {
public:
    unordered_map<int, int> map;
    priority_queue<pair<int, int>> q;
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(int i = 0; i < nums.size(); ++i) {
            map[nums[i]]++;
        }
        for(auto& p : map) {
            if(q.size() < k) {
                q.push(make_pair(-p.second, p.first));
            } else {
                if(q.top().first > -p.second) {
                    q.pop();
                    q.push(make_pair(-p.second, p.first));
                }
            }
        }
        vector<int> arr;
        while(!q.empty()) {
            arr.push_back(q.top().second);
            q.pop();
        }
       return arr;
    }

};

9. 动态规划

9.1. 一维dp

9.1.1. 🌈最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

dp[i]代表以i结尾的最长的递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ans = 1;

        for(int i = 1; i < nums.size(); ++i) {
            for(int j = 0; j < i; ++j) {
                if(nums[i] > nums[j]) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            ans = max(ans, dp[i]);
        }

        return ans;

    }
};

9.1.2. 打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

不要用二维

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        if(n == 1) return dp[0];
        dp[1] = max(nums[0], nums[1]);
        if(n == 2) return dp[1];
        for(int i = 2; i < n; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); 
        }
        return max(dp[n - 1], dp[n - 2]);
    }
};

9.1.3. 单词拆分

139. 单词拆分 - 力扣（LeetCode）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for(int i = 1; i < n + 1; ++i) {
            for(string& str : wordDict) {
                int l = str.length();
                if(i >= l && s.substr(i - l, l) == str) {
                    dp[i] = dp[i] || dp[i - l];
                }
            }
        }    
        return dp[n];
    }
};

9.1.4. 乘积最大子数组

一个dp维护最小，一个dp维护最大

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> dpmax(n, 1);
        vector<int> dpmin(n, 1);
        dpmax[0] = dpmin[0] = nums[0];
        int ans = dpmax[0];
        for(int i = 1; i < n; ++i) {
            dpmax[i] = max(max(dpmax[i - 1] * nums[i], dpmin[i - 1] * nums[i]), nums[i]);
            dpmin[i] = min(min(dpmax[i - 1] * nums[i], dpmin[i - 1] * nums[i]), nums[i]);
            ans = max(ans, dpmax[i]);
        }
        return ans;
    }
};

9.2. 二维dp

9.2.1. 买卖股票最佳时机

遍历一遍，边更新当前最小值边更新结果（非dp）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxV = 0;
        int minV = 1e5;
        for(int i = 0; i < prices.size(); ++i) {
            maxV = max(maxV, prices[i] - minV);
            minV = min(minV, prices[i]);
        }
        return maxV;
    }
};

9.2.2. 买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

dp[i][1]表示持有第i天股票，dp[i][0]表示第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]);

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i = 1; i < n; ++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 max(dp[n - 1][0], dp[n - 1][1]);
    }
};

9.2.3. 杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

感觉也不算是dp

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        res.push_back({1});
        for(int i = 1; i < numRows; ++i) {
            vector<int> ans(i + 1, 0);
            ans[0] = 1;
            ans[i] = 1;
            for(int j = 1; j < i; ++j) {
                ans[j] = res[i - 1][j - 1] + res[i - 1][j];
            }
            res.push_back(ans);
        }
        return res;
    }
};

9.3. 两个字符串匹配

9.3.1. 🌈编辑距离

dp两个维度都是长度 + 1

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();

        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        dp[0][0] = 0;
        for(int i = 0; i < len1 + 1; i++) {
            for(int j = 0; j < len2 + 1; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0) dp[i][j] = dp[i][j - 1] + 1;
                else if(j == 0) dp[i][j] = dp[i - 1][j] + 1;
                else if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};

9.4. 区间DP

9.4.1. 最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

先枚举区间从小到大，注意从for l 2->n

注意区间往里转移的时候考虑区间不合法的情况

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int ans = 1;
        string res = string(1, s[0]);
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = 0; i < n; ++i) dp[i][i] = true;
        for(int l = 2; l <= n; ++l) {
            for(int i = 0; i <= n - l; ++i) {
                if(i + 1 > i + l - 2) dp[i][i + l - 1] = (s[i] == s[i + l - 1]) ? true : false;
                else dp[i][i + l - 1] = (s[i] == s[i + l - 1]) ? dp[i + 1][i + l - 2] : false;
                if(dp[i][i + l - 1]) {
                    if(l > ans) {
                        res = s.substr(i, l);
                        ans = l;
                    }
                }
            }
        }
        return res;
    }
};

9.5. 背包问题

按背包类型分类：

  1. 0/1背包问题：每个元素最多选取一次
  2. 完全背包问题：每个元素可以重复选择
  3. 组合背包问题：背包中的物品要考虑顺序
  4. 分组背包问题：不止一个背包，需要遍历每个背包

按背包问题分类：

  1. 最值问题：要求最大值/最小值
  2. 存在问题：是否存在满足某条件
  3. 组合问题：求所有满足某条件的排列组合

解题模板代码

下面是求最值问题的模板：

void resolve()
{
    vector<int> dp(bagWeight + 1, 0);
    for (int i = 0; i < weight.size(); i++)// 遍历物品
        for (int j = bagWeight; j >= weight[i]; j--)// 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //不取或者取第i个
}

背包类型分类解题模板

  1. 0/1背包：外循环nums，内循环target，target倒序且target>=nums[i]
  2. 完全背包：外循环nums，内循环target，target正序且target>=nums[i]
  3. 组合背包：外循环target，内循环nums，target正序且target>=nums[i]
  4. 分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

问题类型分类题解

  1. 最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
  2. 存在问题(bool)：dp[i]=dp[i]||dp[i-num];
  3. 组合问题：dp[i]+=dp[i-num];

9.5.1. 零钱兑换（完全背包最值问题）

322. 零钱兑换 - 力扣（LeetCode）

给定amount,求用任意数量不同面值的零钱换到amount所用的最少数量

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<long> dp(amount + 1, 1e7);
        long ans = 1e7;
        dp[0] = 0;
        for(int coin : coins) {
            for(int j = 0; j < amount + 1; ++j) {
                if(j >= coin) {
                    dp[j] = min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        return dp[amount] < 1e7 ? dp[amount] : -1;
    }
};

9.5.2. 零钱兑换II（完全背包不考虑顺序的组合问题）

518. 零钱兑换 II - 力扣（LeetCode）

任选硬币凑成指定金额,求组合总数

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<long> dp(amount + 1, 0);
        dp[0] = 1;
        for(int coin : coins) {
            for(int i = 0; i < amount + 1; ++i) {
                if(i >= coin) {
                    dp[i] += dp[i - coin];
                }
            }
        }
        return dp[amount];
    }
};

9.5.3. 完全平方数（完全背包的最值问题）

279. 完全平方数 - 力扣（LeetCode）

对于一个正整数n,找出若干个完全平方数使其和为n,返回完全平方数最少数量

class Solution {
public:
    int numSquares(int n) {
        long ans = 1e7;
        vector<long> dp(n + 1, 1e7);
        dp[0] = 0;
        for(int i = 1; i <= sqrt(n); ++i) {
            for(int j = 1; j < n + 1; ++j) {
                if(j >= i*i) dp[j] = min(dp[j], dp[j - i*i] + 1);
            }
        }
        return dp[n];
    }
};

9.5.4. 目标和

494. 目标和 - 力扣（LeetCode）

为了转化为一般01背包问题（选和不选）：让它只选正数

正数x，负数y

要满足x + y = sum, x - y = target

则x = (sum + target) / 2

转化为只选出正数的那些，01背包target = x

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if((sum + target) % 2 || abs(sum) < abs(target)) return 0;
        int s = (sum + target) >> 1;
        vector<int> dp(s + 1, 0);
        dp[0] = 1;
        for(int n : nums) {
            for(int i = s; i >= 0; --i) {
                if(i >= n) {
                    dp[i] += dp[i - n];
                }
            }
        }
        return dp[s];
    }
};

9.5.5. 分割等和子集

01背包只能外层for遍历物品

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 2) return false;
        sum /= 2;
        vector<bool> dp(sum + 1, false);
        dp[0] = true;
        for(int j = 0; j < nums.size(); ++j) {
            for(int i = sum; i > -1; --i) {
                if(i >= nums[j]) {
                    dp[i] = dp[i] || dp[i - nums[j]];
                }
            }
        }
        return dp[sum];
    }
};

10. 搜索

10.1. 组合/子集/排列

10.1.1. 🌈子集

抽象为树搜索的形状，可以想到每次都是在树的最底下（同一层叶子节点）统计答案

所以在idx == nums.size()统计答案

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(int idx, vector<int>& tmp, vector<int>& nums) {
        if(idx == nums.size()) {
            ans.push_back(tmp);
            return;
        }
        tmp.push_back(nums[idx]);
        dfs(idx + 1, tmp, nums);
        tmp.pop_back();
        dfs(idx + 1, tmp, nums);
    }

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

};

10.1.2. 子集II

子集II含有重复的元素

区分一下什么是在同一层去重，什么是在不同层去重

同一层去重的话先排序 nums[i] == nums[i - 1] 并且 vis[i - 1] == false

注意控制减枝尺度（出现重复元素那个分枝）

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(int idx, vector<bool>& vis, vector<int>& tmp, vector<int>& nums) {
        if(nums.size() == idx) {
            ans.push_back(tmp);
            return;
        }
        
        dfs(idx + 1, vis, tmp, nums);
        if(idx > 0 && nums[idx] == nums[idx - 1] && vis[idx - 1] == false) {
            return;
        }
        tmp.push_back(nums[idx]);
        vis[idx] = true;
        dfs(idx + 1, vis, tmp, nums);
        vis[idx] = false;
        tmp.pop_back();

    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> vis(nums.size(), false);
        vector<int> tmp;
        dfs(0, vis, tmp, nums);
        return ans;
    }
};

10.1.3. 🌈组合

在搜索树中表示的是通过idx来进行层序的（右伸树）

class Solution {
public:
    vector<vector<int>> ans;
    int nn;
    int kk;
    void dfs(int idx, int size, vector<int>& tmp) {
        if(size == kk) {
            ans.push_back(tmp);
            return;
        }
        for(int i = idx + 1; i < nn; ++i) {
            tmp.push_back(i + 1);
            dfs(i, size + 1, tmp);
            tmp.pop_back();
        }

    }
    vector<vector<int>> combine(int n, int k) {
        nn = n;
        kk = k;
        vector<int> tmp;
        dfs(-1, 0, tmp);
        return ans;
    }

};

10.1.4. 🌈全排列

每层节点数相同的搜索树

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& nums, vector<bool>& vis, vector<int>& tmp) {
        if(tmp.size() == nums.size()) {
            ans.push_back(tmp);
            return;
        }
        for(int i = 0; i < nums.size(); ++i) {
            if(!vis[i]) {
                vis[i] = true;
                tmp.push_back(nums[i]);
                dfs(nums, vis, tmp);
                tmp.pop_back();
                vis[i] = false;
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tmp;
        vector<bool> vis(nums.size(), 0);
        dfs(nums, vis, tmp);
        return ans;
    }
};

10.1.5. 全排列II

相比于全排列I只是加了同一层的去重

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& nums, vector<bool>& vis, vector<int>& tmp) {
        if(nums.size() == tmp.size()) {
            ans.push_back(tmp);
            return;
        }

        for(int i = 0; i < nums.size(); ++i) {
            if(i > 0 && nums[i] == nums[i - 1] && vis[i - 1] == false) {
                continue;
            }
            if(!vis[i]) {
                vis[i] = true;
                tmp.push_back(nums[i]);
                dfs(nums, vis, tmp);
                tmp.pop_back();
                vis[i] = false;
            }
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> tmp;
        vector<bool> vis(nums.size(), false);
        dfs(nums, vis, tmp);
        return ans;
    }
};

10.2. 图DFS/BFS

10.2.1. 岛屿数量 图DFS

200. 岛屿数量 - 力扣（LeetCode）

class Solution {
public:
    int coor[5] = {0, 1, 0, -1, 0};
    void dfs(int i, int j, vector<vector<char>>& grid, vector<vector<bool>>& vis) {
        vis[i][j] = true;
        for(int k = 0; k < 4; ++k) {
            int ii = i + coor[k];
            int jj = j + coor[k + 1];
            if(ii < 0 || ii >= grid.size() || jj < 0 || jj >= grid[0].size() || vis[ii][jj] || grid[ii][jj] == '0') continue;
            dfs(ii, jj, grid, vis);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> vis(grid.size(), vector<bool>(grid[0].size(), false));
        int cnt = 0;
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[0].size(); ++j) {
                if(!vis[i][j] && grid[i][j] == '1') {
                    dfs(i, j, grid, vis);
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

10.2.2. 单词搜索 图DFS

class Solution {
public:
    bool f = false;
    int coor[5] = {0, 1, 0, -1, 0};
    void dfs(vector<vector<char>>& board, string word, int i, int j, vector<vector<bool>>& vis, int idx) {
        if(idx == word.length()) {
            f = true;
            return;
        }

        for(int k = 0; k < 4; ++k) {
            int ii = i + coor[k];
            int jj = j + coor[k + 1];
            if(ii < 0 || ii >= board.size() || jj < 0 || jj >= board[0].size() || vis[ii][jj] || board[ii][jj] != word[idx]) continue;
            vis[ii][jj] = true;
            dfs(board, word, ii, jj, vis, idx + 1);
            vis[ii][jj] = false;
        }
        
    }

    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> vis(board.size(), vector<bool>(board[0].size(), false));
        for(int i = 0; i < board.size(); ++i) {
            for(int j = 0; j < board[0].size(); ++j) {
                if(board[i][j] == word[0]) {
                    vis[i][j] = true;
                    dfs(board, word, i, j, vis, 1);
                    vis[i][j] = false;
                }
            }
        }
        return f;
    }
};

10.2.3. 岛屿的最大面积 图DFS

这道题主要学到如何dfs存结果，用返回值

class Solution {
public:
    int coor[5] = {0, 1, 0, -1, 0}; 
    int dfs(vector<vector<int>>& grid, vector<vector<bool>> &vis, int i, int j) {
        int ans = 1;
        for(int k = 0; k < 4; ++k) {
            int ii = i + coor[k];
            int jj = j + coor[k + 1];
            if(ii < 0 || ii >= grid.size() || jj < 0 || jj >= grid[0].size() || vis[ii][jj] || grid[ii][jj] == 0) continue;
            vis[ii][jj] = true;
            ans += dfs(grid, vis, ii, jj);
        }
        return ans;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        vector<vector<bool>> vis(grid.size(), vector<bool>(grid[0].size(), false));
        for(int i = 0 ;i < grid.size(); ++i) {
            for(int j = 0;j < grid[0].size(); ++j) {
                if(vis[i][j] || grid[i][j] == 0) continue;
                vis[i][j] = true;
                ans = max(ans, dfs(grid, vis, i, j));
            }
        }
        return ans;
    }
};

10.2.4. 腐烂的橘子 图BFS

如何判断是否最后还有没有新鲜的：fresh变量—，是否最后减到0

cnt一开始初始化的是-1

如果fresh一开始就是0，直接return 0

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int coor[5] = {0, 1, 0, -1, 0};
        queue<pair<int, int>> q;
        int fresh = 0;
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[0].size(); ++j) {
                if(grid[i][j] == 2) {
                    q.push({i, j});
                } else if(grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        if(fresh == 0) return 0;
        int cnt = -1;
        while(!q.empty()) {
            int qsize = q.size();
            for(int k = 0; k < qsize; ++k) {
                auto pp = q.front();
                q.pop();

                int i = pp.first;
                int j = pp.second;
                for(int t = 0; t < 4; ++t) {
                    int ii = i + coor[t];
                    int jj = j + coor[t + 1];
                    if(ii < 0 || ii >= grid.size() || jj < 0 || jj >= grid[0].size() || grid[ii][jj] != 1) continue;
                    grid[ii][jj] = 2;
                    fresh--;
                    q.push({ii, jj});
                }
            } 
            cnt++;
        }
        return (fresh > 0) ? -1 : cnt;
    }
};

10.3. 图的存储

10.3.1. 课程表表

207. 课程表 - 力扣（LeetCode）

一个map记录指向某个节点入度的链表，一个cnt数组代表每个节点的入度

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> hash;
        vector<int> cnt(numCourses, 0);

        for(auto p : prerequisites) {
            hash[p[1]].push_back(p[0]);
            cnt[p[0]]++;
        }

        queue<int> q;
        for(int i = 0; i < numCourses; ++i) {
            if(cnt[i] == 0) {
                q.push(i);
            } 
        }

        while(!q.empty()) {
            int qsize = q.size();
            for(int i = 0; i < qsize; ++i) {
                auto p = q.front();
                q.pop();

                for(auto pp : hash[p]) {
                    if(--cnt[pp] == 0) {
                        q.push(pp);
                    }
                }
            }
        }

        bool f = true;
        for(int i = 0; i < numCourses; ++i) {
            if(cnt[i] != 0) f = false;
        }
        return f;
    }
};

11. 贪心

11.1. 贪心算法

11.1.1. 跳跃游戏

注意：if(ans < i) return false;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(ans < i) return false;
            ans = max(ans, i + nums[i]);
        }
        return ans >= nums.size() - 1;
    }
};

11.1.2. 跳跃游戏II

其实是dp

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(nums.size(), 1e4);

        dp[0] = 0;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; ++j) {
                if(j + nums[j] >= i) {
                    dp[i] = min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[n - 1];
    }
};

11.1.3. 划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

遍历的过程不断更新nextIdx即可

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.length();
        unordered_map<char, int> hash;
        for(int i = 0; i < n; ++i) {
            char c = s[i];
            hash[c] = i;
        }

        vector<int> ans;
        int len = 0;
        int nextIdx = 0;
        for(int i = 0 ; i < n; ++i) {
            nextIdx = max(nextIdx, hash[s[i]]);
            len++;
            if(i == nextIdx) {
                ans.push_back(len);
                len = 0;
            }
        }
        return ans;
    }
};

12. 模拟

12.1. 二维矩阵模拟

12.1.1. 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> col(m, false);
        vector<bool> row(n, false);

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(matrix[i][j] == 0) {
                    col[i] = true;
                    row[j] = true;
                }
            }
        }

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(col[i] || row[j]) matrix[i][j] = 0;
            }
        }
    }
};

12.1.2. 螺旋矩阵

上下左右边界限制

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int t = 0;
        int b = m - 1;
        int l = 0;
        int r = n - 1;
        vector<int> res;
        while(l <= r && t <= b) {
            for(int i = l; i <= r; ++i) {
                res.push_back(matrix[t][i]);
            }
            if(++t > b) break;
            for(int i = t; i <= b; ++i) {
                res.push_back(matrix[i][r]);
            }
            if(--r < l) break;
            for(int i = r; i >= l; --i) {
                res.push_back(matrix[b][i]);
            }
            if(--b < t) break;
            for(int i = b; i >= t; --i) {
                res.push_back(matrix[i][l]);
            }
            if(++l > r) break;
        }
        return res;
    }
};

12.1.3. 旋转图像

48. 旋转图像 - 力扣（LeetCode）

注意边界

第二个循环是for(int j = i; i + j < n - 1; ++j)

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n / 2; ++i) {
            for(int j = i; i + j < n - 1; ++j) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = t;
            }
        }
    }
};

12.1.4. 搜索二维矩阵II

240. 搜索二维矩阵 II - 力扣（LeetCode）

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        int i = m - 1;
        int j = 0;
        bool f = false;
        while(i > -1 && j < n) {
            if(matrix[i][j] > target) {
                i--;
            } else if(matrix[i][j] < target) {
                j++;
            } else {
                f = true;
                break;
            }
        }
        return f;
    }
};