Leetcode Hot 100

[jasperzhong]

https://leetcode-cn.com/problem-list/2cktkvj/

基本每日一题.

[jasperzhong]

1. 两数之和

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

经典

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (m.count(complement)) {
                return {m[complement], i};
            } 
            m[nums[i]] = i;
        }
        throw std::invalid_argument("no such two numbers");    
    }
};

[jasperzhong]

2. 两数相加

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

其实就是高精度加法.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* pnode = &dummy;

        int c = 0;
        while (l1 && l2) {
            int val = l1->val + l2->val + c;
            c = 0;
            if (val >= 10) {
                val -= 10;
                c = 1;
            }
            auto node = new ListNode(val);
            pnode->next = node;
            pnode = node;

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

        while (l1) {
            int val = l1->val + c;
            c = 0;
            if (val >= 10) {
                val -= 10;
                c = 1;
            }

            auto node = new ListNode(val);
            pnode->next = node;
            pnode = node;

            l1 = l1->next;
        }

        while (l2) {
            int val = l2->val + c;
            c = 0;
            if (val >= 10) {
                val -= 10;
                c = 1;
            }

            auto node = new ListNode(val);
            pnode->next = node;
            pnode = node;

            l2 = l2->next;
        }

        if (c) {
            auto node = new ListNode(c);
            pnode->next = node;
            pnode = node;
        }

        return dummy.next;
    }
};

[jasperzhong]

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

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

用map记录字符位置，同时记录最长子串的开始位置. 遍历字符串，更新map字符位置. 如果碰到出现过的字符，如果其位置 >= 最长子串开始位置，那么说明出现了重复，最长子串开始位置更新到该重复字符的之前位置+1. 时间复杂度是O(n)，空间复杂度是常数（因为字符种类恒定）.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        std::map<char, int> m;
        int j = 0, max_len = 0, len = s.size();
        for (int i = 0; i < len; ++i) {
            if (m.count(s[i]) && m[s[i]] >= j) {
                max_len = std::max(max_len, i - j);
                j = m[s[i]] + 1;
            }
            m[s[i]] = i;
        }
        max_len = std::max(max_len, len - j);
        return max_len;
    }
};

[jasperzhong]

11. 称最多水的容器

https://leetcode-cn.com/problems/container-with-most-water/

双指针分别指向左右两端，如果左边height比右边小，左边指针右移，反之右边指针左移.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int lo = 0, hi = height.size() - 1;
        int max_area = 0;
        while (lo < hi) {
            int area = std::min(height[lo], height[hi]) * (hi - lo);
            max_area = std::max(max_area, area);
            if (height[lo] < height[hi]) {
                lo++;
            } else {
                hi--;
            }
        }
        return max_area;
    }
};

[jasperzhong]

15. 三数之和

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

自己写超时. 看了题解. 重点是找到一个解之后的去重，相同的数不用看直接lo++/hi--.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size(); ++i) {
            if (i && nums[i] == nums[i-1]) continue;
            int lo = i + 1, hi = nums.size() - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == 0) {
                    ans.push_back({nums[i], nums[lo], nums[hi]});

                    while (lo < hi && nums[lo] == nums[lo+1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi-1]) hi--;
                    lo++;
                    hi--;
                } else if (sum < 0) {
                    lo++;
                } else {
                    hi--;
                }

            }
        }
        return ans;
    }
};

[jasperzhong]

17. 电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

dfs.

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if (digits.empty()) return ans;
        char buffer[digits.size()+1]; 
        buffer[digits.size()] = '\0';
        dfs(digits, 0, buffer, ans);
        return ans;
    }

    void dfs(string digits, int cur, char* buffer, vector<string>& ans) {
        if (cur == digits.size()) {
            ans.emplace_back(buffer);
            return;
        }

        auto candidates = m_.find(digits[cur])->second;
        for (auto ch: candidates) {
            buffer[cur] = ch;
            dfs(digits, cur+1, buffer, ans);
        }
    }
private:
    static const std::map<char, string> m_;
};

const std::map<char, string> Solution::m_ = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
};

[jasperzhong]

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

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

快慢指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast, *slow;
        fast = slow = head;

        while (n--) {
            fast = fast->next;    
        }

        while (fast && fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        if (!fast) {
            head = head->next;
        } else {
            slow->next = slow->next->next;
        }

        return head;
    }
};

[jasperzhong]

20. 有效的括号

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

栈的基本应用.

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> st;
        for (auto ch: s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                st.push(ch);
            } else if (ch == ')' && !st.empty() && st.top() == '(') {
                st.pop();
            } else if (ch == ']' && !st.empty() && st.top() == '[') {
                st.pop();
            } else if (ch == '}' && !st.empty() && st.top() == '{') {
                st.pop();
            } else {
                return false;
            }
        }
        if (!st.empty()) return false;

        return true;
    }
};

[jasperzhong]

21. 合并两个有序链表

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

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* pnode = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                pnode->next = l1;
                pnode = pnode->next;
                l1 = l1->next;
            } else {
                pnode->next = l2;
                pnode = pnode->next;
                l2 = l2->next;
            }
        }

        while (l1) {
            pnode->next = l1;
            pnode = pnode->next;
            l1 = l1->next;
        }

        while (l2) {
            pnode->next = l2;
            pnode = pnode->next;
            l2 = l2->next;
        }

        return dummy.next;
    }
};

[jasperzhong]

22. 括号生成

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

dfs.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        char str[n*2+1];
        str[n*2] = '\0';
        vector<string> ans;
        dfs(0, 0, n, str, ans);
        return ans;
    }

    void dfs(int left_cur, int right_cur, int n, char* str, vector<string>& ans) {
        if (right_cur > left_cur) return;
        if (left_cur > n || right_cur > n) return;

        if (left_cur == n && right_cur == n) {
            ans.push_back(str);
            return;
        } 

        str[left_cur+right_cur] = '(';
        dfs(left_cur+1, right_cur, n, str, ans);
        str[left_cur+right_cur] = ')';
        dfs(left_cur, right_cur+1, n, str, ans);
    }
};

[jasperzhong]

33. 搜索旋转排序数组

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

这题其实挺麻烦的. 考虑mid在左半边和右半边两种情况，然后还需要考虑target和nums[mid]、nums.front()大小来判断在哪个区段. 画了个简图

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

[jasperzhong]

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

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

lower_bound + upper_bound.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return {-1, -1};
        int lower = LowerBound(nums, target);
        int upper = UpperBound(nums, target);
        if (lower <= upper) 
            return {lower, upper};
        return {-1, -1};
    }

    int LowerBound(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    int UpperBound(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo-1;
    }

};

[jasperzhong]

39. 组合总和

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

dfs. 去重的办法是不允许搜索之前已经搜过的数字.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> solution;
        dfs(ans, candidates, solution, 0, 0, target);
        return ans;
    }

    void dfs(vector<vector<int>>& ans, vector<int>& candidates, vector<int>& solution, int cur, int value, int target) {
        if (value == target) {
            ans.push_back(solution);
            return;
        } else if (value > target) {
            return;
        }

        for (int i = cur; i < candidates.size(); ++i) {
            solution.push_back(candidates[i]);
            dfs(ans, candidates, solution, i, value + candidates[i], target);
            solution.pop_back();
        }
    }
};

[jasperzhong]

46. 全排列

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

dfs.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        dfs(ans, nums, 0);
        return ans;
    }

    void dfs(vector<vector<int>>& ans, vector<int>& nums, int cur) {
        if (cur == nums.size()) {
            ans.push_back(nums);
            return;
        }

        for (int i = cur; i < nums.size(); ++i) {
            swap(nums[i], nums[cur]);
            dfs(ans, nums, cur+1);
            swap(nums[i], nums[cur]);
        }
    }
};

[jasperzhong]

31. 下一个排列

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

这题实在不会做，看了题解思路. 我觉得不错. https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/ . 按照这个思路我自己写了以下代码ac了.

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() == 1) return;

        int ok = 0;
        for (int i = nums.size() - 2; i >= 0; --i) {
            // (nums[i], nums[i+1]): first increasing order pair
            if (nums[i] < nums[i+1]) {
                for (int j = nums.size() - 1; j > i; --j) {
                    // nums[j]: smallest element that is larger than nums[i]
                    if (nums[j] > nums[i]) {
                        std::swap(nums[i], nums[j]);
                        break;
                    }
                }
                std::reverse(nums.begin() + i + 1, nums.end());
                ok = 1;
                break;
            }
        }
        if (!ok) {
            std::reverse(nums.begin(), nums.end());
        }
    }
};

[jasperzhong]

48. 旋转图像

https://leetcode-cn.com/problems/rotate-image/

in-place旋转90度: 先转置后对称.

class Solution {
public:
    // (i, j) -> (j, n-i-1)
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();
        int rows = n / 2, cols = rows + (n % 2);
        for (int i = 0; i < rows ; ++i) {
            for (int j = 0; j < cols; ++j) {
                // matrix[i][j] -> matrix[j][n-i-1] -> matrix[n-i-1][n-j-1] -> matrix[n-j-1][i] 
                int tmp = 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] = tmp;
            }
        }
    }
};

[jasperzhong]

49. 字母异位词分组

https://leetcode-cn.com/problems/group-anagrams/

没找到很好的hash数组的函数. 用了比较笨的办法.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::map<int, vector<string>> m;
        for (auto str: strs) {
            int table[26] = {0};
            for (auto ch: str) {
                table[ch - 'a'] += 1;
            }
            m[hash_func(table)].push_back(str);
        }

        vector<vector<string>> ans;
        for (auto it = m.begin(); it != m.end(); ++it) {
            // std::cout << it->first << std::endl;
            ans.push_back(it->second);
        }
        return ans;
    }

    int hash_func(int table[26]) {
        string s;
        for (int i = 0;i < 26; ++i) {
            s += to_string((i+1)*table[i]);
        }
        return std::hash<string>{}(s);
    }
};

[jasperzhong]

53. 最大子序和

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

做烂了.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, max = std::numeric_limits<int>::min();
        for (auto num: nums) {
            if (sum < 0) sum = 0;
            sum += num;
            max = std::max(max, sum);
        }
        return max;
    }
};

[jasperzhong]

55. 跳跃游戏

https://leetcode-cn.com/problems/jump-game/

一开始用dfs超时了. 后来看了题解，没那么复杂...

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size() == 1) return true;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] == 0) {
                int j = i - 1;
                while (j >= 0 && nums[j] <= (i - j)) --j;
                if (j == -1 && i != (nums.size() - 1)) return false;
            }
        }
        return true;
    }
};

[jasperzhong]

56. 合并区间

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

好像也没有啥好办法. 排序就完了.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& lhs, const vector<int>& rhs) {
            if (lhs[0] != rhs[0]) return lhs[0] < rhs[0];
            return lhs[1] < rhs[1];
        });

        vector<vector<int>> ans;
        auto prev = intervals[0];
        for (int i = 1; i < intervals.size(); ++i) {
            auto& cur = intervals[i];
            if (prev[0] <= cur[0] && prev[1] >= cur[0]) {
                prev[1] = std::max(cur[1], prev[1]);
            } else {
                ans.push_back(prev);
                prev = cur;
            }
        }
        ans.push_back(prev);
        return ans;
    }
};

[jasperzhong]

62. 不同路径

https://leetcode-cn.com/problems/unique-paths/

最简单的dp.

class Solution {
public:
    // dp(i, j) = d(i-1, j) + d(i, j-1)
    int uniquePaths(int m, int n) {
        int dp[101][101] = {0};
        dp[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                else if (i == 0) dp[i][j] = dp[i][j-1]; 
                else if (j == 0) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

[jasperzhong]

64. 最小路径和

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

简单dp.

class Solution {
public:
    // dp(i, j) = min(dp(i-1, j), dp(i, j-1)) + grid[i][j]
    int minPathSum(vector<vector<int>>& grid) {
        int dp[201][201] = {0};
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) dp[i][j] = grid[i][j];
                else if (i == 0) dp[i][j] = dp[i][j-1] + grid[i][j];
                else if (j == 0) dp[i][j] = dp[i-1][j] + grid[i][j];
                else dp[i][j] = std::min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

[jasperzhong]

70. 爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/

class Solution {
public:
    // dp(n) = dp(n-1) + dp(n-2)
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int a = 1, b = 2, c;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

[jasperzhong]

75. 颜色分类

https://leetcode-cn.com/problems/sort-colors/

计数排序.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt[3] = {0};
        for (auto num: nums) {
            cnt[num]++;
        }

        std::fill(nums.begin(), nums.begin() + cnt[0], 0);
        std::fill(nums.begin() + cnt[0], nums.begin() + cnt[0] + cnt[1], 1);
        std::fill(nums.begin() + cnt[0] + cnt[1], nums.end(), 2);
    }
};

[jasperzhong]

78. 子集

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

dfs.

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> subset;
        dfs(ans, 0, nums, subset);
        return ans;
    }

    void dfs(vector<vector<int>>& ans, int cur, const vector<int>& nums, vector<int>& subset) {
        if (cur == nums.size()) {
            ans.push_back(subset);
            return;
        }

        dfs(ans, cur+1, nums, subset);
        subset.push_back(nums[cur]);
        dfs(ans, cur+1, nums, subset);
        subset.pop_back();
    }
};

[jasperzhong]

79. 单词搜索

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

dfs.

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

    bool dfs(vector<vector<char>>& board, string& word, string& search, int cur, int i, int j) {
        if (cur == word.size()) {
            return true;
        }

        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return false;
        if (board[i][j] != word[cur]) {
            return false;
        }

        char ch = board[i][j];
        search.push_back(ch);
        board[i][j] = ' ';

        bool ret = dfs(board, word, search, cur+1, i-1, j) ||
                   dfs(board, word, search, cur+1, i+1, j) ||
                   dfs(board, word, search, cur+1, i, j+1) ||
                   dfs(board, word, search, cur+1, i, j-1);
        search.pop_back();
        board[i][j] = ch;
        return ret;
    }
};

[jasperzhong]

96. 不同的二叉搜索树

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

这题有意思. 自己捣鼓出了状态转移方程. f(n) = \sigma_{i=1}^{n} f(i-1) * f(n-i). 这好像就是卡特兰数.

class Solution {
public:
    // f(n) = \sigma_{i=1}^{n} f(i-1) * f(n-i)
    int numTrees(int n) {
         int dp[20] = {1, 1, 2};
         for (int i = 3; i <= n; ++i) {
            int tmp = 0;
            for (int j = 1; j <= i; ++j) {
                tmp += dp[j-1] * dp[i-j];
            }
            dp[i] = tmp;
         }
         return dp[n];
    }
};

[jasperzhong]

98. 验证二叉搜索树

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

dfs. 这题时间花得有点长..

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        std::shared_ptr<int> prev;
        return dfs(root, prev);
    }

    bool dfs(TreeNode* root, std::shared_ptr<int>& prev) {
        if (root) {
            auto lhs = dfs(root->left, prev);
            if (!prev) {
                prev = std::make_shared<int>(root->val);
            }
            else {
                if (*prev >= root->val) {
                    return false;
                }
                *prev = root->val;
            }
            auto rhs = dfs(root->right, prev);
            return lhs && rhs;
        }
        return true;
    }
};

[jasperzhong]

101. 对称二叉树

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* lhs, TreeNode* rhs) {
        if (lhs && rhs) {
            return (lhs->val == rhs->val) && dfs(lhs->left, rhs->right) && dfs(lhs->right, rhs->left);
        } else if (!lhs && !rhs) {
            return true;
        } else {
            return false;
        }
    }
};

[jasperzhong]

102. 二叉树的层序遍历

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

一开始还用了个std::pair<TreeNode*, int>来存level, 后来看了评论发现没有必要, 直接一次性遍历完一层.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int count = q.size();
            vector<int> level;
            while (count-- > 0) {
                auto front = q.front();
                q.pop();
                level.push_back(front->val);

                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            ans.push_back(level);
        }
        return ans;
    }
};

[jasperzhong]

104. 二叉树的最大深度

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

一行.

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

[jasperzhong]

105. 从前序与中序遍历序列构造二叉树

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

好像copy有点多...

class Solution {
public:
    TreeNode* buildTree(vector<int> preorder, vector<int> inorder) {
        if (preorder.empty()) return nullptr;
        auto root = preorder.front();
        int left_num;
        for (int i = 0; i < inorder.size(); ++i) {
            if (inorder[i] == root) {
                left_num = i;
                break;
            }
        }
        TreeNode* node = new TreeNode(root);
        node->left = buildTree(std::vector<int>(preorder.begin()+1, preorder.begin()+1+left_num), std::vector<int>(inorder.begin(), inorder.begin() + left_num));
        node->right = buildTree(std::vector<int>(preorder.begin()+1+left_num, preorder.end()), std::vector<int>(inorder.begin()+left_num+1, inorder.end()));

        return node;
    }
};

[jasperzhong]

114. 二叉树展开为链表

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

看了题解...真没想到这个 右 -> 左 -> 根 的方法...

class Solution {
public:
    void flatten(TreeNode* root) {
        last = nullptr;
        dfs(root);
    }

    void dfs(TreeNode* root) {
        if (root) {        
            dfs(root->right);    
            dfs(root->left);

            root->right = last;
            root->left = nullptr;
            last = root;
        }
    }
private:
    TreeNode* last;
};

[jasperzhong]

121. 买卖股票的最佳时机

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

看每日涨跌就行了，转化成和最大的子序列问题.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        for (int i = prices.size() - 1; i >= 1; --i) {
            prices[i] -= prices[i-1];
        }

        int sum = 0, max = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (sum < 0) sum = 0;
            sum += prices[i];
            max = std::max(max, sum);
        }
        return max;
    }
};

[jasperzhong]

128. 最长连续序列

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

看了题解. 题解思路不错. 先放到一个set里面去重，然后遍历set，如果x-1没出现过，那就从x-1开始慢慢遍历x, x+1, x+2, ... 为什么是检查x-1存不存在呢？倘若存在，直接跳过就可以了，因为遍历到x-1这个数的时候，会去检查x-2存不存在. 所以没必要从x-1再来一遍了.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        std::set<int> s;
        for (auto num: nums) {
            s.insert(num);
        }

        int longest_streak = 0;
        for (auto num: s) {
            if (!s.count(num-1)) {
                int cur_num = num;
                int cur_streak = 1;

                while (s.count(cur_num+1)) {
                    cur_num++;
                    cur_streak++;
                }

                longest_streak = std::max(longest_streak, cur_streak);
            }
        }
        return longest_streak;
    }
};

[jasperzhong]

136. 只出现一次的数字

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

挺经典的题

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for (auto num: nums) {
            x ^= num;
        }
        return x;
    }
};

[jasperzhong]

141. 环形链表

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

快慢指针.

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

[jasperzhong]

142. 环形链表2

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

逐个判断就行了. 看经过这个节点的次数，如果大于1，就说明该点是环起点（因为fast不可能绕两圈还没找到slow）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        while (head) {
            if (hasCycle(head)) {
                return head;
            }
            head = head->next;
        }
        return nullptr;
    }

    bool hasCycle(ListNode *head) {
        ListNode* fast, *slow;
        fast = slow = head;
        int cnt = 0;
        while (fast && fast->next) {
            if (fast == head ) cnt++;
            if (fast->next == head) cnt++;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                if (cnt > 1) {
                    return true;
                }
                return false;
            }
        }
        return false;
    }
};

[jasperzhong]

146. LRU缓存机制

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

哈希表+双向链表. 蛮有意思的一题.

class LRUCache {
public:
    struct DNode {
        int key;
        int val;
        DNode* prev, *next;

        DNode(): prev(nullptr), next(nullptr) {}
        DNode(int k, int v): key(k), val(v), prev(nullptr), next(nullptr) {}
    };

    LRUCache(int capacity): capacity_(capacity) {
        head.next = &tail;
        tail.prev = &head;
    }

    int get(int key) {
        if (m_.count(key) != 0) {
            DNode* node = m_[key];
            node->prev->next = node->next;
            node->next->prev = node->prev;

            node->next = head.next;
            node->prev = &head;
            head.next->prev = node;
            head.next = node;
            return m_[key]->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (m_.count(key) != 0) {
            DNode* node = m_[key];
            node->val = value; 
            node->prev->next = node->next;
            node->next->prev = node->prev;

            node->next = head.next;
            node->prev = &head;
            head.next->prev = node;
            head.next = node;
        } else {
            if (m_.size() >= capacity_) {
                tail.prev->prev->next = &tail;
                DNode* node = tail.prev;
                tail.prev = node->prev;
                m_.erase(node->key);
                delete node;
            } 
            DNode* node = new DNode(key, value);
            m_[key] = node;
            node->next = head.next;
            node->prev = &head;
            head.next->prev = node;
            head.next = node;
        }
    }
private:
    int capacity_;
    std::unordered_map<int, DNode*> m_;
    DNode head, tail;    
};

[jasperzhong]

155. 最小栈

写过好几遍了.

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int val) {
        int min = val;
        if (!s_.empty()) {
            if (val > min_.top()) {
                min = min_.top();
            }
        }
        s_.push(val);
        min_.push(min);
    }

    void pop() {
        s_.pop();
        min_.pop();
    }

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

    int getMin() {
        return min_.top();
    }
private:
    std::stack<int> s_;
    std::stack<int> min_;
};

[jasperzhong]

160. 相交链表

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

先看下各自链表多长，长的那个先走就行了. 吐槽一下题解的做法：鬼想的出来啊!

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
        ListNode *pa = headA, *pb = headB;
        int cnt_a = 0, cnt_b = 0;
        while (pa->next) {
            pa = pa->next;
            cnt_a++;
        }

        while (pb->next) {
            pb = pb->next;
            cnt_b++;
        }

        if (pa != pb) {
            return nullptr;
        }

        int diff = std::abs(cnt_b - cnt_a);
        pa = headA; 
        pb = headB;
        if (cnt_a < cnt_b) {
            while (diff--) {
                pb = pb->next;
            }

        } else {
            while (diff--) {
                pa = pa->next;
            }
        }

        while (pa && pb) {
            if (pa == pb) return pa;
            pa = pa->next;
            pb = pb->next;
        }

        // should not reach here
        return pa;
    }
};

[jasperzhong]

169. 多数元素

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

摩尔投票法.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = nums.front();
        int cnt = 0;
        for (auto num: nums) {
            if (x == num) {
                cnt++;
            } else {
                cnt--;
                if (cnt == 0) {
                    x = num; 
                    cnt = 1;
                }
            }
        }
        return x;
    }
};

[jasperzhong]

198. 打家劫舍

https://leetcode-cn.com/problems/house-robber/

感觉要好好练下dp了.

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

[jasperzhong]

200. 岛屿数量

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

想起了大一.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || 
            j >= grid[0].size() || grid[i][j] != '1') return;

        grid[i][j] = '0';

        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
};

[jasperzhong]

206. 反转链表

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

[jasperzhong]

207. 课程表

https://leetcode-cn.com/problems/course-schedule/

拓扑排序. 用了dfs.

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        std::vector<vector<int>> graph(numCourses);
        for (auto edge: prerequisites) {
            graph[edge[0]].push_back(edge[1]);
        }

        std::vector<int> visit(numCourses, 0);

        for (int node = 0; node < numCourses; ++node) {
            if (!dfs(graph, node, visit)) return false;
        }

        return true;
    }

    bool dfs(const std::vector<vector<int>>& graph, int node, std::vector<int>& visit) {
        if (visit[node] == 2) return true;
        if (visit[node] == 1) return false;

        visit[node] = 1; 

        for (auto next: graph[node]) {
            if (!dfs(graph, next, visit)) return false;
        }

        visit[node] = 2;
        return true;
    }
};

[jasperzhong]

338. 比特位计数

https://leetcode-cn.com/problems/counting-bits/

看了题解. 这题有点巧.

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n+1, 0);
        for (int i = 1; i <= n; ++i) {
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
    }
};

[jasperzhong]

226. 翻转二叉树

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

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        std::swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

[jasperzhong]

234. 回文链表

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

真麻烦....

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) return true;

        ListNode* second = EndOfFirstPart(head);
        ListNode* p2 = ReverseList(second->next);

        ListNode* p1 = head;
        int ok = 1;
        while (p2) {
            if (p1->val != p2->val) {
                ok = 0;
                break;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        ReverseList(second->next);

        return ok;
    }

    ListNode* ReverseList(ListNode* head) {
        ListNode *cur = head, *prev = nullptr;
        while (cur) {
            auto next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    ListNode* EndOfFirstPart(ListNode* head) {
        ListNode *fast, *slow;
        fast = slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow; 
    }
};

[jasperzhong]

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

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

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