一、LeetCode Hot100

​

1. 两数之和 (opens new window)

• 算法：HashMap
• 误区：
  • 误区一：排序 + 双指针，这个算法排序的时候下标发生了变化，得出的不是预期的结果
  • 误区二：先遍历一次存入哈希，再遍历检查元素（会获取到自身元素）

public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();

// 误区二
for(int i = 0;i < nums.length;i ++){
   if(map.containsKey(target - nums[i])){
       return new int[]{i, map.get(target - nums[i])};
   }else {
       map.put(nums[i], i);
   }
}

return new int[]{-1, -1};
}

2. 两数相加 (opens new window)

• 算法：双指针
• 重点：
  • 满十进位
  • 处理最后一个满十进位

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode p1 = l1;
ListNode p2 = l2;
ListNode head = new ListNode();
ListNode p = head;

int toNextVal = 0;

while(p1 != null && p2 != null){
   int val = (p1.val + p2.val + toNextVal) % 10;
   toNextVal = (p1.val + p2.val + toNextVal) / 10;
   p.next = new ListNode(val);

   p = p.next;
   p1 = p1.next;
   p2 = p2.next;
}

while(p1 != null){
   int val = (p1.val + toNextVal) % 10;
   toNextVal = (p1.val + toNextVal) / 10;

   p.next = new ListNode(val);
   p = p.next;
   p1 = p1.next;
}

while(p2 != null){
   int val = (p2.val + toNextVal) % 10;
   toNextVal = (p2.val + toNextVal) / 10;

   p.next = new ListNode(val);
   p = p.next;
   p2 = p2.next;
}

if(toNextVal != 0){
   p.next = new ListNode(toNextVal);
}
return head.next;
}

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

• 算法：滑动窗口法
  • 窗口存放[left, right)中字符的数量

public int lengthOfLongestSubstring(String s) {

    int left = 0;
    int right = 0;
    Map<Character, Integer> windows = new HashMap<>();
    int maxVal = 0;

    while(right < s.length()){
        char c = s.charAt(right);
        windows.put(c, windows.getOrDefault(c, 0) + 1);
        right ++;

        while(windows.get(c) > 1){
            char d = s.charAt(left);
            windows.put(d, windows.get(d) - 1);
            left ++;
        }
        maxVal = Integer.max(maxVal, right - left);
    }

    return maxVal;
}

• 优化版
  • left不需要一个一个滑动，map存放的是下标，但是容易出错

public int lengthOfLongestSubstring(String s) {

    int left = 0;
    int right = 0;
    Map<Character, Integer> windows = new HashMap<>();
    int maxVal = 0;

    while(right < s.length()){
        char c = s.charAt(right);

        if(windows.containsKey(c) && windows.get(c) >= left){
            maxVal = Integer.max(maxVal, right - left);
            left = windows.get(c) + 1;
        }

        windows.put(c, right);
        right ++;
    }
    maxVal = Integer.max(maxVal, right - left);

    return maxVal;
}

5. >最长回文子串

• 解法：中心扩列法

• 注意：substring需要的是左右的下标

• 推荐解法：直接在findLongestPalindrome中判断和获取回文串

String res = "";
public String longestPalindrome(String s) {

    for(int i = 0;i < s.length();i ++){
        findLongestPalindrome(s, i, i + 1);
        findLongestPalindrome(s, i, i);
    }

    return res;
}

private void findLongestPalindrome(String s, int left, int right){

    while(left >= 0 && right < s.length()){
        if(s.charAt(left) == s.charAt(right)){
            if(right - left + 1 > res.length()){
                res = s.substring(left, right + 1);
            }
            left --;
            right ++;
        }else {
            return;
        }
    }

    return;
}

• 优雅版：代码耦合度低，但是理解困难

public String longestPalindrome(String s) {

    int left = 0;
    int maxLen = 1;

    for(int i = 0;i < s.length();i ++){
        int len1 = subLongestPalindrome(s, i , i);
        int len2 = subLongestPalindrome(s, i , i + 1);
        int subMax = Integer.max(len1, len2);

        if(subMax > maxLen){
            left = i - (subMax - 1) / 2;
            maxLen = subMax;
        }
    }

    return s.substring(left, left + maxLen);
}

private int subLongestPalindrome(String s, int left, int right){
    
    int maxLen = 0;
    while(left >= 0 && right < s.length()){
        if(s.charAt(left) == s.charAt(right)){
            maxLen = Integer.max(maxLen, right - left + 1);
            left --;
            right ++;
        }else {
            return maxLen;
        }
    }

    return maxLen;
}

11. >盛最多水的容器

• 双指针
  • 移动长板：面积一定变小，因为短板不变，长度变小
  • 移动短板：可能变大，长度虽然变小，但是下一个板可能比当前短板大

public int maxArea(int[] height) {

    int max = 0;
    int left = 0;
    int right = height.length - 1;

    while(left < right){
        max = Integer.max(max, Integer.min(height[left], height[right]) * (right - left));

        if(height[left] < height[right]){
            left ++;
        }else {
            right --;
        }
    }

    return max;
}

15. >三数之和

• 三指针：排序，固定一指针，移动另外两个指针
• 重点：去重，本质是跟上一个元素进行比较，比如相同则继续移动

public List<List<Integer>> threeSum(int[] nums) {

    Arrays.sort(nums);

    List<List<Integer>> ans = new ArrayList<>();
    for(int i = 0;i < nums.length;i ++){

        int left = i + 1;
        int right = nums.length - 1;

        // 去重
        if(i > 0 && nums[i] == nums[i - 1]){
            continue;
        }

        while(left < right){
            int sum = nums[left] + nums[right] + nums[i];
            if(sum == 0){
                ans.add(Arrays.asList(nums[left], nums[right], nums[i]));
                left ++;
                right --;

                // 去重
                while(left < right && nums[left] == nums[left - 1]) left ++;
                while(left < right && nums[right] == nums[right + 1]) right --;
            }else if(sum < 0){
                left ++;
            }else {
                right --;
            }
        }
    }

    return ans;
}

17. >电话号码的字母组合

• 算法：回溯法（递归本质上就是一种深度遍历）

组合和排列一般都会用到回溯法，排列和组合的区别：组合不考虑顺序，例如对[A,B]选两个数进行排列组合，[A,B]即组合成一组，而排列考虑顺序，[A,B]、[B,A]为不同排列。

public List<String> letterCombinations(String digits) {
    if(digits == null || digits.length() == 0){
        return new ArrayList<>();
    }

    Map<Character, String> map = new HashMap<>();
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");

    List<String> ans = new ArrayList<>();
    backtract(digits, new StringBuilder(), ans, map, 0);

    return ans;
}

public void backtract(String digits, StringBuilder subAns, List<String> ans, Map<Character, String> map, int index){
    if(subAns.length() == digits.length()){
        ans.add(new String(subAns));
        return;
    }

    char c = digits.charAt(index);
    String nums = map.get(c);

    for(int i = 0;i < nums.length();i ++){
        char c2 = nums.charAt(i);
        subAns.append(c2);
        backtract(digits, subAns, ans, map, index + 1);
        subAns.deleteCharAt(subAns.length() - 1);
    }

}

19. *删除链表的倒数第 N 个结点

• 算法：快慢指针
• 注意：添加dummyHead

删除倒数节点可以记为模版（删除倒数第n个节点）：

• 快指针先移动n位（因为有dummyhead节点，不然的话移动n位自然就在目标节点处，这个很容易理解）
• 快慢指针同时走，直到快指针走到尾部节点，不走null

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head == null || n <= 0){
        return head;
    }
    
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode p1 = dummyHead;
    ListNode p2 = dummyHead;
	
    // 倒数第几个就走几步
    for(int i = 1;i <= n;i ++){
        p1 = p1.next;
    }
    
    // 在目标前一位停下 
    while(p1.next != null){
        p1 = p1.next;
        p2 = p2.next;
    }

    p2.next = p2.next.next;

    return dummyHead.next;
}

20. >有效的括号

• 算法：利用栈
  • 遇到左符合则入栈
  • 遇到右符合则检查栈不为空且栈顶元素需为其左符号
• 记录：❌

public boolean isValid(String s) {

    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');

    for(char c : s.toCharArray()){
        if(map.containsKey(c)){
            stack.push(c);
        }else {
            if(stack.isEmpty() || map.get(stack.peek()) != c){
                return false;
            }
            stack.pop();
        }
    }

    return stack.isEmpty();
}

21. 合并两个有序链表 (opens new window)

• 思路：归并排序

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    ListNode dummyHead = new ListNode();
    ListNode p3 = dummyHead;
    ListNode p1 = list1;
    ListNode p2 = list2;

    while(p1 != null && p2 != null){
        if(p1.val < p2.val){
            p3.next = p1;
            p1 = p1.next;;
        }else {
            p3.next = p2;
            p2 = p2.next;;
        }

        p3 = p3.next;
    }

    while(p1 != null){
        p3.next = p1;
        p1 = p1.next;
        p3 = p3.next;
    }

    while(p2 != null){
        p3.next = p2;
        p2 = p2.next;
        p3 = p3.next;
    }

    return dummyHead.next;
}

22. 括号生成 (opens new window)

• 算法：回溯法（全排列） - 暴力解法

public List<String> generateParenthesis(int n) {

    List<String> ans = new ArrayList<>();
    backtract(ans, new StringBuilder(), n, n);

    return ans;
}

public void backtract(List<String> ans, StringBuilder subAns, int left, int right){
    if(left == 0 && right == 0){
        String str = new String(subAns);
        if(valid(str)) ans.add(str);
        return;
    }

    if(left > 0){
        subAns.append("(");
        backtract(ans, subAns, left - 1, right);
        subAns.deleteCharAt(subAns.length() - 1);
    }

    if(right > 0){
        subAns.append(")");
        backtract(ans, subAns, left, right - 1);
        subAns.deleteCharAt(subAns.length() - 1);
    }
}

private boolean valid(String subAns){
    int cnt = 0;
    for(char c : subAns.toCharArray()){
        if(c == '('){
            cnt ++;
        }else {
            if(cnt > 0){
                cnt --;
            }else {
                return false;
            }
        }
    }

    return cnt == 0;
}

• （推荐）最优：优化后

public List<String> generateParenthesis(int n) {

    List<String> ans = new ArrayList<>();
    backtract(ans, new StringBuilder(), n, n);

    return ans;
}

public void backtract(List<String> ans, StringBuilder subAns, int left, int right){
    if(left == 0 && right == 0){
        ans.add(new String(subAns));
        return;
    }

    if(left > 0){
        subAns.append("(");
        backtract(ans, subAns, left - 1, right);
        subAns.deleteCharAt(subAns.length() - 1);
    }
	
	// 关键点
    if(right > left){
        subAns.append(")");
        backtract(ans, subAns, left, right - 1);
        subAns.deleteCharAt(subAns.length() - 1);
    }
}

31. 下一个排列 (opens new window)

• 算法：两次扫描
  1. 从后往前找到第一个非降序的元素a
  2. 从后往前找往前找到第一个大于元素a的元素b
  3. 交换a，b的元素值
  4. a后面的元素进行reserve

public void nextPermutation(int[] nums) {

    int n = nums.length;
    int i = n - 2;

    while(i >= 0 && nums[i] >= nums[i + 1]){
        i --;
    }

    if(i >= 0){
        int j = n - 1;
        while(j >= 0 && nums[j] <= nums[i]){
            j --;
        }
        swap(nums, i , j);
    }

    // 如果没有任何变化，也要将其倒置，所以需要在括号外，case：321
    reserve(nums,i + 1, n - 1);
}

private void swap(int[] nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

private void reserve(int[] nums, int l,int r){
    while(l < r){
        swap(nums, l, r);
        l ++;
        r --;
    }
}

*32. 最长有效括号 (opens new window)

算法：

• 解法一：动态规划
• 解法二：栈
  • 栈底存放上一个不匹配的右括号，初始化为-1
  • 基础核心思路：
    • 遇到左括号则入栈
    • 遇到右括号则出栈
      • 栈不为空，则更新最长有效括号
      • 栈为空，则说明当前的右括号没有匹配，将其入栈

• 栈解法

public int longestValidParentheses(String s) {
    int max = 0;
    Deque<Integer> deque = new ArrayDeque<>();
    // 栈底存放上一个不匹配的右括号下标，初始化-1
    deque.push(-1);

    for(int i = 0;i < s.length();i ++){
        char c = s.charAt(i);
        if(c == '('){
            deque.push(i);
        }else {
            deque.pop();
            if(deque.isEmpty()){
                deque.push(i);
            }else {
                max = Integer.max(max, i - deque.peek());
            }
        }
    }

    return max;
}

• 推荐解法：贪心解法

public int longestValidParentheses(String s) {
    int left = 0;
    int right = 0;
    int len = s.length();
    int max = 0;

    for(int i = 0;i < len;i ++){
        char c = s.charAt(i);
        if(c == '('){
            left ++;
        }else {
            right ++;
        }

        if(left == right){
            max = Integer.max(max, 2 * left);
            // 左遍历是right > left
        }else if(right > left){
            // right > left则说明不再匹配，重新开始
            right = left = 0;
        }
    }

    right = left = 0;
    for(int i = len - 1;i >= 0;i --){
        char c = s.charAt(i);
        if(c == '('){
            left ++;
        }else {
            right ++;
        }

        if(left == right){
            max = Integer.max(max, 2 * left);
            // 右遍历是left > right
        }else if(left > right){
            // right > left则说明不再匹配，重新开始
            right = left = 0;
        }
    }

    return max;
}

33. 搜索旋转排序数组 (opens new window)

算法：二分搜索（对于有序数组要求Log(n)的时间复杂，通常为二分搜索）

思路：

• 旋转后的数组必以mid为中心分为两段，必然至少存在一段为有序的情况，另一段可能有序可能无序的。
• 我们的算法核心为：找到有序的一边，判断target是否在该段内，按正常二分思维走。

public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
	
    // 注意为等号
    while(l <= r){
        int mid = l + (r - l) / 2;
        if(nums[mid] == target){
            return mid;
        }
		
        // 说明是有序的
        if(nums[mid] >= nums[l]){
            if(target >= nums[l] && target <= nums[mid]){
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }else{
            if(target >= nums[mid] && target <= nums[r]){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
    }

    return -1;
}

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

算法：二分查找

思路：两次二分查找，分别查找其左边界和有边界（假如只有一个数符合，以寻找左边界为例子，即使第一步r就不包含目标了，但是最终l = mid + 1会执行r的右边一位，即为目标值）

public int[] searchRange(int[] nums, int target) {

    int left = binarySearchLeft(nums, target);
    int right = binarySearchRight(nums, target);

    return new int[]{left, right};
}

private int binarySearchLeft(int[] nums, int target){

    int l = 0;
    int r = nums.length - 1;

    while(l <= r){
        int mid = l + (r - l) / 2;
        if(target <= nums[mid]){
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }

    if(l < nums.length && nums[l] == target){
        return l;
    }

    return -1;
}

private int binarySearchRight(int[] nums, int target){

    int l = 0;
    int r = nums.length - 1;

    while(l <= r){
        int mid = l + (r - l) / 2;
        if(target >= nums[mid]){
            l = mid + 1;
        }else {
            r = mid - 1;
        }
    }

    if(r >= 0 && nums[r] == target){
        return r;
    }

    return -1;
}

39. 组合总和 (opens new window)

算法：回溯法

重点：

• 去重：通过在方法上传递index去重，因为组合可以选择自身，所以传入的参数为i

public List<List<Integer>> combinationSum(int[] candidates, int target) {

    List<List<Integer>> ans = new ArrayList<>();
    backtract(candidates, ans, new ArrayList<>(), target, 0);

    return ans;
}

private void backtract(int[] candidates, List<List<Integer>> ans, List<Integer> subAns, int target, int index){

    if(target == 0){
        ans.add(new ArrayList<>(subAns));
        return;
    }

    if(target < 0){
        return;
    }

    for(int i = index;i < candidates.length;i ++){
        subAns.add(candidates[i]);
        // 通过index去重，因为可以选择自身，所以传入的是i
        backtract(candidates, ans, subAns, target - candidates[i], i);
        subAns.remove(subAns.size() - 1);
    }
}

42. 接雨水 (opens new window)

算法：动态规划

思路：左右两遍存储，分别存储不包含当前height的左边和右边最大的height，两边去最小的减去当前的height即为所求，本质上就是计算每个height槽位能够存储多少水然后相加。

public int trap(int[] height) {

    int n = height.length;
    int[] left = new int[n];
    int[] right = new int[n];
    int res = 0;

    for(int i = 1;i < n;i ++){
        left[i] = Integer.max(left[i - 1], height[i -  1]);
    }

    for(int i = n - 2;i >= 0;i --){
        right[i] = Integer.max(right[i + 1], height[i + 1]);
    }


    for(int i = 0;i < n;i ++){
        res += Integer.max(0, Integer.min(left[i], right[i]) - height[i]);
    }

    return res;
}

46. 全排列 (opens new window)

算法：回溯法

思路：通过used数组标识元素是否被使用

boolean[] used = new boolean[7];
public List<List<Integer>> permute(int[] nums) {

    List<List<Integer>> ans = new ArrayList<>();
    backtract(ans, new ArrayList<>(), nums);

    return ans;
}

private void backtract(List<List<Integer>> ans, List<Integer> subAns, int[] nums){
    if(subAns.size() == nums.length){
        ans.add(new ArrayList<>(subAns));
        return;
    }

    for(int i = 0;i < nums.length;i ++){
        if(!used[i]){
            used[i] = true;
            subAns.add(nums[i]);
            backtract(ans, subAns, nums);
            subAns.remove(subAns.size() - 1);
            used[i] = false;
        }
    }
}

49. 字母异位词分组 (opens new window)

算法：Map

重点：key的确定，有以下两种方式

• 对key进行排序
• 用count[26]的数组统计数量，key = ((char) a + i) + count[i];

public List<List<String>> groupAnagrams(String[] strs) {

    Map<String, List<String>> map = new HashMap<>();
    for(String s : strs){
        int[] counts = new int[26];

        for(char c : s.toCharArray()){
            counts[c - 'a'] ++;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < 26;i ++){
            if(counts[i] > 0){
                sb.append((char) i + 'a');
                sb.append(counts[i]);
            }
        }

        String key = sb.toString();
        List<String> list = map.getOrDefault(key, new ArrayList<>());
        list.add(s);

        map.put(key, list);
    }

    return new ArrayList<List<String>>(map.values());
}

53. 最大子数组和 (opens new window)

算法：动态规划

• dp[i]：代表包含当前num[i]元素的最大连续和
  • dp[i] = dp[i - 1] > 0 ? (dp[i - 1] + nums[i]) : nums[i];
• dp[0] = nums[0]

public int maxSubArray(int[] nums) {

    int n = nums.length;
    int[] dp = new int[n];
    int max = nums[0];

    dp[0] = nums[0];
    for(int i = 1;i < n;i ++){
        if(dp[i - 1] < 0){
            dp[i] = nums[i];
        }else {
            dp[i] = nums[i] + dp[i - 1];
        }

        max = Integer.max(max, dp[i]);
    }

    return max;
}

72. 编辑距离 (opens new window)

算法：动态规划

public int minDistance(String word1, String word2) {

    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

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

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

    for(int i = 1;i <= m;i ++){
        for(int j = 1;j <= n;j ++){
            if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1];
            }else {
                dp[i][j] = Integer.min(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = Integer.min(dp[i][j], dp[i - 1][j - 1]) + 1;
            }
        }
    }

    return dp[m][n];
}

75. 颜色分类 (opens new window)

算法：双指针

解法一：两次遍历 + 双指针，遇到0置换到p0，遇到2置换到p2

解法二（容易出错）：一次遍历 + 双指针

public void sortColors(int[] nums) {

    int n = nums.length;
    int p0 = 0;
    int p2 = n - 1;
    
  	// <= p2是重点，保证即使所有数都为2，或者0，都能够退出循环
    for(int i = 0;i <= p2;i ++){
        if(nums[i] == 0){
            swap(nums, i, p0);
            p0 ++;
        }

        if(nums[i] == 2){
            swap(nums, i, p2);
            p2 --;
						
          	// 最终置换完i所在的位置需要为1，否则说明还需要进行置换，将i指针-1
            if(nums[i] != 1){
                i --;
            }
        }
    }
}

private void swap(int[] nums, int l,int r){
    int tmp = nums[l];
    nums[l] = nums[r];
    nums[r] = tmp;
}

76. 最小覆盖子串 (opens new window)

算法：滑动窗口

public String minWindow(String s, String t) {

  String ans = "";
  Map<Character, Integer> windows = new HashMap<>();
  Map<Character, Integer> need = new HashMap<>();
  int left = 0;
  int right = 0;
  // 已经满足条件的字符数量
  int valid = 0;
	
  // 注意need窗口和windows窗口不要混
  for(char c : t.toCharArray()){
    need.put(c, need.getOrDefault(c, 0) + 1);
  }

  while(right < s.length()){
    char c = s.charAt(right);
    
    // 只比较need需要的字符，否则need.get(c)可能为null
    if(need.containsKey(c)){
      windows.put(c, windows.getOrDefault(c, 0) + 1);
      if(windows.get(c).equals(need.get(c))){
        valid ++;
      }
    }
    right ++;

    while(valid == need.size()){
      if(ans.isEmpty() || ans.length() > right - left){
        ans = s.substring(left, right);
      }

      char d = s.charAt(left);
      if(need.containsKey(d)){
        if(need.get(d).equals(windows.get(d))){
          valid --;
        }
        windows.put(d, windows.get(d) - 1);
      }
      left ++;
    }
  }

  return ans;
}	

78. 子集 (opens new window)

算法：回溯（递归）

public List<List<Integer>> subsets(int[] nums) {

    List<List<Integer>> ans = new ArrayList<>();
    backtract(ans, new ArrayList<>(), nums, 0);

    return ans;
}

private void backtract(List<List<Integer>> ans , List<Integer> subAns, int[] nums, int index){
    ans.add(new ArrayList<>(subAns));
    if(index == nums.length){
        return;
    }

    for(int i = index;i < nums.length;i ++){
        subAns.add(nums[i]);
        backtract(ans, subAns, nums, i + 1);
        subAns.remove(subAns.size() - 1);
    }
}

79. 单词搜索 (opens new window)

算法：回溯法

boolean[][] used = new boolean[7][7];
public boolean exist(char[][] board, String word) {

    int m = board.length;
    int n = board[0].length;

    for(int i = 0;i < m;i ++){
        for(int j = 0;j < n;j ++){
            boolean res = trave(board, i, j, word, 0);
            if(res){
                return res;
            }
        }
    }

    return false;
}

private boolean trave(char[][] board,int i,int j, String word, int index){
    if(index == word.length()){
        return true;
    }

    char c = word.charAt(index);
    if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != c || used[i][j]){
        return false;
    }

    used[i][j] = true;
    boolean top = trave(board, i - 1, j, word, index + 1);
    boolean down = trave(board, i + 1, j, word, index + 1);
    boolean right = trave(board, i, j + 1, word, index + 1);
    boolean left = trave(board, i, j - 1, word, index + 1);
    used[i][j] = false;

    return top || down || right || left;
}

84. 柱状图中最大的矩形 (opens new window)

Todo

算法：单调栈

思路：在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。

• 通过单调栈确定以当前下标所在高度最大可能矩形的左边边界（不包含）和右边边界（不包含）

public int largestRectangleArea(int[] heights) {
  Deque<Integer> stack = new ArrayDeque<>();

  int n = heights.length;
  // 矩形的左横坐标 - 1
  int[] left = new int[n];
  // 矩形的右横坐标 + 1
  int[] right = new int[n];

  Arrays.fill(right, n);

  for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
      right[stack.peek()] = i;
      stack.pop();
    }
    left[i] = stack.isEmpty() ? -1 : stack.peek();
    stack.push(i);
  }

  int max = 0;
  for (int i = 0; i < n; i++) {
    max = Integer.max(max, heights[i] * (right[i] - left[i] - 1));
  }

  return max;
}

85. 最大矩形 (opens new window)

Todo

算法：单调栈

public int maximalRectangle(char[][] matrix) {

  if (matrix == null || matrix.length == 0) {
    return 0;
  }

  int n = matrix.length;
  int m = matrix[0].length;
  int[] height = new int[m];

  int max = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (matrix[i][j] == '1') {
        height[j]++;
      } else {
        height[j] = 0;
      }
    }

    max = Integer.max(max, maxArea(height));
  }

  return max;
}

public int maxArea(int[] heights) {

  Deque<Integer> stack = new ArrayDeque<>();
  int len = heights.length;
  int[] left = new int[len];
  int[] right = new int[len];
  Arrays.fill(right, len);

  for (int i = 0; i < heights.length; i++) {
    while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
      right[stack.peek()] = i;
      stack.pop();
    }
    left[i] = stack.isEmpty() ? -1 : stack.peek();
    stack.push(i);
  }

  int ans = 0;
  for (int i = 0; i < len; i++) {
    ans = Integer.max(ans, (right[i] - left[i] - 1) * heights[i]);
  }

  return ans;
}

94. 二叉树的中序遍历 (opens new window)

算法：递归

public List<Integer> inorderTraversal(TreeNode root) {

  List<Integer> ans = new ArrayList<>();
  trave(root, ans);

  return ans;
}

private void trave(TreeNode root, List<Integer> ans){
  if(root == null){
    return;
  }

  trave(root.left, ans);
  ans.add(root.val);
  trave(root.right, ans);
}

96. 不同的二叉搜索树 (opens new window)

算法：动态规划

思路：dp[i]：代表有i个节点，其不同的二叉搜索树的数量

public int numTrees(int n) {

    int[] dp = new int[n + 1];
    dp[0] = 1;

    for(int i = 1;i <= n;i ++){
        // i个节点中，以其中一个为父节点，剩余的i - 1个节点即为左右子树节点的数量
        for(int j = 0;j <= i - 1;j ++){
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }

    return dp[n];
}

98. 验证二叉搜索树 (opens new window)

算法：中序遍历

注意：需要用Long.MIN_VALUE，因为题目的最小值为Integer.MIN_VALUE，而二叉搜索树必须是父节点大于左节点，小于右节点

long preVal = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {

    if(root == null){
        return true;
    }

    boolean left = isValidBST(root.left);
    if(root.val <= preVal){
        return false;
    }
    preVal = root.val;
    boolean right = isValidBST(root.right);

    return left && right;
}

101. 对称二叉树 (opens new window)

算法：递归

思路：同时对左右子树反方向递归

public boolean isSymmetric(TreeNode root) {

  return validSym(root.left, root.right);
}

public boolean validSym(TreeNode root1, TreeNode root2){
  if(root1 == null && root2 == null){
    return true;
  }

  if(root1 == null || root2 == null){
    return false;
  }

  return root1.val == root2.val && validSym(root1.left, root2.right) && validSym(root1.right, root2.left);
}

102. 二叉树的层序遍历 (opens new window)

算法：模拟（借助队列数据机构）

注意：不为null的节点才入队

public List<List<Integer>> levelOrder(TreeNode root) {
    Deque<TreeNode> queue = new ArrayDeque<>();

    List<List<Integer>> ans = new ArrayList<>();
    if(root != null){
        queue.offer(root);
    }

    while(!queue.isEmpty()){
        int nums = queue.size();
        List<Integer> subAns = new ArrayList<>();
        for(int i = 1;i <= nums;i ++){
            TreeNode node = queue.poll();
            subAns.add(node.val);

            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        ans.add(subAns);
    }

    return ans;
}

121. 买卖股票的最佳时机 (opens new window)

思路：

• 保存遍历过的最小值，如果有遇到更小的则更新（因为后面卖出肯定比当前的最小值赚更多）
• 每遍历一个数，则计算当天卖出的利益：price[i] - minPrice

public int maxProfit(int[] prices) {

	// 通过最小价格参数，当遇到更小的时候直接更新，因为后面卖出肯定必当前的赚，相当把暴力破解中的非必要遍历剪除了
    int minPrice = prices[0];
    int max = 0;
    for(int i = 0;i < prices.length;i ++){
        if(prices[i] < minPrice){
            minPrice = prices[i];
        }else {
            max = Integer.max(max, prices[i] - minPrice);
        }
    }

    return max;
}

124. 二叉树中的最大路径和 (opens new window)

Todo

算法：后序遍历

思路：递归计算经过当前节点的最大路径和

private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {

  maxPath(root);
  return max;
}

public int maxPath(TreeNode root){
  if(root == null){
    return 0;
  }

  int left = Integer.max(maxPath(root.left), 0);
  int right = Integer.max(maxPath(root.right), 0);

  max = Integer.max(max , left + right + root.val);

  return Integer.max(left, right) + root.val;
}

139. 单词拆分 (opens new window)

算法：动态规划

注意：易忘/错题

public boolean wordBreak(String s, List<String> wordDict) {

    int n = s.length();
    // 前i个字符的拆分能否在字典中查找到
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    Set<String> set = new HashSet<>(wordDict);
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= i;j ++){
            if(dp[j] && set.contains(s.substring(j, i))){
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

141. 环形链表 (opens new window)

思路：快慢指针

思路：快慢指针分别走，如果为环，则肯定会相互，否则则不是

注意：while的判断条件为fast指针的判断即可（类似于滑动窗口）

public boolean hasCycle(ListNode head) {

  ListNode slow = head;
  ListNode fast = head;

  while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;

    if(slow == fast){
      return true;
    }
  }

  return false;
}

*128. 最长连续序列 (opens new window)

算法：哈希表

思路：类似于中心扩列的思路，每次都是从最小的那个开始往后扩列，从而保证时间复杂度为O(n)

public int longestConsecutive(int[] nums) {

  Set<Integer> set = new HashSet<>();
  int ans = 0;

  for(int num : nums){
    set.add(num);
  }

  for(int num : set){
    // 保证从最小的那个数开始往大数查找，对于不是最小的则不进入
    if(!set.contains(num - 1)){
      int subAns = 1;
      int currentNums = num;

      while(set.contains(currentNums + 1)){
        subAns += 1;
        currentNums += 1;
      }

      ans = Integer.max(ans, subAns);
    }
  }

  return ans;
}

142. 环形链表 II (opens new window)

算法：快慢指针

思路：快慢指针同时走，相遇的时候，新添加一个指针p指向头部，并且p指针和慢指针同时走，相遇时即为相交点

注意：while循环只判断fast指针即可（fast != null && fast.next != null)

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next == null){
        return null;
    }

    ListNode fast = head;
    ListNode slow = head;

    fast = fast.next.next;
    slow = slow.next;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;

        if(fast == slow){
            ListNode p = head;
            while(p != slow){
                p = p.next;
                slow = slow.next;
            }

            return p;
        }
    }

    return null;
}

146. LRU 缓存 (opens new window)

思路：HashMap（key为key，value为Node链表） + 链表

class DLinkNode {
    int key;
    int value;

    DLinkNode next;
    DLinkNode prev;

    public DLinkNode(){}
    public DLinkNode(int key, int value){
        this.key = key;
        this.value = value;
    }
}

private Map<Integer, DLinkNode> cache;
private int capacity;
private DLinkNode dummyHead;
private DLinkNode dummyTrail;

public LRUCache(int capacity) {
    this.cache = new HashMap<>();
    this.capacity = capacity;
    dummyHead = new DLinkNode();
    dummyTrail = new DLinkNode();

    dummyHead.next = dummyTrail;
    dummyTrail.prev = dummyHead;
}

public int get(int key) {
    DLinkNode node = cache.get(key);
    if(node == null){
        return -1;
    }

    removeNode(node);
    addNodeToHead(node);

    return node.value;
}

public void put(int key, int value) {
    DLinkNode node = cache.get(key);
    if(node == null){
        if(this.capacity <= cache.size()){
            DLinkNode rmNode = dummyTrail.prev;
            removeNode(rmNode);
            cache.remove(rmNode.key);
        }
        DLinkNode newNode = new DLinkNode(key, value);
        cache.put(key, newNode);
        addNodeToHead(newNode);
    }else {
        removeNode(node);
        addNodeToHead(node);
        node.value = value;
    }
}

private void removeNode(DLinkNode node){
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

private void addNodeToHead(DLinkNode node){
    node.prev = dummyHead;
    node.next = dummyHead.next;
    dummyHead.next = node;
    node.next.prev = node;
}

148. 排序链表 (opens new window)

算法：归并排序

思路：

• 快慢指针确定中间位置，并划分为两段链表进行sort和merge

Todo

152. 乘积最大子数组 (opens new window)

算法：动态规划

思路：

• 分别存储包含当前元素的连续乘积的最大最小值
• 当当前元素小于0时，说明max和min是相反的，则进行swap

public int maxProduct(int[] nums) {

    int max = nums[0];
    int min = nums[0];
    int ans = max;

    for(int i = 1;i < nums.length;i ++){
        if(nums[i] < 0){
            int tmp = max;
            max = min;
            min = tmp;
        }

        max = Integer.max(nums[i], max * nums[i]);
        min = Integer.min(nums[i], min * nums[i]);
        ans = Integer.max(ans, max);
    }

    return ans;
}

155. 最小栈 (opens new window)

思路：双栈保存，分别保存元素和当前元素及其下面所有元素（被压在下面的元素）的最小值

注意：先在min_stk中压入Integer.MAX_VALUE

Deque<Integer> stk;
Deque<Integer> min_stk;

public MinStack() {
    stk = new ArrayDeque<>();
    min_stk = new ArrayDeque<>();
    min_stk.push(Integer.MAX_VALUE);
}

public void push(int val) {
    stk.push(val);
    min_stk.push(Integer.min(val, min_stk.peek()));
}

public void pop() {
    stk.pop();
    min_stk.pop();
}

public int top() {
    return stk.peek();
}

public int getMin() {
    return min_stk.peek();
}

198. 打家劫舍 (opens new window)

算法：动态规划

• 通用版

public int rob(int[] nums) {

    int n = nums.length;
    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = nums[0];

    int max = dp[0][1];
    for(int i = 1;i < n;i ++){
        dp[i][0] = Integer.max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + nums[i];

        max = Integer.max(dp[i][0], dp[i][1]);
    }

    return max;
}

• 优化版（dp只与上一个元素的两个状态有关，可以直接存储上个元素的两个状态）

public int rob(int[] nums) {

    int preRob = nums[0];
    int preUnRob = 0;
    int ans = preRob;

    for(int i = 1;i < nums.length;i ++){
        int rob = nums[i] + preUnRob;
        int unRob = Integer.max(preRob, preUnRob);

        preRob = rob;
        preUnRob = unRob;

        ans = Integer.max(ans, Integer.max(rob, unRob));
    }

    return ans;
}

206. 反转链表 (opens new window)

思路：迭代遍历，保存上个节点

public ListNode reverseList(ListNode head) {

    ListNode preNode = null;
    ListNode p = head;
    while(p != null){
        ListNode temp = p.next;
        p.next = preNode;
        preNode = p;
        p = temp;
    }

    return preNode;
}

207. 课程表 (opens new window)

思路：入度 + 邻接表

• 构建每个课程的邻接表（依赖该课程的课程）
• 计算每个课程的入度（完成该课程需要先完成的课程数量）
• 队列存放入度为0的课程，每完成一个课程则更新其邻接表中的课程的入度

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 保存各个课程的入度（即要选该课程需要先完成几门课程）
    int[] indeg = new int[numCourses];

    // 保存各个课程的邻接表（key：某课程，value：依赖key课程的课程）
    Map<Integer, List<Integer>> edges = new HashMap<>();

    // 初始化
    for(int i = 0;i < numCourses; i ++){
        edges.put(i, new ArrayList<>());
    }

    // 构建邻接表
    for(int[] pre : prerequisites){
        List<Integer> edge = edges.get(pre[1]);
        edge.add(pre[0]);

        indeg[pre[0]] ++;
    }

    // 入度为0的课程入队，队列保存可以直接执行的课程，即没有依赖的课程
    Deque<Integer> queue = new ArrayDeque<>();
    for(int i = 0;i < numCourses; i ++){
        if(indeg[i] == 0){
            queue.offer(i);
        }
    }

    int visited = 0;
    while(!queue.isEmpty()){
        int u = queue.poll();
        visited ++;

        // 每完成一个课程，则依赖该课程的课程的入度 - 1
        for(int e : edges.get(u)){
            indeg[e] --;

            if(indeg[e] == 0){
                queue.offer(e);
            }
        }
    }

    // 如果所有课程都可完成，则必须都会进入一次队列
    return visited == numCourses;
}

208. 实现 Trie (前缀树) (opens new window)

算法：前缀树

注意：Trie trie = this;

Trie[] prefix;
boolean isEnd;

public Trie() {
    prefix = new Trie[27];
}

public void insert(String word) {
    Trie trie = this;
    for(char c : word.toCharArray()){
        if(trie.prefix[c - 'a'] == null){
            trie.prefix[c - 'a'] = new Trie();
        }
        trie = trie.prefix[c - 'a'];
    }
    trie.isEnd = true;
}

public boolean search(String word) {

    Trie trie = this;        
    for(char c : word.toCharArray()){
        if(trie.prefix[c - 'a'] == null){
            return false;
        }
        trie = trie.prefix[c - 'a'];
    }

    return trie.isEnd;
}

public boolean startsWith(String prefix) {
    Trie trie = this;        
    for(char c : prefix.toCharArray()){
        if(trie.prefix[c - 'a'] == null){
            return false;
        }
        trie = trie.prefix[c - 'a'];
    }

    return true;
}

215. 数组中的第K个最大元素 (opens new window)

思路：

• 解法一：快排定位
• 解法二：优先队列

• 快排定位
  • 时间：O(n)
  • 空间：O(1)

public int findKthLargest(int[] nums, int k) {

  int n = nums.length;
  int left = 0;
  int right = n - 1;
  int target = n - k;

  while(true){
    int pIndex = partition(nums, left, right);
    if(pIndex == target){
      return nums[pIndex];
    }else if (pIndex > target){
      right = pIndex - 1;
    }else {
      left = pIndex + 1;
    }
  }
}

private int partition(int[] nums, int left, int right){

  int lt = left;
  int pivot = nums[left];

  for(int i = lt + 1;i <= right;i ++){
    if(nums[i] <= pivot){
      lt ++;
      swap(nums, i, lt);
    }
  }
  swap(nums, left, lt);

  return lt;
}

private void swap(int[] nums, int left, int right){
  int tmp = nums[left];
  nums[left] = nums[right];
  nums[right] = tmp;
}

• 优先队列
  • 时间：O(nlog(k))
  • 空间：O(k)

public int findKthLargest(int[] nums, int k) {
  PriorityQueue<Integer> queue = new PriorityQueue<>();

  for(int i = 0;i < k;i ++){
    queue.offer(nums[i]);
  }

  for(int i = k;i < nums.length;i ++){
    if(queue.peek() < nums[i]){
      queue.poll();
      queue.offer(nums[i]);
    }
  }

  return queue.peek();
}

221. 最大正方形 (opens new window)

算法：动态规划

• 当前符号为1，则dp(i)(j) = Integer.min（dp-left，dp-right，dp-对角） + 1

public int maximalSquare(char[][] matrix) {

  int m = matrix.length;
  int n = matrix[0].length;
  int[][] dp = new int[m][n];
  int max = 0;

  for(int i = 0;i < m;i ++){
    if(matrix[i][0] == '1'){
      dp[i][0] = 1;
      max = 1;
    }
  }

  for(int i = 0;i < n;i ++){
    if(matrix[0][i] == '1'){
      dp[0][i] = 1;
      max = 1;
    }
  }

  for(int i = 1;i < m;i ++){
    for(int j = 1;j < n;j ++){
      if(matrix[i][j] == '1'){
        dp[i][j] = Integer.min(dp[i - 1][j], Integer.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
        max = Integer.max(max, dp[i][j]);
      }
    }
  }

  return max * max;
}

226. 翻转二叉树 (opens new window)

思路：后序遍历

public TreeNode invertTree(TreeNode root) {
  if(root == null){
    return root;
  }

  TreeNode left = invertTree(root.left);
  TreeNode right = invertTree(root.right);

  root.left = right;
  root.right = left;

  return root;
}

234. 回文链表 (opens new window)

思路：

• 解法一：用List先保存链表再判断
  • 空间：O(n)
• 解法二：快慢指针找到中间，reserve后半段，再进行比较
  • 空间：O(1)

public boolean isPalindrome(ListNode head) {
  List<Integer> list = new ArrayList<>();
  ListNode p = head;
  while(p != null){
    list.add(p.val);
    p = p.next;
  }

  int p1 = 0;
  int p2 = list.size() - 1;

  while(p1 < p2){
    if(list.get(p1) != list.get(p2)){
      return false;
    }
    p1 ++;
    p2 --;
  }

  return true;
}

236. 二叉树的最近公共祖先 (opens new window)

算法：后序遍历

思路：后序遍历后

• 当前left为null，则返回right
• 当前right为null，则返回left
• 否则返回root

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if(root == null || root == q || root == p){
    return root;
  }

  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);

  if(left == null){
    return right;
  }

  if(right == null){
    return left;
  }

  return root;
}

*238. 除自身以外数组的乘积 (opens new window)

算法：动态规划

• Left-dp[i]：除了当前元素外左边所有元素的乘积
• Right-dp[i]：除了当前元素外右边所有元素的乘积

思路：左右两遍扫描

• 左扫描：利用返回到数组空间存放dp值
• 右扫描：因为每个dp只跟上一个dp有关，所以用right O(1)的空间存储即可

public int[] productExceptSelf(int[] nums) {

  int n = nums.length;
  int[] ans = new int[n];
  ans[0] = 1;

  for(int i = 1;i < n;i ++){
    ans[i] = ans[i - 1] * nums[i - 1];
  }

  int right = 1;
  for(int i = n - 1;i >= 0;i --){
    ans[i] = ans[i] * right;
    right = right * nums[i];
  }

  return ans;
}

*239. 滑动窗口最大值 (opens new window)

算法：滑动窗口 + 单调队列

思路：

• 队尾（右指针移动更新）：单调栈存放单调递增值（如果队尾的元素小于当前元素，则队尾出队）

• 队头（左指针移动更新）：保证队列中的元素下标都在窗口内

public int[] maxSlidingWindow(int[] nums, int k) {

  Deque<Integer> queue = new ArrayDeque<>();
  int left = 0;
  int right = 0;
  int n = nums.length;
  List<Integer> ans = new ArrayList<>();

  while(right < n){
    int c = nums[right];
    while(!queue.isEmpty() && nums[queue.peekLast()] < c){
      queue.pollLast();
    }
    queue.offer(right);
    right ++;

    while(right - left >= k){
      ans.add(nums[queue.peek()]);

      int d = nums[left];
      left ++;

      // 左指针移动一位，则判断队头是否已经不在窗口内
      if(!queue.isEmpty() && queue.peekFirst() < left){
        queue.pollFirst();
      }
    }
  }

  return ans.stream().mapToInt(i -> i).toArray();
}

240. 搜索二维矩阵 II (opens new window)

思路：从右上角开始遍历

public boolean searchMatrix(int[][] matrix, int target) {
  int i = 0;
  int j = matrix[0].length - 1;

  while(i < matrix.length && j >= 0){
    if(matrix[i][j] == target){
      return true;
    }else if(matrix[i][j] < target){
      i ++;
    }else {
      j --;
    }
  }

  return false;
}

*279. 完全平方数 (opens new window)

算法：动态规划

思路：两层for循环遍历，第二层遍历所有的可能的平方数并取其最小的那个

（如果有动态规划思路了，但是不知道状态转移方程，比如感觉逻辑上有多层嵌套，那么可以尝试使用二层for循环遍历，第一层为1-n的遍历，第二层是基于第一层的遍历的遍历）

public int numSquares(int n) {

  int[] dp = new int[n + 1];
  dp[0] = 0;

  for(int i = 1;i <= n;i ++){
    dp[i] = i;
    for(int j = 0;j * j <= i;j ++){
      dp[i] = Integer.min(dp[i - j*j] + 1, dp[i]);
    }
  }

  return dp[n];
}

283. 移动零 (opens new window)

思路：移动非零元素到左边

public void moveZeroes(int[] nums) {

  int le = 0;
  for(int i = 0;i < nums.length;i ++){
    if(nums[i] != 0){
      int tmp = nums[i];
      nums[i] = nums[le];
      nums[le] = tmp;
      le ++;
    }
  }
}

*287. 寻找重复数 (opens new window)

算法：快慢指针

思路：快慢指针相遇后，再新建一个指针从头和慢指针同时走，当再次相遇时，则说明该点为交叉点（重复值）

public int findDuplicate(int[] nums) {

  int slow = 0;
  int fast = 0;

  slow = nums[slow];
  fast = nums[nums[fast]];

  while(slow != fast){
    slow = nums[slow];
    fast = nums[nums[fast]];
  }

  int p = 0;
  while(p != slow){
    p = nums[p];
    slow = nums[slow];
  }

  return slow;
}

297. 二叉树的序列化与反序列化 (opens new window)

todo

300. 最长递增子序列 (opens new window)

算法：动态规划

思路：

• dp[i]：以i下标元素结尾的最长递增长度

public int lengthOfLIS(int[] nums) {

  int n = nums.length;
  int[] dp = new int[n];
  dp[0] = 1;
  int max = dp[0];

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

  return max;
}

*301. 删除无效的括号 (opens new window)

算法：回溯法

思路：

• 计算需要删除的左括号和右括号的数量（与构造有效括号类似，都是先计算左右括号数量）
• 回溯删除

注意：

• 删除某个字符时，左边字符串应该从0开始：s.substring(0, i) + s.substring(i + 1)
• 需要去重

public List<String> removeInvalidParentheses(String s) {
  int lremove= 0;
  int rremove = 0;

  for(char c : s.toCharArray()){
    if(c == '('){
      lremove ++;
    }else if(c == ')'){
      if(lremove > 0){
        lremove --;
      }else {
        rremove ++;
      }
    }
  }

  List<String> ans = new ArrayList<>();
  backtract(ans, s, lremove, rremove, 0);

  return ans;
}


public void backtract(List<String> ans, String s, int lremove, int rremove, int index){
  if(rremove == 0 && lremove == 0){
    if(valid(s)){
      ans.add(s);
    }
    return;
  }

  for(int i = index;i < s.length();i ++){
    char c = s.charAt(i);

    if(i > 0 && c == s.charAt(i - 1)){
      continue;
    }

    if(c == '(' && lremove > 0){
      backtract(ans, s.substring(0, i) + s.substring(i + 1), lremove - 1, rremove, i);
    }else if(c == ')' && rremove > 0){
      backtract(ans, s.substring(0, i) + s.substring(i + 1), lremove, rremove - 1, i);
    }
  }
}

private boolean valid(String s){
  int cnt = 0;
  for(char c : s.toCharArray()){
    if(c == '('){
      cnt ++;
    }else if(c == ')'){
      if(cnt > 0){
        cnt --;
      }else {
        return false;
      }
    }
  }

  return cnt == 0;
}

309. 最佳买卖股票时机含冷冻期 (opens new window)

算法：动态规划

思路：

• dp(i)(j)：表示某天过后为某个状态的最大收益
  • 买入：max(昨天买入，今天买入)
  • 卖出：max(昨天买出，昨天冷冻期)
  • 冷冻期：今天卖出

public int maxProfit(int[] prices) {

  int n = prices.length;
  int[][] dp = new int[n][3];

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

  int max = 0;
  for(int i = 1;i < n;i ++){
    // 今天没有执行操作，卖出状态可能来自上个卖出状态，也可能由冷冻期转化而来
    dp[i][0] = Integer.max(dp[i - 1][0], dp[i - 1][2]);
    // 今天执行了买入操作，或者上个状态就是买入状态
    dp[i][1] = Integer.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    // 今天执行了卖出操作
    dp[i][2] = dp[i - 1][1] + prices[i];

    max = Integer.max(max, Integer.max(dp[i][0], dp[i][2]));
  }

  return max;
}

312. 戳气球 (opens new window)

todo

*322. 零钱兑换 (opens new window)

算法：动态规划

重点：动态规划基本的流程

• 定义dp，初始化dp[0]
• 外层基本循环，内层（循环）选择状态及状态转移
• 求最值

注意：此处的dp[i]需要初始化为：dp[i] = amount + 1;，因为需要考虑没有满足硬币的情况

public int coinChange(int[] coins, int amount) {

  int[] dp = new int[amount + 1];
  dp[0] = 0;

  for(int i = 1;i <= amount;i ++){
    dp[i] = amount + 1;
    for(int coin : coins){
      if(i - coin >= 0){
        dp[i] = Integer.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

337. 打家劫舍 III (opens new window)

算法：动态规划

注意：新建定义一个函数，返回值为int数组：表示当前节点偷与不偷两种状态能偷取到的最大金额

public int rob(TreeNode root) {

  int[] res = robIn(root);
  return Integer.max(res[0], res[1]);
}

public int[] robIn(TreeNode root){
  if(root == null){
    return new int[2];
  }

  int[] left = robIn(root.left);
  int[] right = robIn(root.right);

  int[] ans = new int[2];
  ans[0] = Integer.max(left[0], left[1]) + Integer.max(right[0], right[1]);
  ans[1] = left[0] + right[0] + root.val;

  return ans;
}

338. 比特位计数 (opens new window)

算法：动态规划

思路：

• dp[i]：数字i的比特位为1的个数

• 分为奇数和偶数两种情况分析，获取状态转移方程

  • 奇数：dp[上个偶数：奇数 - 1] + 1

  • 偶数：与**dp(偶数 / 2)**相同，因为偶数最后一位本来就是0，/2即右移一位

public int[] countBits(int n) {

  int[] dp = new int[n + 1];
  dp[0] = 0;

  for(int i = 1;i <= n;i ++){
    if(i % 2 == 0){
      dp[i] = dp[i / 2];
    }else {
      dp[i] = dp[i - 1] + 1;
    }
  }

  return dp;
}

347. 前 K 个高频元素 (opens new window)

思路：

• map统计每个数字的频率
• List数组存储，index为频率，存储的元素为List，有重复的则继续往List添加，画成图的话就是一个数组链表，存储着链表的数组
• 从后往前遍历该数组，遇到非null的则添加，直到ans的大小等于k（即ans的大小小于k都可继续遍历）

public int[] topKFrequent(int[] nums, int k) {

  Map<Integer, Integer> countMap = new HashMap<>();
  int n = nums.length;

  for(int i = 0;i < n;i ++){
    countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);
  }

  List[] list = new List[n + 1];
  for(int key : countMap.keySet()){
    int index = countMap.get(key);
    if(list[index] == null){
      list[index] = new ArrayList<>();
    }
    list[index].add(key);
  }

  List<Integer> ans = new ArrayList<>();
  for(int i = list.length - 1; i >= 0 && ans.size() < k;i --){
    if(list[i] != null){
      ans.addAll(list[i]);
    }
  }

  return ans.stream().mapToInt(i -> i).toArray();
}

394. 字符串解码 (opens new window)

模拟

思路：两个栈分别存储字符和数字，两个变量分别存储当前字符串和数字

• 遇到字符：添加到字符变量
• 遇到数字：添加到数字变量
• 遇到[：当前字符串和数字入栈，并初始化
• 遇到]：提取数字栈中数字，根据其值复制多份当前res，然后将字符串栈尾部取出（str），res = str + res，表示子[]已经执行完，继续下一个[]的执行。

public String decodeString(String s) {

  Deque<StringBuilder> stk1 = new ArrayDeque<>();
  Deque<Integer> stk2 = new ArrayDeque<>();
  StringBuilder res = new StringBuilder();
  int mulNums = 0;

  for(int i = 0;i < s.length();i ++){
    char c = s.charAt(i);
    if(c >= '0' && c <= '9'){
      mulNums = mulNums * 10 + (c - '0');
    }else if(c >= 'a' && c <= 'z'){
      res.append(c);
    }else if(c == '['){
      stk1.push(res);
      stk2.push(mulNums);
      mulNums = 0;
      res = new StringBuilder();
    }else if(c == ']'){
      int n = stk2.pop();
      StringBuilder temp = new StringBuilder();
      for(int j = 1;j <= n;j ++){
        temp.append(res);
      }
      res = stk1.pop().append(temp);
    }
  }

  return res.toString();

406. 根据身高重建队列 (opens new window)

易忘题

思路：排序后插入

• 排序：先按身高降序排序，如果身高相同，按高人数升序排序

• 插入：按照高人数位置插入

public int[][] reconstructQueue(int[][] people) {
  Arrays.sort(people, (o1, o2) -> (o1[0] != o2[0] ? o2[0] - o1[0] : o1[1] - o2[1]));

  List<int[]> ans = new ArrayList<>();
  for(int[] person : people){
    ans.add(person[1], person);
  }

  return ans.toArray(new int[ans.size()][2]);
}

**416. 分割等和子集 (opens new window)

易忘题/重点题

算法：动态规划

注意：需要防止重复选择问题（关键），这道题跟零钱兑换问题最关键的不同是物品只能被拿一次，所以需要两个状态去维护，即dp[][]，而零钱兑换零钱是可以无限取的，所以是`dp[]``。

思路：转化为0-1背包问题，并且是只能取一次的0-1背包

• dp[i][j]：表示前i个物品，有j的容量，能否放满。
  • 选择当前物品：则dp[i][j] = dp[i - 1][j - nums[i]]
  • 不选择当前物品：则dp[i][j] = dp[i-1][j]

public boolean canPartition(int[] nums) {

  int sum = Arrays.stream(nums).sum();
  if(sum % 2 != 0){
    return false;
  }
	
  sum = sum / 2;
  int n = nums.length;
  boolean[][] dp = new boolean[n][sum + 1];
	
  // 初始化第一行
  for(int i = 0;i < n;i ++){
    dp[i][0] = true;
  }
	
  // 初始化第一列
  if(nums[0] <= sum) dp[0][nums[0]] = true;
	
  // 遍历第一个状态
  for(int i = 1;i < n;i ++){
    // 遍历第二个状态
    for(int j = 1;j <= sum;j ++){
      dp[i][j] = dp[i - 1][j];
      if(j - nums[i] >= 0) dp[i][j] |= dp[i - 1][j - nums[i]]; 
    }
  }

  return dp[n - 1][sum];
}

437. 路径总和 III (opens new window)

算法：前缀树（Map） + 回溯法

思路：

• 前序遍历树，记录每个根节点到当前节点到路径和及其频率
• 当前路径和为6，目标路径和为2，则从前缀树中获取路径和为4的频率，即为子答案，将所有子答案相加即为结果

Map<Long, Integer> prefix = new HashMap<>();
int count = 0;
public int pathSum(TreeNode root, int targetSum) {
  prefix.put(0L, 1);
  backtract(root, targetSum, 0L);

  return count;
}

public void backtract(TreeNode root, int targetSum, Long currentSum){
  if(root == null){
    return;
  }

  currentSum += root.val;
  count += prefix.getOrDefault(currentSum - targetSum, 0);
  prefix.put(currentSum, prefix.getOrDefault(currentSum, 0) + 1);

  backtract(root.left, targetSum, currentSum);
  backtract(root.right, targetSum, currentSum);

  prefix.put(currentSum, prefix.get(currentSum) - 1);
  currentSum -= root.val;
}

438. 找到字符串中所有字母异位词 (opens new window)

算法：滑动窗口（框架）

思路：

• 一个当前窗口+一个需要的字符的窗口
• valid：当前已经满足要求的字符数量，与need的大小相同时即窗口中所有字符都满足
• 左右指针则根据题目进行移动

public List<Integer> findAnagrams(String s, String p) {

  Map<Character, Integer> windows = new HashMap<>();
  Map<Character, Integer> need = new HashMap<>();
  List<Integer> ans = new ArrayList<>();
  int valid = 0;
  int left = 0;
  int right = 0;

  for(char c : p.toCharArray()){
    need.put(c, need.getOrDefault(c, 0) + 1);
  }

  while(right < s.length()){

    char c = s.charAt(right);
    if(need.containsKey(c)){
      windows.put(c, windows.getOrDefault(c, 0) + 1);
      if(windows.get(c).equals(need.get(c))){
        valid ++;
      }
    }
    right ++;

    while(right - left >= p.length()){
      if(valid == need.size()){
        ans.add(left);
      }
      char d = s.charAt(left);
      if(need.containsKey(d)){
        if(windows.get(d).equals(need.get(d))){
          valid --;
        }
        windows.put(d, windows.get(d) - 1);
      }
      left ++;
    }
  }

  return ans;
}

448. 找到所有数组中消失的数字 (opens new window)

思路：

• 遍历所有元素，在其对应的下标的元素都加上n
• 小于n的元素的下标说明没有对应的元素

public List<Integer> findDisappearedNumbers(int[] nums) {

  int n = nums.length;
  for(int i = 0;i < n;i ++){
    nums[(nums[i] - 1) % n] += n;
  }

  List<Integer> ans = new ArrayList<>();
  for(int i = 0;i < n;i ++){
    if(nums[i] <= n){
      ans.add(i + 1);
    }
  }

  return ans;
}

461. 汉明距离 (opens new window)

思路：位运算

• 异或运算可以得到位为1即说明该位不同
• 右移动并统计1的数量

public int hammingDistance(int x, int y) {

  int z = x ^ y;
  int count = 0;

  while(z != 0){
    count += z & 1;
    z = z >> 1;
  }

  return count;
}

494. 目标和 (opens new window)

算法：

• 解法一：回溯法
• 解法二：动态规划

• 回溯解法

int count = 0;
public int findTargetSumWays(int[] nums, int target) {

  backtract(nums, target, 0, 0);

  return count;
}

public void backtract(int[] nums, int target, int currentSum, int index){
  if(index == nums.length){
    if(target == currentSum){
      count ++;
    }
    return;
  }

  int num = nums[index];
  backtract(nums, target, currentSum - num, index + 1);
  backtract(nums, target, currentSum + num, index + 1);
}

538. 把二叉搜索树转换为累加树 (opens new window)

算法：逆向中序遍历

int sum = 0;
public TreeNode convertBST(TreeNode root) {
  if(root == null){
    return null;
  }

  TreeNode left = convertBST(root.right);
  sum += root.val;
  root.val = sum;
  TreeNode right = convertBST(root.left);

  return root;
}

543. 二叉树的直径 (opens new window)

思路：后序遍历

int max = 0;
public int diameterOfBinaryTree(TreeNode root) {

  trave(root);

  return max;
}

public int trave(TreeNode root){
  if(root == null){
    return 0;
  }

  int left = trave(root.left);
  int right = trave(root.right);

  max = Integer.max(left + right, max);

  return Integer.max(left, right) + 1;
}

560. 和为 K 的子数组 (opens new window)

算法：前缀和

思路：计算统计连续的元素，路径和的个数的，可以考虑前缀和

• 初始化prefix -（0，1）
• 计算currentSum
• 计算prefix中的（currentSum - target)的count
• prefix put currentSum count

public int subarraySum(int[] nums, int k) {

  Map<Integer, Integer> prefix = new HashMap<>();
  prefix.put(0, 1);

  int currentSum = 0;
  int count = 0;
  for(int i = 0;i < nums.length;i ++){
    currentSum += nums[i];
    count += prefix.getOrDefault(currentSum - k, 0);
    prefix.put(currentSum, prefix.getOrDefault(currentSum, 0) + 1);
  }

  return count;
}

581. 最短无序连续子数组 (opens new window)

思路：

• 从左边到右边维护最大值及right（需要排序的连续元素的右指针），如果大于当前max，则说明正常，继续走，如果小于，则说明是被打乱的元素，更新right。
• 同理更新min和left

public int findUnsortedSubarray(int[] nums) {

  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  int right = -1;
  int left = -1;
  int n = nums.length;

  for(int i = 0;i < n;i ++){

    if(nums[i] >= max){
      max = nums[i];
    }else {
      right = i;
    }

    if(nums[n - 1 - i] <= min){
      min = nums[n - 1 - i];
    }else {
      left = n - 1 - i;
    }
  }

  return right == -1 ? 0 : right - left + 1;
}

617. 合并二叉树 (opens new window)

思路：

• 合并root value
• 合并左右子树到root1
• 返回合并后的root1

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  if(root1 == null){
    return root2;
  }

  if(root2 == null){
    return root1;
  }

  root1.val = root1.val + root2.val;
  TreeNode left = mergeTrees(root1.left, root2.left);
  TreeNode right = mergeTrees(root1.right, root2.right);

  root1.left = left;
  root1.right = right;

  return root1;
}

647. 回文子串 (opens new window)

算法：中心扩列

public int countSubstrings(String s) {

  int ans = 0;
  for(int i = 0;i < s.length();i ++){

    ans += countSubAns(s, i, i);
    if(i > 0){
      ans += countSubAns(s, i - 1, i);
    }
  }

  return ans;
}

private int countSubAns(String s, int left, int right){

  int cnt = 0;
  while(left >= 0 && right < s.length()){
    if(s.charAt(left) == s.charAt(right)){
      cnt ++;
      left --;
      right ++;
    }else {
      return cnt;
    }
  }

  return cnt;
}

739. 每日温度 (opens new window)

算法：单调栈

对于计算“下一个变化值”的这种题目，一般用单调栈或单调队列

public int[] dailyTemperatures(int[] temperatures) {

  Deque<Integer> stk = new ArrayDeque<>();
  int n = temperatures.length;
  int[] ans = new int[n];

  for(int i = 0;i < n;i ++){
    while(!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]){
      int index= stk.pop();
      ans[index] = i - index;
    }
    stk.push(i);
  }

  return ans;
}