LeetCode-Hot100

数组

1.数组——最大子数组和

解题思路：动态规划

动态规划解决问题的步骤：1.理解题意。题目要求只返回结果，不要求得到最大的连续子数组的哪一个，这样的问题常常可以用动态规划。

2.定义子问题：eg：以 −2 结尾的连续子数组的最大和是多少？

3.定义状态转移方程

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

2.数组——合并区间

解题思路：将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

• 如果列表为空，或者列表中最后一个区间的结束值小于当前区间的起始值，则将当前区间直接加入列表。
• 否则，说明当前区间与列表中最后一个区间有重叠或相邻，需要合并。合并的方式是更新列表中最后一个区间的结束值为两者结束值的较大者。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class merge {public static void main(String[] args) {int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};int[][] res = merge(intervals);for (int[] re : res) {for (int i : re) {System.out.print(i);}System.out.println();}}public static int[][] merge(int[][] intervals) {//排序Arrays.sort(intervals, (a, b) -> a[0] - b[0]);//用集合存取合并区间以后的数组List<int[]> mergedIntervals = new ArrayList<>();for(int i = 0; i < intervals.length; i++) {int L = intervals[i][0];int R = intervals[i][1];if(mergedIntervals.size() == 0 || mergedIntervals.get(mergedIntervals.size() - 1)[1] < L) {mergedIntervals.add(new int[]{L, R});}else {mergedIntervals.get(mergedIntervals.size()-1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], R);}}return mergedIntervals.toArray(new int[mergedIntervals.size()][]);}
}

3.数组——轮转数组

解题思路：开辟新的数组，存储移动后的数组的位置，再复制到原数组

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;int[] newNums = new int[n];for (int i = 0; i < n; i++) {newNums[(i+k)%n] = nums[i];}System.arraycopy(newNums, 0, nums, 0, n);}
}

4.数组——除自身以外数组的乘积

解题思路：1.暴力破解，两个for循环，第一个用于遍历nums，第二个求除去nums[i]以外的其他数的乘积

2.降低时间复杂度：两个数组，每个数组存取num[i]的左边和右边的乘积，该数的anwser不就等于左边的乘积和右边的乘积相乘

package CodeThink;public class productExceptSelf {public static void main(String[] args) {int[] nums = new int[]{1,2,3,4};int[] res = productExceptSelf(nums);for (int re : res) {System.out.println(re);}}//暴力破解public static int[] productExceptSelf(int[] nums) {int[] res = new int[nums.length];for(int i = 0 ; i < nums.length ; i++){res[i] = 1;for(int j = 0 ; j < nums.length ; j++){if(i != j){res[i] *= nums[j];}}}return res;}//改进,降低时间复杂度public static int[] productExceptSelf2(int[] nums) {int len = nums.length;int[] L = new int[len];int[] R = new int[len];int[] ans = new int[len];L[0] = 1;for(int i = 1 ; i < len ; i++){L[i] = L[i - 1] * nums[i - 1];}R[len - 1] = 1;for(int i = len - 2 ; i >=0 ; i--){R[i] = R[i + 1] * nums[i + 1];}for(int i = 0 ; i < len ; i++){ans[i] = L[i] * R[i];}return ans;}
}

5.数组——缺失的第一个正数

解题思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。

• 这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。

package CodeThink;public class firstMissingPositive {public static void main(String[] args) {int[] nums = {1,2,0};System.out.println(firstMissingPositive(nums));}public static int firstMissingPositive(int[] nums) {int len = nums.length;//我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。for (int i = 0; i < len; i++) {while (nums[i] > 0 && nums[i] < len && nums[nums[i] - 1] != nums[i]) {swap(nums,nums[i]-1, i);}}for (int i = 0; i < len; i++) {//第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。if (nums[i] != i + 1) {return i + 1;}}// 都正确则返回数组长度 + 1return len+1;}private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

矩阵

6.矩阵——矩阵置零

解题思路：标记法，先遍历一次矩阵，如果当前元素为零，就记录下对应的行号和列号，行号和列号用两个一维数组存储，然后再次遍历，如果对应的行号和列号被记录过，则遍历的时候将对应的行和列置为零

package CodeThink;class setZeroes {public void setZeroes(int[][] matrix) {int[] row = new int[matrix.length];int[] col = new int[matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {if (matrix[i][j] == 0) {row[i] = 1;col[j] = 1;}}}for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {if (row[i]==1||col[j]==1){matrix[i][j] = 0;}}}}public static void main(String[] args) {int[][] matrix= {{1,1,1},{1,0,1},{1,1,1}};setZeroes setZeroes = new setZeroes();setZeroes.setZeroes(matrix);for (int[] ints : matrix) {for (int anInt : ints) {System.out.print(anInt+" ");}System.out.println();}}
}

7.矩阵——螺旋矩阵

解题思路：四个指针转圈圈

• 从左到右，顶部一层遍历完往下移一位，top++；
• 从上到下，遍历完右侧往左移一位，right--；
• 从右到左，判断top <= bottom，即是否上下都走完了。遍历完底部上移，bottom--；
• 从下到上，判断left <= right，遍历完左侧右移，left++；

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>();int rows = matrix.length;int cols = matrix[0].length;int left=0,right=cols-1,top=0,bottom=rows-1;while(left<=right&&top<=bottom){//从左到右for(int i=left; i<=right; i++){list.add(matrix[top][i]);}top++;//从上到下for(int i=top; i<=bottom; i++){list.add(matrix[i][right]);}right--;//从右到左if(top<=bottom){for(int i=right; i>=left; i--){list.add(matrix[bottom][i]);}}bottom--;//从下到上if(left<=right){for(int i=bottom; i>=top; i--){list.add(matrix[i][left]);}}left++;}return list;}
}

8.矩阵——旋转图像

解题思路：

1.辅助数组

2.原地修改

package CodeThink;public class rotatematrix {public void rotate(int[][] matrix) {int n = matrix.length;int [][] matrix1 = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix1[j][n-i-1] = matrix[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = matrix1[i][j];}}}public void rotate2(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n / 2; i++) {for (int j = 0; j < (n + 1) / 2; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[n - 1 - j][i];matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];matrix[j][n - 1 - i] = tmp;}}}public static void main(String[] args) {int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};rotatematrix rotatematrix = new rotatematrix();rotatematrix.rotate(matrix);}
}

9.矩阵——搜索二维矩阵 II

解题思路：

1.暴力搜索

2.二分查找

package CodeThink;public class searchMatrix {public boolean searchMatrix(int[][] matrix, int target) {boolean result = false;for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {if (matrix[i][j] == target) {result = true;}}}return result;}public boolean searchMatrix2(int[][] matrix, int target) {for (int[] row : matrix) {int index = search(row,target);if(index >= 0){return true;}}return false;}private int search(int[] nums, int target) {int low = 0, high = nums.length - 1;while (low <= high) {int mid = (high + low) / 2;int num = nums[mid];if (num == target) {return mid;}else if (num < target) {low = mid + 1;}else {high = mid - 1;}}return -1;}public static void main(String[] args) {int[][] matrix = {{1,2,3,4,5,6,7,8,9},};searchMatrix searchMatrix = new searchMatrix();System.out.println(searchMatrix.searchMatrix2(matrix, 9));}
}

链表

10.链表——相交链表

解题思路：我走过你走过的路，如果我们能够相遇，就证明我们有交点

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null||headB==null){return null;}ListNode PA =headA,PB=headB;while(PA!=PB){if(PA!=null){PA = PA.next;}else if(PA==null){PA = headB;}if(PB!=null){PB = PB.next;}else if(PB==null){PB = headA;}}   return PA;                                }
}

11.链表——反转链表

解题思路：遍历反转指向，递归或者迭代

class Solution {public ListNode reverseList(ListNode head) {return reverse(head,null);}public ListNode reverse(ListNode current,ListNode pre){if(current==null) return pre;ListNode temp = current.next;current.next = pre;return reverse(temp,current);}
}

12.链表——回文链表

解题思路:将链表的值复制到数组中，用双指针判断是否是回文

public static boolean isPalindrome(ListNode head) {//讲链表的值复制到数组中ArrayList<Integer> list = new ArrayList<>();while (head != null) {list.add(head.val);head = head.next;}//使用双指针判断是否回文int left=0,right=list.size()-1;while (left < right) {if (!list.get(left).equals(list.get(right))) {return false;}left++;right--;}return true;}

13.链表——环形链表

解题思路：

1.将遍历过的解答存储到set结点，如果再次遍历到该结点，则证明链表中存在环

2.利用快慢指针判断是否有环，相遇则代表有环

//解法1
public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();while (head != null && head.next != null) {if(set.contains(head)) {return true;}set.add(head);head = head.next;}return false;}
//解法2
public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {return true;}}return false;}

14.链表——环形链表 II

解题思路：利用快慢指针判断是否有环，相遇则代表有环

public ListNode detectCycle(ListNode head) {ListNode quickNode = head;ListNode slowNode = head;//利用快慢指针判断是否有环while(quickNode!=null&&quickNode.next!=null){quickNode = quickNode.next.next;slowNode = slowNode.next;//相遇代表有环if(quickNode == slowNode){ListNode current = head;while(current != quickNode){current = current.next;quickNode = quickNode.next;}return current;}}return null;}

15.链表——合并两个有序链表

解题思路：遍历两条链表将较小的结点加入新的链表，直到其中一条遍历完成，然后处理另外一条未遍历完成的链表

package CodeThink;public class mergeTwoLists {public static void main(String[] args) {ListNode l1 = new ListNode(-9);ListNode l2 = new ListNode(3);l1.next = l2;ListNode r1 = new ListNode(5);ListNode r2 = new ListNode(7);r1.next = r2;ListNode merge = mergeTwoLists(l1, r1);while (merge != null) {System.out.println(merge.val);merge = merge.next;}}public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode result = new ListNode();ListNode temp = result;//遍历两条升序链表，加入新链表while(list1!=null && list2!=null){if(list1.val <= list2.val){temp.next = list1;temp = temp.next;list1 = list1.next;} else if (list1.val > list2.val) {temp.next = list2;temp = temp.next;list2 = list2.next;}}//处理其中一条链表为空，另外一条还未遍历完的情况temp.next = list1!=null?list1:list2;return result.next;}
}

16.链表——两数相加

解题思路：遍历两条链表相加，注意两条链表的长度不一致，采用补0的方法补齐，处理进位的情况

package CodeThink;public class addTwoNumbers {public static void main(String[] args) {ListNode l1 = new ListNode(9);ListNode l2 = new ListNode(9);ListNode l3 = new ListNode(9);l1.next = l2;l2.next = l3;l3.next = null;ListNode r1 = new ListNode(9);ListNode r2 = new ListNode(9);r1.next = r2;ListNode merge = addTwoNumbers(l1, r1);while (merge != null) {System.out.println(merge.val);merge = merge.next;}}public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = new ListNode();ListNode cur = new ListNode(0);head.next = cur;while (l1 != null || l2 != null) {//补零if (l1 == null) {l1 = new ListNode(0);}if (l2 == null) {l2 = new ListNode(0);}//当前链表节点对应的值int temp = (l1.val + l2.val + cur.val ) % 10;//进位的数int add = (l1.val + l2.val + cur.val) / 10;//给当前节点赋值，并且给下一节点进位赋值cur.val = temp;//防止最后多加0if(add!=0||l1.next!=null||l2.next!=null){cur.next = new ListNode(add);cur = cur.next;}//l1,2链表指向下一节点l1 = l1.next;l2 = l2.next;}return head.next;}
}

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

解题思路：遍历直接进行节点交换

class Solution {public ListNode swapPairs(ListNode head) {//虚拟头节点ListNode virtualhead = new ListNode();virtualhead.next = head;//创建临时节点进行遍历ListNode current = virtualhead;while (current.next != null && current.next.next != null) {ListNode temp1 = current.next;ListNode temp2 = current.next.next.next;current.next = current.next.next;current.next.next = temp1;temp1.next = temp2;current = current.next.next;}return virtualhead.next;}
}

18.链表——K 个一组翻转链表

解题思路：我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。

package CodeThink;public class reverseKGroup {public static void main(String[] args) {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = null;ListNode res = reverseKGroup(n1,2);while (res != null) {System.out.println(res.val);res = res.next;}}public static ListNode reverseKGroup(ListNode head, int k) {//创建一个虚拟头结点ListNode hair = new ListNode(0);hair.next = head;ListNode pre = hair;while(head != null) {ListNode tail = pre;//查看剩余部分的长度是否大于等于kfor (int i = 0; i < k; i++) {tail = tail.next;if(tail == null) {return hair.next;}}ListNode next = tail.next;ListNode[] reverse = myReverse(head,tail);head = reverse[0];tail = reverse[1];//把子链表重新接回原链表pre.next = head;tail.next = next;pre = tail;head = tail.next;}return hair.next;}//反转链表private static ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev = tail.next;ListNode p = head;while(prev != tail){ListNode next = p.next;p.next = prev;prev = p;p = next;}return new ListNode[]{tail,head};}
}

19.链表——随机链表的复制

解题思路：本题的难点在于随机结点的拷贝，利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。

package CodeThink;import java.util.HashMap;
import java.util.Map;public class copyRandomList {public static void main(String[] args) {Node node1 = new Node(1);Node node2 = new Node(2);node1.next = node2;node1.random = node2;node2.next = null;node2.random = node2;Node node3 = copyRandomList(node1);while (node3 != null) {System.out.println(node3.val);node3 = node3.next;}}public static Node copyRandomList(Node head) {if (head == null) return null;Node cur = head;Map<Node, Node> map = new HashMap<>();//复制各结点，并建立映射关系while (cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}cur = head;//构建新链表while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}
}
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}

20.链表——排序链表

解题思路：

1.用数值存取链表的值，然后排序，创建新链表

2.归并排序

package CodeThink;import java.util.Arrays;public class sortList {public static void main(String[] args) {ListNode n1 = new ListNode(-1);ListNode n2 = new ListNode(5);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(0);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = null;ListNode res = sortList(n1);while (res != null) {System.out.println(res.val);res = res.next;}}public static ListNode sortList(ListNode head) {if (head == null){return null;}// 记录长度ListNode current =  head;int n = 0;while (current != null){n++;current = current.next;}// 值放入数组方便排序int[] arr = new int[n];current = head;for (int i = 0; i < arr.length; i++) {arr[i] = current.val;current = current.next;}Arrays.sort(arr);// 连接新链表ListNode newNode = new ListNode(arr[0]);current = newNode;for (int i = 1; i < arr.length; i++) {current.next = new ListNode(arr[i]);current = current.next;}return newNode;}
}

21.链表——合并 K 个升序链表

解题思路：每个链表本身有序，用优先队列存储每个链表的第一个结点，优先队列中最小的结点出栈，然后将该节点对应的链表的下一结点加入队列，不断重复

package CodeThink;import java.util.PriorityQueue;public class mergeKLists {public static void main(String[] args) {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(4);ListNode n3 = new ListNode(5);n1.next = n2;n2.next = n3;n3.next = null;ListNode r1 = new ListNode(1);ListNode r2 = new ListNode(3);ListNode r3 = new ListNode(4);r1.next = r2;r2.next = r3;r3.next = null;ListNode l1 = new ListNode(2);ListNode l2 = new ListNode(6);l1.next = l2;l2.next = null;ListNode[] lists = new ListNode[3];lists[0] = n1;lists[1] = r1;lists[2] = l1;ListNode node = mergeKLists(lists);while (node != null) {System.out.println(node.val);node = node.next;}}public static ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}//使用优先队列来存储链表的值PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->a.val-b.val);//将所有链表的头结点加入优先队列for (ListNode list : lists) {if (list != null) {pq.add(list);}}ListNode dummy= new ListNode();ListNode cur = dummy;//从优先队列中取出最小的结点，并将下一个结点加入队列while(!pq.isEmpty()) {ListNode node = pq.poll();cur.next = node;cur = cur.next;if(node.next != null) {pq.add(node.next);}}return dummy.next;}
}

22.链表——LRU 缓存

解题思路：参考LinkedHashMap的源码

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
}

23.链表——两两交换链表中的节点

解题思路：创建临时节点进行遍历，直接交换结点

class Solution {public ListNode swapPairs(ListNode head) {//虚拟头节点ListNode virtualhead = new ListNode();virtualhead.next = head;//创建临时节点进行遍历ListNode current = virtualhead;while (current.next != null && current.next.next != null) {ListNode temp1 = current.next;ListNode temp2 = current.next.next.next;current.next = current.next.next;current.next.next = temp1;temp1.next = temp2;current = current.next.next;}return virtualhead.next;}
}

字串

24.字串——和为 K 的子数组

解题思路：暴力破解，两个for循环，第一层遍历数组中的每个数，第二层判断是否存在和为K的子数组

package CodeThink;class subarraySum {public int subarraySum(int[] nums, int k) {int sum = 0;for (int i = 0; i < nums.length; i++) {int temp = 0;for(int j = i; j < nums.length; j++) {temp += nums[j];if(temp == k) {sum++;continue;}}}return sum;}public static void main(String[] args) {subarraySum obj = new subarraySum();System.out.println(obj.subarraySum(new int[]{1,1,1}, 2));}
}

25.字串——滑动窗口最大值

解题思路：其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;PriorityQueue<int []> maxHeap = new PriorityQueue<int []>(new Comparator<int[]>() {public int compare(int[] o1, int[] o2) {return o1[0]!=o2[0]?o2[0]-o1[0]:o2[1]-o1[1];}});for(int i=0; i<k; ++i){maxHeap.offer(new int [] {nums[i],i});}int[] result = new int[n-k+1];result[0] = maxHeap.peek()[0];for(int i=k; i<n; ++i){maxHeap.offer(new int [] {nums[i],i});while (maxHeap.peek()[1] <= i-k){maxHeap.poll();}result[i-k+1] = maxHeap.peek()[0];}return result;}
}

26.字串——最小覆盖子串

解题思路：原理和 209 题一样，按照视频中的做法，我们枚举 s 子串的右端点 right（子串最后一个字母的下标），如果子串涵盖 t，就不断移动左端点 left 直到不涵盖为止。在移动过程中更新最短子串的左右端点。

具体来说：

初始化 ansLeft=−1, ansRight=m，用来记录最短子串的左右端点，其中 m 是 s 的长度。

用一个哈希表（或者数组）cntT 统计 t 中每个字母的出现次数。

初始化 left=0，以及一个空哈希表（或者数组）cntS，用来统计 s 子串中每个字母的出现次数。

遍历 s，设当前枚举的子串右端点为 right，把 s[right] 的出现次数加一。

遍历 cntS 中的每个字母及其出现次数，如果出现次数都大于等于 cntT 中的字母出现次数：

如果 right−left<ansRight−ansLeft，说明我们找到了更短的子串，更新 ansLeft=left, ansRight=right。

把 s[left] 的出现次数减一。

左端点右移，即 left 加一。

重复上述三步，直到 cntS 有字母的出现次数小于 cntT 中该字母的出现次数为止。

最后，如果 ansLeft<0，说明没有找到符合要求的子串，返回空字符串，否则返回下标 ansLeft 到下标 ansRight 之间的子串。

class Solution {public String minWindow(String S, String t) {char[] s = S.toCharArray();int m = s.length;int ansLeft = -1;int ansRight = m;int[] cnt = new int[128];int less = 0;for (char c : t.toCharArray()) {if (cnt[c] == 0) {less++; // 有 less 种字母的出现次数 < t 中的字母出现次数}cnt[c]++;}int left = 0;for (int right = 0; right < m; right++) { // 移动子串右端点char c = s[right]; // 右端点字母cnt[c]--; // 右端点字母移入子串if (cnt[c] == 0) { // 原来窗口内 c 的出现次数比 t 的少，现在一样多less--;}while (less == 0) { // 涵盖：所有字母的出现次数都是 >=if (right - left < ansRight - ansLeft) { // 找到更短的子串ansLeft = left; // 记录此时的左右端点ansRight = right;}char x = s[left]; // 左端点字母if (cnt[x] == 0) {// x 移出窗口之前，检查出现次数，// 如果窗口内 x 的出现次数和 t 一样，// 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少less++;}cnt[x]++; // 左端点字母移出子串left++;}}return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);}
}

哈希

27.哈希——两数之和

解题思路：

1.暴力解法 两个for循环解决问题 时间复杂度为 O(n2)

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];}
}

2.哈希表

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (map.containsKey(target - nums[i])) {return new int[]{map.get(target - nums[i]), i};}map.put(nums[i], i);}return new int[0];}
}

28.哈希——字母异位词分组

解题思路：字母相同，但排列不同的字符串，排序后都一定是相同的。因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。

import java.util.*;public class groupAnagrams {public static void main(String[] args) {String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};List<List<String>> list= groupAnagrams(strs);list.forEach(System.out::println);}public static List<List<String>> groupAnagrams(String[] strs) {//用map，key存储排序的后的字符串，value就是对应的字符串集合Map<String, List<String>> map = new HashMap<>();//遍历strsfor (String str : strs) {//讲字符串转为char数组char[] chars = str.toCharArray();//对字符串进行排序Arrays.sort(chars);//构建排序后的字符串String key = new String(chars);//如果map中存在key对应的list，返回该list集合，如果不存在，返回一个新的list集合List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);//将key和value存入mapmap.put(key, list);}//讲map转为List进行返回return new ArrayList<List<String>>(map.values());}
}

29.哈希——最长连续序列

解题思路：把输入放入map中，然后遍历判断。难点其实是要求时间复杂度为0.这里遍历的时候就需要做判断，只有当一个数是连续序列的第一个数是才进入内存循环

package CodeThink;import java.util.HashSet;
import java.util.Set;public class longestConsecutive {public static void main(String[] args) {int[] nums = {100,4,200,1,3,2};int res = longestConsecutive(nums);System.out.println(res);}public static int longestConsecutive(int[] nums) {Set<Integer> sets = new HashSet<>();for (int num : nums) {sets.add(num);}int max = 0;for (int set : sets) {if(!sets.contains(set-1)){int temp = 0;while(sets.contains(set)) {temp++;set++;}max = Math.max(max, temp);}}return max;}
}

栈

30.栈——有效的括号

解题思路：用栈存取字符串s，需要判断的是：1.左括号多余 2.右括号多余 3.括号不匹配

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<Character>();char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {//如果是左括号,入栈if (chars[i] == '(' || chars[i] == '{' || chars[i] == '[') {stack.push(chars[i]);}//如果是右括号，则出栈，判断是否是有效的括号else if (chars[i] == ')'||chars[i] == ']'||chars[i] == '}') {//解决右括号多余if (stack.isEmpty()) {return false;}//解决括号不匹配else if (chars[i] == ')') {if(stack.pop()!='(') {return false;}}else if (chars[i] == ']') {if(stack.pop()!='[') {return false;}}else if (chars[i] == '}') {if(stack.pop()!='{') {return false;}}}}//解决左括号多余if(stack.isEmpty()){return true;}return false;}
}

31.栈——最小栈

解题思路：用辅助栈

class MinStack {Stack<Integer> stack;Stack<Integer> minStack;/*  初始化堆栈对象。 */public MinStack() {stack  = new Stack<>();minStack = new Stack<>();minStack.push(Integer.MAX_VALUE);}/* 将元素val推入堆栈。  */public void push(int val) {stack.push(val);minStack.push(Math.min(val, minStack.peek()));}/* 删除堆栈顶部的元素。  */public void pop() {stack.pop();minStack.pop();}/*  获取堆栈顶部的元素。 */public int top() {return stack.peek();}/* 获取堆栈中的最小元素。  */public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

32.栈——字符串解码

解题思路：用栈堆字符串的元素进行存取，字符串的元素无非就是三种情况：1.括号 2.数字 3.字母

如果是数字入栈（需要判断是是否是连续的数字），【和字母入栈。】进行出栈直到遇到【，并且此时栈顶一定是数字。

class Solution {int ptr = 0;public String decodeString(String s) {LinkedList<String> stack = new LinkedList<>();while (ptr < s.length()) {char c = s.charAt(ptr);//如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈if(Character.isDigit(c)) {String digit = getDigits(s);stack.addLast(digit);}//如果当前的字符为字母或者左括号，直接进栈else if (Character.isLetter(c) || c=='[') {//获取一个字母并进栈stack.addLast(String.valueOf(s.charAt(ptr++)));}//如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字else {++ptr;LinkedList<String> temp = new LinkedList<>();while(!"[".equals(stack.peekLast())) {temp.addLast(stack.removeLast());}Collections.reverse(temp);//左括号出栈stack.removeLast();//此时栈顶为当前sub对应的字符串应该出现的次数int repTime = Integer.parseInt(stack.removeLast());StringBuffer sb = new StringBuffer();String o = getString(temp);//构建字符串while (repTime-- > 0){sb.append(o);}//将构造好的字符串入栈stack.addLast(sb.toString());}}return getString(stack);}//从字符串中提取连续的数字字符，直到遇到非数字字符为止public String getDigits(String s) {StringBuffer sb = new StringBuffer();while (Character.isDigit(s.charAt(ptr))) {sb.append(s.charAt(ptr++));}return sb.toString();}//将构造的栈转成字符串private String getString(LinkedList<String> temp) {StringBuffer sb = new StringBuffer();for(String s : temp) {sb.append(s);}return sb.toString();}
}

33.栈——每日温度

解题思路：

1.暴力破解，两个for循环，时间复杂度为O（n方）

2.单调栈：可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

package CodeThink;import java.util.Deque;
import java.util.LinkedList;public class dailyTemperatures {public static void main(String[] args) {int[] temperatures = {73,74,75,71,69,72,76,73};int[] res = dailyTemperatures2(temperatures);for (int re : res) {System.out.println(re);}}public static int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];int index = 0;for (int i = 0; i < temperatures.length-1; i++) {int flag = 0;for (int j = i + 1; j < temperatures.length; j++) {if (temperatures[i] < temperatures[j]) {res[index++] = j-i;flag = 1;break;}}if (flag == 0) {res[index++] = 0;}}return res;}public static int[] dailyTemperatures2(int[] temperatures) {int[] res = new int[temperatures.length];Deque<Integer> stack = new LinkedList<>();for(int i = 0; i < temperatures.length; i++) {int temperature = temperatures[i];while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {int PrevIndex = stack.pop();res[PrevIndex] = i - PrevIndex;}stack.push(i);}return res;}
}

34.栈——柱状图中最大的矩形

解题思路：每个柱子的高度决定了矩形的高度，而矩形的宽度由左右边界决定。左右边界分别就是左边第一个比当前柱子矮的柱子和右边第一个比当前柱子矮的柱子，计算每个柱子称为矩形高时的面积，最大的即为最大的矩形面积。

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int[] left = new int[n];  // 存储每个柱子左边第一个比它矮的柱子的索引int[] right = new int[n]; // 存储每个柱子右边第一个比它矮的柱子的索引Deque<Integer> mono_stack = new ArrayDeque<>(); // 单调栈，用于存储柱子的索引// 计算左边界的索引for (int i = 0; i < n; i++) {// 当栈不为空且栈顶柱子的高度大于等于当前柱子的高度时，弹出栈顶while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {mono_stack.pop();}// 如果栈为空，说明左边没有比当前柱子矮的柱子，左边界的索引为-1// 否则，左边界的索引为栈顶元素left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());// 将当前柱子的索引压入栈中mono_stack.push(i);}// 清空栈，准备计算右边界的索引mono_stack.clear();// 计算右边界的索引for (int i = n - 1; i >= 0; i--) {// 当栈不为空且栈顶柱子的高度大于等于当前柱子的高度时，弹出栈顶while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {mono_stack.pop();}// 如果栈为空，说明右边没有比当前柱子矮的柱子，右边界的索引为n// 否则，右边界的索引为栈顶元素right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());// 将当前柱子的索引压入栈中mono_stack.push(i);}int ans = 0; // 用于存储最大矩形面积// 遍历每个柱子，计算以该柱子为高度的矩形面积for (int i = 0; i < n; i++) {// 矩形的宽度为右边界的索引减去左边界的索引再减1// 矩形的高度为当前柱子的高度ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);}return ans; // 返回最大矩形面积}
}

堆

优先级队列（PriorityQueue）是Java中一个非常实用的数据结构，它基于堆实现，能够高效地管理具有优先级的元素。

35.堆——数组中的第K个最大元素

解题思路：利用优先级队列维护一个大小为k的小根堆，遍历数组，如果堆未满直接加入元素，如果堆满并且当前元素大于堆顶元素，堆顶元素出，当前元素进入堆，遍历完成后，堆顶元素即为数组中第k个最大元素。

package CodeThink;import java.util.PriorityQueue;public class findKthLargest {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>();for (int num : nums) {//如果堆的大小小于k，直接加入if(pq.size() < k){pq.offer(num);}else if(num > pq.peek()){pq.poll();pq.offer(num);}}return pq.peek();}public static void main(String[] args) {int[] nums = {3,2,3,1,2,4,5,5,6};findKthLargest obj = new findKthLargest();System.out.println(obj.findKthLargest(nums, 4));}
}

36.堆——前 K 个高频元素

解题思路：依然是使用优先队列构建小根堆，重写Comparator的compare方法，按照元素的出现次数进行排序，堆顶元素是出现次数最少的元素，用map数组存取元素和其出现的次数，遍历map构建大根堆，如果堆小于k，直接加入元素，堆大于k，丢弃堆顶元素

class Solution {public int[] topKFrequent(int[] nums, int k) {//优先级队列，实现大根堆PriorityQueue<int []> pq = new PriorityQueue<int []>(new Comparator<int []>(){//重写compare方法，按照出现的次数进行排序public int compare(int[] o1,int[] o2){return o1[1]-o2[1];}});//用map存取元素和出现的次数Map<Integer,Integer> map = new HashMap<Integer,Integer>();for(int num:nums){map.put(num,map.getOrDefault(num,0)+1);}//构建大根堆for(var x:map.entrySet()){int[] tmp = new int[2];tmp[0] = x.getKey();tmp[1] = x.getValue();pq.offer(tmp);if(pq.size()>k){pq.poll();}}//存取出现频率前k高的元素int[] res = new int[k];for(int i=0;i<k;i++){res[i] = pq.poll()[0];}return res;}
}

37.堆——数据流的中位数

解题思路：用两个优先队列进行存储，一个使用大根堆存储小于等于中位数的元素，此时栈顶即为中位数，或者是中间值，另外一个使用小根堆存储大于中位数的元素，此时栈顶即为中间值。

package CodeThink;import java.util.PriorityQueue;public class MedianFinder {PriorityQueue<Integer> queMin;PriorityQueue<Integer> queMax;public MedianFinder() {queMin = new PriorityQueue<>((a,b)->b-a);//记录小于等于中位数的数,大根堆queMax = new PriorityQueue<>((a,b)->a-b);//记录大于中位数的数，小根堆}public void addNum(int num) {if(queMin.isEmpty()||num<queMin.peek()){queMin.add(num);if(queMax.size()+1<queMin.size()){queMax.offer(queMin.poll());}}else {queMax.offer(num);if(queMax.size()>queMin.size()){queMin.offer(queMax.poll());}}}public double findMedian() {if(queMin.size()>queMax.size()){return queMax.peek();}return (queMin.peek()+queMax.peek())/2.0;}public static void main(String[] args) {MedianFinder medianFinder = new MedianFinder();medianFinder.addNum(1);    // arr = [1]medianFinder.addNum(2);    // arr = [1, 2]System.out.println(medianFinder.findMedian()); // 返回 1.5 ((1 + 2) / 2)medianFinder.addNum(3);    // arr[1, 2, 3]System.out.println(medianFinder.findMedian()); // return 2.0}
}

二叉树

38.二叉树——二叉树的中序遍历

解题思路：

1.递归遍历

2.非递归遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();inorder(root,list);return  list;}private void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);inorder(root.right, list);}
}

39.二叉树——二叉树的最大深度

解题思路：

1.深度优先遍历，递归遍历

2.广度优先遍历，参考层序遍历，用辅助队列模拟过程

package CodeThink;import java.util.LinkedList;
import java.util.Queue;public class maxDepth {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);System.out.println(maxDepth(root));}public static int maxDepth(TreeNode root) {if (root == null) {return 0;}else{int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) + 1;}}public static int maxDepth2(TreeNode root) {int depth = 0;if (root == null) {return depth;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {depth++;int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return depth;}
}

40.二叉树——翻转二叉树

解题思路：递归，考虑递归循环的条件：1.参数 2.终止条件 3.单词循环的逻辑。本题：1.参数：父节点

2.终止条件：父节点为空 3.单次循环的条件：交换左右结点

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);return root;}
}

41.二叉树——对称二叉树

解题思路：涉及到树的题目通常使用递归来解决。

如果同时满足下面的条件，两个树互为镜像：

• 它们的两个根结点具有相同的值
• 每个树的右子树都与另一个树的左子树镜像对称

class Solution {public boolean isSymmetric(TreeNode root) {return check(root.left, root.right);}public boolean check(TreeNode p,TreeNode q) {if(p==null&&q==null){return true;}if(p==null||q==null){return false;}return p.val==q.val && check(p.left,q.right) && check(p.right,q.left);}
}

42.二叉树——二叉树的直径

解题思路：一条路径的长度等于该路径经过的结点数减一，任意一条路径均可以看作由某个节点为起点，从其左右儿子向下遍历的路径拼接得到的。

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

43.二叉树——二叉树的层序遍历

解题思路：用辅助队列模拟二叉树的层序遍历

package CodeThink;import java.util.*;public class levelOrder {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);List list = levelOrder(root);System.out.println(list);}public static List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if (root == null) {return list;}//用队列模拟层序遍历的过程Queue<TreeNode> stack = new LinkedList<>();stack.offer(root);while (!stack.isEmpty()) {//存储每一层的元素List<Integer> level = new ArrayList<>();//用来记录每一层的个数int size = stack.size();while (size > 0) {TreeNode node = stack.poll();level.add(node.val);size -= 1;if (node.left!=null) {stack.offer(node.left);}if (node.right!=null) {stack.offer(node.right);}}list.add(level);}return list;}
}

44.二叉树——将有序数组转换为二叉搜索树

解题思路：中序遍历，总是选择中间位置左边的数字作为根节点

package CodeThink;public class sortedArrayToBST {public static void main(String[] args) {int[] arr = {-10,-3,0,5,9};TreeNode root = sortedArrayToBST(arr);PreOrderTree(root);}public static TreeNode sortedArrayToBST(int[] nums) {return helper(nums,0,nums.length-1);}private static TreeNode helper(int[] nums, int left, int right) {if(left > right) return null;//总是选择中间位置左边的数字作为根节点int mid = (left + right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid-1);root.right = helper(nums, mid+1, right);return root;}public static void PreOrderTree(TreeNode root){if(root==null){return;}System.out.println(root.val);PreOrderTree(root.left);PreOrderTree(root.right);}
}

45.二叉树——验证二叉搜索树

解题思路：

1.设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

public class isValidBST {public static void main(String[] args) {TreeNode root = new TreeNode(2);root.left = new TreeNode(1);root.right = new TreeNode(3);System.out.println(isValidBST(root));}public static boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public static boolean isValidBST(TreeNode root, long min, long max) {if (root == null) {return true;}if (root.val <= min || root.val >= max) {return false;}return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);}
}

46.二叉树——二叉搜索树中第 K 小的元素

解题思路：利用二叉搜索树的特性，采用中序遍历，然后将遍历到的元素加入集合，此时的集合已经是有序集合

package CodeThink;import java.util.ArrayList;
import java.util.List;public class kthSmallest {public static void main(String[] args) {TreeNode root = new TreeNode(3);root.left = new TreeNode(1);root.right = new TreeNode(4);root.left.right = new TreeNode(2);System.out.println(kthSmallest(root, 1));}public static int kthSmallest(TreeNode root, int k) {List list = new ArrayList<>();Inoder(root,list);return (int) list.get(k-1);}public static List Inoder(TreeNode root, List list){if(root == null){return null;}Inoder(root.left,list);list.add(root.val);Inoder(root.right,list);return list;}
}

47.二叉树——二叉树的右视图

解题思路：利用二叉树的层序遍历，每一层的最右边的一个结点，即为看到的结点

package CodeThink;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class rightSideView {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.right = new TreeNode(5);root.right.right = new TreeNode(4);List list = rightSideView(root);System.out.println(list);}public static List<Integer> rightSideView(TreeNode root) {if (root == null) {return new ArrayList<>();}List<Integer> list = new ArrayList<>();//用队列模拟层序遍历的过程，每一层的最右边的结点即为看见的结点Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {//用来记录每一层的个数int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if(size==1) list.add(node.val);size--;if(node.left != null) {queue.add(node.left);}if(node.right != null) {queue.add(node.right);}}}return list;}
}

48.二叉树——二叉树展开为链表

解题思路：

1.前序遍历，把遍历的元素存在列表里，然后新建链表

2.寻找前驱结点

package CodeThink;import java.util.ArrayList;
import java.util.List;public class flatten {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(5);root.left.left = new TreeNode(3);root.left.right = new TreeNode(4);root.right.right = new TreeNode(6);flatten(root);while (root != null) {System.out.println(root.val);root = root.right;}}//解法1public static void flatten(TreeNode root) {List<Integer> list = new ArrayList<>();List list1 = PreInOrder(root,list);if(list1==null)return;for(int i=1; i<list1.size(); i++){TreeNode node = new TreeNode(Integer.parseInt(list1.get(i).toString()));root.left = null;root.right = node;root = root.right;}}public static List PreInOrder(TreeNode root,List<Integer> list) {if (root == null) {return null;}list.add(root.val);PreInOrder(root.left,list);PreInOrder(root.right,list);return list;}//解法2public void flatten(TreeNode root) {TreeNode curr = root;while (curr != null) {if (curr.left != null) {TreeNode next = curr.left;TreeNode predecessor = next;while (predecessor.right != null) {predecessor = predecessor.right;}predecessor.right = curr.right;curr.left = null;curr.right = next;}curr = curr.right;}}
}

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

解题思路：在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。

package CodeThink;import java.util.HashMap;
import java.util.Map;class buildTree {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍历中的第一个节点就是根节点int preorder_root = preorder_left;// 在中序遍历中定位根节点int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;// 递归地构造左子树，并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树，并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 构造哈希映射，帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}

50.二叉树——路径总和 III

解题思路：用两个函数解决，pathSum用于递归的遍历该二叉树，rootsum用于判断从该节点开始有多少条路径的总和等于targetSum。

package CodeThink;public class pathSum {public int pathSum(TreeNode root, int targetSum) {if(root == null) return 0;int ret = rootsum(root,targetSum);ret += pathSum(root.left,targetSum);ret += pathSum(root.right,targetSum);return ret;}private int rootsum(TreeNode root, long targetSum) {int ret = 0;if(root == null) return 0;int val = root.val;if(val == targetSum) {ret++;}ret += rootsum(root.left,targetSum-val);ret += rootsum(root.right,targetSum-val);return ret;}public static void main(String[] args) {TreeNode root = new TreeNode(10);root.left = new TreeNode(5);root.right = new TreeNode(-3);root.left.left = new TreeNode(3);root.left.right = new TreeNode(2);root.left.left.left = new TreeNode(-3);root.left.left.right = new TreeNode(-2);root.left.right.right = new TreeNode(1);root.right.right = new TreeNode(11);pathSum pathSum = new pathSum();System.out.println(pathSum.pathSum(root, 22));}
}

51.二叉树——二叉树的最近公共祖先

解题思路：递归，遍历该二叉树的每一个节点，然后判断该节点是否可以成为给点的两个节点的祖先节点。关键在于这个节点成为给定节点的祖先节点的判断

package CodeThink;public class lowestCommonAncestor {private TreeNode ans;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root, p, q);return ans;}//深度优先遍历private boolean dfs(TreeNode root,TreeNode p,TreeNode q){if(root == null){return false;}boolean lson = dfs(root.left,p,q);boolean rson = dfs(root.right,p,q);if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {ans = root;}return lson || rson || (root.val == p.val || root.val == q.val);}public static void main(String[] args) {TreeNode root = new TreeNode(3);root.left = new TreeNode(5);root.right = new TreeNode(1);root.left.left = new TreeNode(6);root.left.right = new TreeNode(2);root.right.left = new TreeNode(0);root.right.right = new TreeNode(8);root.left.right.left = new TreeNode(7);root.left.right.right = new TreeNode(4);lowestCommonAncestor lowestCommonAncestor = new lowestCommonAncestor();lowestCommonAncestor.lowestCommonAncestor(root,new TreeNode(5),new TreeNode(1));}
}

52.二叉树——二叉树中的最大路径和

解题思路：首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

package CodeThink;public class maxPathSum {int max = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return max;}private int maxGain(TreeNode root) {if(root == null) return 0;//递归计算左右子节点的最大贡献值//只有在最大贡献值大于0时，才会选择对应字节点int left = Math.max(maxGain(root.left),0);int right = Math.max(maxGain(root.right),0);//节点的最大路径和取决于该节点的值与该节点的左右子结点的最大贡献值int price = root.val + left + right;//更新答案max = Math.max(max,price);//返回节点的最大贡献值return root.val+Math.max(left,right);}public static void main(String[] args) {maxPathSum maxPathSum = new maxPathSum();TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);System.out.println(maxPathSum.maxPathSum(root));}
}

图论

53.图论——岛屿数量

解题思路：我们将二维网格看作一个无向图，开始遍历，如果一个位置有1，就从这个位置开始进行深度优先遍历，在这个搜索的过程每个为1的节点都会置为0，最终岛屿的数量就是我们进行深度优先遍历的次数

class Solution {public int numIslands(char[][] grid) {if(grid==null||grid.length==0){return 0;}int nr = grid.length;int nc = grid[0].length;int num_islands = 0;for(int r=0; r<nr; ++r){for(int c=0; c<nc; ++c){if(grid[r][c]=='1'){++num_islands;dfs(grid,r,c);}}}return num_islands;}void dfs(char[][] grid,int r, int c){int nr = grid.length;int nc = grid[0].length;if(r<0||c<0||r>=nr||c>=nc||grid[r][c]=='0'){return;}grid[r][c] = '0';dfs(grid, r-1, c);dfs(grid, r+1, c);dfs(grid, r, c-1);dfs(grid, r, c+1);}
}

54.图论——腐烂的橘子

解题思路

：一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。

然后进行 BFS 遍历，每个结点的相邻结点可能是上、下、左、右四个方向的结点，注意判断结点位于网格边界的特殊情况。

由于可能存在无法被污染的橘子，我们需要记录新鲜橘子的数量。在 BFS 中，每遍历到一个橘子（污染了一个橘子），就将新鲜橘子的数量减一。如果 BFS 结束后这个数量仍未减为零，说明存在无法被污染的橘子。

class Solution {public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;Queue<int[]> queue = new LinkedList<>();int count = 0;//新鲜橙子的数量for(int r = 0; r<M; r++){for(int c=0; c<N; c++){if(grid[r][c] == 1){count++;}else if(grid[r][c]==2){queue.add(new int[]{r,c});}}}int round = 0;//腐败的轮数while(count>0 && !queue.isEmpty()){round++;int n = queue.size();for(int i=0; i<n; i++){int[] orange = queue.poll();int r = orange[0];int c = orange[1];if(r-1>=0 && grid[r-1][c]==1){grid[r-1][c] = 2;count--;queue.add(new int[]{r-1,c});}if(r+1<M && grid[r+1][c]==1){grid[r+1][c] = 2;count--;queue.add(new int[]{r+1,c});}if (c-1 >= 0 && grid[r][c-1] == 1) {grid[r][c-1] = 2;count--;queue.add(new int[]{r, c-1});}if (c+1 < N && grid[r][c+1] == 1) {grid[r][c+1] = 2;count--;queue.add(new int[]{r, c+1});}}}if (count > 0) {return -1;} else {return round;}}
}

55.图论——课程表

解题思路：

拓扑排序问题

1.根据依赖关系，构建邻接表、入度数组。

2.选取入度为 0 的数据，根据邻接表，减小依赖它的数据的入度。

3.找出入度变为 0 的数据，重复第 2 步。

4.直至所有数据的入度为 0，得到排序，如果还有数据的入度不为 0，说明图中存在环。

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 入度数组，用于记录每门课程的入度int[] inDegree = new int[numCourses];// 邻接表，存储每门课程的后续课程List<List<Integer>> adjList = new ArrayList<>();for (int i = 0; i < numCourses; i++) {adjList.add(new ArrayList<>());}// 计算每门课程的入度，并构建邻接表for (int[] prerequisite : prerequisites) {int course = prerequisite[0];int preCourse = prerequisite[1];inDegree[course]++;adjList.get(preCourse).add(course);}// 存储入度为 0 的课程的队列Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}// 记录已完成课程的数量int count = 0;while (!queue.isEmpty()) {int selectedCourse = queue.poll();count++;// 获取当前课程的后续课程列表List<Integer> nextCourses = adjList.get(selectedCourse);for (int nextCourse : nextCourses) {// 后续课程的入度减 1inDegree[nextCourse]--;if (inDegree[nextCourse] == 0) {queue.offer(nextCourse);}}}// 如果已完成课程的数量等于总课程数，则可以完成所有课程return count == numCourses;}
}

56.图论——实现 Trie (前缀树)

解题思路：用HashSet实现，可以很简单的实现添加元素，判断是否存在元素，遍历set判断是否存在以该元素开头的子字符串

class Trie {HashSet<String> set;public Trie() {set = new HashSet<>();}public void insert(String word) {set.add(word);}public boolean search(String word) {if(set.contains(word)){return true;}return false;}public boolean startsWith(String prefix) {for(String s: set){if(s.startsWith(prefix)){return true;}}return false;}
}/*** 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);*/

双指针

57.双指针—— 移动零

解题思路：

1.双指针移动,右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

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

2.还可以将非零元素移动到最前面，记录非零元素的最后一个位置，后面的全部置为0

class Solution {public void moveZeroes(int[] nums) {int index = 0;for(int i=0;i<nums.length;i++){if(nums[i]!=0){nums[index] = nums[i];index++;}}for(int j=index;j<nums.length;j++){nums[j] = 0;}}
}

58.双指针——盛最多水的容器

解题思路: 首先是暴力解法，两个for循环遍历所有可能的情况，但是时间复杂度较高，容易出现超时问题。想到用双指针来做，移动最小边界则不断改变盛水面积, 即遍历出最有解

package CodeThink;public class maxArea {public static void main(String[] args) {int[] num = {1,8,6,2,5,4,8,3,7};System.out.println(maxArea(num));}public static int maxArea(int[] height) {int res = 0, left = 0, right = height.length - 1;while (left < right) {int area = Math.min(height[left], height[right]) * (right - left);res = Math.max(res, area);if (height[left] < height[right]) {left++;} else if (height[right] <= height[left]) {right--;}}return res;}
}

59.双指针——三数之和

解题思路：第一反应考虑用哈希表来做，但是很麻烦，需要处理很多去重的问题，用双指针完成，通过排序可以很方便的跳过重复元素

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();//对数组进行排序Arrays.sort(nums);//对数组进行遍历for (int i = 0; i < nums.length; i++) {// 如果最小的数大于0，后续的和一定大于0，直接返回结果if(nums[i] > 0){break;}// 跳过重复的元素if(i>0 && nums[i] == nums[i-1]){continue;}int left = i+1;int right = nums.length-1;while(left < right){if(nums[i] + nums[left] + nums[right] > 0){right--;}else if(nums[i] + nums[left] + nums[right] < 0){left++;}else {// 找到一个满足条件的三元组res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳过重复的元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}//移动指针，找到其他可能的元素left++;right--;}}}return res;}
}

60.双指针——接雨水

解题思路：求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

public static int trap(int[] height) {int sum = 0;//最两端的列不用考虑，因为一定不会有水。所以下标从1到length-2for (int i = 1; i < height.length-1; i++) {//找出左边最高int max_left = 0;for(int j = i-1; j>=0; j--){if(height[j]>max_left){max_left = height[j];}}//找出右边最高int max_right = 0;for(int j = i+1; j<height.length; j++){if(height[j]>max_right){max_right = height[j];}}//找出两端较小的int min = Math.min(max_left,max_right);//只有较小的一段大于当前列的高度才会有水，其他情况不会有水if(min>height[i]){sum = sum + (min-height[i]);}}return sum;}public static int trap2(int[] height) {int sum = 0;//max_left [i] 代表第 i 列左边最高的墙的高度int[] max_left = new int[height.length];//max_right[i] 代表第 i 列右边最高的墙的高度int[] max_right = new int[height.length];for(int i=1; i<height.length; i++){max_left[i] = Math.max(max_left[i-1],height[i-1]);}for(int i=height.length-2; i>=0; i--){max_right[i] = Math.max(max_right[i+1],height[i+1]);}for(int i=1;i<height.length;i++){int min = Math.min(max_left[i],max_right[i]);if(min>height[i]){sum = sum + (min-height[i]);}}return sum;}

二分查找

61.二分查找——搜索插入位置

解题思路：本题就是一个简单的二分查找，只是多了一个如果目标值不在数组中，返回他将会被按照顺序插入的位置，按照二分法执行完毕以后，left左边的数一定小于target，left右边的数一定大于target，因此如果目标值不在数组中，直接返回left即可

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

62.二分查找——搜索二维矩阵

解题思路：可以看出矩阵的行和列都是递增的，我们先倒序确定目标值在哪一行，然后再通过二分查找搜索

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int index = 0;for(int i=matrix.length-1;i>=0;i--){if(matrix[i][0]<=target){index = i;break;}}int left=0,right=matrix[index].length;for(int j=0;j<matrix[index].length;j++){int mid = (left+right) / 2;if(matrix[index][j]==target){return true;}else if(matrix[index][j]>target){left = mid+1;}else{right = mid-1;}}return false;}
}

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

解题思路：本题的难点在于该数组中有多个符合条件的target，我们需要找到目标值的开始位置和结束位置，直接采用两次二分查找，第一次找开始位置，第二次找结束位置

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

64.二分查找——搜索旋转排序数组

解题思路：数组选择以后，总有一部分区间是有序的，[l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界。
如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。

如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

class Solution {public int search(int[] nums, int target) {int n = nums.length;int l=0,r=n-1;while(l<=r){int mid = (l+r)/2;if(nums[mid]==target){return mid;}//左半区间有序if(nums[0]<=nums[mid]){if(nums[0]<=target && target <nums[mid]){r = mid - 1;}else{l = mid + 1;}}//右半区间有序else{if(nums[mid]<target && target<=nums[n-1]){l = mid + 1;}else {r = mid - 1;}}}return -1;}
}

65.二分查找——寻找旋转排序数组中的最小值

解题思路：

本题重点在于，如何利用二分。二分的思想在于，每次淘汰一半（记住这个思想，是所有二分题目的关键）。基于这个思想，我们要去想淘汰策略。我们发现本题中，有：
最小元素 m 的左边所有元素都比数组的最后一个元素 x大，右边所有元素（不含x）都比 x 小
于是我们的淘汰策略为：对于每一对low high，比较中间元素值和x的大小：
1.nums[mid]<x：说明 mid 在 m 的右边，即目标 m 在 mid 的左边，故可淘汰右半边；
2.nums[mid]>x：同理淘汰左半边；
3.nums[mid]==x: 不可能，因为数组无重复值，如果成立，则必然有mid==n-1，则必然有low==high==n-1。但当low==high时，我们已经找到m

public int findMin(int[] nums) {int low = 0, high = nums.length - 1;int x = nums[high];while (low < high) { // 注意这里没有=了，=的时候直接退出循环得到答案int mid = (low + high) / 2;if (nums[mid] < x)high = mid;  //这里不是常规的 mid-1 是因为此时的mid有可能就是我们要找的melselow = mid + 1;  //这里和常规一样是 mid+1 是因为此时的mid不可能是m（他都比x大了噻怎么可能是最小的）}return nums[low];}

66.二分查找——寻找两个正序数组的中位数

解题思路：给定两个有序数组，要求找到两个有序数组的中位数，最直观的思路有以下两种：

1.使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。

2.不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 0 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1=nums1.length,length2=nums2.length;int totallength = length1 + length2;if(totallength %2 ==1){int midIndex = totallength/2;double median = getKthElement(nums1,nums2,midIndex+1);return median;}else{int midIndex1 = totallength/2-1,midIndex2 = totallength/2;double median = (getKthElement(nums1,nums2,midIndex1+1)+getKthElement(nums1,nums2,midIndex2+1)) / 2.0;return median;}}public int getKthElement(int[] nums1,int[] nums2,int k){int length1 = nums1.length,length2 = nums2.length;int index1=0, index2=0;int kthElement = 0;while(true){//边界情况if(index1 == length1){return nums2[index2+k-1];}if(index2 == length2){return nums1[index1+k-1];}if(k==1){return Math.min(nums1[index1],nums2[index2]);}//正常情况int half = k/2;int newIndex1 = Math.min(index1+half,length1)-1;int newIndex2 = Math.min(index2+half,length2)-1;int pviot1 = nums1[newIndex1],pviot2 = nums2[newIndex2];if(pviot1<=pviot2){k -= (newIndex1-index1+1);index1 = newIndex1 + 1;}else{k -= (newIndex2-index2+1);index2 = newIndex2 + 1;}}}
}

滑动窗口

67.滑动窗口——无重复字符的最长子串

解题思路：

1.遍历字符串，用hashset存储并记录其最长的字串

package CodeThink;import java.util.HashSet;class lengthOfLongestSubstring {public int lengthOfLongestSubstring(String s) {int longest = 0;for (int i = 0; i < s.length(); i++) {HashSet set = new HashSet();for (int j = i ; j < s.length(); j++) {if(set.contains(s.charAt(j))){break;}else{set.add(s.charAt(j));longest = Math.max(longest, set.size());}}}return longest;}public static void main(String[] args) {String s = "pwwkew";lengthOfLongestSubstring sol = new lengthOfLongestSubstring();System.out.println(sol.lengthOfLongestSubstring(s));}
}

68.滑动窗口——找到字符串中所有字母异位词

解题思路：

遍历字符串s，截取字符串s+p.length为新的字符串，判断该字符串是否为符合条件的字母异位词的字符串，如果符合，加入该字符串的起始下标

package CodeThink;import java.util.ArrayList;
import java.util.List;class findAnagrams {public List<Integer> findAnagrams(String s, String p) {List<Integer> result = new ArrayList<>();for(int i = 0; i <= s.length() - p.length(); i++){String temp = s.substring(i,i+p.length());if(isAnagrams(temp,p)){result.add(i);}}return result;}private boolean isAnagrams(String temp, String p) {int[] count = new int[26];for(int i = 0; i < temp.length(); i++){count[temp.charAt(i) - 'a']++;}for(int i = 0; i < p.length(); i++){count[p.charAt(i) - 'a']--;}for(int i = 0; i < 26; i++){if(count[i] != 0){return false;}}return true;}public static void main(String[] args) {String s = "abab";String p = "ab";List<Integer> ans = new findAnagrams().findAnagrams(s, p);System.out.println(ans);}
}

回溯算法

回溯法其实是一个纯暴力的搜索，并不是什么高效的算法

回溯算法解决问题

组合问题

切割问题

子集问题

排列问题

棋盘问题

如何理解回溯法

回溯法都可以抽象成为一个树形结构，抽象成为一个n叉树

回溯模板

void backtracking(参数){if(终止条件){收集结果;return;}//单层搜索的逻辑for(集合元素){处理节点;递归函数;回溯，撤销处理结果}
}

69.回溯——全排列

解题思路：全排列问题。

• 递归函数参数

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组，标记已经选择的元素

• 递归终止条件

可以看出叶子节点，就是收割结果的地方。那么什么时候，算是到达叶子节点呢？当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

• 单层搜索的逻辑

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次

package CodeThink;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;class permute {List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();//用来存放符合条件结果boolean[] used;//记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次public List<List<Integer>> permute(int[] nums) {if(nums.length == 0) return result;used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(int[] nums) {//终止条件if(path.size() == nums.length) {result.add(new ArrayList<>(path));return;}//单层搜索的逻辑for(int i = 0; i < nums.length; i++) {if(used[i]) continue;used[i] = true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}public static void main(String[] args) {int nums[] = {2,1,3};permute test = new permute();List<List<Integer>> res = test.permute(nums);res.forEach(System.out::println);}
}

70.回溯——子集

解题思路：子集问题。如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

class Solution {List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合List<Integer> path = new LinkedList<>(); //用来存放符合条件结果public List<List<Integer>> subsets(int[] nums) {subsetsHelper(nums,0);return result;}public void subsetsHelper(int[] nums, int startIndex){result.add(new ArrayList<>(path));if(startIndex >= nums.length){return;}for(int i=startIndex; i<nums.length; i++){path.add(nums[i]);subsetsHelper(nums,i+1);path.removeLast();}}
}

71.回溯——电话号码的字母组合

解题思路：组合问题。回溯三部曲：

• 确定回溯函数参数

首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。

• 确定终止条件

例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。

那么终止条件就是如果index 等于 输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。然后收集结果，结束本层递归。

• 确定单层遍历逻辑

首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。然后for循环来处理这个字符集

class Solution {//设置全局列表存储最后的结果List<String> list = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return list;}//初始化对应所有的数字String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//迭代处理backTracking(digits,numString,0);return list;}StringBuilder temp = new StringBuilder();public void  backTracking(String digits, String[] numString, int num){//遍历全部一次记录一次得到的字符串if(num == digits.length()){list.add(temp.toString());return;}//str表示当前num对应的字符串String str = numString[digits.charAt(num) - '0'];for(int i=0; i<str.length(); i++){temp.append(str.charAt(i));//递归处理下一层backTracking(digits, numString, num+1);//剔除末尾的继续尝试temp.deleteCharAt(temp.length()-1);}}
}

72.回溯——组合总和

解题思路：

• 递归函数参数

这里依然是定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）首先是题目中给出的参数，集合candidates, 和目标值target。此外我还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如何target==0就说明找到符合的结果了，但为了代码逻辑清晰，我依然用了sum。

• 递归终止条件

从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。

sum等于target的时候，需要收集结果

• 单层搜索的逻辑

单层for循环依然是从startIndex开始，搜索candidates集合。

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backTracking(candidates,target,0,0);return result;}public void backTracking(int[] candidates, int target, int sum, int idx){if(sum == target){// 添加path的副本到resultresult.add(new ArrayList<>(path));return;}for(int i=idx; i<candidates.length; i++){if(sum + candidates[i] >target) break;path.add(candidates[i]);backTracking(candidates,target,sum+candidates[i],i);path.removeLast();}}
}

73.回溯——括号生成

解题思路：
在递归过程中，我们维护了两个计数器 open 和 close，分别表示左括号和右括号的数量。递归终止条件是当前字符串的长度等于 2 * n，这意味着我们已经生成了一个完整的括号组合。在每一步递归中，我们尝试添加一个左括号（如果 open < n）或一个右括号（如果 close < open），然后继续递归调用。在回溯时，我们撤销上一步的操作，以便尝试其他可能的组合。

class Solution {List<String> result = new ArrayList<>();public List<String> generateParenthesis(int n) {backTracking("",0,0,n);return result;}public void backTracking(String current, int open, int close, int max){//递归终止条件if(current.length() == 2 * max){result.add(current);return;}//单层搜索逻辑// 如果左括号数量小于 max，可以添加左括号if(open<max){backTracking(current+"(",open+1,close,max);}// 如果右括号数量小于左括号数量，可以添加右括号if(close<open){backTracking(current+")",open,close+1,max);}}
}

74.回溯——单词搜索

解题思路：

深度优先搜索： 即暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。

class Solution {public boolean exist(char[][] board, String word) {boolean[][] visted = new boolean[board.length][board[0].length];for(int i=0; i<board.length; i++){for(int j=0; j<board[i].length; j++){if(backTracking(board,visted,i,j,word,0)){return true;}}}return false;}private boolean backTracking(char[][] board,boolean visted[][] ,int x, int y, String word, int index){//终止条件，如果已经匹配了单词的所有字符if(index == word.length()){return true;}//如果当前位置超出网格范围或字符不匹配或已经访问过，则返回falseif(x<0 || x>=board.length || y<0 || y>=board[0].length || board[x][y] != word.charAt(index) || visted[x][y]){return false;} //标记当前位置已访问visted[x][y] = true;//四个方向探索boolean found = backTracking(board, visted, x+1, y, word, index+1)||backTracking(board, visted, x-1, y, word, index+1)||backTracking(board, visted, x, y+1, word, index+1)||backTracking(board, visted, x, y-1, word, index+1);//回溯visted[x][y] = false;return found;}
}

75.回溯——分割回文串

解题思路：切割问题。

• 递归函数参数

全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

• 递归函数终止条件

在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。

• 单层搜索的逻辑

在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串。

class Solution {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}public void backTracking(String s, int index){if(index == s.length()){result.add(new ArrayList<>(path));return;}for(int i=index;i<s.length();i++){String sub = s.substring(index, i + 1);if(isHuiWen(sub)){path.add(sub);backTracking(s, i+1);path.remove(path.size()-1);}}}public boolean isHuiWen(String sub) {int left = 0, right = sub.length() - 1;while (left <= right) {if (sub.charAt(left) != sub.charAt(right)) {return false;}left++;right--;}return true;}
}

76.回溯——N 皇后

解题思路：

• 递归函数参数

我依然是定义全局变量二维数组result来记录最终结果。参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

• 递归终止条件

可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

• 单层搜索的逻辑

递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];for (char[] c : chessboard) {Arrays.fill(c, '.');}backTrack(n, 0, chessboard);return res;}public void backTrack(int n, int row, char[][] chessboard) {if (row == n) {res.add(Array2List(chessboard));return;}for (int col = 0;col < n; ++col) {if (isValid (row, col, n, chessboard)) {chessboard[row][col] = 'Q';backTrack(n, row+1, chessboard);chessboard[row][col] = '.';}}}public List Array2List(char[][] chessboard) {List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}public boolean isValid(int row, int col, int n, char[][] chessboard) {// 检查列for (int i=0; i<row; ++i) { // 相当于剪枝if (chessboard[i][col] == 'Q') {return false;}}// 检查45度对角线for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {if (chessboard[i][j] == 'Q') {return false;}}// 检查135度对角线for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {if (chessboard[i][j] == 'Q') {return false;}}return true;}
}

贪心算法

什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心的两个极端

说实话贪心算法并没有固定的套路。所以唯一的难点就是如何通过局部最优，推出整体最优。

贪心的套路

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

77.贪心——买卖股票的最佳时机

解题思路：

1.暴力循环

2.贪心策略，选择最小的股票买入，最大的时候卖出

package CodeThink;class maxProfit {public int maxProfit(int[] prices) {int maxProfit = 0;int slow=0,fast=0;for(;slow<prices.length-1;slow++){for (fast=slow+1;fast<prices.length;fast++){maxProfit = Math.max(maxProfit,prices[fast]-prices[slow]);}}return maxProfit;}public int maxProfit2(int[] prices) {int maxProfit = 0;int minprice = prices[0];for (int i = 1; i < prices.length; i++) {if(minprice > prices[i]){minprice = prices[i];}else{maxProfit = Math.max(maxProfit,prices[i]-minprice);}}return maxProfit;}public static void main(String[] args) {maxProfit maxProfit = new maxProfit();System.out.println(maxProfit.maxProfit2(new int[]{7,1,5,3,6,4}));}
}

78.贪心——跳跃游戏

解题思路：遍历数组中的每一个位置，并且实时维护数组可以到达的最远的位置

package CodeThink;public class canJump {public boolean canJump(int[] nums) {int n = nums.length;int rightmost = 0;for (int i = 0; i < n; ++i) {if(i <= rightmost){rightmost = Math.max(rightmost, i + nums[i]);if(rightmost >= n-1){return true;}}}return false;}public static void main(String[] args) {int[] nums ={2,0};canJump obj = new canJump();System.out.println(obj.canJump(nums));}
}

79.贪心——跳跃游戏 II

解题思路：

1.反向查找，先找到第一个可以直接到达最后位置的元素下标，将其更新为最后一个位置，找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

2.正向查找，如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

package CodeThink;public class jump {public int jump(int[] nums) {int position = nums.length - 1;int step = 0;while (position > 0) {for (int i=0; i<position; i++) {if(i+nums[i]>=position){position = i;step++;break;}}}return step;}public int jump2(int[] nums) {int step = 0;int maxposition = 0;int end =0;for(int i=0; i<nums.length; i++){maxposition = Math.max(maxposition,nums[i]+i);if(i==end){end=maxposition;step++;}}return  step;}public static void main(String[] args) {int[] nums = {1, 3, 4, 6};jump obj = new jump();System.out.println(obj.jump2(nums));}
}

80.贪心——划分字母区间

解题思路：在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段，具体做法如下。

1.从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0。

2.对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置 end ，则当前片段的结束下标一定不会小于 end ，因此令 end=max(end,end c )。

3.当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是 [start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。

4.重复上述过程，直到遍历完字符串。

package CodeThink;import java.util.ArrayList;
import java.util.List;public class partitionLabels {public List<Integer> partitionLabels(String s) {int[] lastIndex = new int[26];int len = s.length();//得到每个字母最后一次出现的下标位置for (int i = 0; i < len; i++) {lastIndex[s.charAt(i) - 'a'] = i;}List<Integer> res = new ArrayList<>();int start = 0,end = 0;//从左到右遍历字符串，start为当前片段开始下标，end为当前片段的结束下标for (int i = 0; i < len; i++) {end = Math.max(end, lastIndex[s.charAt(i) - 'a']);if (i == end) {res.add(end - start+1);start = end+1;}}return res;}public static void main(String[] args) {String s = "ababcbacadefegdehijhklij";partitionLabels p = new partitionLabels();System.out.println(p.partitionLabels(s));}
}

动态规划

动态规划常见类型

背包问题

打家劫舍

股票问题

子序列问题

动态规划五部曲

1.DP数组含义

2.递推公式

3.DP数组初始化

4.DP数组遍历顺序

5.打印DP数组

81.动态规划——爬楼梯

解题思路：

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

package CodeThink;public class climbStairs {public static void main(String[] args) {climbStairs(1);}public static int climbStairs(int n) {//1.定义dp数组,dp[i]代表第i层有多少种方法可以爬到int[] dp = new int[n+1];//2.递推公式// dp[i] = dp[i-1] + dp[i-2]//3.dp数组初始化dp[0] = 1;dp[1] = 1;//4.dp数组遍历顺序for(int i=2;i<=n;i++){dp[i] = dp[i-1] + dp[i-2];}//5.打印dp数组for (int i : dp) {System.out.println(i);}return dp[n];}
}

82.动态规划——杨辉三角

解题思路：动态规划是解决杨辉三角问题的高效方法，通过存储子问题的解，避免了重复计算。

package CodeThink;import java.util.ArrayList;
import java.util.List;public class generate {public static void main(String[] args) {System.out.println(generate(5));}public static List<List<Integer>> generate(int numRows) {//1.定义dp数组,dp[i][j]代表第i行列的数int[][] dp = new int[numRows][];//2.递推公式//dp[i][j] = dp[i-1][j-1] + dp[i-1][j]//3.dp数组初始化for(int i = 0; i < numRows; i++) {dp[i] = new int[i+1]; //每一行的长度是i+1dp[i][0] = 1; //每一行的第一个元素是1dp[i][i] = 1; //每一行的最后一个元素是1}//4.dp数组遍历顺序for(int i=2; i<numRows; i++) {for(int j = 1; j < i; j++) {dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}}// 将二维数组转换为 List<List<Integer>>List<List<Integer>> result = new ArrayList<>();for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<>();for (int j = 0; j <= i; j++) {row.add(dp[i][j]);}result.add(row);}return result;}
}

83.动态规划——打家劫舍

解题思路：首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k (k>2) 间房屋，有两个选项：

1.偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。

2.不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

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

最终的答案即为 dp[n−1]，其中 n 是数组的长度。

package CodeThink;public class rob {public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}if(nums.length==1){return nums[0];}//dp[i],偷盗到i能够偷盗的金额int[] dp = new int[nums.length];//递推公式：dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1])//dp数组初始化dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);}//循环遍历dp数组return dp[nums.length - 1];}public static void main(String[] args) {int[] nums = new int[]{1,2,3,1};rob rob = new rob();System.out.println(rob.rob(nums));}
}

84.动态规划——完全平方数

解题思路：完全背包问题。

1. 确定dp数组（dp table）以及下标的含义

dp[j]：和为j的完全平方数的最少数量为dp[j]

1. 确定递推公式

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

1. dp数组如何初始化

dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。

有同学问题，那0 * 0 也算是一种啊，为啥dp[0] 就是 0呢？

看题目描述，找到若干个完全平方数（比如 1, 4, 9, 16, ...），题目描述中可没说要从0开始，dp[0]=0完全是为了递推公式。

非0下标的dp[j]应该是多少呢？

从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

1. 确定遍历顺序

我们知道这是完全背包，

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

1. 举例推导dp数组

dp[0] = 0 dp[1] = min(dp[0] + 1) = 1 dp[2] = min(dp[1] + 1) = 2 dp[3] = min(dp[2] + 1) = 3 dp[4] = min(dp[3] + 1, dp[0] + 1) = 1 dp[5] = min(dp[4] + 1, dp[1] + 1) = 2

最后的dp[n]为最终结果

class Solution {public int numSquares(int n) {int max = Integer.MAX_VALUE;//定义dp数组,dp[i]代表整数i需要的最少的完全平方数的数量int[] dp = new int[n+1];//dp数组初始化for(int j=0; j<=n; j++){dp[j] = max;}dp[0] = 0;//遍历背包for(int i=1; i<=n; i++){//遍历物品for(int j=1; j*j <= i; j++){dp[i] = Math.min(dp[i],dp[i-j*j]+1);}}return dp[n];}
}

85.动态规划——零钱兑换

解题思路：和完全平方数类似，一个完全背包问题

题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。

动规五部曲分析如下：

1. 确定dp数组以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

1. 确定递推公式

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

1. dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

其他下标对应的数值呢？

考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

所以下标非0的元素都是应该是最大值。

1. 确定遍历顺序

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

所以本题并不强调集合是组合还是排列。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！

那么我采用coins放在外循环，target在内循环的方式。

1. 举例推导dp数组

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;//定义dp数组,dp[j]代表总金额为j需要的最少硬币个数int[] dp = new int[amount+1];//dp数组初始化for(int j=0; j<dp.length; j++){dp[j] = max;}dp[0]=0;//动态规划公式 dp[j] = Math.min(dp[j], dp[j-coins[i]+1]);for(int i=0; i<coins.length; i++){//正序遍历，完全背包每个硬币可以选择多次for(int j=coins[i]; j<=amount; j++){if(dp[j - coins[i]] != max){dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);}}}return dp[amount] == max ? -1:dp[amount];}
}

86.动态规划——单词拆分

解题思路：依旧是背包问题。单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {//定义dp数组,dp[i]代表字符串长度为i的字符串是否可以拆分boolean[] dp = new boolean[s.length()+1];//dp数组初始化dp[0] = true;//循环,状态转移方程//遍历背包for(int i=1;i<=s.length();i++){//遍历物品for(String word: wordDict){int len = word.length();if(i>=len&&dp[i-len]&&word.equals(s.substring(i-len,i))){dp[i] = true;break;}}}return dp[s.length()];}
}

87.动态规划——最长递增子序列

解题思路：动态规划5部曲

1.定义dp数组

2.递推公式

3.dp[i]的初始化

4.确定遍历顺序

5.举例推导dp数组

package CodeThink;public class lengthOfLIS {public static void main(String[] args) {int[] arr = {10,9,2,5,3,7,101,18};System.out.println(lengthOfLIS(arr));}public static int lengthOfLIS(int[] nums) {if(nums.length==0){return 0;}//以nums[i]为尾的最长递增子序列的长度int[] dp = new int[nums.length];dp[0] = 1;for(int i =1;i<nums.length;i++){dp[i] = 1;for(int j=0;j<i;j++){if(nums[i]>nums[j]){dp[i] = Math.max(dp[i],dp[j]+1);}}}int length = 1;for(int i =0;i<nums.length;i++){length=Math.max(length,dp[i]);}return length;}
}

88.动态规划——乘积最大子数组

解题思路：

1.定义dp数组，用两个dp数组，一个用来记录以i结尾的最大值，一个用来记录以i为结尾的最小值

2.初始化首元素为nums[0]

3.状态转移方程

maxdp[i] = Math.max(Math.max(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]),nums[i]);

mindp[i] = Math.min(nums[i], Math.min(maxdp[i-1] * nums[i], mindp[i-1] * nums[i]));

class Solution {public int maxProduct(int[] nums) {//maxdp[i]代表以i结尾的子数组的最大对应乘积int[] maxdp = new int[nums.length];//mindp[i]代表以i结尾的子数组的最小对应乘积int[] mindp = new int[nums.length];//dp数组初始化maxdp[0] = nums[0];mindp[0] = nums[0];//循环，状态转移方程,num[i] = Math.max(num[i-1]*num[i],num[i]);for(int i=1; i<nums.length; i++){maxdp[i] = Math.max(Math.max(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]),nums[i]);mindp[i] = Math.min(nums[i], Math.min(maxdp[i-1] * nums[i], mindp[i-1] * nums[i]));}int max = nums[0];for(int i=1;i<maxdp.length;i++){max = Math.max(max,maxdp[i]);}return max;}
}

89.动态规划——分割等和子集

解题思路：背包问题

1. 确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量（所能装的重量）为j的背包，所背的物品价值最大可以为dp[j]。

如果背包所载重量为target， dp[target]就是装满 背包之后的总价值，因为 本题中每一个元素的数值既是重量，也是价值，所以，当 dp[target] == target 的时候，背包就装满了。

拿输入数组 [1, 5, 11, 5]，举例， dp[7] 只能等于 6，因为 只能放进 1 和 5。

而dp[6] 就可以等于6了，放进1 和 5，那么dp[6] == 6，说明背包装满了。

2. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3. dp数组如何初始化

在01背包，一维dp如何初始化，已经讲过，

从dp[j]的定义来看，首先dp[0]一定是0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。

本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
4. 确定遍历顺序

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

5. 举例推导dp数组

dp[j]的数值一定是小于等于j的。如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

class Solution {public boolean canPartition(int[] nums) {if(nums==null||nums.length==0) return false;int n = nums.length;int sum = 0;for(int num: nums){sum += num;}//和为奇数,不能平分if(sum %2 != 0) return false;int target = sum/2;//定义dp数组int[] dp = new int[target+1];//遍历物品for(int i=0;i<n;i++){//遍历背包for(int j=target; j>=nums[i]; j--){dp[j] =  Math.max(dp[j], dp[j-nums[i]] + nums[i]);}//剪枝if(dp[target] == target){return true;}}return dp[target] == target;}
}

90.动态规划——最长有效括号

解题思路：

class Solution {public int longestValidParentheses(String s) {int maxans = 0;int[] dp = new int[s.length()];for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == ')') {if (s.charAt(i - 1) == '(') {dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxans = Math.max(maxans, dp[i]);}}return maxans;}
}

多维动态规划

91.多维动态规划——不同路径

解题思路：

class Solution {public int uniquePaths(int m, int n) {int[][] f = new int[m][n];for (int i = 0; i < m; ++i) {f[i][0] = 1;}for (int j = 0; j < n; ++j) {f[0][j] = 1;}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {f[i][j] = f[i - 1][j] + f[i][j - 1];}}return f[m - 1][n - 1];}
}

92.多维动态规划——最小路径和

解题思路：

class Solution {public int minPathSum(int[][] grid) {for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(i == 0 && j == 0) continue;else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];}}return grid[grid.length - 1][grid[0].length - 1];}
}

93.多维动态规划——最长回文子串

解题思路：

public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] 表示 s[i..j] 是否是回文串boolean[][] dp = new boolean[len][len];// 初始化：所有长度为 1 的子串都是回文串for (int i = 0; i < len; i++) {dp[i][i] = true;}char[] charArray = s.toCharArray();// 递推开始// 先枚举子串长度for (int L = 2; L <= len; L++) {// 枚举左边界，左边界的上限设置可以宽松一些for (int i = 0; i < len; i++) {// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得int j = L + i - 1;// 如果右边界越界，就可以退出当前循环if (j >= len) {break;}if (charArray[i] != charArray[j]) {dp[i][j] = false;} else {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}
}

94.多维动态规划——最长公共子序列

解题思路：

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++) {char c1 = text1.charAt(i - 1);for (int j = 1; j <= n; j++) {char c2 = text2.charAt(j - 1);if (c1 == c2) {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];}
}

95.多维动态规划——编辑距离

解题思路：

class Solution {public int minDistance(String word1, String word2) {int n = word1.length();int m = word2.length();// 有一个字符串为空串if (n * m == 0) {return n + m;}// DP 数组int[][] D = new int[n + 1][m + 1];// 边界状态初始化for (int i = 0; i < n + 1; i++) {D[i][0] = i;}for (int j = 0; j < m + 1; j++) {D[0][j] = j;}// 计算所有 DP 值for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {int left = D[i - 1][j] + 1;int down = D[i][j - 1] + 1;int left_down = D[i - 1][j - 1];if (word1.charAt(i - 1) != word2.charAt(j - 1)) {left_down += 1;}D[i][j] = Math.min(left, Math.min(down, left_down));}}return D[n][m];}
}

技巧

96.技巧——只出现一次的数字

解题思路：

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

97.技巧——多数元素

解题思路：

1.用hashmap存储元素和出现的次数遍历返回多数元素

2.直接排序返回

class Solution {public int majorityElement(int[] nums) {int n = nums.length;HashMap<Integer,Integer> map = new HashMap<>();for(int num: nums){if(!map.containsKey(num)){map.put(num,1);}else{map.put(num, map.get(num) + 1);}}// 使用 entrySet() 遍历键值对for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if(entry.getValue()>n/2){return entry.getKey();}}return 0;}
}class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}
}

98.技巧——颜色分类

解题思路：

单指针，遍历两遍数组，用一个指针跟踪更新后的数组下标，第一次遍历用于找到0的数交换，第二次遍历用于找到1的数交换。

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

99.技巧——下一个排列

解题思路：两遍扫描

class Solution {public void nextPermutation(int[] nums) {int i= nums.length - 2;while(i>=0 && nums[i] >= nums[i+1]){i--;}if(i >= 0){int j = nums.length - 1;while(j>=0&&nums[i]>=nums[j]){j--;}swap(nums,i,j);}reverse(nums,i+1);}public void swap(int[] nums, int i, int j ){int temp = nums[j];nums[j] = nums[i];nums[i] = temp;}public void reverse(int[] nums, int start){int left=start, right = nums.length-1;while(left<right){swap(nums,left,right);left++;right--;}}
}

100.技巧——寻找重复数

解题思路：有点类似于之前的多数元素的解题思路，不过直接用hashset进行存储元素，存储的时候判断，如果hashset中包含该元素，证明是重复元素，直接返回。

class Solution {public int findDuplicate(int[] nums) {int n = nums.length;Set Set = new HashSet<>();for(int i=0;i<n;i++){if(!Set.contains(nums[i])){Set.add(nums[i]);}else{return nums[i];}}return 0;}
}