hot 100

1.两数之和-简单题-哈希表的初级应用

力扣题目链接
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

使用哈希表，每遍历一个元素，先在哈希 Map 中查找是否存在 target - nums[i]，若存在，则返回由二者下标组成的数组；若不存在，则将 nums[i] 与 i 加入哈希 Map，继续探测下一个元素。

class Solution {
    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])) {
                int j = map.get(target - nums[i]);
                return new int[] { i, j };
            }
            map.put(nums[i], i);
        }
        return new int[] { -1, -1 };
    }
}

2.字母异位词分组-中等题-哈希表

力扣题目链接
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

用哈希表存储数据，键为排序后的字符串（注意：需要先转成 char 数组才能排序）。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans=new ArrayList<>();
        Map<String,List<String>> map=new HashMap<>();
        for(String str:strs){
            char[] temp=str.toCharArray();
            Arrays.sort(temp);
            String ss=new String(temp);
            if(map.containsKey(ss)){
                map.get(ss).add(str);
            }else{
                List<String> path=new ArrayList<>();
                path.add(str);
                map.put(ss,path);
            }
        }
        for(String str:map.keySet()){
            ans.add(map.get(str));
        }
        return ans;
    }
}

3.最长连续序列-中等题-哈希表

力扣题目链接
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

核心是时间复杂度要求 O(n)，所以考虑空间换时间，使用哈希表去存储每一个元素（顺便去重，所以之后遍历是遍历哈希集合而不是原数组）。当遇到一个元素时，检查该元素 - 1 是否存在，若存在则跳过，原因毋庸置疑。若不存在，则依次检查该元素 + 1 是否存在。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int num : set) {
            int next = num + 1;
            if (set.contains(num - 1)) {
                continue;
            }
            while (set.contains(next)) {
                next++;
            }
            ans = Math.max(ans, next - num);
        }
        return ans;
    }
}

4.移动零-简单题-双指针的最简单应用

力扣题目链接
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

双指针，当 right 指针不为 0 时，将其放在 left 指针处。也就是说，right 指针找到每一个不为 0 的元素并把他们按原顺序放到正确的位置上。

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
        }
    }
}

5.盛最多水的容器-中等题-双指针结合一点点贪心的思想

力扣题目链接
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

为什么说有一点点贪心的思想？因为盛水最多，其实就是形成的矩阵面积最大，矩阵面积等于底乘高，先让底最长（即双指针指向数组两端），求出当前面积。如果想让盛水量比当前还多，那么必须在向内收缩的时候（因为我们不能向外收缩了呀），找到比 Math.min(height[right],height[left]) 更大的（短板效应），因为我们必须找到比当前更短的板子更长的一个板子。

class Solution {
    public int maxArea(int[] height) {
        int ans = Integer.MIN_VALUE;
        int left = 0, right = height.length - 1;
        while (left <= right) {
            int cur = (right - left) * Math.min(height[right], height[left]);
            ans = Math.max(cur, ans);
            if (height[right] < height[left]) {
                right--;
            } else {
                left++;
            }
        }
        return ans;
    }
}

3.无重复字符的最长字串-中等题-典型的滑动窗口

力扣题目链接
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

滑动窗口，初始化 left 和 right，并且借助 HashSet 判断重复。在遍历的过程中，遇到不重复的字符则 right++，遇到重复的字符则 left++ 直到窗口内没有重复，顺便在 right++ 的过程中计算长度即可。（毕竟 left++ 代表着长度缩短）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set=new HashSet<>();
        int left=0,right=0;
        int ans=0;
        while(right<s.length()){
            if(set.contains(s.charAt(right))){
                set.remove(s.charAt(left));
                left++;
            }else{
                set.add(s.charAt(right));
                right++;
                ans=Math.max(ans,right-left);
            }
        }
        return ans;
    }
}

4.和为 K 的子数组-中等题-前缀和配哈希表

力扣题目链接
给你一个整数数组 nums 和一个整数 k，请你统计返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

虽然这道题暴力也能破解，但是不保证暴力可以拿到 offer，所以还是前缀和配哈希表解决吧。具体来说，前缀和可以快速计算数组中两个元素之间区间的和。我们只需要在遍历的时候，一边计算前缀和，一边在哈希表中查找是否存在 k - 当前前缀和，一边把当前前缀和记录在哈希表中即可。

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);//别忘记
        int sum = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

5.最大子数组和-中等题-动态规划可以搞定

力扣题目链接
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

dp 数组表示以 i 结尾的序列的最大子数组和，不难推导 dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);在计算过程中不断更新 ans = Math.max(dp[i], ans) 即可。

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int ans = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

6.搜索二维矩阵Ⅱ-中等题-类似于二分查找

力扣题目链接
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

从右上角开始搜索，若当前元素大于 target，则最后一列可以不搜了；反之第一行可以不搜了。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i <= matrix.length - 1 && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}

7.环形链表Ⅱ-中等题-都快背会了

力扣题目链接
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

快慢指针，运动到直到二者相遇，然后将慢指针置于 head 处，二者以相同速度运动，下次相遇的结点便是入环结点。

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

8.二叉树的直径-简单题-树的题无非就是递归

力扣题目链接
给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root。两节点之间路径的长度由它们之间边数表示。

递归查找答案，递归返回值是当前结点能够贡献的最大长度。在递归过程中，计算当前结点左侧最大贡献 + 当前结点右侧最大贡献，并更新 ans。别忽略，null结点的贡献是 -1 不是 0。

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return -1;
        }
        int left = dfs(root.left) + 1;
        int right = dfs(root.right) + 1;
        ans = Math.max(ans, left + right);
        return Math.max(left, right);
    }
}

9.只出现一次的数字-简单题-异或运算规则

力扣题目链接
给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

自身和自身异或运算为 0，0 和任何数运算得任何数，所以全部异或一遍，答案就是那个只出现一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
        int ans=0;
        for(int num:nums){
            ans^=num;
        }
        return ans;
    }
}

10.多数元素-简单题-完全的技巧

力扣题目链接
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

排序之后最中间的那个元素就是多数元素。

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

14.找到字符串中所有字母异位词-中等题-滑动窗口

力扣题目链接
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

关键的问题是何时该判断是否是字母异位词呢？是 right - left + 1 = p.length() 的时候。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int[] cntp = new int[26];
        int[] cnts = new int[26];
        for (char c : p.toCharArray()) {
            cntp[c - 'a']++;
        }
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            cnts[s.charAt(right) - 'a']++;
            if (right - left + 1 == p.length()) {
                if (aid(cnts, cntp)) {
                    list.add(left);
                    cnts[s.charAt(left) - 'a']--;
                    left++;
                } else {
                    cnts[s.charAt(left) - 'a']--;
                    left++;
                }
            }
        }
        return list;
    }

    private boolean aid(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }
}

15.颜色分类-中等题-相当于移动零

力扣题目链接
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

确实和移动零那道题一模一样，双指针，每次都把正确的元素放在该放在的位置上（其实是交换到）。

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[left];
                nums[left] = temp;
                left++;
            }
        }
        for (int i = left; i < nums.length; i++) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[left];
                nums[left] = temp;
                left++;
            }
        }
    }
}

16.寻找重复数-中等题-相当于判断环形

力扣题目链接
给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。

关键在于快慢指针的起始在于 fast = slow = 0，而不是 nums[0]。（其实一个从 nums[0] 开始，另一个从 nums[nums[0]] 开始也可以），如果都初始化为 nums[0]，如果 nums[0] == 1，那么快指针下一步走到nums[1]，慢指针下一步也走到 nums[1]，则无限循环。

class Solution {
    public int findDuplicate(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return -1;
        }
        if (nums.length == 2) {
            return nums[0];
        }
        int fast = nums[nums[0]], slow = nums[0];
        do {
            fast = nums[nums[fast]];
            slow = nums[slow];
        } while (fast != slow);
        slow = 0;
        do {
            slow = nums[slow];
            fast = nums[fast];
        } while (fast != slow);
        return fast;
    }
}

17.下一个排列-中等题-纯技巧没有感情

力扣题目链接
给你一个整数数组 nums，找出 nums 的下一个排列。

先找第一个顺序对，再从后往前找第一个比顺序对起始位大的数字，交换二者，随后翻转后序即可。（注意：如果没找到顺序对，不用进入第二个循环，写代码的时候别忘记）

class Solution {
    public void nextPermutation(int[] nums) {
        int start = -1;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                start = i - 1;
                break;
            }
        }
        if (start != -1) {
            for (int j = nums.length - 1; j > start; j--) {
                if (nums[j] > nums[start]) {
                    int temp = nums[j];
                    nums[j] = nums[start];
                    nums[start] = temp;
                    break;
                }
            }
        }
        reverse(nums, start + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[end];
            nums[end] = nums[start];
            nums[start] = temp;
            start++;
            end--;
        }
    }
}

18.数组中的第 K 个最大元素-中等题-堆的最简单应用

力扣题目链接
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

把元素都存放在堆中（大顶堆），挨个 poll 出来就好了。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (b - a));
        for (int num : nums) {
            queue.add(num);
        }
        int ans = 0;
        while (k > 0) {
            ans = queue.poll();
            k--;
        }
        return ans;
    }
}

19.前 K 个高频元素-中等题-堆和哈希表的配合

力扣题目链接
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

将元素和出现的次数存放在哈希表中，然后重写优先队列的排序规则，挨个取出来即可。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (int num : map.keySet()) {
            queue.offer(num);
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll();
        }
        return ans;
    }
}

20.数据流的中位数-困难题-两个堆配合

力扣题目链接
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象
void addNum(int num) 将数据流中的整数 num 添加到数据结构中
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受

一个大顶堆，存放比中位数小的，存放的数字更多。一个小顶堆。加入元素的时候，考虑两种情况，即大顶堆小顶堆元素数目不一致，和大顶堆小顶堆元素数目一致。

class MedianFinder {
    PriorityQueue<Integer> A = new PriorityQueue<>((a, b) -> (b - a));//大顶堆，存放比中位数小的，放的数更多
    PriorityQueue<Integer> B = new PriorityQueue<>();

    public MedianFinder() {

    }

    public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        return A.size() == B.size() ? (A.peek() + B.peek()) / 2.0 : A.peek();
    }
}

21.寻找两个正序数组的中位数-困难题-归并排序而已

力扣题目链接
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

归并排序，根据数目奇偶性判断中位数应该是哪个。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        int p1 = 0, p2 = 0;
        // 合并两个数组
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] < nums2[p2]) {
                list.add(nums1[p1]);
                p1++;
            } else {
                list.add(nums2[p2]);
                p2++;
            }
        }
        // 添加 nums1 中剩余的元素
        while (p1 < nums1.length) {
            list.add(nums1[p1]);
            p1++;
        }
        // 添加 nums2 中剩余的元素
        while (p2 < nums2.length) {
            list.add(nums2[p2]);
            p2++;
        }

        int size = list.size();
        if (size % 2 == 0) {
            // 偶数个元素，取中间两个元素的平均值
            return (list.get(size / 2 - 1) + list.get(size / 2)) / 2.0;
        } else {
            // 奇数个元素，取中间元素
            return list.get(size / 2);
        }
    }
}

22.搜索插入位置-简单题-二分查找模板

力扣题目链接
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

二分查找模板，注意条件 left <= right。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return left;
    }
}

23.在排序数组中查找元素的第一个位置和最后一个位置-中等题-其实也是二分查找

力扣题目链接
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

两个二分查找，核心思路是查查查，先查最左，再查最右。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int start = -1, end = -1;
        //先找最左位置
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                start = mid;
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                end = mid;
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[] { start, end };
    }
}

24.搜索旋转排序数组-中等题

力扣题目链接
给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

数组有序（起码是部分有序），时间复杂度 O(log n)，显然是二分查找。关键在于怎么查？那需要确定是左半部分有序，还是右半部分有序，二者查找的思路是不一样的。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            //左半部分有序，注意等于号
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { //右半部分有序
                if (nums[mid] < target && nums[right] >= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

25.寻找旋转排序数组中的最小值-中等题-抽象的二分查找

力扣题目链接
给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

二分查找有个很有趣的思路，二分查找其实就是每次淘汰一半的数字，所以二分的时间复杂度是 O(log n)。对于一个旋转数组，如果中间的数字比右侧指针的数字大，那么最小值一定在右半部分。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[left];
    }
}

26.爬楼梯-简单题-动态规划的入门

力扣题目链接
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

没什么好说的，只需要注意 dp[0] = 1。

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

27.杨辉三角-简单题-不用数组的动态规划

力扣题目链接
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

只需要注意开头和末尾都是 1，所以循环不需要从开头开始，不需要在末尾结束。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(1);
        ans.add(path);
        for (int i = 1; i < numRows; i++) {
            path = new ArrayList<>();
            path.add(1);
            for (int j = 1; j < i; j++) {
                path.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
            path.add(1);
            ans.add(path);
        }
        return ans;
    }
}

28.打家劫舍-中等题-动态规划

力扣题目链接
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

dp 公式：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])。

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];
        if (nums.length == 1) {
            return nums[0];
        }
        dp[0] = nums[0];
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

29.完全平方数-中等题-动态规划

力扣题目链接
给你一个整数 n，返回和为 n 的完全平方数的最少数量。

做的时候忘记内层循环应该是 j * j <= i 了，可恶可恶。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int ans = i + 1;
            for (int j = 1; j * j <= i; j++) {
                ans = Math.min(ans, dp[i - j * j] + 1);
            }
            dp[i] = ans;
        }
        return dp[n];
    }
}

30.零钱兑换-中等题-动态规划

力扣题目链接
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

当 i - coins[j] >= 0 时，一定需要更新 dp[i] 吗？显然不是的，因为 dp[i - coins[j]] 可能是 Integer.MAX_VALUE，也就是凑不出来的！

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            int ans = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    ans = Math.min(ans, dp[i - coins[j]] + 1);
                }
            }
            dp[i] = ans;
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

31.单词拆分-中等题-动态规划有点抽象

力扣题目链接
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

什么情况下 dp[i] 可以为 true？当且仅当长度大于当前遍历的字符串，且最后面的字符子串和当前字符串一模一样，且前面的字符字串的 dp 值已经为 true。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String str : wordDict) {
                if (i >= str.length() && s.substring(i - str.length(), i).equals(str) && dp[i - str.length()]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

32.最长递增子序列-中等题-动态规划

力扣题目链接
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

最长严格递增子序列一定必须以最末尾的数字为尾吗？显然是不一定的，例如 1 2 3 4 5 1，显然 dp[5] = 1，但它根本不是答案。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int len = 1;
        for (int i = 1; i < nums.length; i++) {
            int ans = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    ans = Math.max(dp[j] + 1, ans);
                }
            }
            dp[i] = ans;
            len = Math.max(len, dp[i]);
        }
        return len;
    }
}

33.乘积最大子数组-中等题-背诵题多看看

力扣题目链接
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

定义 max 和 imax 和 imin，在遍历的过程中如果遇到负数，就交换 imax 和 imin，然后再计算 imax 和 imin，同时更新 max。

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(imax, max);
        }
        return max;
    }
}

34.分割等和子集-中等题-多维动态规划更好理解

力扣题目链接
给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

多维动态规划更好理解吧，可以选当前数字或者不选当前数字。（以当前要凑的数字和当前遍历的数组元素大小分类讨论）

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i < nums.length + 1; i++) {
            for (int j = 0; j < target + 1; j++) {
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length][target];
    }
}

35.最长有效括号-困难题-算了吧别动归了

力扣题目链接
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

针对每个起始位置，当遇到 help 小于 0，那就无论如何都不会匹配了，换下一个起始位置开始。

class Solution {
    public int longestValidParentheses(String s) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            int j = i;
            int help = 0;
            while (j < s.length()) {
                if (s.charAt(j) == '(') {
                    help++;
                } else {
                    help--;
                }
                if (help == 0) {
                    ans = Math.max(ans, j - i + 1);
                    j++;
                } else if (help > 0) {
                    j++;
                } else {
                    break;
                }
            }
        }
        return ans;
    }
}

36.LRU 缓存-中等题-太经典了

力扣题目链接
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字

移动到头需要删除以及加到头，再加一个删除尾，四个辅助函数来回用。

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node() {
        }

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

    private int capacity;
    private int size;
    private HashMap<Integer, Node> map = new HashMap<>();
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            Node newnode = new Node(key, value);
            map.put(key, newnode);
            addToHead(newnode);
            size++;
            if (size > capacity) {
                Node nod = removeTail();
                map.remove(nod.key);
                size--;
            }
        }
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private Node removeTail() {
        Node node = tail.prev;
        remove(node);
        return node;
    }
}

37.路径总和Ⅲ-中等题-有点抽象（两个递归）

力扣题目链接
给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。

一个统计从当前节点开始路径和等于给定值的路径数量（dfs），一个统计二叉树里路径和等于给定值的路径数量（pathSum）。

class Solution {

    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int ans = dfs(root, targetSum);
        ans += pathSum(root.left, targetSum);
        ans += pathSum(root.right, targetSum);
        return ans;
    }

    private int dfs(TreeNode root, long targetSum) {
        int len = 0;
        if (root == null) {
            return len;
        }
        if (root.val == targetSum) {
            len++;
        }
        len += dfs(root.left, targetSum - root.val);
        len += dfs(root.right, targetSum - root.val);
        return len;
    }
}

38.二叉树中的最大路径和-困难题-和最长路径有点相似

力扣题目链接
二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root，返回其最大路径和。

关键是有负值，在计算每个结点左右链能产生的最大值时，如果左右链为负数，那还不如不要，所以需要和零进行比较。

class Solution {
    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = Math.max(dfs(root.left), 0);
        int rightMax = Math.max(dfs(root.right), 0);
        ans = Math.max(ans, leftMax + rightMax + root.val);
        return Math.max(leftMax, rightMax) + root.val;
    }
}

39.买卖股票的最佳时机-简单题-我就用动归

力扣题目链接
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

用动态规划，dp 数组中存储右侧最大高度，遍历的过程中求答案。

class Solution {
    public int maxProfit(int[] nums) {
        int[] dp = new int[nums.length];
        int ans = 0;
        dp[nums.length - 1] = nums[nums.length - 1];
        for (int j = nums.length - 2; j >= 0; j--) {
            dp[j] = nums[j] >= dp[j + 1] ? nums[j] : dp[j + 1];
            ans = Math.max(dp[j] - nums[j], ans);
        }
        return ans;
    }
}

40.电话号码的字母组合-中等题-回溯算法

力扣题目链接
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

考虑清楚第一次能选的，循环代表着每次能选的字母，递归代表着下次去哪里找能选的字母。

class Solution {
    List<String> ans = new ArrayList<>();
    String path = new String();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return ans;
        }
        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");
        trace(digits, 0, map);
        return ans;
    }

    private void trace(String digits, int start, Map<Character, String> map) {
        if (start == digits.length()) {
            ans.add(new String(path));
            return;
        }
        char digit = digits.charAt(start);
        for (int i = 0; i < map.get(digit).length(); i++) {
            path += map.get(digit).charAt(i);
            trace(digits, start + 1, map);
            path = path.substring(0, path.length() - 1);
        }
    }
}

41.组合总和-中等题-回溯算法

力扣题目链接
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。

记得先排序，不然可能递归压根不会发生。（其实是因为剪枝是依赖排序的，只有当前不满足条件，可以推出之后也不满足条件，才可以剪枝，不然剪什么？）

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        trace(candidates, target, 0);
        return ans;
    }

    private void trace(int[] nums, int target, int start) {
        if (target == 0) {
            ans.add(new ArrayList(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > target) {
                break;
            }
            path.add(nums[i]);
            trace(nums, target - nums[i], i);
            path.remove(path.size() - 1);
        }
    }
}

42.分割回文串-中等题-回溯算法有点抽象

力扣题目链接
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

其实是选隔间。

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        trace(s, 0);
        return ans;
    }

    private void trace(String s, int start) {
        if (start == s.length()) {
            ans.add(new ArrayList(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (help(sub)) {
                path.add(sub);
                trace(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean help(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

43.子集-中等题-回溯算法

力扣题目链接
给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

在回溯的过程中每次都把 path 记录下来即可。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        trace(nums, 0);
        return ans;
    }

    private void trace(int[] nums, int start) {
        ans.add(new ArrayList(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            trace(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

非 hot 100

快速排序

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 分区操作，获取基准元素的最终位置
        int pivotIndex = partition(arr, low, high);
        // 递归排序左子序列
        quickSort(arr, low, pivotIndex - 1);
        // 递归排序右子序列
        quickSort(arr, pivotIndex + 1, high);
    }
}
private static int partition(int[] arr, int low, int high) {
    // 选择最后一个元素作为基准
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准元素放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

组合-中等题-回溯模板题目

力扣题目链接
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

考虑清楚横向遍历的方案，以及递归的深度（截止条件）。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        trace(1, n, k);
        return ans;
    }

    private void trace(int i, int n, int k) {
        if (path.size() == k) {
            ans.add(new ArrayList(path));
            return;
        }
        for (int j = i; j <= n; j++) {
            path.add(j);
            trace(j + 1, n, k);
            path.remove(path.size() - 1);
        }
    }
}

组合总和Ⅲ-中等题-依然回溯

力扣题目链接
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次

递归深度由 path.size() == k 和 n == 0 决定。遍历宽度就是 1 ~ 9。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        trace(1, n, k);
        return ans;
    }

    private void trace(int start, int n, int k) {
        if (n == 0 && path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= 9; i++) {
            path.add(i);
            trace(i + 1, n - i, k);
            path.remove(path.size() - 1);
        }
    }
}

组合总和Ⅱ-中等题-回溯算法

力扣题目链接
给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

剪枝和去重的完美结合。剪枝用 break，去重用 continue。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        trace(candidates, target, 0);
        return ans;
    }

    private void trace(int[] nums, int target, int start) {
        if (target == 0) {
            ans.add(new ArrayList(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > target) {
                break;
            }
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            trace(nums, target - nums[i], i + 1);
            path.remove(path.size() - 1);
        }
    }
}

复原 IP 地址-中等题-感觉像难题的回溯法

力扣题目链接
给定一个只包含数字的字符串 s,用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

有点抽象，有时间再看看。

class Solution {
    List<String> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        trace(s, 0);
        return ans;
    }

    private void trace(String s, int start) {
        if (path.size() == 4 && start == s.length()) {
            ans.add(String.join(".", path));
            return;
        }
        for (int i = start; i < s.length() && i - start < 3; i++) {
            if (i > start && s.charAt(start) == '0') {
                break;
            }
            int num = Integer.parseInt(s.substring(start, i + 1));
            if (num >= 0 && num <= 255) {
                path.add(s.substring(start, i + 1));
                trace(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
}

子集Ⅱ-中等题-去重的回溯

力扣题目链接
给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

和子集相比，多个去重的步骤。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        trace(nums, 0);
        return ans;
    }

    private void trace(int[] nums, int start) {
        ans.add(new ArrayList(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            trace(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

非递减子序列-中等题-回溯算法

力扣题目链接
给你一个整数数组 nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。