Top 100

3. 无重复字符的最长子串 ¶

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
        }
        return maxStr;

    }
};

146. LRU缓存机制 ¶

基于LinkedHashMap实现：¶

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }

        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }

    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

基于Linked源码：¶

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    // 这个可不写
    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

25. K 个一组翻转链表 ¶

class Solution {
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head), prev = dummy;
        while (true) {
            // 检查剩余节点是否有k个，不足则返回
            ListNode last = prev;
            for (int i = 0; i < k; i++) {
                last = last.next;
                if (last == null) {
                    return dummy.next;
                }
            }

            // 翻转k个节点
            ListNode curr = prev.next, next;
            for (int i = 0; i < k - 1; i++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
        }
    }
}

206. 反转链表 ¶

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while(cur != nullptr) {
            ListNode* tmp = cur->next; // 暂存后继节点 cur.next
            cur->next = pre;           // 修改 next 引用指向
            pre = cur;                 // pre 暂存 cur
            cur = tmp;                 // cur 访问下一节点
        }
        return pre;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);           // 调用递归并返回
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre) {
        if (cur == nullptr) return pre;        // 终止条件
        ListNode* res = recur(cur->next, cur); // 递归后继节点
        cur->next = pre;                       // 修改节点引用指向
        return res;                            // 返回反转链表的头节点
    }
};

215. 数组中的第K个最大元素 ¶

¶

官方堆结构¶

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = 
            new PriorityQueue<Integer>((n1,n2)->n1-n2);
        for(int n : nums){
            heap.add(n);
        }
        while (heap.size() > k){
            heap.poll();
        }
        return heap.poll();
    }
}

自写堆结构¶

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

快排求K大元素：先升序排序求倒数第K¶

class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)
            return quickselect(nums, l, j, k);
        else 
            return quickselect(nums, j + 1, r, k);
    }

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

15. 三数之和 ¶

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 排序 将相同数据放在一起
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
            // i不为0并且i和前面i相同
            if (i && nums[i] == nums[i - 1]) {
                continue;
            }
            // 初始三指针
            int j = i + 1, k = n - 1;
            while (j < k) {
                // 计算x数值
                int x = nums[i] + nums[j] + nums[k];
                if (x < 0) {
                    // 说明过小 增加j的值
                    ++j;
                } else if (x > 0) {
                    // 说明过大 减少k的值
                    --k;
                } else {
                    // 说明符合要求
                    ans.push_back({nums[i], nums[j++], nums[k--]});
                    // 调整j和k的范围 消除重复数据
                    while (j < k && nums[j] == nums[j - 1]) {
                        ++j;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        --k;
                    }
                }
            }
        }
        return ans;
    }
};

103. 二叉树的锯齿形层次遍历 ¶

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
        if (root == nullptr) return {};
        vector<vector<int>> ans;
        queue<TreeNode *> q;
        q.push(root);
        for (bool even = false; !q.empty(); even = !even) {
            vector<int> vals;
            for (int n = q.size(); n--;) {
                auto node = q.front(); q.pop();
                vals.push_back(node->val);
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (even) reverse(vals.begin(), vals.end());
            ans.emplace_back(vals);
        }
        return ans;
    }
};

121. 买卖股票的最佳时机 ¶

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

200. 岛屿数量 ¶

class Solution {
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();

        // 将当前点设置为0
        grid[r][c] = '0';
        // dfs将该点周边点设置为0
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};

33. 搜索旋转排序数组 ¶

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                // left 到 mid 是顺序区间
                (target >= nums[left] && target < nums[mid]) ? right = mid - 1 : left = mid + 1;
            }
            else {
                // mid 到 right 是顺序区间
                (target > nums[mid] && target <= nums[right]) ? left = mid + 1 : right = mid - 1;
            }
        }
        return -1;
    }
};

160. 相交链表 ¶

/**
 * 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) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode * pA = headA, *pB = headB;
        // 消除长度差 从相同的地方开始 
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA -> next;
            pB = pB == nullptr ? headA : pB -> next;
        }
        return pA;
    }
};

1. 两数之和 ¶

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for (int i = 0; i <= nums.size(); i++) {
            if (mp.count(target - nums[i]) != 0) {
                return {i, mp[target - nums[i]]};
            }
            mp[nums[i]] = i;
        }
        return {};
    }
};

54. 螺旋矩阵 ¶

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector <int> ans;
        if(matrix.empty()) return ans; //若数组为空，直接返回答案
        int u = 0; //赋值上下左右边界
        int d = matrix.size() - 1;
        int l = 0;
        int r = matrix[0].size() - 1;
        while(true)
        {
            for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
            if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
            for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
            if(-- r < l) break; //重新设定有边界
            for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
            if(-- d < u) break; //重新设定下边界
            for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
            if(++ l > r) break; //重新设定左边界
        }
        return ans;
    }
};

42. 接雨水 ¶

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            // 构建单调递减栈
            while (!st.empty() && height[i] > height[st.top()]) {
                int mid = st.top();
                st.pop();
                if (!st.empty()) {
                    int h = min(height[st.top()], height[i]) - height[mid];
                    int w = i - st.top() - 1;
                    sum += h * w;
                }
            }
            st.push(i);
        }
        return sum;
    }
};

5. 最长回文子串 ¶

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // dp[i][j]表示i到j是否是一个回文串，从中心扩散
        vector<vector<int>> dp(n, vector<int>(n));
        string ans;
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    // 如果长度为0 此时说明l=1，即长度为1
                    dp[i][j] = 1;
                } else if (l == 1) {
                    // 如果为2 判断i和j是否相同
                    dp[i][j] = (s[i] == s[j]);
                } else {
                    // i和j相同 并且里面一层的也是回文串
                    dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
                }
                // 如果满足 并且长度大于答案就更新答案
                if (dp[i][j] && l + 1 > ans.size()) {
                    ans = s.substr(i, l + 1);
                }
            }
        }
        return ans;
    }
};

236. 二叉树的最近公共祖先 ¶

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;
        if(root == p || root == q) 
            return root;

        // 找出左侧存在的点
        TreeNode* left =  lowestCommonAncestor(root->left, p, q);
        // 找出右侧存在的点
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 如果其中存在空，返回相反
        if (!left || !right) {
            return left == NULL ? right : left;
        }
        // 不为空说明 当前p和q在两侧
        if(left && right) // p和q在两侧
            return root;

        return NULL; // 必须有返回值
    }
};

53. 最大子序和 ¶

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};

46. 全排列 ¶

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

31. 下一个排列 ¶

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2, j = nums.size() - 1;
        while(i >= 0 && nums[i] >= nums[i+1])   --i;    //寻找比后面那个数小的nums[i]
        if(i >= 0) {
            while(j >= 0 && nums[j] <= nums[i]) --j;    //寻找比nums[i]大的第一个数
            swap(nums[i], nums[j]);
        }
        sort(nums.begin() + i + 1, nums.end());     //如果不存在下一个排列，i为-1
    }
};

23. 合并K个排序链表 ¶

class Solution {
public:
    // 合并两个有序结点
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        // 判空
        if ((!a) || (!b)) return a ? a : b;
        // 头结点，尾部
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr;
                aPtr = aPtr->next;
            } else {
                tail->next = bPtr;
                bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        // 把剩下合在一起
        tail->next = (aPtr ? aPtr : bPtr);
        // 返回head的next
        return head.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

300. 最长上升子序列 ¶

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        // dp[i]表示以i结尾的上升子序列
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            // 自己为1
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                // j < i才做判断
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        // 获得0-n - 1中最大的
        return *max_element(dp.begin(), dp.end());
    }
};

199. 二叉树的右视图 ¶

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> rightmostValueAtDepth;
        int max_depth = -1;

        queue<TreeNode*> nodeQueue;
        queue<int> depthQueue;
        nodeQueue.push(root);
        depthQueue.push(0);

        while (!nodeQueue.empty()) {
            TreeNode* node = nodeQueue.front();nodeQueue.pop();
            int depth = depthQueue.front();depthQueue.pop();

            if (node != NULL) {
                // 维护二叉树的最大深度
                max_depth = max(max_depth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth[depth] = node -> val;

                nodeQueue.push(node -> left);
                nodeQueue.push(node -> right);
                depthQueue.push(depth + 1);
                depthQueue.push(depth + 1);
            }
        }

        vector<int> rightView;
        for (int depth = 0; depth <= max_depth; ++depth) {
            rightView.push_back(rightmostValueAtDepth[depth]);
        }

        return rightView;
    }
};

143. 重排链表 ¶

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr) {
            return;
        }
        ListNode* mid = middleNode(head);
        ListNode* l1 = head;
        ListNode* l2 = mid->next;
        mid->next = nullptr;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    // 中间值
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;

            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    // 合并链表
    void mergeList(ListNode* l1, ListNode* l2) {
        ListNode* l1_tmp;
        ListNode* l2_tmp;
        while (l1 != nullptr && l2 != nullptr) {
            l1_tmp = l1->next;
            l2_tmp = l2->next;

            l1->next = l2;
            l1 = l1_tmp;

            l2->next = l1;
            l2 = l2_tmp;
        }
    }
};

102. 二叉树的层序遍历 ¶

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) {
            return ans;
        }
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int len = que.size();
            vector<int> tmp;
            for (int i = 0; i < len; i++) {
                auto x = que.front(); que.pop();
                tmp.emplace_back(x -> val);
                if (x -> left) que.push(x -> left);
                if (x -> right) que.push(x -> right);
            }
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

20. 有效的括号 ¶

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (auto c: s) {
            // 只判断右括号
            if (c == ')' || c == '}' || c == ']') {
                if (stk.size() == 0) return false;
                char top = stk.top();
                // 当前如果还有未匹配的括号说明有未识别错误
                if (top == ')' || top == '}' || top == ']') return false;

                // 判断是否合法
                switch (c) {
                    case ')':
                        if (top != '(') return false;
                        break;
                    case '}':
                        if (top != '{') return false;
                        break;
                    case ']':
                        if (top != '[') return false;
                        break;
                }
                // 弹出栈尾
                stk.pop();
            } else {
                stk.push(c);
            }
        }
        return stk.empty();
    }
};

88. 合并两个有序数组 ¶

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
         int idx = m + n - 1;
         int i = m - 1, j = n - 1;
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j >= 0) {
                if (nums1[i] > nums2[j]) {
                    nums1[idx--] = nums1[i];
                    i--;
                } else {
                    nums1[idx--] = nums2[j];
                    j--;
                }
            } else {
                // 处理剩余元素
                if (i == -1) {
                    nums1[idx--] = nums2[j];
                    j--;
                }else {
                    nums1[idx--] = nums1[i];
                    i--;
                }
            }

        }
    }
};

21. 合并两个有序链表 ¶

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }

        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
};

41. 缺失的第一个正数 ¶

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) { // 因为可能不止一次操作，所以此处不用 if ，而改用while
                check(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return nums.length + 1;
    }

    public void check(int[] nums, int index1, int index2) {
        // 互换位置
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

141. 环形链表 ¶

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != nullptr) {
            fast = fast->next;
            if(fast != nullptr) {
                fast = fast->next;
            }
            if(fast == slow) {
                return true;
            }
            slow = slow->next;
        }
        return false;
    }
};

415. 字符串相加 ¶

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;
            ans.push_back('0' + result % 10);
            add = result / 10;
            i -= 1;
            j -= 1;
        }
        // 计算完以后的答案需要翻转过来
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

124. 二叉树中的最大路径和 ¶

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        maxSum = max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

92. 反转链表 II ¶

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        // 穿针引线
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }
};

221. 最大正方形 ¶

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        int maxSide = 0;
        int rows = matrix.size(), columns = matrix[0].size();
        // dp[i][j]表示以i,j点的全是1的正方形边长
        vector<vector<int>> dp(rows, vector<int>(columns));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        // 处于边界
                        dp[i][j] = 1;
                    } else {
                        // 非边界 木桶效应 取短板
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    // 更新答案
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
};

56. 合并区间 ¶

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        for (int i = 0; i < n; i++) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            while(i + 1 < n && right >= intervals[i + 1][0]) {
                right = max(right, intervals[i + 1][1]);
                i++;
            }
            ans.push_back({left, right});
        }
        return ans;
    }
};

148. 排序链表 ¶

/**
 * 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) {}
 * };
 */
 bool cmp(ListNode* a, ListNode* b) {
        return a -> val < b -> val;
}
class Solution {
public:

    ListNode* sortList(ListNode* head) {
        vector<ListNode*> tmp;
        ListNode* dummy = head;
        if (head == nullptr) {
            return head;
        }
        while (dummy != nullptr) {
            tmp.push_back(dummy);
            dummy = dummy -> next;
        }
        sort(tmp.begin(), tmp.end(), cmp);
        for (int i = 0; i < tmp.size(); i++) {
            tmp[i] -> next = i + 1 == tmp.size() ? nullptr : tmp[i + 1];
        }
        return tmp[0];
    }
};

129. 求根到叶子节点数字之和 ¶

class Solution {
public:
    void dfs(TreeNode *root, int &ans, string cur) {
        if (root -> left == nullptr && root -> right == nullptr) {
            cur += to_string(root -> val);
            ans += atoi(cur.c_str());
            return;
        }
        cur += to_string(root -> val);
        if (root -> left) dfs(root -> left, ans, cur);
        if (root -> right) dfs(root -> right, ans, cur);
    }
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        dfs(root, ans, "");
        return ans;
    }
};

72. 编辑距离 ¶

class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp[i][j]表示 word1前i个字符 和 word2前j个字符中的最小编辑距离
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i < dp.size(); i++) {
            // i改到0删除i次
            dp[i][0] = i;
        }
        for (int j = 0; j < dp[0].size(); j++) {
            // 0到i增加j次
            dp[0][j] = j;
        }

        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].size(); j++) {
                // 三个值取最小+1
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (word1[i - 1] == word2[j - 1]) {
                    // 如果已经相等 说明可以不用更改取最小
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp.back().back();
    }
};

69. x 的平方根 ¶

袖珍计算器¶

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

二分查找¶

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

牛顿迭代¶

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};

101. 对称二叉树 ¶

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) {
            return true;
        }
        //调用递归函数，比较左节点，右节点
        return dfs(root.left,root.right);
    }

    boolean dfs(TreeNode left, TreeNode right) {
        //递归的终止条件是两个节点都为空
        //或者两个节点中有一个为空
        //或者两个节点的值不相等
        if(left==null && right==null) {
            return true;
        }
        if(left==null || right==null) {
            return false;
        }
        if(left.val!=right.val) {
            return false;
        }
        //再递归的比较 左节点的左孩子 和 右节点的右孩子
        //以及比较  左节点的右孩子 和 右节点的左孩子
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }
}

队列实现¶

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null || (root.left==null && root.right==null)) {
            return true;
        }
        //用队列保存节点
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点的左右孩子放到队列中
        queue.add(root.left);
        queue.add(root.right);
        while(queue.size()>0) {
            //从队列中取出两个节点，再比较这两个节点
            TreeNode left = queue.removeFirst();
            TreeNode right = queue.removeFirst();
            //如果两个节点都为空就继续循环，两者有一个为空就返回false
            if(left==null && right==null) {
                continue;
            }
            if(left==null || right==null) {
                return false;
            }
            if(left.val!=right.val) {
                return false;
            }
            //将左节点的左孩子， 右节点的右孩子放入队列
            queue.add(left.left);
            queue.add(right.right);
            //将左节点的右孩子，右节点的左孩子放入队列
            queue.add(left.right);
            queue.add(right.left);
        }

        return true;
    }
}

165. 比较版本号 ¶

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n = version1.length(), m = version2.length();
        int i = 0, j = 0;
        while (i < n || j < m) {
            long long x = 0;
            for (; i < n && version1[i] != '.'; ++i) {
                x = x * 10 + version1[i] - '0';
            }
            ++i; // 跳过点号
            long long y = 0;
            for (; j < m && version2[j] != '.'; ++j) {
                y = y * 10 + version2[j] - '0';
            }
            ++j; // 跳过点号
            if (x != y) {
                return x > y ? 1 : -1;
            }
        }
        return 0;
    }
};

补充题4. 手撕快速排序 ¶

普通版本

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

加了随机数版本

105. 从前序与中序遍历序列 ¶

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //保存inorder中节点值和索引之间的一一对应关系
        for (int i = 0; i < inorder.size(); ++i) {
            m_inorderIndex[inorder[i]] = i;
        }
        int preorder_start = 0, preorder_len = preorder.size();
        int inorder_start = 0, inorder_len = inorder.size();
        TreeNode* root = buildTree_help(preorder, inorder, preorder_start, preorder_len, inorder_start, inorder_len);
        return root;
    }

    TreeNode* buildTree_help(vector<int>& preorder, vector<int>& inorder, int preorder_start, int preorder_len, int inorder_start, int inorder_len) {
        //递归结束的条件
        if (preorder_len <= 0 || inorder_len <= 0) {
            return NULL;
        }
        TreeNode* node = new TreeNode(preorder[preorder_start]);
        int node_in_inorder = m_inorderIndex[preorder[preorder_start]];
        //递归生成左子树
        node->left = buildTree_help(preorder, inorder, preorder_start + 1, node_in_inorder - inorder_start, inorder_start, node_in_inorder - inorder_start);
        //递归生成右子树
        node->right = buildTree_help(preorder, inorder, preorder_start + 1 + node_in_inorder - inorder_start, inorder_len - node_in_inorder + inorder_start - 1, node_in_inorder + 1, inorder_len - node_in_inorder + inorder_start - 1);
        return node;
    }

private:
    unordered_map<int, int> m_inorderIndex;
};

22. 括号生成 ¶

class Solution {
    void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
        if (cur.size() == n * 2) {
            ans.push_back(cur);
            return;
        }
        // 左括号小于n
        if (open < n) {
            cur.push_back('(');
            backtrack(ans, cur, open + 1, close, n);
            cur.pop_back();
        }
        // 右括号小于左括号
        if (close < open) {
            cur.push_back(')');
            backtrack(ans, cur, open, close + 1, n);
            cur.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
};

32. 最长有效括号 ¶

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    maxans = max(maxans, i - stk.top());
                }
            }
        }
        return maxans;
    }
};

93. 复原IP地址 ¶

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ret = new ArrayList<>();

        StringBuilder ip = new StringBuilder();

        for(int a = 1 ; a < 4 ; ++ a)
            for(int b = 1 ; b < 4 ; ++ b)
                for(int c = 1 ; c < 4 ; ++ c)
                    for(int d = 1 ; d < 4 ; ++ d)
                    {
                        if(a + b + c + d == s.length() )
                        {
                            int n1 = Integer.parseInt(s.substring(0, a));
                            int n2 = Integer.parseInt(s.substring(a, a+b));
                            int n3 = Integer.parseInt(s.substring(a+b, a+b+c));
                            int n4 = Integer.parseInt(s.substring(a+b+c));
                            if(n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255)
                            {
                                ip.append(n1).append('.').append(n2)
                                        .append('.').append(n3).append('.').append(n4);
                                if(ip.length() == s.length() + 3) ret.add(ip.toString());
                                ip.delete(0, ip.length());
                            }
                        }
                    }
        return ret;
    }
}

4. 寻找两个正序数组的中位 ¶

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        int n = len1 + len2;
        for (auto num : nums2) {
            nums1.push_back(num);
        }
        sort(nums1.begin(), nums1.end());
        if (n % 2 == 1) return nums1[n / 2];
        else {
            int mid = n / 2 - 1;
            double a = nums1[mid], b = nums1[mid + 1];
            return (a + b) / 2;
        }

    }
};

142. 环形链表 II ¶

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

112. 路径总和 ¶

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        targetSum -= root->val;
        if(!root->left && !root->right && !targetSum)
            return true;
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

76. 最小覆盖子串 ¶

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        // 记录t中字符
        for (auto c: t) ht[c] ++ ;
        string res;
        // cnt用于记录当前满足的字符数
        int cnt = 0;
        // 滑动窗口i，j
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            // 当前创建内的字符+1
            hs[s[i]] ++ ;
            // 如果增加完之后仍然满足则视为有效，否则在后续步骤内删除
            if (hs[s[i]] <= ht[s[i]]) cnt ++ ;
            // 不满足 则删除到满足
            while (hs[s[j]] > ht[s[j]]) hs[s[j ++ ]] -- ;
            if (cnt == t.size()) {
                // 等于则视为有效
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

232. 用栈实现队列 ¶

class MyQueue {
private:
    // B为存数的队列
    std::stack<int> A, B;

public:
    MyQueue() {}

    void push(int x) {
        A.push(x);
    }

    int pop() {
        int peek = this->peek();
        if (!B.empty()) {
            B.pop();
        }
        return peek;
    }

    int peek() {
        // 不为空则直接返回队列首部
        if (!B.empty()) return B.top();
        if (A.empty()) return -1;
        while (!A.empty()){
            B.push(A.top()), A.pop();
        }
        int res = B.top();
        return res;
    }

    bool empty() {
        return A.empty() && B.empty();
    }
};

39. 组合总和 ¶

class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

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

98. 验证二叉搜索树 ¶

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* dummy = new ListNode(0, head);

        ListNode* cur = dummy;
        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x) {
                    cur->next = cur->next->next;
                }
            }
            else {
                cur = cur->next;
            }
        }

        return dummy->next;
    }
};

2. 两数相加 ¶

class Solution {
public:
    // l1 和 l2 为当前遍历的节点，carry 为进位
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2, int carry = 0) {
        if (l1 == nullptr && l2 == nullptr) // 递归边界：l1 和 l2 都是空节点
            return carry ? new ListNode(carry) : nullptr; // 如果进位了，就额外创建一个节点
        if (l1 == nullptr) // 如果 l1 是空的，那么此时 l2 一定不是空节点
            swap(l1, l2); // 交换 l1 与 l2，保证 l1 非空，从而简化代码

        carry += l1->val + (l2 ? l2->val : 0); // 节点值和进位加在一起
        l1->val = carry % 10; // 每个节点保存一个数位
        l1->next = addTwoNumbers(l1->next, (l2 ? l2->next : nullptr), carry / 10); // 进位
        return l1;
    }
};

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        auto dummy = new ListNode(); // 哨兵节点
        auto cur = dummy;
        int carry = 0; // 进位
        while (l1 || l2 || carry) { // 有一个不是空节点，或者还有进位，就继续迭代
            carry += (l1 ? l1->val : 0) + (l2 ? l2->val : 0); // 节点值和进位加在一起

            cur = cur->next = new ListNode(carry % 10); // 每个节点保存一个数位
            carry /= 10; // 新的进位

            if (l1) l1 = l1->next; // 下一个节点
            if (l2) l2 = l2->next; // 下一个节点
        }
        return dummy->next; // 哨兵节点的下一个节点就是头节点
    }
};

94. 二叉树的中序遍历 ¶

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

322. 零钱兑换 ¶

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        // dp[i]表示组成i金额需要的最少硬币数
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    // 金额数值小于i才能计算
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        // 组成amount的金额超过amount则说明没有方案
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

78. 子集 ¶

class Solution {
public:
  vector<int>t;
  vector<vector<int>>ans;
  void dfs(int num,vector<int>nums){
      if(num==nums.size()){
          ans.push_back(t);
          return;
      }
      // 选
      t.push_back(nums[num]);
      dfs(num + 1, nums);
      t.pop_back();
      // 不选
      dfs(num + 1, nums);
  }
  vector<vector<int>> subsets(vector<int>& nums) {
       dfs(0,nums);
       return ans;
  }
};

19. 删除链表的倒数第N个节 ¶

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
     ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }

        while(q){
            p = p->next;
            q = q->next;
        }

        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;

        return retNode;

    }
};

394. 字符串解码 ¶

string decodeString(string s) {
    stack<int> counts;   // 用于保存重复次数的栈
    stack<string> strs;  // 用于保存当前处理的字符串的栈
    int num = 0;         // 用于累积读取完整数字
    string curr = "";    // 用于累积当前解码的字符串

    for (int i = 0; i < s.length(); i++) {
        if (isdigit(s[i])) {  
            // 当遇到数字时，继续读取整个数字
            num = num * 10 + (s[i] - '0');
        } else if (s[i] == '[') {
            // 当遇到左括号，表示一个新的编码字符串开始
            counts.push(num);    // 将累积的数字压栈
            strs.push(curr);     // 将当前字符串压栈
            num = 0;             // 重置数字和字符串，以便处理新的编码字符串
            curr = "";
        } else if (s[i] == ']') {
            // 当遇到右括号，表示当前编码字符串结束
            int count = counts.top();  // 获取当前编码字符串的重复次数
            counts.pop();
            string prev = strs.top();  // 获取之前的字符串部分
            strs.pop();
            for (int j = 0; j < count; j++) {
                prev += curr;  // 重复当前字符串指定次数并连接到之前的字符串部分
            }
            curr = prev;      // 更新当前字符串为解码后的结果
        } else {
            // 当遇到字母时，直接添加到当前字符串中
            curr += s[i];
        }
    }

    // 返回最终的解码结果
    return curr;
}

209. 长度最小的子数组 ¶

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

113. 路径总和 II ¶

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;

    void dfs(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return;
        }
        path.emplace_back(root->val);
        targetSum -= root->val;

        if (root->left == nullptr && root->right == nullptr && targetSum == 0) {
            ret.emplace_back(path);
        }
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }
};

122. 买卖股票的最佳时机 II ¶

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 0：持有现金
        // 1：持有股票
        // 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
}

补充题1. 排序奇升偶降链表 ¶

按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL
反转偶链表，得1->3->5->7->NULL和2->4->6->8->NULL
合并两个有序链表，得1->2->3->4->5->6->7->8->NULL

public class Solution {

    TreeNode* sortOddEvenList(TreeNode* root) {
        if (root || root -> next) {
            return root;
        }

    }
    // 按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL
    pair<TreeNode*, TreeNode*> partition(TreeNode* root) {
        TreeNode* evenHead = root -> next;
        TreeNode* odd = root, *even = evenHead;
        while (even && even -> next) {
            odd -> next = even -> next;
            odd = odd -> next;
            even -> next = odd -> next;
            even = even -> next;
        }
        odd.next = nullptr;
        return {head, evenHead};
    }
    // reverseList
    TreeNode* reverse(TreeNode *root) {
        TreeNode* dumpy = new ListNode(-1);
        TreeNode* p = root;
        while (p) {
            TreeNode* tmp = p -> next;
            p -> next = dumpy -> next;
            dumpy -> next = p;
            p = tmp;
        }
        return dumpy -> next;
    }
    // 合并两个有序链表
    TreeNode *merge(TreeNode *p, TreeNode *q) {
        auto head = new TreeNode(-1);
        auto r = head;
        while (p && q) {
            if (p -> val <= q.val) {
                r -> next = p;
                p = p -> next;
            } else {
                r -> next = q;
                q = q -> next;
            }
            r = r -> next;
        }
        return head -> next;
    }
}

662. 二叉树最大宽度 ¶

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long res = 1;
        vector<pair<TreeNode *, unsigned long long>> arr;
        arr.emplace_back(root, 1L);
        while (!arr.empty()) {
            vector<pair<TreeNode *, unsigned long long>> tmp;
            for (auto &[node, index] : arr) {
                if (node->left) {
                    tmp.emplace_back(node->left, index * 2);
                }
                if (node->right) {
                    tmp.emplace_back(node->right, index * 2 + 1);
                }
            }
            // 用每层最右边编号 减去最左边编号
            res = max(res, arr.back().second - arr[0].second + 1);
            // 将arr指向当前层
            arr = move(tmp);
        }
        return res;
    }
};

70. 爬楼梯 ¶

class Solution {
public:
    int climbStairs(int n) {
        // r 是上一部, p 是上两步，q是上一步
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

155. 最小栈 ¶

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }

    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }

    void pop() {
        x_stack.pop();
        min_stack.pop();
    }

    int top() {
        return x_stack.top();
    }

    int getMin() {
        return min_stack.top();
    }
};

1143. 最长公共子序列 ¶

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        // dp[i][j]表示前text1前i个字符，text2前j个字符的最长公共子序列
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = text1[i - 1];
            for (int j = 1; j <= n; j++) {
                char c2 = text2[j - 1];
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // i前面 或者j
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

239. 滑动窗口最大值 ¶

堆：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            // 不会被窗口扫描到的最大值下标可以丢弃
            while (q.top().second <= i - k) {
                q.pop();
            }
            // 取大根堆top
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

队列：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0 || k == 0) return {};
        deque<int> deque;
        vector<int> res(nums.size() - k + 1);
        // 未形成窗口
        for(int i = 0; i < k; i++) {
            while(!deque.empty() && deque.back() < nums[i])
                deque.pop_back();
            deque.push_back(nums[i]);
        }
        res[0] = deque.front();
        // 形成窗口后
        for(int i = k; i < nums.size(); i++) {
            // 队首是第一个元素的话说明在窗口向后移动加一之后永远不会再出现
            if(deque.front() == nums[i - k])
                deque.pop_front();
            // 保证降序排列
            while(!deque.empty() && deque.back() < nums[i])
                deque.pop_back();
            deque.push_back(nums[i]);
            res[i - k + 1] = deque.front();
        }
        return res;
    }
};

470. 用 Rand7() 实现 Rand10()¶

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int a = rand5(); 
        int b = rand2(); 
        return 2 * a + (b - 1);
    }
    int rand5() {
        int ans = rand7();
        while (ans > 5) {
            ans = rand7();
        }
        return ans;
    }
    int rand2() {
        int ans = rand7();
        while (ans == 7) ans = rand7();
        return ans % 2;
    }
};

int rand10() {
        return (rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7())%10+1;
    }

240. 搜索二维矩阵 II ¶

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

补充题2. 圆环回原点问题 ¶

若设dp[i][j]为从0点出发走i步到j点的方案数，则递推式为:

走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。

class Solution {
public:
    int back2zero(int n) {
        int len = 10;
        auto dp = vector<int>(len, vector<int>(n + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < len; j++) {
                // (j - 1 + len) % len表示左侧 dp[i - 1][(j + 1) % length()]表示右侧
                dp[i][j] = dp[i - 1][(j - 1 + len) % len] + dp[i - 1][(j + 1) % length()];
            }
        }
        // 走n步到0点
        return dp[n][0];
    }
};

543. 二叉树的直径 ¶

class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans - 1;
    }
};

695. 岛屿的最大面积 ¶

递归：

class Solution {
    int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
            return 0;
        }
        // 设置当前土地为0
        grid[cur_i][cur_j] = 0;
        int di[4] = {0, 0, 1, -1};
        int dj[4] = {1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
            // 向四个方向移动
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        return ans;
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                ans = max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }
};

dfs：

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                int cur = 0;
                stack<int> stacki;
                stack<int> stackj;
                stacki.push(i);
                stackj.push(j);
                while (!stacki.empty()) {
                    int cur_i = stacki.top(), cur_j = stackj.top();
                    stacki.pop();
                    stackj.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {0, 0, 1, -1};
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        stacki.push(next_i);
                        stackj.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

bfs:

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                int cur = 0;
                queue<int> queuei;
                queue<int> queuej;
                queuei.push(i);
                queuej.push(j);
                while (!queuei.empty()) {
                    int cur_i = queuei.front(), cur_j = queuej.front();
                    queuei.pop();
                    queuej.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {0, 0, 1, -1};
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        queuei.push(next_i);
                        queuej.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

440. 字典序的第K小数字 ¶

class Solution {
public:
    int getSteps(int curr, long n) {
        int steps = 0;
        long first = curr;
        long last = curr;
        while (first <= n) {
            steps += min(last, n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }

    int findKthNumber(int n, int k) {
        int curr = 1;
        // 减去当前头结点
        k--;
        while (k > 0) {
            // 获得当前curr下有几个节点
            int steps = getSteps(curr, n);
            // 如果小于k说明还在后边 将curr++
            if (steps <= k) {
                // 舍去当前节点下的所有值，目前还在cur层不用减一
                k -= steps;
                curr++;
            } else {
                // 大于k说明在cur的子节点下
                // cur移步到下一层
                curr = curr * 10;
                // k-把curr减去，因为移步到了下一层
                k--;
            }
        }
        return curr;
    }
};

48. 旋转图像 ¶

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 先按对角线翻转
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // 再按每行中心点反转
        int mid = n >> 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < mid; j++) {
                swap(matrix[i][j], matrix[i][n - j - 1]);
            }
        }
    }
};

剑指 Offer 22. 链表中倒数第k个结点 ¶

class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        ListNode* tmp = head;
        while (cnt--) {
            tmp = tmp -> next;
        }
        ListNode* target = head;
        while(tmp) {
            tmp = tmp -> next;
            target = target -> next;
        }
        return target;
    }
};

139. 单词拆分 ¶

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict) {
            wordDictSet.insert(word);
        }
        // dp[i] 表示s的前i个字符是否能满足
        auto dp = vector <bool> (s.size() + 1);
        // 0个字符为true
        dp[0] = true;
        // i表示字符串长度
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                // 当前j可以构成 判断i到j是否能构成 找到一个即可
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

64. 最小路径和 ¶

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (i == 0 && j == 0) continue;
                int tmp = grid[i][j];
                if (i == 0) {
                    // 只能由左移动
                    grid[i][j] = grid[i][j - 1];
                } else if (j == 0) {
                    // 从上面而来
                    grid[i][j] = grid[i - 1][j];
                } else {
                    // 可能从上或者左
                    grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]);
                }
                grid[i][j] += tmp;
            }
        }
        return grid[n - 1][m - 1];
    }
};

补充题23. 检测循环依赖 ¶

拓扑排序算法过程：

选择图中一个入度为0的点，记录下来
在图中删除该点和所有以它为起点的边
重复1和2，直到图为空或没有入度为0的点。

vector<int> haveCircularDependency(int n, vector<vector<int>> &prerequisites) {
    vector<vector<int>> g(n); //邻接表存储图结构
    vector<int> indeg(n); //每个点的入度
    vector<int> res; //存储结果序列
    for(int i = 0; i < prerequisites.size(); i ++) {
        // prerequisites为有向图
        int a = prerequisites[i][0], b = prerequisites[i][1]; 
        g[a].push_back(b);
        indeg[b] ++;
    }
    queue<int> q;
    //一次性将入度为0的点全部入队
    for(int i = 0; i < n; i ++) {
        if(indeg[i] == 0) q.push(i);
    }
    while(q.size()) {
        int t = q.front();
        q.pop();
        res.push_back(t);
        //删除边时，将终点的入度-1。若入度为0，果断入队
        for(int i = 0; i < g[t].size(); i ++) {
            int j = g[t][i];
            indeg[j] --;
            if(indeg[j] == 0) {
                q.push(j);
            }
        }
    }
    if(res.size() == n) return res;
    else return {};
}

43. 字符串相乘 ¶

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int m = num1.size(), n = num2.size();
        auto ansArr = vector<int>(m + n);
        // 从最右侧开始乘
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.at(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.at(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        // 向前进位
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        // 忽略头部为0的
        int index = ansArr[0] == 0 ? 1 : 0;
        string ans;
        while (index < m + n) {
            ans.push_back(ansArr[index]);
            index++;
        }
        for (auto &c: ans) {
            // 转为字符串
            c += '0';
        }
        return ans;
    }
};

198. 打家劫舍 ¶

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        //vector<int> dp(n + 1, 0); // dp[i]表示偷前i个房子的最大金额
        //dp[1] = nums[0];
        int cur = nums[0], pre = 0;
        for (int i = 2; i <= n; i++) {
            int temp = cur;
            cur = max(cur, pre + nums[i - 1]);
            pre = temp;
            //dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return cur;
    }
};

79. 单词搜索 ¶

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                // 从ij开始
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
private:
    int rows, cols;
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        // 不满足条件
        if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
        // 找到符合的路径字符
        if (k == word.size() - 1) return true;
        // 置为已访问过
        board[i][j] = '\0';
        // 上下左右四个方向
        bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        // 回退
        board[i][j] = word[k];
        return res;
    }
};

剑指 Offer 26. 树的子结构 ¶

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        // 三种情况满足之一：A和B是相同树，B存在于A的左子树，B存在于A的右子树
        return (A != nullptr && B != nullptr) && (recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
    }
private:
    bool recur(TreeNode* A, TreeNode* B) {
        // B为空肯定存在于A中
        if(B == nullptr) return true;
        // 如果B不为空，A为空或者A和B当前节点值不相等返回false
        if(A == nullptr || A->val != B->val) return false;
        // 继续向左右子树判断
        return recur(A->left, B->left) && recur(A->right, B->right);
    }
};

958. 二叉树的完全性检验 ¶

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        bool flg = false;
        while (!q.empty())
        {
            int cnt = q.size();
            while (cnt--)
            {
                TreeNode* front = q.front();
                q.pop();
                if (!front->left && front->right) // 左空右有
                    return false;

                if (front->left)  q.push(front->left);
                if (front->right) q.push(front->right);

                if (flg == true && (front->left || front->right)) // flg为真，再有节点存在左右孩子就错误了
                    return false;

                if (!front->left || !front->right) // 左空或右空，说明走到叶了，flg置真
                    flg = true;
            }
        }
        return true;
    }
};

取巧方法：找第一个空结点

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (root == NULL)
            return true;

        queue<TreeNode*> q;
        q.push(root);
        // 1. 找到第一个空结点
        while (!q.empty()) 
        { 
            TreeNode* front = q.front();
            q.pop();
            if (front == NULL) 
                break;
            else 
            {
                q.push(front->left);
                q.push(front->right);
            }
        }
        // 2. 检查队列中剩余结点是否有非空结点
        while (!q.empty()) 
        {
            TreeNode* front = q.front();
            q.pop();
            if (front) 
                return false;
        }
        return true;
    }
};

402. 移掉K位数字 ¶

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> stk;

        for (auto& digit: num) {
            while (!stk.empty() && stk.back() > digit && k) {
                // 构建单调不降stk
                stk.pop_back();
                k -= 1;
            }
            stk.push_back(digit);
        }

        // 如果k还存在剩余
        for (; k > 0; --k) {
            // 弹出栈订
            stk.pop_back();
        }


        string ans = "";
        bool isLeadingZero = true;
        for (auto& digit: stk) {
            // 如果是0开头则忽略
            if (isLeadingZero && digit == '0') {
                continue;
            }
            // 添加到ans中
            isLeadingZero = false;
            ans += digit;
        }
        return ans.empty() ? "0" : ans;
    }
};

152. 乘积最大子数组 ¶

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <int> maxF(nums), minF(nums);
        for (int i = 1; i < nums.size(); ++i) {
            // 取当前能拿到的最大值，两种case：1、正数：maxF[i - 1] * nums[i] 2、负数：minF[i - 1] * nums[i]。两者取max
            maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
            // 取当前能拿到的最小值，两种case：1、正数：minF[i - 1] * nums[i] 2、负数：maxF[i - 1] * nums[i]。两者取最小
            minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

104. 二叉树的最大深度 ¶

dfs：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

bfs:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz-- > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
            }
            ans += 1;
        } 
        return ans;
    }
};

62. 不同路径 ¶

数学推导：C(m - 1, m + n + 2)

def uniquePaths(self, m: int, n: int) -> int:
        # math.factorial返回阶乘
        return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))

dp：

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 处于上边界
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        // 处于左边界
        for (int i = 0; i < m; i++) dp[i][0] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];  
    }
}

dp空间优化：

class Solution {
    public int uniquePaths(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                // 因为对于长方形的对角从两个方向出发的路径是一致的
                cur[j] += cur[j-1] ;
            }
        }
        return cur[n-1];
    }
}

128. 最长连续序列 ¶

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> mp;
        int l, r, res = 0, len;
        // dp[i] = dp[i - 1] + dp[i + 1] + 1;
        for(int num : nums) {
            // 如果是新数字则加入map
            if(!mp[num]) {
                // 去除左右两侧数字的值
                l = mp[num - 1];
                r = mp[num + 1];
                // 更新区间
                len = l + r + 1;
                if(res < len) res = len;
                // 将当前值更新为len 周围两个数字也为
                mp[num] = len;
                mp[num - l] = len;
                mp[num + r] = len;
            }
        }
        return res;
    }
};

110. 平衡二叉树 ¶

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return max(height(root->left), height(root->right)) + 1;

    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        // 判断当前节点左右子树不超过1，判断左子树，判断右子树
        return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

8. 字符串转换整数 (atoi)¶

class Solution {
public:
    int myAtoi(string str) {
         if (str.empty()) return 0;
        int index = 0, n = str.size(), sign = 1, res = 0;
        // 处理前置空格
        while (index < n && str[index] == ' ') {
            ++index;
        }
        // 处理符号
        if (index < n && (str[index] == '+' || str[index] == '-')) {
            sign = str[index++] == '+' ? 1 : -1;
        }
        // 处理数字
        while (index < n && isdigit(str[index])) {
            int digit = str[index] - '0';
            // 判断是否溢出
            if (res > (INT_MAX - digit) / 10) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            res = res * 10 + digit;
            ++index;
        }
        return res * sign;
    }
};

226. 翻转二叉树 ¶

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        auto tmp = root -> left;
        root -> left = invertTree(root -> right);
        root -> right = invertTree(tmp);
        return root;
    }
};

24. 两两交换链表中的节点 ¶

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode* pre = dummy;
        if (head == nullptr || head -> next == nullptr) {
            return head;
        }
        ListNode* cur = head, *next = head -> next;
        while(next != nullptr) {
            // 做反转操作
            cur -> next = next -> next;
            next -> next = cur;
            pre -> next = next;

            pre = cur;
            cur = cur -> next;
            if (!cur) {
                break;
            }
            next = cur -> next;

        }

        return dummy -> next;
    }
};

297. 二叉树的序列化与反 ¶

class Codec
{
private:
public:
    Codec()
    {
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
        string ans = "";
        if (root == NULL)
            return ans;
        void *addr = static_cast<void *>(root);
        stringstream tp;
        tp << addr;
        ans = tp.str();
        return ans;
    }

    //  Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
        TreeNode *ans = NULL;
        const char *datas = data.c_str();
        long long addr = strtoll(datas, NULL, 16);
        ans = (TreeNode *)addr;
        return ans;
    }
};

class Codec {
public:
    string serialize(TreeNode* root) {
        return __Serializer__::serialize(root);
    }
    TreeNode* deserialize(string data) {
        return __Deserializer__::toTreeNode(data);
    }
};

518. 零钱兑换 II ¶

剑指 Offer 09. 用两个栈实现队 ¶

class MyQueue {
private:
    // B为存数的队列
    std::stack<int> A, B;

public:
    MyQueue() {}

    void push(int x) {
        A.push(x);
    }

    int pop() {
        int peek = this->peek();
        if (!B.empty()) {
            B.pop();
        }
        return peek;
    }

    int peek() {
        // 不为空则直接返回队列首部
        if (!B.empty()) return B.top();
        if (A.empty()) return -1;
        while (!A.empty()){
            B.push(A.top()), A.pop();
        }
        int res = B.top();
        return res;
    }

    bool empty() {
        return A.empty() && B.empty();
    }
};

704. 二分查找 ¶

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};

11. 盛最多水的容器 ¶

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 从两边逼近
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                max(res, (j - i) * height[i++]): 
                max(res, (j - i) * height[j--]); 
        }
        return res;
    }
};

739. 每日温度 ¶

单调递减栈从左往右找当前元素大于栈顶元素的弹出

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<int> st;
        for (int i = 0; i < temperatures.size(); ++i) {
            // 构建单调递减栈
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                auto t = st.top(); st.pop();
                // 当前温度大于栈
                res[t] = i - t;
            }
            st.push(i);
        }
        return res;
    }
};