感谢Chang Gao分享的 LeetCode 101 - A LeetCode Grinding Guide (C++ Version)，带我走过了迷茫阶段

一、双指针

167.有序数组的两数和

在有序数组中找出两个数，使他们的和为target

思路：使用双指针分别指向数组两端，左侧指针在Sum小于target时，往右移；右侧指针在Sum大于target时，向左移。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i= 0, j=numbers.length-1;

        while (i<j){
            int sum = numbers[i] + numbers[j];
            
            if(sum == target){
                return new int[]{i + 1, j + 1};  // java要返回数组
            } else if (sum > target){
                j--;
            }else{
                i++;
            }
        }
        return null;
    }
}       

15.三数之和(medium)

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解题思路：先对数组进行排序，然后对于当前数字nums[i]，在其右侧创建双指针，持续判断nums[i]+nums[L]+nums[R]是否等于0。由于三元组不可重复，所以必须对当前数字、左右指针均进行去重：

• 如果当前数字nums[i]和上一个数字nums[i-1]，则必须跳过（之前已经来过一次搜索了）
• 如果已经找到和为0的三个数字了：
  • 若左指针指向的数字nums[L]和其右侧数字相同，则必须跳过右侧数字
  • 若右指针指向的数字nums[R]和其左侧数字相同，则必须跳过左侧数字
  • 以上过程持续进行，直至对当前数字nums[i]而言，去掉所有和左右指针相同的数字。

class Solution {   
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length < 3)  return res;
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;

            int L = i+1, R = nums.length - 1;         
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while(L < R && nums[L] == nums[L+1]) L++;
                    while(L < R && nums[R] == nums[R-1]) R--;
                    L++;
                    R--;
                }else if(sum > 0){
                    R--;
                }else{
                    L++;
                }
            }
        }
        return res;
    }
}

88.归并两个有序数组

存在两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

思路：使用双指针分别指向两个有序数组的尾部元素，比较两元素，

• 若左指针元素小于右指针元素，将左侧元素添加到结果数组中，左指针左移1位；右侧小，将右侧元素添加到结果数组中，右指针左移1位；
• 若左侧元素已遍历完，直接将右侧元素添加到结果数组中，右侧元素遍历完时直接添加左侧元素。
• 需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m-1, index2 = n-1;
        int indexMerge = m+n-1;

        while(index1 >= 0  || index2 >= 0){
            // 左侧数组已遍历完，直接将右侧数组插入到结果数组中
            if (index1 < 0){
                nums1[indexMerge--] = nums2[index2--];
            }else if (index2 < 0){   // 右侧数组已遍历完，直接将左侧数组插入到结果数组中
                nums1[indexMerge--] = nums1[index1--];
            }else if (nums1[index1] >= nums2[index2]){    // 哪边元素大，哪边放入结果数组
                nums1[indexMerge--] = nums1[index1--];
            }else{
                nums1[indexMerge--] = nums2[index2--];
            }
        }
    }
}

🌟 滑动窗口

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路：1,2,3…target-1，维护一个滑动窗口，左边界为l，右边界为r。默认右移右边界，如果窗口内的元素和已经大于target了，右移左边界直至其符合要求。如果找到符合要求的窗口，将其中所有元素加到临时数组中。

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();

        // 维护一个滑动窗口,l为左边界，r为右边界
        for(int l = 1, r = 1, sum = 0; r <= (target+1)/2; r++){
            sum += r;
            while(sum > target){  // 移动左边界
                sum -= l++;
            }
            if(sum == target){
                int[] temp = new int[r-l+1];  // 窗口宽度为r-l+1
                for(int i = 0; i < temp.length; i++){
                    temp[i] = l+i;    // 把窗口中的元素(左边界元素为l)加入数组中
                }
                list.add(temp);
            }
        }

        // 将ArrayList转换为数组
        return list.toArray(new int[0][]);
    }
}

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

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路：创建一个长度为128的数组，记录字符上一次出现的位置，初始值为-1，表示尚未出现。每次比较当前字符最后出现的位置和当前窗口的起始点，以更新窗口起始位置，之后计算窗口最大宽度，并更新当前字符最后出现的位置。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];  // 记录字符上一次出现的位置
        Arrays.fill(last, -1);
        int res = 0;
        int start = 0;  // 窗口开始位置

        for(int i = 0; i < s.length(); i++){
            // abbac
            start = Math.max(start, last[s.charAt(i)]+1);  // 更新窗口的开始位置(+1是为了跳过前一次出现的位置) 
            res = Math.max(res, i-start+1);  // 计算窗口宽度
            last[s.charAt(i)] = i;  // 更新当前字符最后出现的位置
        }

        return res;
    }
}

76.最小覆盖子串(medium)

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        //维护两个数组，记录s和t中指定字符中出现次数
        //ASCII表总长128
        int[] chars = new int[128];  // 默认值0
        boolean[] flags = new boolean[128];  // 默认值false

        for (int i = 0; i < t.length(); i++) {
            flags[t.charAt(i)] = true;
            chars[t.charAt(i)]++;
        }

        // 移动滑动窗口，不断更改统计数据
        int cnt = 0, l = 0, min_l = 0, min_size = s.length()+1;
        for (int r = 0; r < s.length(); ++r) {
            if (flags[s.charAt(r)]){
                if (--chars[s.charAt(r)] >= 0){
                    ++cnt;
                }
                // 若目前统计窗口中已包含所需的全部字符，开始收缩左侧边界
                while (cnt == t.length()){
                    if (r-l+1 < min_size){
                        min_l = l;
                        min_size = r-l+1;
                    }
                    if (flags[s.charAt(l)] && ++chars[s.charAt(l)] > 0){
                        --cnt;
                    }
                    ++l;
                }
            }

        }
        System.out.println(min_l+"\n"+min_size);
        //返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串
        if (min_size == s.length() + 1) {
            return "";
        }
        return s.substring(min_l, min_l+min_size);
    }
}

🌟 链表

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

解题思路：使用两个指针 first 和 second同时对链表进行遍历，并且 first比 second 超前 n个节点。当 first 遍历到链表的末尾时，second就恰好处于倒数第 n 个节点。

• 为何方便删除操作，我们设置second的初始位置为哑节点，这样当first到达尾部时，second刚好到n-1个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;

        ListNode ans = dummy.next;
        return ans;
    }
}

141.判断链表是否存在环

题目描述：给定一个链表，判断链表中是否有环。

思路：使用双指针分别指向链接头部，其中一个指针每次移动一个节点，另一个指针每次以移动两个节点，如果存在环，则两者必相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode l1 =head, l2 = head.next;

        // l1,l2均不为空，且由于l2每次走两步，也要考虑l2.next
        while(l1 != null && l2 != null && l2.next != null){
            if (l1 == l2){
                return true;
            }
            l1 = l1.next;
            l2 = l2.next.next;
        }
        return false;        
    }
}

142.环形链表Ⅱ

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路：给定快慢指针slow和fast，起始位置均为链表头部，每次快指针移动两格，慢指针移动一格；

• 如果两者没有走到链表尾部，而是相遇了，那么就证明了存在环路；

• 此时，将快指针移动到链表头部，每次也是移动一格，当再次和满指针邂逅时，就是环路的起始点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head, fast = head;
        // 第一次相遇
        do{
            if(slow == null || fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }while(slow != fast);
        // 将快指针移动到首节点，开始准备第二次邂逅
        fast = head;
        while(fast != slow){
           slow = slow.next;
            fast = fast.next; 
        }
        return fast;
    }
}

二、二分查找

🌟 求开方

69.求开方

要求：给定一个整数，求他的开方，向下取整

解题思路：二分查找

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return x;
        int l = 1, r = x, mid, sqrt;
        while (l <= r){
            mid = l + (r-l)/2;
            sqrt = x/mid;
            if (sqrt == mid){  
                return mid;
            } else if (sqrt < mid){  // mid^2 > x,右边界左移
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return r;
    }
}

牛顿迭代法

class Solution {
    public int mySqrt(int x) {
        //if (x < 2) return x;
        long a = x;
        while(a*a > x){
            a = (a+x/a)/2;
        }
        return (int)a;
    }
}

🌟 查找区间

34.查找区间

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target开始和结束位置，其实我们要找的就是数组中「第一个等于 target的位置」（记为 leftIdx）和「第一个大于 target的位置减一」（记为 rightIdx）。

二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx即为在数组中寻找第一个大于 target的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target的位置，如果 lower为 true，则查找第一个大于等于 target的下标，否则查找第一个大于 target的下标。

最后，因为 target可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx和 rightIdx，看是否符合条件，如果符合条件就返回 [leftIdx,rightIdx]，不符合就返回 [−1,−1]。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    // 二分查找
    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

🌟 旋转数组查找数字

81.旋转数组查找数字

存在一个旋转排序数组，编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

解题思路：虽然数组整体上已经不符合递增性了，但部分依然存在。先比较当前中点索引的元素值和尾部元素，若中点元素小，则可证明右侧区间为递增的，此时若目标元素在右侧区间内（目标元素和中点值、尾部元素比较即可），直接丢弃左侧区间，在右侧区间中继续寻找；否则丢弃右侧区间，在左侧区间中继续寻找。

class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0, end = nums.length-1;
        while (start <= end){
            int mid = start+ (end -start)/2;
            if (nums[mid] == target){
                return true;
            }
            if (nums[mid] == nums[end]){
                end--;
            }else if (nums[mid] < nums[end]){  // 右边递增的
                if (target > nums[mid] && target <= nums[end]){ // 如果目标元素在右区间中，丢弃左区间
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }else{  // 左边递增的
                 if (target >= nums[start] && target < nums[mid]){ // 如果目标元素在左区间中，丢弃右区间
                    end = mid - 1;  //
                }else{
                    start = mid + 1;
                }
            }
        }
        return false;
    }
}

154.寻找旋转排序数组中的最小值 II

三、排序算法

🌟 常用排序算法整理

十种排序：选冒插，快归希堆，桶计基

• 平均时间复杂度：恩方，恩老，(恩加k，最后基数恩乘k)

• 平均空间复杂度：前面全部常数1，叛徒快归老恩恩，(恩加k中单个k)

• 稳定性：”插冒归，桶计基” 选希快堆

插入、堆、归并、快速

🌟 快速排序

选择p到r之间的任意一个数据作为pivot（分区点），遍历 p 到 r 之间的数据，将小于pivot的放到左边，将大于 pivot的放到右边，将pivot放到中间。

public void quickSort(int[] nums, int left, int right){
    if (left<right){
        int mid = partition(nums, left, right);
        quickSort(nums, left, mid);
        quickSort(nums, mid, right);
    }
}

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

    int pi = nums[right];
    int i = left;  // 小于pi的元素的索引指针，左侧的元素全都小于
    for(int j = left; j < right; j++){
        if (nums[j] < pi) {
            swap(nums, i , j);   // left ~ i-1的所有元素都小于pi
            i++;
        }
    }
    swap(nums, i, right);   // 此时，i指向的数字是大于pi的，因此再交换一次
    return i;
}

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

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

借助快速排序的思想，每次找到一个mid(左侧元素全小于它，右侧元素都大于它)。如果它的索引恰好为nums.length - K(表示第K大元素)，则返回其具体元素；如果大于nums.length - K，则表示第k大元素在左子集中，去那里面继续找。

import java.util.Random;

class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        int target = nums.length - k;
        while(true){
            int mid = partition(nums, left, right);
            if (mid == target){
                return nums[mid];
            }else if (mid > target){  // mid左侧的某个数，可能为第K大元素；对左侧继续排序
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
    }

    public int partition(int[] nums, int left, int right){
        // 打乱数组先， 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = right - 1 - random.nextInt(right - left);
            swap(nums, right, randomIndex);
        }

        int pivot = nums[right];
        int i = left;   // 小于pi的元素的索引指针
        for(int j = left; j < right; j++){
            if (nums[j] < pivot){
                swap(nums, i, j);   // 把小的数都挪到左侧，使left~i-1 都小于pivot
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }
    
    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

NC119 最小的K个数

import java.util.*;

public class Solution {
    
    Random random = new Random();
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        int left = 0, right = input.length - 1;
        ArrayList<Integer> res = new ArrayList<>();
        if(k == 0) return res;
        //if(k == input.length) return Arrays.asList(input)；
        
        while(true){
            int midIdx = partition(input, left, right) ;
            if(midIdx == k - 1){
                //res = Arrays.copyOf(input, midIdx);
                for(int i = 0; i <= midIdx; i++) res.add(input[i]);
                return res;
            }else if(midIdx > k - 1){
                right = midIdx - 1;
            }else{
                left = midIdx + 1;
            }
        }
    }
    
   public int partition(int[] nums, int left, int right){
       if(right > left)  swap(nums, right, right - 1 - random.nextInt(right - left));
       int pivot = nums[right];
       int i = left;
       for(int j = left; j < right; j++){
           if(nums[j] < pivot){
               swap(nums, i, j);
               i++;
           }
       }
       swap(nums, i, right);
       return i;      
   }
    
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

🌟 桶排序

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

347.数组中的前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

解题思路：

【基于桶排序】，首先根据题干中的整数数组nums构造HashMap，统计每个元素出现的次数；然后构造一个桶的集合，其中每个元素又都是一个桶，第i个桶中存放nums中出现次数为i的所有数字；之后我们倒序遍历这些桶，填充要返回的结果数组即可。

[[x1,x2],[y1,y2]]

class Solution {

    public int[] topKFrequent(int[] nums, int k) {
        // 统计出现次数
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for(int num : nums){
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 按照不同的出现次数放到不同的桶中
        ArrayList<Integer>[] countArray = new ArrayList[nums.length + 1];  // 最少0次，最多nums.length次。泛型！！这里不写，下面new的时候写没用，增强for依旧得手动进行类型转换
        for(int num : countMap.keySet()){
            int count = countMap.get(num);
            if(countArray[count] == null) countArray[count] = new ArrayList<Integer>();
            countArray[count].add(num);
        }

        // 倒叙访问桶
        int[] res = new int[k];
        int idx = 0;
        for(int i = countArray.length - 1; i > 0 && idx < k; i--){
            if(countArray[i] != null){
                for(int num : countArray[i]) res[idx++] = num;
            }
        }
        return res;
    }
}

【基于最小堆】

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个数字出现的次数
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
               map.put(num, map.get(num) + 1);
             } else {
                map.put(num, 1);
             }
        }
        
        // 定义小根堆，根据数字频率自小到大排序
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> map.get(v1) - map.get(v2));
        // 遍历数组，维护一个大小为 k 的小根堆：
        // 不足 k 个直接将当前数字加入到堆中；否则判断堆中的最小次数是否小于当前数字的出现次数，若是，则删掉堆中出现次数最少的一个数字，将当前数字加入堆中。
        map.forEach((num, cnt) -> {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (map.get(pq.peek()) < cnt) {
                pq.poll();
                pq.offer(num);
            }
        });
        
        // 构造返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}

四、DFS/回溯/BFS

🌟 深度优先搜索DFS

dfs的实现分为三步：条件判断、修改状态、递归子节点

695.岛屿的最大面积

给定一个二维的0-1矩阵，其中0表示海洋，1表示陆地。单独的或者相邻的陆地可以构成岛屿，每个格子只与其上下左右四个位置相连。求最大的岛屿面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
       if (grid.length == 0 || grid[0].length == 0) return 0; 
       int max_aera = 0;
       for (int i = 0; i< grid.length; i++){
           for (int j = 0; j< grid[0].length; j++){
               if (grid[i][j] == 1){  // 当前格子为岛屿，开始搜索周围岛屿
                   max_aera = Math.max(dfs(grid, i, j), max_aera);
               }               
           }
       }
       return max_aera;
    }

    public int dfs(int[][] grid, int i, int j){
        // 边界条件 或者 已经访问过
        if(i<0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) return 0;

        grid[i][j] = 0;  // 已访问过的岛屿标记为0，避免再次访问
        
        // 当前位置的岛屿 + 上下左右位置的岛屿
        int ans = 1 + dfs(grid, i-1, j) + dfs(grid, i+1, j)  
                    + dfs(grid, i, j-1) + dfs(grid, i, j+1);
        return ans;
    }
}

200.岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int num = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    num ++;
                    dfs(grid, i, j);
                }
            }
        }
        return num;
    }

    public void dfs(char[][] grid, int i, int j){
        if(i<0 || i >= grid.length || j<0 || j >= grid[0].length || grid[i][j] != '1'){
            return ;  // return null 会报错，一个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);
    }
}

547.朋友圈/省份数量

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];  // 顶点是否被访问
        int cnt = 0;  // 遍历过的连通域的数量
        
        for (int i = 0; i < n; i++) {
            // 若当前顶点 i 未被访问，说明又是一个新的连通域，则遍历新的连通域且cnt+=1.
            if (!visited[i]) { 
                cnt++;
                dfs(i, isConnected, visited);
            }
        }
        return cnt;
    }

    private void dfs(int i, int[][] isConnected, boolean[] visited) {
        // 对当前顶点 i 进行访问标记
        visited[i] = true;
        
        // 继续遍历与顶点 i 相邻的顶点（使用 visited 数组防止重复访问）
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(j, isConnected, visited);
            }
        }
    }
}

417.太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标

【DFS】

/**
    建立两个矩阵can_reach_p和can_reach_a, 当can_reach_p[i][j]和can_reach_a[i][j]同时为true时表示该位置可以同时到达Atlantic和Pacific
    便历时的技巧为: 只需要从四个边界开始遍历即可(类似泛洪的思想, 只要可以从边界出发到达, 就说明该位置的水可以流向对应的海洋)
**/
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<> ();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;

        int m = matrix.length, n = matrix[0].length;
        boolean[][] can_reach_p = new boolean[m][n];
        boolean[][] can_reach_a = new boolean[m][n];;
       

        for(int i = 0; i < m; i++){
            // 左右两条边
            dfs(matrix, can_reach_p, i, 0);
            dfs(matrix, can_reach_a, i, n-1);
        }

        for(int j = 0; j < n; j++){
            // 上下两条边
            dfs(matrix, can_reach_p, 0, j);
            dfs(matrix, can_reach_a, m-1, j);
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (can_reach_a[i][j] && can_reach_p[i][j]){
                    res.add(Arrays.asList(i,j));
                }
            }
        }

        return res;        
    }

    public void dfs(int[][] matrix, boolean[][] can_reach, int i, int j){
        if(can_reach[i][j]) return;
        
        can_reach[i][j] = true;
        
        int offset[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x,y;
        for(int temp = 0; temp < 4; temp++){
            x = i + offset[temp][0];
            y = j + offset[temp][1];
            if (x>=0 && x < matrix.length && y>=0 && y < matrix[0].length
                && matrix[i][j] <= matrix[x][y]){
                    dfs(matrix, can_reach, x, y);
                }
        }
    }
}

另一种DFS的写法

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<> ();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;

        int m = matrix.length, n = matrix[0].length;
        boolean[][] can_reach_p = new boolean[m][n];
        boolean[][] can_reach_a = new boolean[m][n];;
       

        for(int i = 0; i < m; i++){
            // 左右两条边
            dfs(matrix, can_reach_p, i, 0, matrix[i][0]);
            dfs(matrix, can_reach_a, i, n-1, matrix[i][n-1]);
        }

        for(int j = 0; j < n; j++){
            // 上下两条边
            dfs(matrix, can_reach_p, 0, j, matrix[0][j]);
            dfs(matrix, can_reach_a, m-1, j, matrix[m-1][j]);
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (can_reach_a[i][j] && can_reach_p[i][j]){
                    res.add(Arrays.asList(i,j));
                }
            }
        }

        return res;        
    }

    public void dfs(int[][] matrix, boolean[][] can_reach, int i, int j, int pre){
        if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length ||   // 超出边界了
           	can_reach[i][j] || matrix[i][j] < pre){    // 已访问过了，或当前位置海拔不符合要求
            return;
        }

        can_reach[i][j] = true;
        dfs(matrix, can_reach, i-1, j, matrix[i][j]);  // 找比当前位置海拔高的
        dfs(matrix, can_reach, i+1, j, matrix[i][j]);
        dfs(matrix, can_reach, i, j-1, matrix[i][j]);
        dfs(matrix, can_reach, i, j+1, matrix[i][j]);
    }
}

🌟 回溯法

46.全排列

给定一个『没有重复数字』的序列，返回其所有可能的全排列。

解题思路：回溯相比于DFS，多了一层撤销修改状态，即【修改当前节点状态】—> 【递归子节点】—>【撤销修改状态】

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 结果数组
        List<List<Integer>> res = new ArrayList<>();
        
        // 中间变量，将原先int[]类型的nums转换为List形式，便于交换元素和最终添加到结果数组
        List<Integer> tempList = new ArrayList<>();
        for (int num: nums){
            tempList.add(num);
        }

        int n = nums.length;
        backtrack(res, tempList, 0, n);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> temp, int level, int n) {
        // 所有位置都填上数了，可以添加到结果数组中了
        if(level == n){
            res.add(new ArrayList<Integer>(temp));
        }
        
        for(int i = level; i < n; i++){
            Collections.swap(temp, i, level);   // 修改当前节点状态
            backtrack(res, temp, level+1, n);   // 递归子节点
            Collections.swap(temp, i, level);   // 撤销修改
        }
    }
}

其中，Collection.swap只能对List进行操作，无法对int[]进行操作

不采用中间变量数组也可以，但最终添加到结果数组时要进行转换：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        backtrackiing(nums, 0, ans);
        return ans;
    }

    public void backtrackiing(int[] nums, int level, List<List<Integer>> ans){
        if(level == nums.length - 1){
            ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList())); // int[]转换为List
            return;
        }
        for(int i = level; i < nums.length; i++){
            swap(nums, i, level);
            backtrackiing(nums, level+1, ans);
            swap(nums, i, level);
        }
    }

    public void swap(int[] nums, int i ,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

剑指 Offer 38. 字符串的排列(medium)

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

解题思路：回溯法实现全排列，但字符串中可能有重复元素，所以还需要使用HashSet对其进行去重

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

    public String[] permutation(String s) {
        char[] c = s.toCharArray();
        bk(0,c);
        return ans.toArray(new String[ans.size()]);  // 集合转换为数组
    }

    public void bk(int level, char[] c){
        if(level == c.length - 1){
            ans.add(new String(c));
            return;
        }

        HashSet<Character> set = new HashSet<>();
        for(int i = level; i < c.length; i++){ 
            // 通过HashSet去重！！！
            if(set.contains(c[i])) continue;
            set.add(c[i]);

            swap(c, i, level);  // 修改
            bk(level+1, c);     // 递归子节点
            swap(c, i, level);  // 撤销修改
        }
    }

    public void swap(char[] nums, int i ,int j){
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

77.组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

解题思路：回溯法，此处回溯的是是否将当前数字添加到集合中

class Solution {
    private List<List<Integer>> res;
    private int n, k;
    
    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();   // List是接口，无法实例化；
        this.n = n;
        this.k = k;
        if(k > n) return res; // 每组有k个元素

        backtracking(new ArrayList<>(), 1, 0);  // 统计1~n之间的k个正整数
        return res;
    }

    public void backtracking(List<Integer> list, int index, int count){
        if(count == k){
            res.add(new ArrayList<>(list));  // 再复制一份，避免引用传递
            return;
        }

        // 剪枝：剩下的数已经不够了，直接退出吧
        if ((n-index+1) < k -count)  return;

        for(int i = index; i <= n; i++){   // 统计iindex~n之间的数
            list.add(i);  // 添加路径
            backtracking(list, i+1, count+1);  // 回溯子节点
            list.remove(list.size()-1);  // 撤销添加，回退状态
        }
    }
}

需要加强的Java语法点：

1. List的remove方法既可以删除指定元素，也可以删除指定索引处的元素。
2. List可以直接打印输出

79.单词搜索

/**
* 回溯法：相比于DFS，多了一步『撤销修改节点状态』
*/
class Solution {
    private boolean find;  // 定义为成员变量，方便以下两个成员方法使用和修改

    public boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        find = false;

        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                backtracking(i, j, board, word, visited, 0);  // 从左上角开始遍历棋盘每个格子
            }
        }
        return find;
    }

    /**
    * i,j,board：棋盘格及当前元素的坐标
    * word: 要搜索的目标单词
    * visited：记录当前格子是否已被访问过
    * pos: 记录目标单词的字符索引，只有棋盘格字符和pos指向的字符一致时，才有机会继续搜索接下来的字符；如果pos已经过了目标单词的尾部了，那么便说明找到目标单词了
    */
    public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos){
        // 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了
        if(i<0 || i>= board.length || j<0 || j >= board[0].length || visited[i][j] || find
           || board[i][j]!=word.charAt(pos))  return;

        if(pos == word.length()-1){
            find = true;
            return;
        }

        visited[i][j] = true;  // 修改当前节点状态
        backtracking(i+1, j, board, word, visited, pos+1);  // 遍历子节点
        backtracking(i-1, j, board, word, visited, pos+1);
        backtracking(i, j+1, board, word, visited, pos+1);
        backtracking(i, j-1, board, word, visited, pos+1);
        visited[i][j] = false; // 撤销修改
    }

}

51.N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

解题思路：类似于在矩阵中寻找字符串，本题也是通过修改状态矩阵来进行回溯。不同的是，我们需要对每一行、列、左右对角线建立访问数组，来记录是否放置了皇后。

• 左斜线上：横纵坐标之和固定
• 右斜线上：（横左边-纵坐标）固定，为何避免出现负数索引，可采用n-1-(横左边-纵坐标)
• n皇后问题，左右对角线分别有2*n-1条

class Solution {

    List<List<String>> ans;

    public List<List<String>> solveNQueens(int n) {
        ans = new ArrayList<>();
        if(n == 0){
            return ans;
        }

        char[][] board = new char[n][n];
        // Arrays.fill只能作用于一维数组
        for(char[] i : board){
            Arrays.fill(i, '.');
        }

        // 记录该列、对角线上是否已经放置了皇后
        boolean[] column = new boolean[n];
        boolean[] ldiag = new boolean[2*n-1];
        boolean[] rdiag = new boolean[2*n-1];

        backtracking(board, column, ldiag, rdiag, 0, n);
        return ans; 
    }


    /*
    * 回溯函数：
    * ans：结果数组、board：自己根据n构造的棋盘，默认填充为'.'
    * column,ldiag,rdiag：对每一行，建立列、左斜、左斜访问数组，来记录这些位置是否已经存放皇后了
    * row：当前的行数
    * n：几皇后问题，即棋盘有几行几列
    */
    public void backtracking(char[][] board, boolean[] column, boolean[] ldiag, boolean[] rdiag, int row, int n){
        // 已经走完所有行了，可以把当前棋盘放入结果数组了
        if(row == n){          
            // char[][] 转换为List<String>
            List<String> temp = new ArrayList();
            for (char[] a : board){
                temp.add(String.valueOf(a));
            }
            ans.add(temp);  
            return;
        }

        for (int i = 0; i < n; i++){
            // 对第row行而言，当前列i、左斜线或者右斜线的某个位置已经有王后了，跳过该列，继续搜索
            // 左斜线上：横纵坐标之和固定
            // 右斜线上：（横左边-纵坐标）固定，为何避免出现负数索引，因此采用n-1(横左边-纵坐标)
            // 0-3,1-2,2-1,3-0,-1-4,-2-5,-3-6
            if (column[i] || rdiag[n-1-row+i] || ldiag[row+i]){
                continue;
            }   
            // 修改当前节点状态
            board[row][i] = 'Q';
            column[i] = rdiag[n-1-row+i] = ldiag[row+i] = true;
            // 递归子节点
            backtracking(board, column, ldiag, rdiag, row + 1, n);
            // 撤销修改
            board[row][i] = '.';
            column[i] = rdiag[n-1-row+i] = ldiag[row+i] = false;            
        }
    }
}

🌟 广度优先搜索BFS

934.最短的桥

最短的桥，即寻找两座岛之间的最短路径。

我们可以线通过dfs找到第一座岛屿的位置，然后基于这座岛屿开始一层层的bfs，当找到另一座岛时的层数就是所求的最短路径。

• 此处使用LinkedList记录访问路径，采用ArrayDeque也行

• 开始采用的是Queue<List<Integer>>，速度15ms，更改为Queue<int[]>后成功缩短到8ms

class Solution {

    LinkedList<int[]> path; 
    
    public int shortestBridge(int[][] grid) {
        path = new LinkedList<>();
        boolean findFirstLand = false;       

        // 找到第一座岛屿，并记录岛上所有点的坐标
        for(int i = 0; i < grid.length && !findFirstLand; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1)  {
                    dfs(grid, i, j);
                    findFirstLand = true;
                    break; // 只能跳出一层循环！！
                }                
            }
        }

        int step = 0; 
        int[][] obsets = {{1,0},{-1,0},{0,1},{0,-1}};
        // 从第一座岛屿出发（坐标修改为-1），bfs式寻找第二座岛屿
        while(!path.isEmpty()){
            // 遍历该层元素
            int n = path.size();  // 集合一直在变化，因此必须先取一次此刻集合的元素数量！！！否则就没有层次可言了
            for(int i = 0 ; i < n; i++){
                int[] coor = path.removeFirst();
                // 上下左右搜索
                for(int[] obset : obsets){
                    int newX = coor[0] + obset[0];
                    int newY = coor[1] + obset[1];

                    // 超出边界了；第一座岛屿上的点或者已填海造陆
                    if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length
                        || grid[newX][newY] == -1) continue;

                    // 找到第二座岛屿了
                    if(grid[newX][newY] == 1) return step;

                    // 当前为0，未找到新岛屿，填海造陆
                    grid[newX][newY] = -1;
                    path.add(new int[]{newX, newY});
                }
            }            
            step++;
        }
        return step;
    }

    public void dfs(int[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) return;

        grid[i][j] = -1;
        path.add(new int[]{i, j});

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

322.零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

解题思路：

BFS，从amount开始，每次减去coin，看几步能到0，步数就是待求的硬币个数

• 为了加快速度，可以先对coins进行排序
• 当剩下的金额小于coin时，就跳过

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[amount + 1];

        visited[amount] = true;
        queue.offer(amount);   // 添加初始元素

        // 排序是为了加快广度优先遍历过程中，对硬币面值的遍历，起到剪枝的效果
        Arrays.sort(coins);

        int step = 1;
        while (!queue.isEmpty()) {
            for (int i = 0; i < queue.size(); i++) {   // 遍历本层元素
                Integer tempAmount = queue.poll(); // 弹出本层的一个元素
                for (int coin : coins) {
                    int next = tempAmount - coin;                    
                    if (next == 0) {  // 只要遇到 0，就找到了一个最短路径
                        return step;
                    }

                    if (next >= coin && !visited[next]) {  // 剩下的金额还能凑、当前金额也没访问过
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
            step++;
        }
        
        // 能凑出当前面值在前面的循环中就已经return了
        return -1;
    }
}

动态规划

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins == null) return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+2);
        dp[0] = 0;

        for(int i = 1; i <= amount; i++){
            for(int coin: coins){
                if(i >= coin){  // 当前背包放的下该硬币
                    dp[i] = Math.min(dp[i], dp[i-coin]+1);
                }  
            }
        }
        if(dp[amount] == amount+2){  // 没找到
            return -1;
        }else{
            return dp[amount];
        }  
    }
}

1162.地图分析

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。如果网格上只有陆地或者海洋，请返回 -1。

解题思路：

class Solution {
    public int maxDistance(int[][] grid) {
        LinkedList<int[]> queue = new LinkedList<>();
        int n = grid.length;

        // 找到所有的陆地，便于之后多源BFS
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    queue.add(new int[]{i,j});
                }
            }
        }

        // 全是陆地或者海洋
        if(queue.size() == 0 || queue.size() == n*n) return -1;

        int[][] offsets = {{0,1},{0,-1},{1,0},{-1,0}};
        int[] coor = null;  // 必须显式初始化！！
        // 从每个陆地出发，一层层地寻找海洋，最后到达的海洋就是离陆地最远的海洋
        while(!queue.isEmpty()){
            int qSize = queue.size();
            for(int i = 0; i < qSize; i++){
                coor = queue.removeFirst();  // 当前到达的坐标
                for(int[] offset: offsets){
                    int newX = coor[0] + offset[0];
                    int newY = coor[1] + offset[1];
                    
                    // 出边界了，或者不是新海洋了(访问过的海洋或者陆地)
                    if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length 
                        || grid[newX][newY] != 0) continue;
                    
                    // 当前海洋的值 为附件陆地到此海洋的最短路径
                    grid[newX][newY] = grid[coor[0]][coor[1]] + 1;
                    queue.add(new int[]{newX, newY});
                }
            }
        }

        // 路径起始值为1，因此减去1
        return grid[coor[0]][coor[1]] - 1;
    }
}

五、贪心算法

贪心算法采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果也是全局最优的

🌟 分配问题

455.分配饼干

解题思路：先对孩子的饥饿度和饼干大小进行排序，然后从饥饿度最小的孩子开始分配

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0;
        int cookie = 0;
        while(child < g.length && cookie < s.length){
            if(g[child] <= s[cookie]){
                child++;
            }
            cookie++;
        }
        return child;
    }
}

135.分配糖果

分配要求：每个孩子至少分配到 1 个糖果，且评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果

解题思路：对孩子的得分进行两次遍历，第一次从左到右遍历，若右侧孩子得分大于左侧，则右侧孩子的糖果数 = 左侧孩子糖果数+1；第二次则从右往左遍历，若左侧孩子得分大于右侧，则左侧孩子糖果数为 =【右侧孩子糖果+1 与 左侧孩子当前糖果数 取最大值】

class Solution {
    public int candy(int[] ratings) {
        int size = ratings.length;
        if (size < 2){
            return size;
        }
        // 初始化，每个孩子一个糖果
        int[] num = new int[size];
        Arrays.fill(num,1);
        //从左到右遍历，如右侧孩子得分大于左侧，则右侧的糖果数为左侧孩子糖果数+1
        for(int i = 1; i< size; i++){
            if(ratings[i] > ratings[i-1]){
                num[i] = num[i-1] + 1;
            }
        }
        // 从右往左遍历，若左侧孩子得分大于右侧，则左侧孩子糖果数为 右侧孩子糖果+1 与 左侧当前糖果 取最大值
        for(int j = size-1; j > 0; j--){
            if(ratings[j] < ratings[j-1]){
                num[j-1] = Math.max(num[j-1], num[j]+1);
            }
        }
        // 统计结果数组
        int sum = 0;
        for(int i: num){
            sum += i;
        }
        return sum;
    }
}

🌟 区间问题

435.互不重叠区间

• 题目要求：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
• 解题思路：先把区间按照结尾元素的大小进行排序，每次选择 结尾元素最小且和前一个选择的区间不重叠的区间。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if(n < 2){
            return 0;
        }

        // 按照结尾大小，从小到大排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int ans = 0, prev = intervals[0][1];
        for(int i = 1; i < n; i++){
            if(intervals[i][0] < prev){
                ans++;
            }else{
                prev = intervals[i][1];
            }
        }

        return ans;
    }
}

此处通过比较器来自定义了规则，数组长度默认为2，则a[1]和b[1]就是末尾元素了，当a[1] - b[1]<0，即a[1]< b[1],此处自定义的比较器结合sort就会升序排列。经过lamba表达式简化，即为Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

Arrays.sort(intervals, new Comparator<int[]>(){
           // Compares its two arguments for order.  Returns a negative integer,
           //     * zero, or a positive integer as the first argument is less than, equal
           //     * to, or greater than the second
            @Override
            public int compare(int[] a, int[] b){
                return a[1] - b[1];
            }
        });

Java中手动创建二维数组并赋值：int [][] intervals = new int[][]{{4,5},{2,3},{1,6}};，全是大括号

343.整数拆分(medium)

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。（和剑指 Offer 14- I. 剪绳子相同）

解题思路：dp，对于长度为i的绳子，在位置j处修建，分为j和i-j两段，其中j在2~i中变量，i-j又分为不修建和继续修建两种情况

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;

        for(int i = 3; i <= n; i++){
            for(int j = 2; j <= i; j++){ // 第一段长度为1，对结果无意义
                dp[i] = Math.max(dp[i], j*Math.max(i-j, dp[i-j]));  
            }           
        }
        return dp[n];
    }
}

贪心，每次尽可能剪成长度为3的绳子（等长时长度最大，3是优于2的）

• 如果剩下的绳子长度为1，$n/3 4 > n1$，将这个1和前面的一段3组成4，返回
• 如果剩下的绳子长度为2，$n2 >n1*1$，不再继续剪了，返回

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n-1; //3--2,2--1,1--0
        
        int a = n/3, b = n%3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a-1) * 4;  // 3*1 < 2*2=4
        return (int)Math.pow(3, a)*2; // b=2，无需再拆分
    }
}

2 <= n <= 1000，如果考虑越界问题，则可以采用循环的形式来取幂，每次都取余

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n-1;
        if(n == 4) return 4;
       
        long res = 1;
        while(n > 4){
            res = (res * 3) % 1000000007;
            n = n - 3;
        }
        return (int)(res*n% 1000000007);
    }
}

六、分治算法

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

• 分解：将原问题分解成一系列子问题；
• 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
• 合并：将子问题的结果合并成原问题。

最常见的体现分治算法思想就是归并排序算法了

归并思路	合并实例图

241.为运算表达式设计优先级

给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果

解题思路：利用分治思想，分而治之。对于每个运算符号，先执行处理两侧的数学表达式，再处理运算符号。

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ways = new LinkedList<>();

        for(int i = 0; i < input.length(); i++){
            char c = input.charAt(i);            
            if(c == '+' || c == '-' || c == '*'){
                // 分解：以运算符为分割符，分别计算左右两侧的运算结果集
                // 解决：通过递归计算两侧子问题的解                
                List<Integer> left = diffWaysToCompute(input.substring(0,i));
                List<Integer> right = diffWaysToCompute(input.substring(i+1));
                // 合并：根据运算符合并子问题的解
                for(int l: left){
                    for(int r: right){                        
                        if(c == '+'){
                            ways.add(l+r); 
                        }
                        if(c == '-'){
                            ways.add(l-r); 
                        }
                        if(c == '*'){
                            ways.add(l*r); 
                        }
                    }
                }
                //System.out.println("ways:"+ways);
            }
        }
        // 只有一个数字字符传入了递归函数，那么此次调用直接返回其值即可
        if(ways.size() == 0){
            ways.add(Integer.valueOf(input)); // 字符转换为int
            return ways;
        }

        return ways;
    }
}

七、动态规划

列动态规划方程，考虑初始状态

🌟 一维

70.爬楼梯

假设你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？（注意：给定 n 是一个正整数）

解题思路：第i阶楼梯可以从第 i-1 和 i-2 阶楼梯再走一步到达，因此：

$$dp[i]=dp[i-1]+dp[i-2]$$

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

class Solution {
    public int climbStairs(int n) {
        if(n < 2) return n;
        int pre_pre = 1;  // dp[1] 
        int pre = 2;   // dp[2]
        
        for(int i = pre; i < n ; i++){
            int cur = pre_pre + pre;  // dp[i] = dp[i-2] + dp[i-1]
            pre_pre = pre;  // g更新状态
            pre = cur;
        }
        return pre;
    }
}

198.打家劫舍

抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。

解题思路：定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以

$$dp[i] = max(dp[i-1], dp[i-2]+nums[i])$$

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的空间复杂度 O(N) 优化到 O(1) 。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];

        int pre_pre = nums[0];   // dp[0],相当于有一个元素了已经，不等于0
        int pre = Math.max(nums[0], nums[1]);  // dp[1]

        for(int i = 2; i < nums.length; i++){
            int cur = Math.max(pre, pre_pre+nums[i]);   // dp[i] = max(dp[i-1], dp[i-2]+nums[i])
            pre_pre = pre;
            pre = cur;
        }
        return pre;
    }
}

213.打家劫舍 II

待抢劫的房屋是围成一圈的，首位相邻。依旧是无法抢劫连续相邻的房子，否则会报警。求解最大抢劫量。

解题思路：环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题

• 不偷窃第一个房子，nums[1:]
• 不偷窃最后一个房子，nums[:-1]

最后两种dp情况取最大值即可

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(dp(Arrays.copyOfRange(nums, 1, nums.length)),   // 不偷第一座房子
                        dp(Arrays.copyOfRange(nums, 0, nums.length-1)));   // 不偷最后一座房子
    }

    public int dp(int[] nums){
        // 传过来的数组长度可能为1
        if(nums.length == 1) return nums[0];

        int pre_pre = nums[0];  // dp[0]
        int pre = Math.max(nums[0], nums[1]);  // dp[1]

        for(int i = 2; i < nums.length; i++){
            int cur = Math.max(pre, pre_pre + nums[i]);
            pre_pre = pre;
            pre = cur;
        }
        return pre;
    }
}

413.等差数列划分

给定一个数组，求这个数组中连续且等差的子数组一共有多少个

解题思路： 等差数组，则A[i] - A[i-1] == A[i-1] - A[i-2]。由于dp通常是『以i结尾，满足某些条件的子数组数量』，而等差子数组可以在任意一个位置终结。

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        if (n < 3)  return 0;
        int[] dp = new int[n];   //默认填充0
        int sum = 0;

        for(int i=2; i < n; i++){
            if(A[i] - A[i-1] == A[i-1] - A[i-2]){
                dp[i] = dp[i-1] + 1;
                sum += dp[i]; 
            }
        }
        return sum;  //IntStream.of(dp).sum();
    }
}

剑指 Offer 60. n个骰子的点数(medium)

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

解题思路：假设f(x,i)为x个骰子的点数之和为i的概率，新加入一个骰子，与f(x,i)有关的为f(x+1, i+1), f(x+1, i+2), … , f(x+1, i+6)。

class Solution {
    public double[] dicesProbability(int n) {
        double[] res = new double[6];
        Arrays.fill(res, 1.0/6.0);

        for(int i = 2; i <= n; i++){   // 色子个数
            double[] tmp = new double[5*i+1];  // i个色子，和总共有5*i+1种可能(i~6*i)
            
            // i-1个色子(res)的贡献传递给i个色子(tmp)
            for(int j = 0; j < res.length; j++){
                for(int k = 0; k < 6; k++){   // 
                    tmp[j+k] += res[j]/6.0;   
                }
                
            }
            res = tmp;
        }
        return res;
    }
}

剑指 Offer 49. 丑数(medium)

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

解题思路：第n个丑数可能由前面的某三个丑数×2、×3或者×5得来，建立动态规划方程

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        
        int a = 0, b = 0, c = 0;
        
        for(int i = 1; i < n; i++){
            int t1 = 2*dp[a], t2 = 3*dp[b], t3 = 5*dp[c];
            dp[i] = Math.min(Math.min(t1, t2), t3);
            
            if(dp[i] == t1) a++;
            if(dp[i] == t2) b++;
            if(dp[i] == t3) c++;
        }
        return dp[n-1];
    }
}

🌟 二维网络

64.最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小，返回最小路径和。每次只能向下或者向右移动一步。

解题思路：我们可以定义一个二维dp数组，其中dp[i][j]表示从左上角开始到(i,j)位置的最小路径和。由于每次只能向下或者往右移动，则状态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。由于边界情况下可能只有一个方向可以走，因此需根据边界条件对状态转移方程进行相应的调整

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        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] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];        
    }
}

由于dp矩阵的每一个值只与左边和上面的值有关，因此，我们可以将空间复杂度由O(MN)减小到O(N)。对于第i行，在遍历到第j列时，dp[j-1]代表的就是原先的dp[i][j]，而dp[j]当前存储的是第i-1行时的值即dp[i-1][j]，因此新的状态转移方程为dp[j] = min(dp[j-1], d[[j]) + grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i==0 && j==0){
                    dp[j] = grid[i][j];   // 原点
                }else if(i == 0){
                    dp[j] = dp[j-1] + grid[i][j]; // 只能从左侧过来
                }else if(j == 0){
                    dp[j] = dp[j] + grid[i][j]; // 只能从上方过来
                }else{
                    dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
                }
            }
        }
        return dp[n-1];        
    }
}

174.地下城游戏

存在一个地下城，请编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

解题思路：从右下角往左上角走，这时只需考虑最低初始健康点数即可，不用考虑中途死亡的情况

==TODO:补充图解==

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int N = dungeon.length;
        int M = dungeon[0].length;

        int[][] dp = new int[N][M];

        for(int i = N-1; i >= 0; i--){
            for(int j = M-1; j >= 0; j--){
                if(i == N-1 && j == M-1){  // 终点
                    dp[i][j] = Math.max(1, 1-dungeon[i][j]);
                }else if(i == N-1){  // 最后一行
                    dp[i][j] = Math.max(1, dp[i][j+1] - dungeon[i][j]);
                }else if(j == M-1){   // 最后一列
                    dp[i][j] = Math.max(1, dp[i+1][j] - dungeon[i][j]);
                }else{
                    dp[i][j] = Math.max(1, Math.min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j]);
                }
            }
        }  

        return dp[0][0];
    }
}

62.不同路径

统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动

解题思路：每次只能下移或者右移，状态转移方程可以为dp[i][j] = dp[i-1][j] + dp[i][j-1]；二维dp数组是可以压缩到一维的，新得状态转移方程为dp[j] = dp[j] + dp[j-1]

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 只有一行或者一列时，只有一条路径

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

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。

解题思路：对于当前元素(i,j)，搜索距离最近的0，分上下左右4个方向搜索。当前节点为0是，最近路径为0，因此只需处理每个1即可，多源BFS问题。首先将每个0入队，然后从每个0出发同时一圈一圈地向1扩散，用int[][] dist 来记录距离（即扩散的层次）并同时标志是否访问过。

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();
		
        // 所有0入队，且将1标记为-1 -->未被访问过
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    queue.offer(new int[] {i,j});
                }else{
                    matrix[i][j] = -1;
                }
            }
        }

        int offset[][] = {{0,1},{0,-1},{1,0},{-1,0}};
        while(!queue.isEmpty()){
            int[] pos = queue.poll();
            int x = pos[0], y = pos[1];
            for(int i = 0; i < 4; i++){
                int new_X = x + offset[i][0];
                int new_Y = y + offset[i][1];
                // 未出界，且当前节点为未被访问过的1。当前节点的最近距离为原始节点最短距离+1
                if(new_X >= 0 && new_X < m && new_Y >= 0 && new_Y < n && matrix[new_X][new_Y] == -1){
                    matrix[new_X][new_Y] = matrix[x][y] + 1;
                    queue.offer(new int[] {new_X, new_Y});
                }
            } 
        }

        return matrix;
    }
}

• 每个点入队出队一次，所以时间复杂度：O(n∗m)
• 虽然我们是直接原地修改的原输入数组来存储结果，但最差的情况下即全都是 0时，需要把 m∗n个 0都入队，因此空间复杂度是 O(n∗m)

该题采用动态规划也可以，对于任一点 (i,j)，距离最近的0的距离为：

$$f(i, j)=\left\{\begin{array}{ll}1+\min (f(i-1, j), f(i, j-1), f(i+1, j), f(i, j+1)) & \text { if matrix[i] }[\mathrm{j}]==1 \\ 0 & \text { if matrix }[\mathrm{i}][\mathrm{j}]==0\end{array}\right.$$

从左上到右下遍历一次，从右下到左上遍历一次，两次即可完成四个方向的搜索。

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        
        // 初始化
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = matrix[i][j]==0 ? 0 : 10000;   // 当前格子为0，最短路径即为0；
            }
        }

        // 左上角开始遍历
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(j > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1);  // 左方
                }
                if(i > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1);  // 上方
                }                
            }
        }

        //右下角开始遍历
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                if(j < n-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j+1]+1);  // 右方
                }
                if(i < m-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i+1][j]+1);  // 下方
                }                
            }
        }

        return dp;

    }
}

221.最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

解题思路：创建一个二维动态规划数组dp，其中dp[i][j]表示以(i,j)为右下角组成的正方形的最大边长。有点类似于木桶效应，该点组成正方形的最大边长受限于其左侧、上侧、左上节点组成的最大正方形的最短边长，即dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) return 0;
        
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max_side = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){   // 当前节点值为1，才可组成题干要求的正方形
                    if(i == 0 || j == 0) {  // 第一列、第一行
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                }

                max_side = Math.max(max_side, dp[i][j]);
            }
        }
        return max_side*max_side;
    }
}

🌟 背包问题

基本介绍

背包问题是一种组合优化的NP完全问题：有N个物品和一个容量为W的背包，每个物品都有自己的体积w和价值v，求拿哪些物品可以使得背包所装下物品的总价值最大。

如果限制每种物品只能选0个或者1个，则该问题成为0-1背包问题；如果不限定每种物品的数量，则成为完全背包问题。

😎 0-1背包：限制每种物品只能选0个或者1个

定义一个二维数组dp存储最大价值，其中dp[i][j]表示遍历到了第i个物品，当前背包容量/体积不超过j。

• 如果将该物品放入，则dp[i][j] = dp[i-1][j - weight[i-1]] + value[i-1]；
• 不放入，则取前i-1个物品时的最大价值即可，即dp[i][j] = dp[i-1][j]。

此外，还需考虑当前背包的容量能否满足装下该物品，之后再考虑装还是不装.

时间复杂度和空间复杂度都是O(NW)

public int knapsack(int[] weights, int[] values, int N, int W) {
    int[][] dp = new int[N+1][W+1];
    for(int i = 1; i <= N; i++){
        int w = weights[i-1], v = values[i-1];  // 第i个物品的体积和价值
        for(int j = 1; j <= W; j++){
            if(j >= w){  // 当前背包容量j大于物品的体积
                dp[i][j] = Math.max(dp[i-1][j-w] + v, dp[i-1][j]);
            }else{  // 当前背包容量不满足要求，无法装入物品
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];        
}

0-1背包的空间优化：假设i=2，其体积w=2，价值v=3，对于背包容量j，则dp[2][j] = max(dp[1][j], dp[1][j-2] + 3)。观察发现，后面取最大值时，依赖的总是上一排i=1的信息。因此，第一个维度可以去掉，简化为dp[j] = max(dp[j], dp[j-w] + v)。但每一列必须逆向遍历，保证dp[j]和dp[j-w]为上一排时存储的信息。

public int knapsack(int[] weights, int[] values, int N, int W) {
    int[] dp = new int[W+1];
    for(int i = 1; i <= N; i++){  // 外层是所需体积/价值，内层是物品的体积/价值反向迭代
        int w = weights[i-1], v = values[i-1];  // 第i个物品的体积和价值
        for(int j = W; j >= w; j--){  // 反向遍历
			dp[j] = Math.max(dp[j], dp[j-w] + v);  // 需要上一列存储的信息
        }
    }
    return dp[W];        
}

😎 完全背包：一个物品可拿多次

public int ksnapsack(int[] weights, int[] values, int N, int W){
    int[][] dp = new int[N+1][W+1];
    for(int i = 1; i <= N; i++){  // 物品数量
        int w = weight[i-1], v = values[i-1];
        for(int j = 1; j <= W; j++){  // 背包体积
            if (j >= w){ // 背包体积大于物品体积，可以放下
                dp[i][j] = Math.max(dp[i][j-w] + v, dp[i-1][j]);  // 和 0-1背包 的区别仅仅是dp[i-1][j-w] ——> dp[i][j-w]，因为完全背包可以放多个
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];
}

完全背包的空间优化：和0-1背包思路一样，通过移除第一维信息简化空间复杂度为O(W)。由于需要当前物品在第j-w列的信息，因此正向遍历！

public int ksnapsack(int[] weights, int[] values, int N, int W){
    int[] dp = new int[W+1];
    for(int i = 1; i <= N; i++){  
        int w = weights[i-1], v = values[i-1];
        for(int j = 1; j <= W; j++){   // 正向遍历
            dp[j] = Math.max(dp[j-w] + v, dp[j]);
        }
    }
    return dp[W];
}

416.分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解题思路：转换为0-1背包问题，每个数字只能取0或者1次，使组成的和为数组总和的一半。

dp[i][j]表示对于前i个数字中能否达到总和的一半：

• 不选第i个数字，dp[i][j] = dp[i-1][j]
• 选第i个数字，dp[i][j] = dp[i-1][j-w]

只与上一排的信息有关，则可压缩空间复杂度。但要反向遍历数字大小

如果已经找到了一半，可以提前退出，加快速度。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n == 0) return false;  // 数组长度为0
        
        int sum = IntStream.of(nums).sum();
        if(sum % 2 == 1) return false;  //总和的一半不是偶数，无法分割
        int target = sum/2;

        boolean[] dp = new boolean[target+1];
        dp[0] = true;

        for(int i = 1; i <= n; i++){
            for(int j = target; j >= nums[i-1]; j--){  // 反向遍历
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
            if(dp[target]) return true;  // 已经找到了，提前退出
        }
        return dp[target];
    }
}

474.一和零

322.零钱兑换(medium)

给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

解题思路：因为每个硬币可以用无数次，所以零钱兑换可以看作完全背包问题。创建一个一维dp数组，dp[i]表示恰好装满容量为i的背包，最少用多少硬币；由于dp时要取最小值，我们将dp数组初始化为amount+2（i ≤ amount+1，因此即使每次是1，凑钱次数也小于amount+2)。dp[0]初始化为0！

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins == null) return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+2);
        dp[0] = 0;

        for(int i = 1; i <= amount; i++){  // 外层物品数量，内存物品体积
            for(int coin: coins){
                if(i >= coin){  // 当前背包放的下该硬币
                    dp[i] = Math.min(dp[i], dp[i-coin]+1);
                }  
            }
        }
        
        if(dp[amount] == amount+2){  // 没找到
            return -1;
        }else{
            return dp[amount];
        }  
    }
}

🌟 股票交易

121.最多可以交易一次

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票各一次），设计一个算法来计算你所能获取的最大利润。你不能在买入股票前卖出股票。

解题思路：只能交易一次，则记录『今天买入的最小值』，计算『今天卖出的最大获利』，比较『每天的获利』，取最大值即可

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

        int ans = 0;
        for(int i=1; i < prices.length; i++){
            prices[0] = Math.min(prices[0], prices[i]);  // 记录到当天为止买入的最小值
            ans = Math.max(ans, prices[i]-prices[0]);   // 比较每天的获利，取最大值
        }
        return ans;
    }
}

122.可以交易无数次

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）

输入: [7,1,5,3,6,4]
输出: 7
解释：（5-1）+（6-3）=7

解题思路：

【贪心算法】遍历整个股票交易日价格列表 price，所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）：不考虑手续费，落袋为安，之后当天价格比前一天价格高，就卖出。连续上涨，可看做每天都进行买卖。pn-p1=(p2-p1)+(p3-p2)+...+(pn-pn-1)；同一天可以进行多支股票的买入和卖出，但对同一只股票，只能买入或者卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;     
        for (int i = 1; i < prices.length; i++){  //遍历所有价格，如果当天价格比前一天高，就卖
            int tmp = prices[i] - prices[i-1]; 
            if (tmp > 0){
                profit += tmp;
            }
        }
        return profit;
    }
}

【动态规划】定义三维数组dp，其中dp[i][k][0] 表示第i天，操作了k次，未持有股票的最大利益

• dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) ：前一天无股票、前一天有且卖出了

• dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])：前一天有股票、前一天无且买入了

• 由于k为无穷大，因此k这一维可以省略，定义状态dp[i][j]为第i天的最大收益：
  • dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]) ：当天未持有股票
  • dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i])：当天持有股票

设定初始值，dp[0][0]=0未持有，dp[0][1]=-prices[i]持有股票

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len < 2){  // 1天时，只能买不能卖
            return 0;
        }
        
        // 定义状态数组，并初始化
        int[][] dp = new int[len][2];
        dp[0][0] = 0;  // 第0天未持有股票
        dp[0][1] = -prices[0];  // 第0天持有股票

        for(int i=1; i < len; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);    // 当天未持有股票，已经全部卖出了
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);    // 第i天持有股票
        }

        return dp[len-1][0];  // dp[len-1][0]必然大于dp[len-1][1]

    }
}

309.交易有冻结期

可以交易无数次，但卖出股票后无法在第二天买入股票 (即冷冻期为 1 天)

解题思路：k为无穷大，且要隔一天才能买入/出，若第i天买，必须看第i-2天状态：

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：当天无股票
• dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])：当天有股票，此时前一天若无股票，需要用大前天时的收益买入

class Solution {
    public int maxProfit(int[] prices) {
        /*
            时间复杂度：O(N)，空间复杂度：O(N)
        */
//        int days = prices.length;
//        int[][] dp = new int[days][2];
//
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//
//        for(int i = 1; i < days; i++){
//            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 
//            if(i == 1){  // 此时木得i-2，单独考虑
//                dp[1][1] = Math.max(dp[i-1][1], - prices[i]);
//                continue;
//            }
//            dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
//        }
//        return dp[days-1][0];

        /*
            时间复杂度：O(N)，空间复杂度：O(1)
        */
         int days = prices.length;
         int dp_i0 = 0, dp_i1 = Integer.MIN_VALUE;
         int dp_pre_0 = 0;     // 前天的max_profit，dp[i-2][0]
        
         for(int i = 0; i < days; i++){
             int tmp = dp_i0;  // 昨天的max_profit
             dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
             dp_i1 = Math.max(dp_i1, dp_pre_0 - prices[i]);
             dp_pre_0 = tmp;
         }
         return dp_i0;
    }

714.交易有手续费

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

解题思路：k为无穷大，且买卖时有手续费，则：

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：当天无股票
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)：当天有股票，此时前一天若无股票，买入还需减去手续费

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int days = prices.length;
        if(prices == null || prices.length < 2){
            return 0;
        }

        /**
         * 时间复杂度：O(N)，空间复杂度：O(N)
         */
//        int[][] dp = new int[days][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0] - fee;  // 别忘了手续费
//
//        for(int i = 1; i < days; i++){
//            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
//        }
//        return dp[days-1][0];

        /**
         * 时间复杂度：O(N)，空间复杂度：O(1)
         */
        int dp_i0 = 0, dp_i1 = Integer.MIN_VALUE;
        for (int i = 0; i < days; i++) {
            int tmp = dp_i0;
            dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
            dp_i1 = Math.max(dp_i1, tmp - prices[i] - fee);
        }
        return dp_i0;

    }
}

123.最多可以完成交易两次

设计一个算法来计算你所能获取的最大利润，你最多可以完成两笔交易

解题思路：定义三维数组dp，其中dp[i][k][0] 表示第i天，操作了k次，未持有股票的最大利益

• 买入再卖出算一次，因此买入时次数-1或者卖出时-1，别乱了

• dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) ：前一天无股票、前一天有且卖出了

• dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])：前一天有股票、前一天无且买入了

class Solution {
    public int maxProfit(int[] prices) {       
        /*
            时间复杂度：O(N)，空间复杂度：O(N)
        */
        // int days = prices.length;
        // int max_k = 2;
        // int[][][] dp = new int[days][max_k+1][2];

        // // 开始遍历每个状态
        // for(int i = 0; i < days; i++){
        //     for(int k = 1;k <= max_k; k++){
        //         if(i == 0){
        //            dp[i][k][0] = 0;
        //            dp[i][k][1] = -prices[0];  // 第0天过后，最多进行了k1次交易，手头持有股票，最大收益应该为 负的第0天的价格
        //            continue;
        //        }
        //         dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
        //         dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
        //     }
        // }
        // return dp[days-1][max_k][0];  // 最后一天，完全交易完了，已无股票

        
        /*
        	max_k = 2，则可以对空间复杂度进行优化，则k=1或者2，直接枚举上方的dp方程即可
            时间复杂度：O(N)，空间复杂度：O(1)
        */
        int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
        int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;

        for(int price: prices){
            dp_i20 = Math.max(dp_i20, dp_i21 + price);
            dp_i21 = Math.max(dp_i21, dp_i10 - price);
            dp_i10 = Math.max(dp_i10, dp_i11 + price);
            dp_i11 = Math.max(dp_i11, - price);
        }
        return dp_i20;

    }
}

188.最多可以交易K次

解题思路：和k=2一样，定义三维数组dp，其中dp[i][k][0] 表示第i天，操作了k次，未持有股票的最大利益。

但当k比较大时，内存可能会爆。因此考虑k的大小限制：

• 一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，此时和k=2时一样；如果超过，就没有约束作用了，相当于 k = +infinity

class Solution {
    public int maxProfit(int k, int[] prices) {
        // dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
        // dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

        int days = prices.length;
        if(prices == null || prices.length < 2){
            return 0;
        }

        if(k > days/2){  // 交易次数大于总天数的一半，相当于k=正无穷大
            return maxProfit_inf(prices); 
        }

        int[][][] dp = new int[days][k+1][2];

        for (int i = 0; i < days; i++) {
            for (int k1 = 0; k1 <= k; k1++) {
                // 处理i-1和k-1越界
                if(i == 0){
                    dp[i][k1][0] = 0;
                    dp[i][k1][1] = -prices[0];  // 第0天过后，最多进行了k1次交易，手头持有股票，最大收益应该为 负的第0天的价格
                    continue;
                }
                if(k1 == 0){  // 未进行交易 
                    dp[i][k1][0] = 0;   
                    dp[i][k1][1] = Integer.MIN_VALUE;  // Integer.MIN_VALUE 表示这种情况不存在
                    continue;
                }
                
                dp[i][k1][0] = Math.max(dp[i-1][k1][0], dp[i-1][k1][1] + prices[i]);
                dp[i][k1][1] = Math.max(dp[i-1][k1][1], dp[i-1][k1-1][0] - prices[i]);
            }
        }
        return dp[days-1][k][0];
    }

    public int maxProfit_inf(int[] prices) {
        int dp_i0 = 0,dp_i1 = Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            int tmp = dp_i0;
            dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
            dp_i1 = Math.max(dp_i1, tmp - prices[i]);
        }
        return dp_i0;
    }
}

🌟 分割类型题

279.完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

解题思路：分割类型题，动态规划的状态转移方程通常不依赖相邻的位置，而是依赖于满足分割条件的位置。该题分割条件是满足完全平方分割，因此我们可以定义一个一维dp数组，其中dp[i]表示数字i 最少可有几个完全平方数组成。dp[i]依赖于dp[i-k]这些位置，如dp[i-1]、dp[i-4]、dp[i-9]。因此状态转移方程可以为dp[i] = 1 + min(dp[i-k])，其中1表示j*j这个数.

还是有点迷糊啊

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,10000);
        dp[0] = 0;

        for(int i = 1; i <= n; i++){
            int upper = (int)Math.sqrt(i);
            for(int j = 1; j <= upper; j++){
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

91.解码方法

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

解题思路：创建一个dp数组：到字符串s[i]为止，合法的方法为 dp[i+1] 个。

1.字符串长度为0，或者以0开头，无法解码，返回0；

2.字符串长度为1，只有一种解码结果

3.字符串长度大于1时，两位两位地看：

【×】00或者大于30、40这种情况无法解码，直接返回0；

【√】能解码的两位数分为10~26和27~99这两种：

​ 对于10~26，若个位为0，即10、20，解码后的10或者20加入到前移两位的结果集中，并未另拓展结果集，改变前移两位的结果数量，即dp[i] = dp[i-2]…..联想120和20

​ 若个位不为0，即11-19、21~26，这两位数可以分别解码添加到前移一位的结果集中，也可一起解码添加到前移两位的结果集中，即dp[i] = dp[i-1] + dp[i-2]…联想1122—>11 2 2 和11 22，

​ 对于27~99，只能一位一位的解码，和前移一位的解码结果数量一样,即dp[i] = dp[i-1]，联想12—>1 27

class Solution {
    public int numDecodings(String s) { 
        int n = s.length();
        // 空字符，或者以0开头，无法解码，返回0    
        if (n == 0 || s.charAt(0) == '0') return 0;
        // 只有一个字符（0~9），只有一种解码结果
        if (n == 1) return 1;

        int[] dp = new int[n+1];
        Arrays.fill(dp, 1);
        int pre = s.charAt(0) - '0';   // 十位是什么数字

        for(int i = 2; i <= n; i++){
            int cur = s.charAt(i-1) - '0';  // 个位是什么数字。
            if ((pre == 0 || pre > 2) && cur == 0) return 0;  // 00、30、40、50...
            
            if (pre == 1 || (pre == 2 && cur < 7)){  // 10-26
                if(cur != 0){  // 11-19、21-26
                    dp[i] = dp[i-1] + dp[i-2];
                }else{ // 10、20
                    dp[i] = dp[i-2];
                }
            }else{  // 27-99
                dp[i] = dp[i-1];
            }
            pre = cur;  // 右移
        }
        return dp[n];
    }
}

139.单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词；你可以假设字典中没有重复的单词。

解题思路：创建一维数组dp，其中dp[i]表示字符串s的前i位能否拆分为wordDict。

类似于完全平方数分割问题（分割条件为能否被开方），此处分割条件为拆分后的字符串是否在wordDict中。因此，在考虑每个分割位置时，需要遍历wordDict，确认当前位置是否可以成功分割。默认dp[0]为true

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       int n = s.length();
       boolean[] dp = new boolean[n+1];
       dp[0] = true;

       for(int i = 1; i <= n; i++){
           for(String word: wordDict){
               int len = word.length();
               // java中字符串用==比较，比较的是内存地址，一般都会返回false
               if (i >= len && s.substring(i-len, i).equals(word)){
                   dp[i] = dp[i] || dp[i - len];
               }
           }
       }
       return dp[n]; 
    }
}

🌟 子序列问题

对于Leetcode，通常而言，子序列不必连续，子数组或者子字符串必须连续。

300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列不一定是连续的。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列）

解题思路：创建一个一维数组dp，用dp[i]表示到数组nums第i个元素位置为止、最长递增子序列的长度。

对于每一个位置i，如果其之前的某个位置j对应的元素nums[j]小于nums[i]，则dp[i]的长度为dp[j]的长度+1。两层遍历的时间复杂度为O(n^2)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length, max_length = 0;
        if (n <= 1) return n;

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){ // 寻找比当前元素小的元素
                if (nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);  // 更新i位置处为止、最长递增子序列的长度
                }
            }
            max_length = Math.max(max_length, dp[i]);   // 记录所有位置长度中最大的长度
        }
        return max_length;
    }
}

本题可以采用二分法将时间复杂度降低为O(nlogn)。首先创建一个数组tail来存储递增子序列，用end表示已填入元素的数量。遍历nums中所有元素：当nums当前元素大于tail尾部元素时，将该元素添加到tail中组成新的递增子序列；否则，tails中必然有大于等于该元素的元素，二分法找到第一个这种元素，更新为nums[i]。相当于把一个较大的元素替换为一个较小的元素，这样递增子序列的最大长度可能存在更大的可能，潜力更大。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len <= 1) return len;

        int[] tail = new int[len];
        tail[0] = nums[0];
        int end = 0;

        for (int i = 1; i < len; i++) {
            if (nums[i] > tail[end]) {  // 当前元素大于递增子序列的最后一个元素时，招安当前元素
                end++; 
                tail[end] = nums[i];
            } else {   // 找到递增子序列中第一个大于该元素的元素，更新为当前元素
                int idx = lower_bound(tail, nums[i], end);
                tail[idx] = nums[i];
            }
        }
        end++;
        return end;
    }

    public int lower_bound(int[] tail, int temp, int end){
        int left = 0;
        int right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //int mid = left + ((right - left) >>> 1);
            if (tail[mid] < temp) {
                left = mid + 1;  // 待查找的元素在右区间中，更新左边界
            } else {
                right = mid -1;
            }
        }
        return left;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        vector<int> dp;
        dp.push_back(nums[0]);
        for(int i = 1; i < n; i++){
            if(dp.back() < nums[i]){  // 当前元素大于递增子序列的最后一个元素时，招安当前元素
                dp.push_back(nums[i]);
            }else{  // 找到递增子序列中第一个大于该元素的元素，更新为当前元素
                auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);  
                *itr = nums[i];
            }
        }
        return dp.size();
    }
};

1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

解题思路：创建一个二维数组dp，其中dp[i][j]表示到第一个字符串位置i为止，第二个字符串位置j为止，最长公共子序列的长度。

遍历两个字符串，如指向的字符相同，则原公共子序列长度+1；若不同，则比较(i-1, j)和(i, j-1)处元素大小，取较大值。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];        
    }
}

🌟 字符串编辑

72.编辑距离(hard)

给定两个字符串，已知你可以删除、替换或者插入任何字符串中的任意字符，求最少编辑几步可以使两个字符串变成相同

解题思路：创建二维数组dp，其中dp[i][j]表示第一个字符串到第i个字符为止、第二个字符串到第j个字符为止，两者相同最少需要编辑几步。

• 若第i个字符和第j个字符相同，则无需再编辑，dp[i][j]= dp[i-1][j-1]
• 若不同，则可以从dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个状态转移过来

Tips:

1.字符串长度用length()，列表[]的长度用length；

2.初始化最好在循环的外面，可以节省一定的时间

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int j = 0; j <= n; j++) dp[0][j] = j;   // 有一个字符串为空，则另一个字符串一个一个删字符
        for(int i = 0; i <= m; i++) dp[i][0] = i;

		// 两个字符串均不为空
        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] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[m][n];        
    }
}

650.只有两个键的键盘(medium)

给定一个字母A，已知你可以每次选择复制全部字符、或者粘贴之前复制的字符。求最少需要几次操作可以把字符串延展到指定长度。

解题思路：创建一维数组dp，其中dp[i]表示延展到长度i的最少操作次数。

• 如果i是一个质数/素数，无法分解，则只能一个A一个A的粘贴；
• 如果不是，则要寻找它的因子。若j是i的因子，则可复制一次j，并粘贴i/j-1次，共i/j次。
• 递推公式：dp[i] = dp[j] + dp[i/j]。有待进一步思考

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n+1];
        int h = (int)Math.sqrt(n);

        for (int i = 2; i <= n; i++){
            dp[i] = i;  // i是质数，无法拆分，只能一个A一个A的paste。1+i-1=i
            for(int j = 2; j <= h; j++){ 
                if(i % j == 0){   // 寻找因子
                    dp[i] = dp[j] + dp[i/j];
                    break;                 
                }
            }
        }
        return dp[n];
    }
}

10.正则表达式匹配

八、数学问题

🌟 公倍数和公因数

辗转相除法/欧几里得算法：

设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下:用a除以b，得a÷b=q…..r1(0≤r1)。若r1=0，则(a，b)=b;若r1≠0，则再用b除以r1，得b÷r1=q…….r2 (0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，如此下去，直到能整除为止。其最后一个为被除数的余数的除数即为(a, b)。

例如:a=25,b=15，a%b=10,b%10=5,10%5=0,最后一个为被除数余数的除数就是5,5就是所求最大公约数。

利用辗转相除法，可以很方便地求得两个数的最大公因数(greatest common divisor, gcd)；

将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm）

public int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}

public int lcm(int a, int b){
    return a * b / gcd(a,b);
}

🌟 质数

质数，又称素数，指在大于1的自然数中，除了1和其他本身外，再无其他因数。每一个数都可以分解为质数的乘积？

204.计数质数(easy)

统计所有小于非负整数n的质数的数量。

解题思路：【埃拉托斯特尼筛法】如果x是质数，那么大于x的x的倍数 2x,3x,… 一定不是质数。从1到n遍历，假设当前遍历到i，则把所有小于n、且是i的倍数的整数标记为合数，遍历完成后，没有被标记为合数的即为质数。

class Solution {
    public int countPrimes(int n) {
        if(n <= 2) return 0;
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);

        int count = n -2;  // 除去0和1
        for(int i = 2; i < n; i++){
            if(prime[i]){
                for(int j = 2*i; j < n; j+= i){  // 将其倍数标记为合数
                    if(prime[j]){  // 未访问过
                        prime[j] = false;
                        --count;
                    }
                }
            }
        }
        return count;        
    }
}

最小的质数一定小于开方数，因此无需遍历到n，到sqrt(n)即可。

每次找当前素数x的倍数时，当x>2时，2x被已经素数2遍历过了，因此无需再从2x开始寻找倍数，从x^2开始即可

class Solution {    
    public int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        
        // 从 2 开始枚举到 sqrt(n)。
        for (int i = 2; i * i < n; i++) {
            // 如果当前是素数
            if (isPrim[i]) {
                // 就把从 i*i 开始，i 的所有倍数都设置为 false。
                for (int j = i * i; j < n; j+=i) {
                    isPrim[j] = false;
                }
            }
        }

        // 计数
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrim[i]) {
                cnt++;
            }
        }
        return cnt;
    }
}

🌟 数字处理

504.七进制数(easy)

给定一个整数，将其转化为7进制，并以字符串形式输出。

解题思路：进制转换类型的题目，通常利用除法和取模(mod)来进行计算，同时也要注意一些细节，比如复数和0。当输出为数字类型而非字符串时，也需要考虑是否超出整数上下界（java为-2^31 ~ 2^31-1）

class Solution {
    public String convertToBase7(int num) {
        if(num == 0) return "0";
        boolean is_negative = num < 0;
        if(is_negative) num *= -1;
        String ans = "";

        while(num > 0){
            int b = num % 7;
            ans = "" + b + ans;  // 倒序，因此b要在ans的前面
            num = num/7;
        }
        
        return is_negative ? "-" + ans : ans;
    }
}

相比于String类型，在多次改变字符串属性时，StringBuilder要快的多！！

class Solution {
    public String convertToBase7(int num) {
        if(num == 0) return "0";
        boolean is_negative = num < 0;
        if(is_negative) num *= -1;

        StringBuilder ans = new StringBuilder();

        while(num > 0){
            int i = num % 7;
            ans.append(i);
            num = num/7;
        }
        
        return is_negative ? ans.append("-").reverse().toString() : ans.reverse().toString();
    }
}

172.阶乘后的零(easy)

给定一个整数n，返回 n! 结果尾数中零的数量。

解题思路：每个尾部的0都是由2×5=10计算得来，因此我们可以把阶乘的每一个元素拆分为质数相乘，统计有几个2和5。明显的，质因子2的数量要远多于质因子5的数量，因此我们可以只统计阶乘结果中有多少个质因子5.

class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n/5 + trailingZeroes(n/5);
    }
}

415.字符串相加(easy)

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。不能使用任何內建BigInteger库，也不能直接将输入的字符串转换为整数形式

解题思路：使用两个指针分别指向两个字符串的尾部，来模拟加法.

• 两个指针指向元素相加后，除以10得到进位，用10取余得到本次结果
• 索引溢出处理： 当指针 i或j 走过数字首部后，给 n1，n2 赋值为 0，相当于给 num1，num2 中长度较短的数字前面填 0，以便后续计算
• 当遍历完 num1，num2 后跳出循环，并根据 carry 值决定是否再在头部添加进位 1，最终返回 res 即可。

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res = new StringBuilder("");
        int i = num1.length() - 1, j = num2.length() - 1, jinwei = 0;
        while(i >= 0 || j >= 0){
            int m = i >= 0 ? num1.charAt(i) - '0' : 0;
            int n = j >= 0 ? num2.charAt(j) - '0' : 0;
            int he = m + n + jinwei;
            jinwei = he / 10;
            res.append(he%10);
            i--;j--;
        }
        if(jinwei == 1) res.append(1);

        return res.reverse().toString();

    }
}

326.是否3的幂(easy)

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

解题思路：【对数】设$3^m=n$即$log_3^n=m$，如果n是3的整数次幂，则m一定是整数。由于java中无法以3为底，因此使用换底公式换底:$m=log_3^n=log_{10}^n/log_{10}^3$。此外，整数的话，和1取余必为0

class Solution {
    public boolean isPowerOfThree(int n) {
         return (Math.log10(n)/Math.log10(3)) % 1 == 0;
    }
}

【找范围内的最大次方】int范围（-2^31 ~ 2^31-1）内的3的最大次方为1162261467，如果n为3的整数次幂，则一定可以被1162261467整除。

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467%n == 0;
    }
}

50.数值的整数次方(medium)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。

思路：每次将n变为n/2，即$x^n = (x^2)^{n/2}$。保证n/2是整数，则需考虑n为奇数/偶数的情况：

• n为偶数，$x^n = (x^2)^{n//2}$
• n为奇数，$x^n = x(x^2)^{n//2}$

class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;   // 防止x=1/x报错

        double res = 1.0;
        long n2 = n; // 防止n2= -n2出错
        if(n2 < 0){
            x = 1/x;
            n2 = -n2;
        }

        while(n2 > 0){
            if((n2 & 1) == 1) res *= x;  // n为奇数
            x *= x;
            n2 >>= 1;
        }
        return res;
    }
}

🌟 随机与取样

384.打乱数组(medium)

给你一个整数数组nums，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

• Solution(int[] nums) 使用整数数组nums初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

解题思路：采用Fisher-yates洗牌发，即随机交换位置实现随机打乱。在每次迭代中，生成一个 范围在当前下标到数组末尾元素下标之间 的随机整数，作为待交换元素的位置索引，即rand.nextInt(max - min) + min

class Solution {
    int[] origin;
    int n;
    Random rand = new Random();
    public void copy(int[] a, int[] b){
        for(int i = 0; i < a.length; i++){
            b[i] = a[i];
        }
    }

    public void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private int randRange(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    public Solution(int[] nums) {
        n = nums.length;
        origin = new int[n];
        copy(nums, origin);
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] shuffled = new int[n]; 
        copy(origin, shuffled);
        
        for(int i = 0; i < n; i++){
            int pos = randRange(i, n);
            swap(shuffled, i, pos);
        }
        return shuffled;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

其中自定义的copy函数可以用clone()代替，比如int[] shuffled = new int[n];copy(origin, shuffled);可简写为int[] shuffled = origin.clone();

clone在第一步是和new相似的，都是分配内存，调用clone方法时，分配的内存和源对象（即调用clone方法的对象）相同，然后再使用原对象中对应的各个域，填充新对象的域， 填充完成之后，clone方法返回，一个新的相同的对象被创建，同样可以把这个新对象的引用发布到外部。

但为什么clone方法是浅拷贝呢？难道这么理解，int是可以直接存的对象，不同于String，clone数组时,直接填进去了相同的数字。

也可以直接使用Collections.shuffle(listName)打乱数组，但要先把int[]转换为ArrayList

528.按权重随机选择(medium)

给定一个数组，数组每个位置的值表示该位置的权重，要求按照权重的概率去随机采样

解题思路：先取前缀和psum（递增的，最大值记为tot），之后随机产生一个范围在0~tot间的数字targ，并使用二分法查找其在前缀和中的位置x(x是满足$\text{targ} < psum[x]$的最小下标)，以模拟随机采样过程。

class Solution {

    List<Integer> psum = new ArrayList<>();
    int tot = 0;
    Random rand = new Random();

    public Solution(int[] w) {
        for (int x : w) {
            tot += x;   // 前缀和
            psum.add(tot);
        }
    }

    public int pickIndex() {
        int targ = rand.nextInt(tot);  // 生成随机数

        int lo = 0;
        int hi = psum.size() - 1;
        // 二分法查找位置
        while (lo != hi) {
            int mid = (lo + hi) / 2;
            if (targ >= psum.get(mid)) lo = mid + 1;
            else hi = mid;
        }
        return lo;   // 最小下标
    }
}

二分法也可是采用Arrays.binarySearch(listName, name),要先确保list是有序的

• 如果找到关键字，则返回值为关键字在数组中的位置索引，且索引从0开始

• 如果没有找到关键字，返回值为负的插入点值，所谓插入点值就是第一个比关键字大的元素在数组中的位置索引，而且这个位置索引从1开始。

class Solution {
    int[] weight;
    int sum = 0;
    Random random = new Random();

    public Solution(int[] w) {
        weight = w;
        for(int i = 1; i < w.length; i++){
            weight[i] += weight[i-1];
        }
        sum = weight[w.length-1];
    }
    
    public int pickIndex() {
        int r = random.nextInt(sum);
        int idx = Arrays.binarySearch(weight, r+1);
        if(idx < 0){
            idx = -idx -1;
        }
        return idx;
    }
}

382.链表随机节点(medium)

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

解题思路：【水库采样】不同于数组，在未完成遍历链表前，是无法获取其总长度的。因此，为了只遍历一遍链表，可以采用水库采样法，在遍历到第m个节点时，以1/m的概率选择这个节点覆盖到之前选中的节点，且链表的其他节点均未被选中。

对于长度为n的链表的第m个节点，最后其被采样的充要条件为 该节点被选择且之后的所有节点都未被选择。概率为

$$\frac{1}{m} \times \frac{m}{m+1} \times \frac{m+1}{m+2} \times \cdots \times \frac{n-1}{n} = \frac{1}{n}$$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode head;
    Random random = new Random();
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int ans = 0, cnt = 0;
        ListNode p = head;
        while(p != null){
            cnt++;
            int tmp = random.nextInt(cnt);    // [0, cnt-1] 共cnt个数，随机选一个的概率为 1/cnt
            if(tmp == 0){
                ans = p.val;
            }
            p = p.next;
        }
        return ans; 
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

🌟 其他

剑指 Offer 67. 把字符串转换成整数(medium)

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

解题思路：本题主要是整数的越界处理，数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。此处采用long先存储整数，如果超过了Integer.MAX_VALUE，则根据正负号返回对应的值

class Solution {
    public int strToInt(String str) {
        str = str.trim();  // 去掉首位空格
        if(str.length() == 0) return 0;
        long res = 0;

        int flag = 1, i = 1;
        if((str.charAt(0)) == '-') flag = -1;
        else if((str.charAt(0)) != '+') i = 0;  // 只有第一位是正负号时，才从第二个字符开始取；否则从第一个开始

        for(int j = i; i < str.length(); i++){
            if(!Character.isDigit(str.charAt(i))) break;
            if(str.charAt(i) - '0' + res*10 > Integer.MAX_VALUE) return flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;  // 越界处理
            res = str.charAt(i) - '0' + res*10;           
        }
        return (int)(flag*res);
    }
}

剑指 Offer 64. 求1+2+…+n(medium)

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

解题思路：无法用关键字等，可以用递归来模拟循环。无法使用条件判断，可以利用AND等的短路特性来中断递归

class Solution {
    public int sumNums(int n) {
        int sum = n;
        boolean flag = n > 0 && (sum += sumNums(n-1)) > 0;
        return sum;
    }
}

剑指 Offer 46. 把数字翻译成字符串(medium)

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

解题思路：动态规划，两位数字一看，如果其可以单独转换，则dp[i] = dp[i-2] + dp[i-1]；如果只能分别转换，则dp[i] = dp[i-1]。

class Solution {
    public int translateNum(int num) {
        String snum = ""+num;
        int a = 1, b = 1;

        for(int i = 2; i <= snum.length(); i++){
            String cur = snum.substring(i-2, i);
            int c = cur.compareTo("10") >= 0 && cur.compareTo("25") <= 0 ? a + b : b;
            a = b;
            b = c;
        }

        return b;
    }
}

递归

class Solution {
    public int translateNum(int num) {
        if(num < 10){
            return 1;
        }else if(num < 26){
            return 2;
        }else if(num < 100){
            return 1;
        }

        if(num%100 >= 10 && num%100 <= 25){
            return translateNum(num/10) + translateNum(num/100);
        }else{
            return translateNum(num/10);
        }
    }
}

剑指 Offer 39. 数组中出现次数超过一半的数字(easy)

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：摩尔投票法，遍历数组 nums 中的每个数字 num ；

• 当 票数 votes 等于 0 ，则假设当前数字 num 是众数；
• 当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 ；

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

Hash计数

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num: nums){
            int count = map.getOrDefault(num, 0) + 1;
            if(count > nums.length/2) return num;
            map.put(num, count);
        }
        return 0;
    }
}

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

解题思路：如果xy<yx，则看作x”小于”y，最终拼成的字符串x要在y的左侧。因此可以按照这种规则对数组进行从”小”到”大”排序。

class Solution {
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            str[i] = "" + nums[i];
        }

        // 从小到大排序
        Arrays.sort(str, (x,y)->(x+y).compareTo(y+x));

        StringBuilder res = new StringBuilder();
        for(String s : str){
            res.append(s);
        }

        return res.toString();
    }
}

class Solution {
    public String minNumber(int[] nums) {
        Queue<String> queue = new PriorityQueue<>(new Comparator<String>(){
            @Override
            public int compare(String o1, String o2){
                return (o1+o2).compareTo(o2+o1);
            }
        });

        for(int num: nums){
            queue.add(""+num);
        }

        StringBuilder res = new StringBuilder();
        while(!queue.isEmpty()){
            res.append(queue.poll());
        }

        return res.toString();
    }
}

剑指 Offer 43. 1～n 整数中 1 出现的次数(hard)

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

解题思路：遍历每个数字，然后统计其中1的个数，必然超时；此处，我们可以转为统计小于等于n的所有正整数中，个位上出现的次数 + 十位上出现的次数 + 百位上出现的次数 + …

• 通过digit表示位数，digit = 1, 10, 100,1000 …，找出当前位为1的数字

• 当前位表示为cur，左侧为高位high，右侧为低位low

• 当前位又可分为cur = 0, cur = 1, cur > 1三种情况：

  | cur = 0 (n = 1004) | cur = 1 (n = 1014) | cur > 1 (n = 1024) |
  | :—————————————————————————————: | :—————————————————————————————: | :—————————————————————————————: |
  | | | |
  | cur = 0，找出不大于它小的数中所有cur=1的数字 | cur = 1，找出不大于它的数中所有cur=1的数字 | cur > 1，找出不大于它的数中所有cur=1的数字 |

class Solution {
    public int countDigitOne(int n) {
        int high = n, low = 0, cur = 0, digit = 1;
        int count = 0;
        while(high != 0 || cur != 0){
            cur = high % 10;  // 当前位
            high /= 10;   // 高位

            if(cur == 0) count += high*digit;
            else if(cur == 1) count += high*digit + low + 1;
            else count += high*digit + digit;

            low += cur*digit;  // 低位
            digit *= 10;
        }
        return count;
    }
}

剑指 Offer 66. 构建乘积数组(medium)

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

解题思路：不能使用除法，可以借助类似前缀和的思想，先将B[i]的左半部分乘积算出来，然后再从右往左算右半部分乘积。

class Solution {
    public int[] constructArr(int[] a) {
        int[] res = new int[a.length];

        for(int i = 0, product = 1; i < a.length; i++){            
            res[i] = product;  // 左边数的乘积
            product *= a[i];
        }

        for(int i = a.length -1, product = 1; i >= 0; i--){
            res[i] *= product;  // 计算好的左边乘积 × 当前右边数的乘积
            product *= a[i];
        }

        return res;
    }
}

九、神奇的位运算

🌟 基础知识

常见的位运算符号有：

• 按位异或^、按位与&、按位或|、取反~、算数左移<<、算数右移>>

常见的处理技巧：

• 去除n的级数表示中最低的那一位：n&(n-1) 11110100 —> 11110000
• 获得n的级数中最低的那一位：n&(-n) —> 100

🌟 位运算基础问题

461.汉明距离

给出两个十进制数字 x 和 y，计算它们之间的汉明距离（二进制、不同位的个数）。

解题思路：对两个数按位异或，然后统计1的个数即可

class Solution {
    public int hammingDistance(int x, int y) {
        int diff = x^y, ans = 0;
        
        // 统计1的个数
        while(diff > 0){
            ans += diff & 1;    //当前位为1，相与为1；当前位为0，相与为0；
            diff = diff >> 1;    // 右移一位，即移除当前位
        }
        
        return ans;
    }
}

190.颠倒二进制位(easy)

颠倒给定的 32 位无符号整数的二进制位。

解题思路：循环32次，每次结果ans左移1位，获取n的最后一位添加到结果中，n再右移更新最后一位

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
       int ans = 0;
       for(int i = 0; i < 32; i++){
           ans <<= 1;
           ans += n&1;
           n >>= 1;
       } 
       return ans;
    }
}

136.只出现一次的数字(easy)

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解题思路：

【位运算—按位异或】利用x ^ x = 0和x ^ 0 = x的性质，将数组内的所有数字按位异或。出现两次的所有数字按位异或后结果为0,0与出现一次的数字异或后为其本身:

2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3

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

【HashMap】

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);   // 元素不存在则存入map中，计数为1；否则次数+1
        }

        for(int num : map.keySet()){
            if(map.get(num) == 1){
                return num;
            }
        }
        return 0;
    }
}

【HashSet】

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }

        HashSet<Integer> set = new HashSet<>();
        for(int num: nums){
            if(set.contains(num)){  // 存在则移除，不存在则加入
                set.remove(num);
            }else{
                set.add(num);
            }
        }
        return set.iterator().next();  // 返回仅剩的一个元素
    }
}

【栈】

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }

        Arrays.sort(nums);
        Stack<Integer> stack = new Stack<>();
        for (int x : nums){
           if (stack.isEmpty()) {
               stack.push(x);
               continue;
           }
            
           if (stack.peek() != x) { //不同时直接跳出
               break;
           }
           stack.pop();  //相同时弹出元素         
        }
        return stack.peek();

    }
}

【排序后邻位比较】

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }

        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i += 2){    // 每次跳两步！！
            if(nums[i] == nums[i-1]){
                continue;
            }else{
                return nums[i-1];
            }
        }
        return nums[nums.length - 1];
    }
}

剑指 Offer 56 - I. 数组中数字出现的次数(medium)

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

class Solution {
    public int[] singleNumbers(int[] nums) {
        // 先遍历一遍，找到x = a^b
        int x = 0;
        for(int num : nums) x ^= num;

        // 找到不为0的最低位
        int flag = x & (-x);

        // 利用此最低位将原数组分为两组，分别进行异或：
        //    (1)相同的数字分到同一组(num&flag的结果必相同)，
        //    (2)不一样的两个数字分到两组中(这两个数字某一位必不相同，而它们的异或值很好了体现了这种差异。
        //         这两个数 和它们异或值的最低位 取与的结果必不同)
        //            010 ^ 110 = 100, 010 & 100 = 0, 110 & 100 = 100
        // [4,1,3,4,6,3] ==> 6 ==> [4,4,6],[1,3,3]
        int a = 0, b = 0;
        for(int num: nums){
            if((num & flag) != 0) a ^=num;  
            else b ^= num;
        }

        return new int[]{a,b};
    }
}

342.4的幂(easy)

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

解题思路：【换底公式】

class Solution {
    public boolean isPowerOfFour(int n) {
        return (Math.log10(n)/Math.log10(4)) % 1 == 0;
    }
}

【利用二进制的特性】一个数是2的整数次方，必然存在n&(n-1)=0；一个数如果是4的次方，二进制中1的位数必须为奇数位。可以把n和二进制的10101…101（即十进制下的1431655765）做按位与，如果加过不为0，则说明在奇数位有数字，是4的倍数。

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n&(n-1)) == 0 && (n&1431655765) != 0;
    }
}

318.最大单词长度乘积(medium)

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0

解题思路：如何快速判断两个字符串是否含有相同数字呢？

• 首先为每一个字符串创建一个26位的二进制数字，每个位置表示是否存在对应的字母。
• 当两个字符串含有相同的字符时，他们的二进制数字相与后不为0。

class Solution {
    public int maxProduct(String[] words) {
        int length = words.length;
        int[] ints = new int[length];

        // 为每一个字符串创建一个26位的二进制数字，每个位置表示是否存在对应的字母。
        // 比如：abc  --> 111,也就是7
        for (int i = 0; i < length ; i++) {
            for (char c : words[i].toCharArray()){
                ints[i] |= (1 << (c - 'a'));
            }
        }

        // 如果两个字符串含有相同的字符，则他们的二进制数字相与后不为0.
        int ans = 0;
        for (int i = 0; i < length -1 ; i++) {
            int pre1 = ints[i];
            for (int j = i + 1; j < length; j++) {
                int pre2 = ints[j];
                if ((pre1 & pre2) == 0){//与运算
                    int te = words[i].length() * words[j].length();
                    ans = Math.max(ans, te);
                }

            }
        }
        return ans;
    }
}

338.比特位计数(medium)

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

解题思路：定义一个数组dp，其中dp[i]表示数字i的二进制含有1的个数。

【奇偶性区分】如果i为奇数，则一定比前一个数字(偶数)多一个1；如果i为偶数，则等于其一半时的状态（除以2相当于右移一位，去掉个0）…比如8（1000）、4（100）、2（10）。

class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num+1];
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            if(i % 2 == 0){
                dp[i] = dp[i/2];
            }else{
                dp[i] = dp[i-1] + 1;
            }
        }
        return dp;
    }
}

奇偶性是可以根据二进制表示的最后一位来看的，比如最后一位为1，由于其他位表示的是2、4、8、16等等偶数，则其必为奇数；相反，如果最后一位为0，就无法发现另外的奇数了，最后必为偶数。因此只需使i和1相与，得到最后一位即可

class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num+1];
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            //dp[i] = ((i&1) == 1) ? dp[i-1] + 1: dp[i/2];
            //dp[i] = ((i&1) == 1) ? dp[i-1] + 1: dp[i>>1];
            dp[i] = dp[i>>1] + (i&1);
        }
        return dp;
    }
}

【二进制技巧】由于n&(n-1)会将n二进制表示中最右边的1去掉，因此n必然比n&(n-1)多一个1

class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num+1];
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            dp[i] = dp[i&(i-1)] + 1;
        }
        return dp;
    }
}

十、妙用数据结构

🌟 常见数据结构

Array

• 创建数组：int[][] temp = new int[m][n]、int[] temp = {1,2,3}
• 获取长度：temp.length、temp[0].length
• 给数组赋值：Arrays.fill(temp, 1)
• 排序：Arrays.sort(temp)，默认升序
• 二分查找元素：int idx = Arrays.binarySearch(temp, key)，在调用方法前数组需有序，若发现了key，返回索引，否则返回负的插入点值。所谓插入点值就是第一个比关键字大的元素在数组中的位置索引。因此第一个比key的元素的索引为-idx-1
• 数组转ArrayList：List<String> list = Arrays.asList("张三", "李四")
  • ArrayList转数组：String[] array = (String[])list.toArray(new String[size]);

ArrayList

• 创建集合：ArrayList<String> temp = new ArrayList<String>();

• 获取长度：temp.size()

• 增删改查：

  • 添加元素：temp.add(“MicroSoft”);
  • 删除元素：temp.remove(0); // 变量为元素索引
  • 修改元素：temp.set(0, “Google”); // 第一个变量为索引
  • 访问元素：temp.get(0); // 变量为元素索引
• 判断元素是否在集合中：temp.contains(a)
• 转换为数组、字符串：temp.toArray()、temp.toString()
• 是否为空：temp.isEmpty()
• 排序、打乱顺序：Collection.sort(temp)、Collection.shuffle(temp)

LinkedList

• 创建集合：LinkedList<String> temp = new LinkedList<>();
• 获取长度：temp.size()
• 增删改查：
  • 添加元素：temp.add(“ThoughtWorks”)、temp.offer(“Apple”)、temp.addFirst("Wiki")
  • 移除元素：temp.remove(idx)、temp.removeFirst()、temp.removeLast()、
  • 获取元素：temp.get(idx)、temp.peek()、temp.poll()删除并返回第一个元素
  • 查找元素第一次出现的索引: temp.indexOf("wiki")
• 转换为数组：temp.toArray()

HashSet

• 创建：HashSet<String> set = new HashSet<String>();
• 获取长度：set.size()
• 判断元素是否存在：set.contains("Google")
• 删除元素：set.remove(“Google”)

HashMap

• 创建散列表：HashMap<String, String> ans = new HashMap<>();

• 获取大小：ans.size()

• 增删改查：

  • 添加元素：ans.put("key", "value")

  • 移除元素：ans.remove(“key”)、ans.clear()

  • 获取元素：ans.get(“key”)

• 遍历：

  for(String key: ans.keySet()){
      System.out.println(ans.get(key));
  }
  
  for(String value: ans.values()){
      System.out.println(value);
  }

Stack

• 先进后出

• 创建栈：Stack<Integer> s1 = new Stack<Integer>();

• 元素压入顶部：s1.push(100)

• 弹出顶部元素：s1.pop()
• 获取顶部元素：s1.peek()
• 栈是否为空：s1.empty()

Queue

• 先进先出，只能在表的前端删除元素、后端插入元素

• 创建：Queue<String> queue = new LinkedList<String>();

• 添加：queue.offer()
• 获取第一个元素：queue.peek()

• 删除第一个元素：queue.poll()

• 创建小根堆

  // 定义小根堆，根据数字频率自小到大排序
  Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> map.get(v1) - map.get(v2));
  
  // 遍历数组，维护一个大小为 k 的小根堆：
  // 不足 k 个直接将当前数字加入到堆中；否则判断堆中的最小次数是否小于当前数字的出现次数，若是，则删掉堆中出现次数最少的一个数字，将当前数字加入堆中。
  map.forEach((num, cnt) -> {
      if (pq.size() < k) {
          pq.offer(num);
      } else if (map.get(pq.peek()) < cnt) {
          pq.poll();
          pq.offer(num);
      }

🌟 数组

448.找到所有数组中消失的数字(easy)

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。

解题思路：遍历一遍数组(如[4,3,2,7,8,2,3,1])，将大于0的数作为索引，将该索引处的数取反（出现两次的数/索引处数字为正，出现一次的数/索引处数字为负）；最后再遍历一遍数组，找到正数元素及其对应的索引即可，索引即为未出现的数字

• 4,3,2,-7,8,2,3,1 → 4,3,-2,-7,8,2,3,1 → 4,-3,-2,-7,8,2,3,1 → 4,-3,-2,-7,8,2,-3,1 →
• 4,-3,-2,-7,8,2,-3,-1 → 4,-3,-2,-7,8,2,-3,-1 → 4,-3,-2,-7,8,2,-3,-1 → -4,-3,-2,-7,8,2,-3,-1

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for(int num: nums){
            int pos = Math.abs(num) - 1;
            if(nums[pos] > 0) nums[pos] = -nums[pos];
        }
        // 元素为正：此元素未被访问，其对应索引不曾出现
        // 元素未负：此元素被访问过，其对应索引出现过了
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0)   ans.add(i+1);
        }
        return ans;
    }
}

48.旋转图像(medium)

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

解题思路：每次考虑四个点，翻转后新的横坐标等于原先的纵坐标，新的纵坐标=n-原先的横坐标

class Solution {
    public void rotate(int[][] matrix) {
    	int temp = 0, n = matrix.length - 1;
        for(int i = 0; i <= n/2; i++){   // 自外向内一共有不超过 n/2 层
            for(int j = i; j < n-i; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[n-j][i];
                matrix[n-j][i] = matrix[n-i][n-j];
                matrix[n-i][n-j] = matrix[j][n-i];
                matrix[j][n-i] = temp;
            }
        }
    }
}

【两次翻转】

先以左上-右下对角线为轴进行翻转，然后再以每一行中点为轴左右翻转，即可实现矩阵的顺时针旋转90°

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n-1; i++){
            for(int j = i +1; j < n; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        int mid = n/2;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < mid; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n-1-j];
                matrix[i][n-1-j] = tmp;
            }
        }
    }
}

240.搜索二维矩阵 II(medium)

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

解题思路：从矩阵右上角开始搜索，若当前元素大于目标值，左移；小于目标值，下移；等于目标值，返回true

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

769.最多能完成排序的块(medium)

数组arr是[0, 1, …, arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

解题思路：记录到当前位置i处为止的最大值cur_max，如果其等于位置索引i，则发现一个分割点；若大于位置索引，则说明其右侧必有比i还小的数，无法分割，等到了那个位置再分割；由于是0~n-1间的数字，当前最大值不可能小于当前位置索引。

【画插图】

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int ans = 0, cur_max = 0;

        for(int i = 0; i < n; i++){
            cur_max = Math.max(cur_max, arr[i]);
            if(cur_max == i)  ans++;
        }
        return ans;
    }
}

🌟 栈和队列

232.用栈实现队列(easy)

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

解题思路：将栈s1的元素依次读出，并存放到s2.这样原来在栈底的元素就跑到了栈顶，可以直接获取和弹出了。

class MyQueue {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();

    /** Initialize your data structure here. */
    public MyQueue() {
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        in2out();
        return s2.pop();

    }
    
    /** Get the front element. */
    public int peek() {
        in2out();  // 防止有新的元素压入栈
        return s2.peek();
    }

    // 将栈s1中的元素依次读出存到s2中，倒序了
    public void in2out(){
        if(s2.empty()){
            while(!s1.empty()){
                int x = s1.pop();
                s2.push(x);
            }
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

155.最小栈

设计一个支持 push，pop，top操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

解题思路：新建一个栈来存放原栈的『当前及历史最小值』。

• 原栈插入元素时，若元素小于等于最小栈的栈，则将其也插入到最小栈中
• 原栈移除栈顶元素时，若元素等于最小栈的栈顶元素，则最小栈的元素也要移除

class MinStack {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();

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

    }
    
    public void push(int x) {
        s1.push(x);
        if(s2.empty() || x <= s2.peek())  s2.push(x);
    }
    
    public void pop() {
        if(!s2.empty() && s1.peek() == s2.peek())  s2.pop();
        s1.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

20.有效的括号

定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。

解题思路：建立一个栈，同时遍历字符串。当当前字符为左括号时，将对应的右括号压入栈中（可以不用建立Map）；当前字符时右括号时，弹出栈顶元素，和当前字符进行比较，若相同则继续遍历，不同则返回false。最终有效的字符串组成的栈会是空的，检测一下栈就好。

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n == 0 || s == null) return true; 
        Stack<Character> s1 = new Stack<>();

        for(int i = 0; i < n; i++){
            int tmp = s.charAt(i);
            if(tmp == '['){
                s1.push(']');
            }else if(tmp == '{'){
                s1.push('}');
            }else if(tmp == '('){
                s1.push(')');
            }else if(s1.empty() || tmp != s1.pop()){
                return false;
            }
        }

        return s1.empty();
    }
}

🌟 单调栈

739.每日温度(medium)

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

解题思路：维护一个单调递减的栈。遍历列表，如果『当前栈非空』且『栈顶元素对应元素小于当前元素』，则栈顶元素可以计算得到需要等待的天数了，并弹出当前栈顶元素；如果『当前栈非空』或『栈顶元素大于等于当前元素』，则将当前元素的索引也加入栈中。索引带有索引和索引指向的元素两层信息，是比直接放入元素更好的。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] ans = new int[n];
        Stack<Integer> s = new Stack<>();

        for(int i = 0; i < n; i++){
            while(!s.empty() && T[s.peek()] < T[i]){
                ans[s.peek()] = i - s.peek();
                s.pop();
            }
            s.push(i);
        }

        return ans;
    }
}

🌟 优先队列

优先队列（priority）是0个或多个元素的集合，每个元素都有一个优先权或值。每次从队列中取出的是具有最高优先权的元素。

• 可以在O(1)时间内获得最大值，并且可以在O(logn)时间内取出最大值或插入任意值。

优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置i的节点的父节点位置一定为i/2，而它的两个子节点的位置又一定分别为2i和2i+1。

Java 1.5之后，PriorityQueue类被引入，其中元素可以默认自然排序或者通过提供的Comparator在队列实例化的时排序。

• 不允许空值、且线程不安全
• 大小不受限制。可以在创建时指定初始大小，后续增加元素时其会自动扩容

基本操作：

• 创建优先队列：Queue<Integer> q = new PriorityQueue<>()

• 添加元素：q.offer(1)

• 获取顶部元素：q.peek()

• 弹出顶部元素：q.poll()

• 定义比较器，实现按特定规则排序

  Comparator<Student> comparator = new Comparator<Student>() {
      @Override
      public int compare(Student o1, Student o2) {
          return (o1.id - o2.id);
      }
  };
  
  Queue<Student> queue2 = new PriorityQueue<Student>(comparator);
  
  // 根据id从小到大排序
  Queue<Student> queue3 = new PriorityQueue<Student>((o1, o2)-> o1.id - o2.id);
  
  
  queue2.add(new Student(2, "B"));
  queue2.add(new Student(1, "A"));
  queue2.add(new Student(3, "C"));
  
  while (!queue2.isEmpty()) {
      Student s = queue2.poll();
      System.out.println(s.toString());
  }

23.合并K个升序链表(hard)

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路：维护一个优先队列，将题干所给的所有链表存放到优先队列中。之后，每次取出所有链表头部节点最小的那个节点，直到所有链表被提取完。由于优先队列在此处默认会先弹出最大的，因此需重写比较器。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
		
        // 维护一个优先队列（此处为小根堆），存储题干给的所有链表
        Queue<ListNode> pq = new PriorityQueue<>((a, b)->(a.val - b.val));
        for(ListNode list: lists){
            if(list != null) pq.offer(list);
        }

        
        ListNode ans = new ListNode(0);  // 空的
        ListNode cur = ans;   // 相当于head了
        while (!pq.isEmpty()) {
            cur.next = pq.poll(); // 获取当前头部节点值最小的节点，存入ans
            cur = cur.next;  
            if (cur.next != null) pq.offer(cur.next);   // ??
        }
        return ans.next;
    }
}

218.天际线问题(hard)

🌟 双端队列

239.滑动窗口最大值(hard)

🌟 哈希表

哈希表，又称散列表，使用$O(n)$空间复杂度存储数据，通过哈希函数映射位置、从而实现近似$O(1)$时间复杂度的插入、查找、删除等操作。

1.两数之和(easy)

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。

解题思路：创建一个哈希表，存放整数数组的元素及其索引。遍历整数数组，每次查询散列表中是否包含target - 当前元素值，如果包含，则找到正确答案，返回即可

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] ans = new int[2];
        for(int i = 0; i < nums.length; i++){
            int temp = target-nums[i];
            if(map.containsKey(temp)){   // 包含待寻找的目标值
                return new int[]{i, map.get(temp)}; 
            }else{    // 不包含，则将当前元素及其索引放到哈希表中
                map.put(nums[i], i);
            }
        }    
        return new int[0];    
    }   
}

128.最长连续序列(hard)

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

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for(int num : nums){   // 通过HashSet去除重复元素
            set.add(num);
        }

        int res = 0;
        for(int num: nums){
            if(set.contains(num - 1)){  // 如果包含num - 1，则num必在连续序列中，不可能为连续序列的左边界
                continue;
            }else{
                int len = 0;    
                while(set.contains(num++))  len++;  // 找所有可能的最大连续边界长度
                res = Math.max(res, len);
            }
        }
        return res;
    }
}

时间复杂度：$O(n)$。外层循环需要 $O(n)$的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。总时间复杂度也为 $O(n)$

空间复杂度：$O(n)$

149.直线上最多的点数

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

解题思路：对于每个点，分别建立哈希表，统计同一斜率的点有几个。（由一个点和一个斜率可以确定唯一一条直线）

斜率在用double类型进行除法计算时，可能会有精度损失，使两个原本不同的斜率变成了相同的。可以通过求得最大公因子的方式来确定斜率是否一致。如6/-4=3/-2 = -3/2

class Solution {
    public int maxPoints(int[][] points) {
        int res = 0;
        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0; i < points.length; i++){
            int same = 0, tmp_max = 0;
            for(int j = i+1; j < points.length; j++){
                int dy = points[j][1] - points[i][1];
                int dx = points[j][0] - points[i][0];
                if(dy == 0 && dx == 0){   // 相同的点
                    same++;
                    continue;
                }
                int g = gcd(dy, dx);    // 计算最大公因子
                if(g != 0){   // 化简，同时去除符号的影响
                    dy /= g;
                    dx /= g;
                }
                String tmp = String.valueOf(dy) + "/" + String.valueOf(dx);
                map.put(tmp, map.getOrDefault(tmp, 0) + 1);
                tmp_max = Math.max(tmp_max, map.get(tmp));  // 经过当前点，当前最多的点数
            }
            res = Math.max(res, same + tmp_max + 1);  // 当前基准点，当前最多的点数
            map.clear();
        }
        return res;
    }

    public int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }
}

🌟 前缀和与积分图

一维的前缀和，二维的积分图，都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划。

303.区域和检索 - 数组不可变(easy)

给定一个整数数组nums，求出数组从索引i到j（i ≤ j）范围内元素的总和，包含 i、j两点。

实现NumArray类：

• NumArray(int[] nums)使用数组nums初始化对象
• int sumRange(int i, int j)返回数组nums从索引i到j（i ≤ j）范围内元素的总和，包含 i、j 两点

解题思路：最简单的方法是每次遍历数组left到right间的值求和，但多次查询时时间较慢；为了提高速度，可以采用前缀和思想来解决此问题。先遍历一遍数组，统计前i个数字的和，保存到dp数组中。之后要查询时，直接用dp[right] - dp[left] + nums[left]即可（包含左右边界元素）

class NumArray {

    int[] nums;
    int[] dp;
    public NumArray(int[] nums) {
        this.nums = nums;

        dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = dp[i-1] + nums[i];    // 索引从0到i的元素的总和
        }
    }
    
    public int sumRange(int left, int right) {
        return dp[right] - dp[left] + nums[left];
    }
}

304.二维区域和检索 - 矩阵不可变(medium)

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

解题思路：创建二维dp数组，保存到(i,j)位置的所有元素之和。推荐dp数组元素维度比题干数组元素多一维，这样可以避免初始化条件以及matrix某一维度为空时的场景。

class NumMatrix {
    int[][] matrix;
    int[][] dp;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        dp = new int[matrix.length+1][matrix[0].length+1];

        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1] + dp[row1][col1] - dp[row2+1][col1] - dp[row1][col2+1] ;   // 有部分元素减了两次，有个元素漏了，所以要+ dp[row1][col1]
    }
}

560.和为K的子数组（medium)

给定一个整数数组和一个整数 k，你需要找到该数组中和为k的连续的子数组的个数。数组的长度大于1；数组中元素的范围是[-1000, 1000]，且整数k的范围是 [-1e7, 1e7]。

解题思路：依旧是前缀和，但这里采用HashMap来实现，其key为前缀和，value为对应的前缀和出现的个数。由寻找数组和为k转换为寻找当前前缀和-k：当访问到元素i时，查看看下HashMap中当前前缀和-k的个数。

psum-k对应着一个k，因此当前psum-k出现的次数=k出现的次数，只需查看当前psum-k出现的次数就相当于查看k出现的次数了

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, psum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();  // key为前缀和,value为对应的前缀和个数
        map.put(0,1);

        for(int num: nums){
            psum += num;
            count += map.getOrDefault(psum-k, 0);   // 更新前缀和为psum-k的个数。若没有则为0，若有则返回其值
            map.put(psum, map.getOrDefault(psum, 0) + 1);  // 将当前前缀和放到hashmap中，value也+1
        }
        return count;

    }
}

时间复杂度：O(N)；空间复杂度：O(N)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] dp = new int[nums.length+1];
        for(int i = 1; i <= nums.length; i++){
            dp[i] = dp[i-1] + nums[i-1];
        }

        int count = 0;
        for(int i = 1; i <= nums.length; i++){
            for(int j = 0; j < i; j++){
                if(dp[i]-dp[j]==k) count++;
            }
        }
        return count;
    }
}

时间复杂度：O(N^2)；空间复杂度：O(N)

十一、令人头大的字符串

🌟 字符串比较

242.有效的字母异位词(easy)

给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。

解题思路：可以采用数组或者HashMap统计字符串中字符出现的次数，若次数相同则返回true。数组的话，可以用26位，对应26个字母。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())  return false;
        int[] counts = new int[26];
        for(int i = 0; i < s.length(); i++){
            counts[s.charAt(i)-'a']++;
            counts[t.charAt(i)-'a']--;
        }

        for(int i = 0; i < 26; i++){
            if(counts[i] != 0) return false;
        }

        return true;
    }
}

205.同构字符串(easy)

给定两个字符串s和t，判断它们是否是同构的。

如果s中的字符可以按某种映射关系替换得到t，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

解题思路：记录两个字符串相同位置处字符第一次出现的位置，如果对应的2个字符第一次出现的位置相同，则是同构的，否则异构。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        //System.out.println(s.indexOf(s.charAt(1)));
        for(int i = 0; i < s.length(); i++){
            if(s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))){
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] s_first_index = new int[128];   // 128位Asci码
        int[] t_first_index = new int[128];

        for(int i = 0; i < s.length(); ++i){
            if(s_first_index[s.charAt(i)] != t_first_index[t.charAt(i)]) {
                return false;
            }
            s_first_index[s.charAt(i)] = i+1;
            t_first_index[t.charAt(i)] = i+1;
        }

        return true;
    }
}

时间复杂度和空间复杂度都是O(N)

647.回文子串个数(medium)

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。(回文子串是指从左到右读和从右到左读一样的字符串)

解题思路：从字符串的每个位置开始，从左到右依次寻找回文子串。判断存在多少以当前位置为中轴的回文子字符串。

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            count += extendSubstrings(s, i, i);    // 奇数长度，以s.charAt(i)为中心点向两侧拓展
            count += extendSubstrings(s, i, i+1);  // 偶数长度，以s.charAt(i)、s.charAt(i+1)为中心的回文串
        }
        return count;
    }

    // 若当前对应字符相同，则以中心点为基准，像左右两侧拓展
    public int extendSubstrings(String s, int l, int r){
        int count = 0;
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            --l;
            ++r;
            ++count; // 回文子串数量+1
        }
        return count;
    }
}

时间复杂度：O(N^2)、空间复杂度：O(1)

5.最长回文子串(medium)

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;

        String ans = "";
        for(int i = 0; i < s.length(); i++){
            String l_p = Palindrome(s, i, i);  // 奇数和偶数长度
            String r_p = Palindrome(s, i, i+1);
            
            ans = ans.length() > r_p.length() ? ans:r_p;  // 取长度较长的回文子串
            ans = ans.length() > l_p.length() ? ans:l_p;
        }
        return ans;
    }

    public String Palindrome(String s, int l, int r){
        // 字符相同，向两侧扩张
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            --l;
            ++r;
        }
        return s.substring(l+1, r);   // 跳出的时候s.charAt(l) ！= s.charAt(r)，因此不能取l和r
    }
}

🌟 字符串理解

227.基本计算器 II(medium)

给你一个字符串表达式 s （），请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开

解题思路：遍历字符串s，并用变量preSign记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据preSign 来决定计算方式：

• 加号：将数字压入栈；
• 减号：将数字的相反数压入栈；
• 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。

处理完该数字后，更新preSign为当前遍历的字符。 遍历完字符串s后，将栈中元素累加，即为该字符串表达式的值。

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<>();
        char preSign = '+';
        int num = 0, n = s.length();

        for(int i = 0; i < n; i++){
            // 寻找从i位置开始的数字
            if(Character.isDigit(s.charAt(i))){
                num = num*10 + (s.charAt(i) - '0');
            }
            // 当前字符为 运算符或者 达到了边界
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1){
                switch(preSign){
                    case '+':   
                        stack.push(num);
                        break;
                    case '-':   
                        stack.push(-num);
                        break;
                    case '*':   
                        stack.push(stack.pop() * num);
                        break;
                    default:   
                        stack.push(stack.pop() / num);
                        break;
                }
                preSign = s.charAt(i);
                num = 0;   // 初始化，开始新一轮的数字寻找
            }
        }

        int ans = 0;
        while(!stack.isEmpty()){
            ans += stack.pop();
        }
        return ans;
    }
}

224.基本计算器(hard)

给定由数字、'+'、'-'、'('、')'、和 ' ' 组成的字符串s，请你实现一个基本计算器来计算并返回它的值。

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        // sign 代表正负
        int sign = 1, res = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);

            // 寻找数字
            if (Character.isDigit(ch)) {
                int cur = ch - '0';
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
                    cur = cur * 10 + s.charAt(++i) - '0';
                res = res + sign * cur;
            } else if (ch == '+' || ch == '-') {
                sign = ch == '+'? 1: -1;
            } else if (ch == '(') {
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            } else if (ch == ')') {
                res = stack.pop() * res + stack.pop();
            }
        }
        return res;
    }
}

十二、指针三剑客：链表

🌟 链表的基础操作

206.反转链表(easy)

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解决思路：

【双指针】一直右移，每次将当前节点指向前一节点

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;  // 前一个节点、当前指针节点
        while(cur != null){
            ListNode nextTemp = cur.next;
            cur.next = prev;  // 当前节点指向前一节点，不再指向后一个节点
            
            prev = cur;  // 右移，以便处理新的当前节点
            cur = nextTemp;
        }
        return prev;  // 退出循环时，cur == null，前一个非空节点为prev
    }
}

【递归】首先是递归的终止条件：链表为空或者只有一个节点了；本次递归做什么：反转当前节点后面的所有节点，并改变当前节点和反转后尾部节点指向；返回值：翻转后的链表

class Solution {
    public ListNode reverseList(ListNode head) {
       if(head == null || head.next == null)        return head;

        ListNode doneHead = reverseList(head.next);  // 反转当前列表之后的所有节点
        
        // 本级递归所做的事
        head.next.next = head;  // head后一个节点 指向head
        head.next = null;  // head指向空
        
        // 本级递归返回值
        return doneHead;
    }
}

21.合并两个有序链表(easy)

【双指针】一直比较，小的加入结果链表；当有一方遍历结束时，退出循环，结果链表直接加上另一方的结果

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(100), node = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                node.next = l1;
                l1 = l1.next;
            }else{
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        node.next = l1==null ? l2:l1;  // 某个链表已空，dummy直接继承剩下的
        return dummy.next;
    }
}

【递归】首先是递归终止条件：其中一个链表空了；本级递归做什么：哪个链表当前节点对应值小，则以其为起始点，合并剩下来的链表；本级递归返回值：返回合并后的链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)  return l2;
        if(l2 == null)  return l1;
        
        if(l1.val < l2.val){  // l1当前节点值小，则以l1当前节点为起始点，合并剩下来的l1和l2;
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{  // l2当前节点值小，则以l2当前节点为起始点，合并剩下来的l2和l1;
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }        
    }
}

24.两两交换链表中的节点(medium)

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表;你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

输入：head = [1,2,3,4]
输出：[2,1,4,3]

解题思路：依旧是递归，首先考虑递归的终止条件，即当前链表为空或者只有一个节点；本级递归应该做什么：交换head以及head.next节点；本级递归返回值：新的已经处理好的链表。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode next = head.next;
        
        head.next = swapPairs(next.next);  // head指向已经处理好的部分
        next.next = head;  // next指向head
        
        return next;

    }
}

递归思路醍醐灌顶解答方案：三道题套路解决递归问题

83.删除排序链表中的重复元素(easy)

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次;返回同样按升序排列的结果链表。

解题思路：递归三要素1-截止条件：链表为空或者只有一个节点了，此时不存在元素重复一说；递归三要素2-本级递归做些什么：如当前节点值和后一个节点值相等，则移除后一个节点；三要素3-本级返回值：移除重复元素后的链表

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 链表为空，或者仅剩一个节点
        if(head == null || head.next == null) return head;

        // 递归处理后面的节点
        head.next = deleteDuplicates(head.next);
        // 本级递归要做的事：如果当前值和已处理完的链表首节点值相等，移除重复元素
        if(head.val == head.next.val) head = head.next;
        // 返回值
        return head;
    }
}

🌟 其他链表技巧

160.相交链表(easy)

编写一个程序，找到两个单链表相交的起始节点。

解题思路：使两个链表以相同的速度，从各自的头节点出发，若某一个到达自己的尾部，则换到另一个链表继续走。

（缺一个图，待补充）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA, l2 = headB;
        while(l1 != l2){
            l1 = l1 != null ? l1.next : headB;
            l2 = l2 != null ? l2.next : headA;
        }
        return l1;
    }
}

234.回文链表(easy)

请判断一个链表是否为回文链表。

解题思路：先通过快慢指针找到链表的中部节点，然后翻转后半部分链表；最后将翻转后的半部分链表和原先链表作比较，若值出现不同则返回false

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        ListNode slow = head, fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 将链表的后一半翻转
        ListNode node = reversePa(slow.next);

        // 比较
        while(node != null){
            if(node.val != head.val){
                return false;
            }
            node = node.next;
            head = head.next;
        }

        return true;
    }

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

更简洁的思路是，在用快慢指针寻找中间点时，慢指针顺手将当前节点反转。此时，当到达中心点时，左侧为朝向左的链表，右侧为朝向右的链表。从当前点开始向两侧进军，若两个节点的值不相等，则返回false；若成功走过了头部和尾部节点，则返回true

2.两数相加(medium)

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

解题思路：由于两个非负整数是逆序存储的，因此可以直接进行相加。当两个整数长度不一致时，用0补齐。设置一个carry作为给下一级的进位，所以当前和可以表示为l1_val + l2_val + carry。此外，最后两个链表都遍历完，但进位不为0，也要把该进位放到结果链表中。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;

        while(l1 != null || l2 != null){
            int l1_val = l1==null ? 0 : l1.val;
            int l2_val = l2==null ? 0 : l2.val;

            int sum = l1_val + l2_val + carry;
            carry = sum > 9 ? 1 : 0;

            cur.next = new ListNode(sum%10);
            cur = cur.next;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }

        if(carry != 0) cur.next = new ListNode(carry);

        return pre.next;
    }
}

148.排序链表(medium)

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

解题思路：傻瓜式做法，先将链表中所有的值存储到集合中，排序，然后将排好序的元素再存回链表中。

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode dummy = head;
        List<Integer> ans = new ArrayList<>();

        while(head != null){
            ans.add(head.val);
            head = head.next;
        }
        Collections.sort(ans);
        
        head = dummy;
        for(int i = 0; i < ans.size(); i++){
            head.val = ans.get(i);
            head = head.next;
        }

        return dummy; 
    }
}

递归，先找到当前链表的中点，然后一分为二，分别对两个子部分进行排序。最后归并两个字部分

class Solution {
    public ListNode sortList(ListNode head) {
        // 递归退出条件：链表为空或者仅剩一个节点
        if(head == null || head.next == null) return head;
        // 1.双指针找到链表中心点
        ListNode fast = head, slow = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2.根据中心点将链表分成两部分
        ListNode head2 = slow.next;
        slow.next = null;
        // 3.分治：分别对着两部分排序
        ListNode left = sortList(head);
        ListNode right = sortList(head2);
        // 4.归并这两部分的结果
        ListNode res = new ListNode(0);
        ListNode dummy = res;
        while(left != null && right != null){
            if(left.val < right.val){
                dummy.next = left;
                left = left.next;
            } 
            else {
                dummy.next = right;
                right = right.next;
            }
            dummy = dummy.next;
        }
        // 不要忘了多出来的链表（两部分可能不一样长）
        dummy.next = left == null ? right : left;

        return res.next;
    }
}

十三、指针三剑客：二叉树

🌟 数据结构介绍

作为（单）链表的升级版，我们通常接触的树都是二叉树（binary tree），即每个节点最多有 两个子节点；且除非题目说明，默认树中不存在循环结构。LeetCode 默认的树表示方法如下。

//Definition for a binary tree node.
public class TreeNode {
    int val;         //  当前节点的值
    TreeNode left;   // 左子树
    TreeNode right;  // 右子树
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
    }
}

🌟 树的递归

104.二叉树的最大深度(easy)

给定一个二叉树，找出其最大深度。(二叉树的深度为根节点到最远叶子节点的最长路径上的节点数)

解题思路：从宏观角度来看，只需要考虑当前节点及左右子树。递归截止条件，当前树没有节点了，为空树，此时深度为0；本级递归做的事：比较左右子树哪个深度更大些；本级递归返回值：深度更大的子树的深度+当前节点的1。

class Solution {
    public int maxDepth(TreeNode root) {
       if(root == null) return 0;

       int left_depth = maxDepth(root.left);
       int right_depth = maxDepth(root.right);

       return Math.max(left_depth, right_depth) + 1;
    }
}

110.平衡二叉树(easy)

给定一个二叉树，判断它是否是高度平衡的二叉树。(本题中，一棵高度平衡二叉树是指：该二叉树每个节点 的左右两个子树的高度差的绝对值不超过1)

解题思路：平衡二叉树，先判断当前节点的两个子树的高度差的绝对值是否超过1，然后再深度到左右子树中判断每个节点是否都符合平衡二叉树的条件。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        // 若为平衡二叉树，当前节点左右子树高度差绝对值不超过1 且 左、右子树中所有节点均符合平衡二叉树的条件
        return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.right) && isBalanced(root.left);  

    }

    // 获取当前字树的深度
    public int getHeight(TreeNode root){
        return root != null ? Math.max(getHeight(root.left), getHeight(root.right))+1 : 0;
    }
}

543.二叉树的直径(easy)

给定一棵二叉树，你需要计算它的直径长度（一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点）。

解题思路：由于路径可能不经过根节点，则对于本级递归而言，返回值为一侧子树的深度，本级递归需要做的事为：计算两个子树的深度，并更新全局直径。

class Solution {

    int nodeCount;

    public int diameterOfBinaryTree(TreeNode root) {
        nodeCount = 0;
        getHeight(root);
        return nodeCount - 1;  // 边数为节点数-1
    }

    public int getHeight(TreeNode root){
        if(root == null) return 0;
        // 计算左、右子树深度
        int left_height = getHeight(root.left);
        int right_height = getHeight(root.right);
        // 左子树深度+右子树深度+1 为 当前节点的最大直径 可能值，比较后更新全局直径
        nodeCount = Math.max(nodeCount, left_height + right_height + 1);

        return Math.max(left_height, right_height) + 1;
    }
}

113.路径总和 II(medium)

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

解题思路：回溯，将当前节点值加入路径并判断当前路径是否已符合要求；递归子节点；撤销修改状态

class Solution {

    List<List<Integer>> ans;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ans = new ArrayList<>();
        back(root, targetSum, new ArrayList<>());
        return ans;        
    }


    public void back(TreeNode root, int targetSum, List<Integer> curPath){
        // 递归退出条件
        if(root == null) return;

        curPath.add(root.val);  // 修改
        // 到达叶子节点，且路径总和符合要求了，将路径添加到结果集中
        if(root.left == null && root.right == null && targetSum - root.val == 0){
            ans.add(new ArrayList<>(curPath));  // 不可直接传递curPath
        }
        
        back(root.left, targetSum - root.val, curPath); // 递归子节点   
        back(root.right, targetSum - root.val, curPath);         
        curPath.remove(curPath.size() - 1); // 撤销修改
    }
}

437.路径总和 III(medium)

给定一个二叉树，它的每个结点都存放着一个整数值，找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解题思路：任意节点出发，则本节点、左子树、右子树出发均可。

【递归】若当前节点添加到路径，为了保证路径连续性，必须连续添加路径或者不再添加了；若当前节点不加入路径，则去考虑左、右子树。35ms

class Solution {

    // 路径无需一定在根节点开始，也无需一定在叶子节点结束
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        // 从本节点、左子节点、右子节点出发皆可
        return getPath(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    public int getPath(TreeNode root, int targetSum){
        // 递归结束条件
        if(root == null) return 0;

        // 当前路径已符合要求！结果路径数+1
        int count = 0;
        if(root.val == targetSum) count = 1;

        // 当前节点加入路径了，则必须连续添加直到路径和符合要求
        return count + getPath(root.left, targetSum - root.val)
                     + getPath(root.right, targetSum - root.val);
    }
}

【前缀和+回溯】设置一个HashMap保存当前路径总和及出现次数。当前路径总和为prefix_sum，如果prefix_sum - sum已经在HashMap出现过，则sum也必定也存在，因此当前节点所在路径符合要求！！且对当前prefix_sum，prefix_sum - sum和sum两者出现次数相同。3ms

class Solution {
    int prefix_sum = 0, count = 0;
    HashMap<Integer, Integer> prefix_sum_map;

    public int pathSum(TreeNode root, int targetSum){
        if(root == null) return 0;

        prefix_sum_map = new HashMap<>();
        prefix_sum_map.put(0, 1);  // 起始状态：前缀和为0，出现次数为1次
        bk(root, targetSum);

        return count;
    }


    public void bk(TreeNode root, int targetSum){
        if(root == null) return;

        // 1.修改状态（注意顺序，当前修改不可影响后面的状态判断）
        prefix_sum += root.val;  // 更新当前前缀和
        count += prefix_sum_map.getOrDefault(prefix_sum - targetSum, 0);  // 更新已求得的路径数量(当前节点求得的前缀和符合要求，则当前节点所在路径必为待求路径的一部分，更新已求得路径数量)
        prefix_sum_map.put(prefix_sum, prefix_sum_map.getOrDefault(prefix_sum, 0) + 1);  // 更新当前前缀和出现次数

        // 2.递归子节点
        bk(root.left, targetSum);
        bk(root.right, targetSum);

        // 3.撤销修改（顺序添加、逆序撤销）
        prefix_sum_map.put(prefix_sum, prefix_sum_map.getOrDefault(prefix_sum, 0) - 1);  
        prefix_sum -= root.val;
    }
}

101.对称二叉树(easy)

给定一个二叉树，检查它是否是镜像对称的。

解题思路：

【递归】判断是否对称，四步嘛：(1)若两个子树均为空格，则他们对称；(2)若两个子树中仅有一个为空，则他们不对称；(3)若两个子树根节点值不相等，则必定不对称；（4）递归处理左子树的左边-右子树的右边、左子树的右边-右子树的左边。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode leftNode, TreeNode rightNode){
        // 两侧均为空
        if(leftNode == null && rightNode == null) return true;
        
        // 仅一侧为空
        if(leftNode == null || rightNode == null) return false;

        // 两侧均不为空
        return leftNode.val == rightNode.val && isSymmetric(leftNode.left, rightNode.right)
                                             && isSymmetric(leftNode.right, rightNode.left);
    }
}

【队列】将左子树和右子树先后放入队列中，若队列不为空，则取出并进行条件判断。之后再分别放入左子树的左边-右子树的右边、左子树的右边-右子树的左边。依次，访问到树的每个节点。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return true;
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        
        while(queue.size() > 0){
            TreeNode leftNode = queue.removeFirst();
            TreeNode rightNode = queue.removeFirst();
		   // 两侧为空，当前节点判断结束，继续判断其他节点
            if(leftNode == null && rightNode == null) continue;   // 此处不同于递归法，不能直接返回true！
            // 仅一侧为空，直接false
            if(leftNode == null || rightNode == null) return false;
            // 两侧均不为空
            if(leftNode.val != rightNode.val) return false;
            queue.add(leftNode.left);
            queue.add(rightNode.right);
            queue.add(leftNode.right);
            queue.add(rightNode.left);
        }
        return true;
    }
}

1110.删点成林(medium)

给出二叉树的根节点 root，树上每个节点都有一个不同的值。如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

解题思路：依旧是递归三要素，

- 递归结束条件：二叉树已空

- 本级递归做的事情：如果当前节点存在于待删除列表中，则将其非空子树存储到forest中，并移除该节点

- 本级递归返回值：移除掉特定节点后的二叉树

class Solution {
    HashSet<Integer> to_delete_set;
    List<TreeNode> ans;

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        to_delete_set = new HashSet<>();
        ans = new ArrayList<>();
        for(int i : to_delete){
            to_delete_set.add(i);
        }

        root = delNodes(root);
        if(root != null) ans.add(root);  // 不要漏了处理完的非空节点
        return ans;
    }

    public TreeNode delNodes(TreeNode root){
        // 递归结束条件
        if(root == null) return root;

        // 递归处理子节点
        //   如果本节点要删除，保存的非空子树必须是已经处理过的；
        //   如果本节点不删除，也要处理其子节点
        root.left = delNodes(root.left);
        root.right = delNodes(root.right);

        // 本级递归任务
        if(to_delete_set.contains(root.val)){
            if(root.left != null) ans.add(root.left);
            if(root.right != null) ans.add(root.right);
            root = null;
        }

        // 本级递归返回值：处理过的本节点（所有子节点也处理过了）
        return root;
    }
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)。B是A的子结构， 是指 A中有出现和B相同的结构和节点值。

解题思路：

• 先找到当前节点的值和B的根节点的值相等的节点，继续比较B其余的节点是否也和此节点的子节点匹配。
• 当然，这种和B根节点相等的节点可能存在多个，所以前面不匹配的时候，需继续搜索找到每一个相等的节点。

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        
		// 当前节点值相等，且B中其余子节点也符合要求！！
        if(A.val == B.val && tools(A,B)) return true;
        
        // 当前节点不是合适的根节点，去子节点中继续找
        return isSubStructure(A.left, B) || isSubStructure(A.right, B); 
    }

    // C和B当前节点的值当前已经相等了，接下来继续比较其余子节点
    public boolean tools(TreeNode C, TreeNode B){
        // 递归退出条件
        if(B == null) return true;  
        if(C == null) return false;
        if(C.val != B.val) return false;
		
        // 继续比较其余子节点
        return tools(C.left, B.left) && tools(C.right, B.right);
    }
}

🌟 树的层次遍历

我们可以使用广度优先搜索进行层次遍历。注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

637.二叉树的层平均值(easy)

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

解题思路：BFS,，维护一个队列，当队列不为空时，执行相关业务，业务执行完再将接下来要访问的节点入队。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
   
        while(!queue.isEmpty()){
            double sum = 0; // 返回值为double类型，因此sum指定为double
            int nodeCount = queue.size();
            // 计算当前层的节点值的和，并将下一层节点入队。
            for(int i = 0; i < nodeCount; i++){
                TreeNode node = queue.removeFirst();
                sum += node.val;
                if(node.left != null)  queue.add(node.left);
                if(node.right != null)  queue.add(node.right);
            }
            ans.add(sum/nodeCount); // 计算当前层平均值
        }
        return ans;
    }
}

102. 二叉树的层序遍历(medium)

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

和前面一样BFS，但一个是easy，一个是medium，鬼扯

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) return ans;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> curLayerNodeVal = new ArrayList<>();
            // 提取出这个常量，放到循环中条件会紊乱(循环体中修改了queue内容)
            int nodeCount = queue.size();  
            for(int i = 0; i < nodeCount; i++){
                TreeNode node = queue.removeFirst();
                curLayerNodeVal.add(node.val);

                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            } 
            ans.add(new ArrayList<>(curLayerNodeVal));
        }
        
        return ans;
    }
}

107.二叉树的层序遍历II(medium)

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) return ans;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> curLayerNodeVal = new ArrayList<>();
            // 提取出这个常量，放到循环中条件会紊乱(循环体中修改了queue内容)
            int nodeCount = queue.size();  
            for(int i = 0; i < nodeCount; i++){
                TreeNode node = queue.removeFirst();
                curLayerNodeVal.add(node.val);

                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            } 
            ans.add(new ArrayList<>(curLayerNodeVal));
        }
        
        // 翻转二维集合
        int ansCount = ans.size();
        for(int i = 0; i < ansCount/2; i++){
            List<Integer> tmp = ans.get(i), tmp2 = ans.get(ansCount -1 - i);
            ans.set(i, tmp2);
            ans.set(ansCount-1 - i, tmp);
        }
        return ans;
    }
}

🌟 前中后序遍历

前序遍历、中序遍历和后序遍历是三种利用深度优先搜索遍历二叉树的方式。它们是在对节点访问的顺序有一点不同，其它完全相同。考虑如下一棵树，

    1
   / \
  2   3
 / \   \
4   5   6

（1）前序遍历：父节点、左子树、右子树。因此遍历顺序为[1,2,4,5,3,6] —> 第一个点为首节点

void preOrder(TreeNode root){
    visit(root);  // 处理当前父节点
    preOrder(root.left);
    preOrder(root.right);
}

（2）中序遍历：左子树、父节点、右节点。因此遍历顺序为[4,2,5,1,3,6] —> 首节点的左侧为左子树，右侧为右子树

void inOrder(TreeNode root){
    preOrder(root.left);
    visit(root);  // 处理当前父节点
    preOrder(root.right);
}

（3）后序遍历：左子树、右子树、父节点。因此遍历顺序为[4,5,2,6,3,1] —>最后一个节点为首节点

void postOrder(TreeNode root){
    preOrder(root.left);
    preOrder(root.right);
    visit(root);  // 处理当前父节点
}

144. 二叉树的前序遍历(medium)

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

解题思路：

// 常规递归思路
class Solution {
    List<Integer> ans;
    public List<Integer> preorderTraversal(TreeNode root) {
        ans = new ArrayList<>();
        preOrder(root);      
        return ans;
    }

    public void preOrder(TreeNode root){
        if(root == null) return;
        ans.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
}

// 迭代：用栈来模拟递归思路
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;

        Stack<TreeNode> s = new Stack<>();
        s.add(root);

        while(!s.empty()){ 
            TreeNode node = s.pop();  // 不同于层次遍历，此处无循环来考虑层次，直接弹出即可
            ans.add(node.val); 
            // 父节点、左子树、右子树，由于栈先进后出，因此先存储的是右子树
            if(node.right != null) s.add(node.right); 
            if(node.left != null) s.add(node.left);
        }        
        return ans;
    }
}

// 【更推荐，容易和其他两种联系】迭代：父左右，则先将根节点及其所有的左孩子入栈，并放入结果中
public List<Integer> preorderTraversal(TreeNode root){
    List<Integer> res = new ArrayList<>();
    LinkedList<TreeNode> queue = new LinkedList<>();

    while(!queue.isEmpty() || root != null){
        while(root != null){
            res.add(root.val); // 父节点取值
            queue.add(root);  // 存储当前节点，以便后面拿到其右子节点
            root = root.left; // 到左子树中取值
        }
        TreeNode node = queue.removeLast();  // 先进后出，模拟 栈
        root = node.right;  // 父节点和左子树已取值完毕，到右子树中取值
    }
    return res;
}

94.二叉树的中序遍历(medium)

// 迭代.递归太简单了就先不写了
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();

        while(!queue.isEmpty() || root != null){
            while(root != null){  
                queue.add(root);   // 左父右，根节点和左子树入队，
                root = root.left;  // 先一口气扎到最左侧
            }
            TreeNode node = queue.removeLast();  // 逆序取出（先拿到的是左子树，再是父节点）
            res.add(node.val);  // 左子树和父节点取值
            root = node.right;  // 最后，到右子树取值
        }
        return res;
    }
}

145.二叉树的后序遍历(medium)

左右父，因此可以先父右左（类似前序遍历），然后反转结果数组。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 左右父 --> 父右左
        while(!queue.isEmpty() || root != null){
            while(root != null){
                res.add(root.val);  // 存储父节点
                queue.add(root);   
                root = root.right;  // 父节点、右子树先后入队
            }
            TreeNode node = queue.removeLast();  // 逆序取出
            root = node.left;  // 最后左子树取值
        }

        Collections.reverse(res);  // 结果逆序，即为后序遍历结果
        return res;
    }
}

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

根据一棵树的前序遍历与中序遍历构造二叉树。

解题思路：

• 前序遍历（父左右）的第一个值为根节点，
• 中序遍历（左父右）根据前面拿到的根节点，其左侧均为左子树元素、右侧均为右子树元素。

事先对中序遍历数组中的元素建立哈希索引（key为中序遍历数组的各元素，value为元素在数组中的位置索引），便于查找元素位置。

class Solution {
    HashMap<Integer, Integer> map;
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || preorder == null) return null;
        map = new HashMap<>();
        this.preorder = preorder; 

        // key为中序遍历数组的各元素，value为元素在数组中的索引
        for(int i = 0; i < preorder.length; i++){  
            map.put(inorder[i], i);
        }

        return restoreHelper(0, preorder.length - 1, 0);
    }

    /*
    * @Param s0/e0/：中序遍历数组inorder中 左子树数组的首索引、右子树数组的尾索引
    * @Param s1: 前序遍历数组preorder中 元素的索引
    */
    public TreeNode restoreHelper(int s0, int e0, int s1){
        if(s0 > e0) return null;

        // 前序遍历数组的第1个节点(s1=0时)对应的值mid, 在中序遍历数组中索引为index, 
        // 其左边子数组(长度为leftLen)构成了左子树，右边为右子树
        int mid = preorder[s1], index = map.get(mid), leftLen = index - s0 ; // index -1 - s0 + 1

        // 以该元素为父节点值, 创建Tree
        TreeNode node = new TreeNode(mid);
        node.left = restoreHelper(s0, index-1, s1+1);   // 构建左子树 
        node.right = restoreHelper(index+1, e0, s1+1+leftLen);  // 构建右子树

        return node;
    }
}

🌟 二叉搜索树

二叉搜索树（Binary Search Tree, BST）是指：该树的左子树节点值 <= 父节点值 <= 右子树节点值。因此对于一个二叉搜索树，可以在O(nlogn)的时间内查找一个值是否存在：从根节点开始，若查找值大于当前节点值，则往右走；否则，往左走。同时，二叉搜索树的中序遍历（左父右）结果，是从小到大的数组；右父左的遍历结果，则是从大到小的数组。

669.修剪二叉搜索树(easy)

给定一个二叉查找树和两个整数 L 和 R，且 L < R，试修剪此二叉查找树，使得修剪后所有节点的值都在 [L, R] 的范围内。

解题思路：根据二叉搜索树的特点，检查当前节点值

• 若当前节点值小于L，则直接扔掉父节点和左子树，去右子树寻找答案
• 若当前节点值大于L，则直接扔掉父节点和右子树，去左子树寻找答案
• 若当前节点值符合条件，则需继续到两个子树中修剪，并更新左右子树，返回root即可

递归截至条件：当前二叉树已空

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return root;
        // 根据二叉搜索树的特性，丢弃部分子树
        if(root.val > high) return trimBST(root.left, low, high);
        if(root.val < low) return trimBST(root.right, low, high);

        // 当前节点已符合要求，继续修建左右子树
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

530.二叉搜索树的最小绝对差(easy)

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

解题思路：二叉树搜索的中序遍历结果就是一个从小到大排好序的数组。因此可以直接在中序遍历过程中直接获得全局 差绝对值最小值

class Solution {
    TreeNode prev;
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        inOrder(root);
        return min;
    }

    public void inOrder(TreeNode root){
        if(root == null) return;

        inOrder(root.left);
        if(prev != null) min = Math.min(min, root.val - prev.val);
        prev = root;
        inOrder(root.right);
    }
}

235. 二叉搜索树的最近公共祖先(easy)

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先（所有节点的值都是唯一的）。

解题思路：根据二叉搜索树 左子树节点 <= 父节点 <= 右子树节点的性质，

• 如果p,q分布在两个子树中，则最近公共祖先必为父节点；
• 如果都在左子树（或者右子树）中，则去左子树（或者右子树）中继续搜索

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		// 都在左子树
        if(p.val < root.val && q.val < root.val)  return lowestCommonAncestor(root.left, p, q);
        // 都在右子树
        if(p.val > root.val && q.val > root.val)  return lowestCommonAncestor(root.right, p, q);
		// 分列两侧
        return root;
    }
}

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先（所有节点的值都是唯一的，且p!=q）。

解题思路：和二叉搜索树的思路类似，判断p和q相对于本节点的位置：

• 如果p和q分散在本节点的左右两侧，则本节点为其最近公共祖先
• 如果p和q都在左侧，则到左子树递归查找最近公共祖先；如果都在右侧，则到右子树递归查找最近公共祖先

通过设置递归退出条件为“在从本节点到叶子节点过程中，遇到了p或者q”，如果没遇到，则为null；通过判断是否为null，确定p和q相对于本节点的位置。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 到叶子节点了(初始的截止条件)，或者 碰到了p或q（找出它俩分散的位置：本节点两侧还是某一侧）
        if(root == null || root == p || root == q) return root;

        // 去左子树找是否存在p和q的最近公共祖先
        TreeNode tmp_left = lowestCommonAncestor(root.left, p, q);
        TreeNode tmp_right = lowestCommonAncestor(root.right, p, q);
        
        if(tmp_left == null) return tmp_right;  // 左子树中没有遇到p和q，那它俩必定在右子树中了，去右子树找最近公共祖先
        if(tmp_right == null) return tmp_left;  

        return root; // p和q分散在两个子树中，则根节点为其最近公共祖先
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点(easy)

给定一棵二叉搜索树，请找出其中第k大的节点。

解题思路：二叉搜索树的中序遍历结果为顺序存储，而右父左则为从大到小的排序结果。

class Solution {
	int count = 0, res = 0;
    public int kthLargest(TreeNode root, int k){
        inOrder(root, k);
        return res;
    }

    public void inOrder(TreeNode root, int k){
        if(root == null) return;

        inOrder(root.right, k);
        if(++count == k) {
            res = root.val;
            return;
        }
        inOrder(root.left, k);
    }
} 

// 中序遍历先拿到整个数组，效率比上一个方法低
class Solution {
    List<Integer> list = new ArrayList<>();

    public int kthLargest(TreeNode root, int k) {
        inOrder(root);
        return list.get(list.size() - k);
    }
	
    public void inOrder(TreeNode root){
        if(root == null) return;

        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }
}

🌟 字典树

字典树（Trie）常用于判断字符串是否存在或者是否具有某种字符串前缀。

为什么需要用字典树解决这类问题呢？假如我们有一个储存了近万个单词的字典，即使我们使用哈希，在其中搜索一个单词的实际开销也是非常大的，且无法轻易支持搜索单词前缀。然而由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 O(n)——近似 O(1)的时间内完成搜索，且额外开销非常小

208.实现 Trie (medium)

根节点是26位的TrieNode数组，如果某个索引处为空，则表示没有这个字母；如果不为空，则可以看着此字母存在，此索引处存储的TrieNode中又包含一个26位的数组。周而复始，通过这种链接串出了一个个字符串。

class Trie {

    // 定义基本结构
    class TrieNode{
        private boolean isEnd;  // 标明该节点是否是一个串的结束
        TrieNode[] next;  // 子节点

        public TrieNode(){  // 无参构造
            isEnd = false;
            next = new TrieNode[26];
        }
    }

    // 定义哨兵节点
    private TrieNode root;


    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for(char c : word.toCharArray()){
             // 此TrieNode还没有存储此字符，创建TrieNode节点存储(索引对应着字符，索引不为空则代表着字符存在)
            if(node.next[c-'a'] == null){ 
                node.next[c-'a'] = new TrieNode();  // 对TrieNode的next属性进行修改（此处引用传递？
            }
            node = node.next[c-'a'];   // 往下移动，继续构建 
        }
        node.isEnd = true;  // 标志为字符串末尾
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for(char c : word.toCharArray()){  // 一个个查该字符串是否存在于node中，若不存在，直接返回false
            if(node.next[c-'a'] == null) return false;  
            node = node.next[c-'a']; 
        }
        return node.isEnd;  // 走到了Trie末尾，才是真正的包含此单词
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(char c : prefix.toCharArray()){
            if(node.next[c-'a'] == null) return false;  
            node = node.next[c-'a']; 
        }
        return true;  // 前缀无需走到字典树中单词的末尾，只需要遍历完前缀字符串即可
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

十四、指针三剑客：图

🌟 数据结构介绍

作为指针三剑客之三，图是树的升级版。图通常分为有向（directed）或无向（undirected） ，有循环（cyclic）或无循环（acyclic） ，所有节点相连（connected）或不相连（disconnected） 。

树即是一个相连的无向无环图，而另一种很常见的图是有向无环图（Directed Acyclic Graph，DAG）

图通常有两种表示方法。假设图中一共有 n 个节点、m 条边。

• 邻接矩阵（adjacency matrix） ：我们可以建立一个 n×n 的矩阵 G，如果第 i 个节点连向第 j 个节点，则 G[i][j] = 1，反之为 0；如果图是无向的，则这个矩阵一定是对称矩阵，即 G[i][j] = G[j][i]。
• 邻接链表（adjacency list） ：我们可以建立一个大小为 n 的数组，每个位置 i 储存一个数组或者链表，表示第 i 个节点连向的其它节点。邻接矩阵空间开销比邻接链表大，但是邻接链表不支持快速查找 i 和 j 是否相连，因此两种表示方法可以根据题目需要适当选择。除此之外，我们也可以直接用一个 m × 2 的矩阵储存所有的边。

🌟 二分图

二分图算法也称为染色法，是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色，并且保证相邻节点的颜色不同，那么图二分。

785.判断二分图(medium)

若无向图 G=(V,E)的顶点集 V可以分割为两个互不相交的子集，且图中每条边的两个顶点分别属于不同的子集，则称图 G 为一个二分图。

解题思路：利用队列和BFS，对未染色的节点进行染色，并且检测是否有颜色相同的相邻节点存在。

• class Solution {
      public boolean isBipartite(int[][] graph) {
          int n = graph.length;  // 节点的个数
          if(n == 0) return true;
          int[] color = new int[n]; // 0表示未检查过的节点，1和-1表示两种不同的颜色
          LinkedList<Integer> queue = new LinkedList<>();
  
          for(int i = 0; i < n; i++){
              if(color[i] == 0){  // 若该节点尚未染色
                  color[i] = 1;
                  queue.add(i);  // 加到队列中以检查相邻节点颜色
              }
              while(!queue.isEmpty()){
                  int node = queue.removeFirst();  // 弹出已染色的节点i
                  for(int j : graph[node]){   // j为 所有 与节点node连接的节点
                      if(color[j] == 0){                         
                          color[j] = -color[node] ;  // 此节点未染色，则根据node节点的情况进行染色
                          queue.push(j);
                      }else if(color[j] == color[node]){   // 此节点染色了，还和node节点颜色一样，gg
                          return false;
                      }
                  }
              }
          }
          return true;
      }
  }

// 深度优先遍历
class Solution {
    int[] color;
    int[][] graph;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        if(n == 0) return true;
        color = new int[n];  //  0 表示未被访问，赋值为 1 或者 -1 表示两种不同的颜色。 
        this.graph = graph;

        for (int i = 0; i < n; i++) {
            if (color[i] == 0 && !dfs(i, 1)) {   // 对每个未染色的节点进行染色。若无法完成染色，dfs(i, 1)=false，不必继续循环，直接返回false即可
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int node, int c) {
        // 若节点已经被染色了，则判断它的颜色是否与本次要染的颜色相同，不同则返回 false。
        if (color[node] != 0) {
            return color[node] == c;
        }
        
        // 对 当前节点 进行染色
        color[node] = c;
        // 将 当前节点的所有邻接点 染为相反的颜色。
        for (int j: graph[node]) {
            if (!dfs(j, -c)) {  // 相邻节点无法完成染色（存在某个相邻节点与本节点颜色一致），则返回false
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean isBipartite(int[][] graph) {
        // 初始化并查集
        UnionFind uf = new UnionFind(graph.length);
        // 遍历每个顶点，将当前顶点的所有邻接点进行合并
        for (int i = 0; i < graph.length; i++) {
            int[] adjs = graph[i];
            for (int w: adjs) {
                // 若某个邻接点与当前顶点已经在一个集合中了，说明不是二分图，返回 false。
                if (uf.isConnected(i, w)) {
                    return false;
                }
                uf.union(adjs[0], w);
            }
        }
        return true;
    }
}

// 并查集
class UnionFind {
    int[] roots;
    public UnionFind(int n) {
        roots = new int[n]; 
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    public int find(int i) {
        if (roots[i] == i) {
            return i;
        }
        return roots[i] = find(roots[i]);
    }

    // 判断 p 和 q 是否在同一个集合中
    public boolean isConnected(int p, int q) {
        return find(q) == find(p);
    }

    // 合并 p 和 q 到一个集合中
    public void union(int p, int q) {
        roots[find(p)] = find(q);
    }
}

🌟 拓扑排序

拓扑排序（topological sort）是一种常见的，对有向无环图排序的算法。给定有向无环图中的N 个节点，我们把它们排序成一个线性序列；若原图中节点 i 指向节点 j，则排序结果中 i 一定在j 之前。拓扑排序的结果不是唯一的，只要满足以上条件即可。

210.课程表 II(medium)

给定 N 个课程和这些课程的前置必修课，求可以一次性上完所有课的顺序。

解题思路：

【BFS】

先为每个节点（课程）建立一个邻接表，并计算每个节点的入度。之后，遍历一遍所有节点，将入度为0的节点（即已经修完所有前置课程了）放入队列中。

在每次从队列中获取节点时，将该节点放入结果集的尾部，并将它指向的所有课程的入度都减1；若在此过程中，若有课程的入度降到0了，则将该课程也加入到队列中。

最终，校验结果集中元素的数量是否等于课程的数量，相同的话就已拍好序了，若不同，则说明里面存在环，未完成排序，返回空数组即可。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses <= 0) return new int[0];

        int[] preCount = new int[numCourses];  // 每门课的前置课程数量
        HashSet<Integer>[] postCourse = new HashSet[numCourses];  // 每门课的后续课程
        for(int i = 0; i < numCourses; i++){
            postCourse[i] = new HashSet<>();  // 注意HashSet这里的<>
        }
        for(int[] pre: prerequisites){
            postCourse[pre[1]].add(pre[0]);  // 统计每门课的前置课程数量、后续课程
            preCount[pre[0]]++;   // [2,0] --> 课程0的后续课程包含课程2，要修2必先修0
        }


        int[] res = new int[numCourses];
        int idx = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(preCount[i] == 0) queue.add(i);  // 已经修完所有前置课程的课程们
        }

        // 更新未修完的课程们的 前置课程数
        while(!queue.isEmpty()){
            int finishedCourseIdx = queue.removeFirst();
            res[idx++] = finishedCourseIdx;
            for(int courseIdx : postCourse[finishedCourseIdx]){
                preCount[courseIdx]--;
                if(preCount[courseIdx] == 0)  queue.add(courseIdx);  // 部分课程此时也修完了所有前置课程了
            }
        }

        if(idx == numCourses) return res;  // 校验成功修完的总课程，相同则不存在环
        return new int[0];   
    }
}

十五、复合数据结构

🌟 并查集

并查集（union-find, 或 disjoint set）可以动态地连通两个点，并且可以非常快速地判断两个点是否连通。假设存在 n 个节点，我们先将所有节点的父亲标为自己；每次要连接节点 i 和 j 时，我们可以将 i 的父亲标为 j；每次要查询两个节点是否相连时，我们可以查找 i 和 j 的祖先是否最终为同一个人

并查集样例，其中 union 操作可以将两个集合连在一起，find 操作可以查找给定节点的祖先，并且如果可以的话，将集合的层数/高度降低。

684.冗余连接

在无向图找出一条边，移除它之后该图能够成为一棵树（即无向无环图） 。如果有多个解，返回在原数组中位置最靠后的那条边

解题思路：可以通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。

class Solution {

    // 并查集类中包含union和find方法，其中union方法根据某种属性构建对象间的联系、find方法根据这种联系寻找对象。
    // 本冗余连接例子中，初始化每个节点的父节点为本身，之后通过union方法调用find方法分别寻找节点A和节点B的父节点，
    //    如果两者父节点相同，则将这两个节点作为坐标，添加到冗余连接结果数组中；
    //    如果父节点不想同，则设置节点A为节点B的父节点，构建对象间的联系。

    public int[] findRedundantConnection(int[][] edges) {
        UnionAndFind unionArray =  new UnionAndFind(edges.length + 1);  // m条边，m+1个顶点
        for(int[] edge: edges){
            unionArray.union(edge[0], edge[1]);
        }
        return unionArray.res;
    }

    private class UnionAndFind{
        int[] parents;
        int[] res;

        public UnionAndFind(int n){
            parents = new int[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
            }
            res = new int[2];
        }

        public void union(int x, int y){
            int x_parent = find(x);
            int y_parent = find(y);
            if(x_parent != y_parent){
                // 将x设为y的父节点
                parents[y_parent] = x_parent;
            }else{
                res[0] = x;
                res[1] = y;
            }            
        }

        public int find(int node){
            // 【压缩路径】 如果其父节点为自身，则直接返回；否则再寻找父节点的父节点，并将本节点的父节点直接设置为老祖宗
            //  一个不是很恰当的类比，判断句容县和盱眙县是不是同一个省的，得先查找市，再找到省；但如果都是县级市，直接跳过市连接到了省，判断速度加快
            if(parents[node] != node)  parents[node] = find(parents[node]);
            return parents[node];
        }

    }
}

🌟 LRU缓存

146.LRU 缓存机制(medium)

设计一个固定大小的，最少最近使用缓存 (least recently used cache, LRU)。每次将信息插入未满的缓存的时候，以及更新或查找一个缓存内存在的信息的时候，将该信息标为最近使用。在缓存满的情况下将一个新信息插入的时候，需要移除最旧的信息，插入新信息，并将该信息标为最近使用。

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

解题思路：

LRU可以采用哈希表+双向链表构成的哈希链表来实现。

class LRUCache {
    HashMap<Integer, ListNode> cache;
    int capacity;
    ListNode head;
    ListNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)) return -1;
    
        ListNode node = cache.get(key);   
        node.next.pre = node.pre;
        node.pre.next = node.next;
        addToTail(node);

        return node.value;
    }
    
    public void put(int key, int value) {
        if(get(key) != -1){
            ListNode node = cache.get(key);
            node.value = value;
            return;
        }

        ListNode node = new ListNode(key, value);
        cache.put(key, node);
        addToTail(node);
        // 核查添加完，是否超出容量
        if(cache.size() > capacity){
            cache.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }
    }

    public void addToTail(ListNode node){
        node.pre = tail.pre;
        tail.pre.next = node;
        node.next = tail;
        tail.pre = node;
    }

    private class ListNode{
        int key;
        int value;
        ListNode pre;
        ListNode next;

        public ListNode(int key, int value){
            this.key = key;
            this.value = value;
            pre = null;
            next = null;
        }
    }
}


LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4