知识点

1.关于取模运算:

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a b) % p = (a % p b % p) % p

热题 HOT 100

简单

1. 两数之和

https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         HashMap<Integer,Integer> map=new HashMap<>();
  4.         for(int i=0;i<nums.length;i++){
  5.             if(map.containsKey(target-nums[i])) 
  6.                 return new int[]{map.get(target-nums[i]),i};
  7.             map.put(nums[i],i);
  8.         }
  9.         return new int[0];
  10.     }
  11. }

136. 只出现一次的数字

https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出:1

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int x=0;
  4.         for(int num:nums){
  5.             x^=num;
  6.         }
  7.         return x;
  8.     }
  9. }

21. 合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
LeetCode题目 - 图1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         ListNode preHead=new ListNode(-1);
  4.         ListNode newHead=preHead;
  5.         while(l1!=null&&l2!=null){
  6.             if(l1.val<=l2.val){
  7.                 newHead.next=l1;
  8.                 l1=l1.next;
  9.             }else{
  10.                 newHead.next=l2;
  11.                 l2=l2.next;
  12.             }
  13.             newHead=newHead.next;
  14.         }
  15.         newHead.next=(l1==null)?l2:l1;
  16.         return preHead.next;
  17.     }
  18. }

206. 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if(head==null) return null;
  4.         ListNode preHead=null;
  5.         ListNode curHead=head;
  6.         while(curHead!=null){    
  7.             ListNode next=curHead.next;//保存下一个节点
  8.             curHead.next=preHead;
  9.             preHead=curHead;
  10.             curHead=next;
  11.         }
  12.         return preHead;
  13.     }
  14. }

461. 汉明距离

https://leetcode-cn.com/problems/hamming-distance/solution/
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

  1. class Solution {
  2.     public int hammingDistance(int x, int y) {
  3.         int temp=x^y;
  4.         int count=0;
  5.         while(temp!=0){
  6.             count++;
  7.             temp&=(temp-1);
  8.         }
  9.         return count;
  10.     }
  11. }

160. 相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode/
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
LeetCode题目 - 图2
在节点 c1 开始相交。

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         ListNode hA=headA;
  4.         ListNode hB=headB;
  5.         while(hA!=hB){
  6.             hA=(hA==null)?headB:hA.next;
  7.             hB=(hB==null)?headA:hB.next;
  8.         }
  9.         return hA;
  10.     }
  11. }

69. 多数元素

https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 ：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：

  • 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

    1. class Solution {
    2. public int majorityElement(int[] nums) {
    3.    int votes=0,x=0;
    4.    for(int num:nums){
    5.        if(votes==0) 
    6.            x=num;
    7.        votes+=(x==num)?1:-1;
    8.    }
    9.    return x;
    10. }
    11. }

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

    https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/zhao-dao-suo-you-shu-zu-zhong-xiao-shi-d-mabl/
    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
    找到所有在 [1, n] 范围之间没有出现在数组中的数字。
    您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
    示例:
    输入:
    [4,3,2,7,8,2,3,1]
    输出:
    [5,6]

    1. class Solution {
    2. public List<Integer> findDisappearedNumbers(int[] nums) {
    3.    int len=nums.length;
    4.    for(int num:nums){
    5.        int i=(num-1)%len;
    6.        nums[i]+=len;
    7.    }
    8.    List<Integer> res=new ArrayList<>();
    9.    for(int i=0;i<len;i++){
    10.        if(nums[i]<=len){
    11.            res.add(i+1);
    12.        }
    13.    }
    14.    return res;
    15. }
    16. }

    234. 回文链表

    https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
    请判断一个链表是否为回文链表。
    示例 1:
    输入: 1->2
    输出: false
    示例 2:
    输入: 1->2->2->1
    输出: true
    进阶：
    你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

    1. class Solution {
    2. public boolean isPalindrome(ListNode head) {
    3.    if(head==null) return true;
    4.    //找到中点
    5.    ListNode halfNode=halfNode(head);
    6.    //从中点开始反转了的链表
    7.    ListNode reverseNode=reverseList(halfNode.next);
    8.    //判断是否为回文
    9.    ListNode p1=head;
    10.    ListNode p2=reverseNode;
    11.    boolean result=true;
    12.    while(result&&p2!=null){
    13.        if(p1.val!=p2.val){
    14.            result=false;
    15.        }
    16.        p1=p1.next;
    17.        p2=p2.next;
    18.    }
    19.    //还原被反转了的链表
    20.    reverseNode=reverseList(reverseNode);
    21.    return result;
    22. }
    24. //找到链表的中点：快慢指针找到中点
    25. private ListNode halfNode(ListNode head){
    26.    ListNode slow=head;
    27.    ListNode fast=head;
    28.    while(fast.next!=null&&fast.next.next!=null){
    29.        slow=slow.next;
    30.        fast=fast.next.next;
    31.    }
    32.    return slow;    
    33. }
    34. //反转链表的函数
    35. private ListNode reverseList(ListNode head){
    36.    ListNode pre=null;
    37.    ListNode cur=head;
    38.    while(cur!=null){
    39.        ListNode nex=cur.next;
    40.        cur.next=pre;
    41.        pre=cur;
    42.        cur=nex;
    43.    }//跳出时cur==null
    44.    return pre;
    45. }
    46. }
    47. 或
    48. //利用链表的后序遍历(递归)，但是增加了O(N)的时间复杂度
    49. class Solution{
    50. ListNode left;
    51. public boolean isPalindrome(ListNode head) {
    52.    left=head;
    53.    return traverse(head);
    54. }
    55. private boolean traverse(ListNode head) {//利用链表的后序遍历
    56.    if(head==null) return true;
    57.    boolean res=traverse(head.next);
    58.    res=res&&(left.val==head.val);
    59.    left=left.next;
    60.    return res;
    61. }
    62. }

    617. 合并二叉树

    https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/
    给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
    你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
    示例 1:
    输入:
    Tree 1 Tree 2
    1 2
    / \ / \
    3 2 1 3
    / \ \
    5 4 7
    输出:
    合并后的树:
    3
    / \
    4 5
    / \ \
    5 4 7
    注意: 合并必须从两个树的根节点开始。

    1. class Solution {
    2. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    3.    if(root1==null){
    4.        return root2;
    5.    }
    6.    if(root2==null){
    7.        return root1;
    8.    }
    9.    TreeNode mergeNode=new TreeNode(root1.val+root2.val);
    10.    mergeNode.left=mergeTrees(root1.left,root2.left);
    11.    mergeNode.right=mergeTrees(root1.right,root2.right);
    12.    return mergeNode;
    13. }
    14. }

    226. 翻转二叉树

    https://leetcode-cn.com/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode-solution/
    翻转一棵二叉树。
    示例：
    输入：
    4
    / \
    2 7
    / \ / \
    1 3 6 9
    输出：
    4
    / \
    7 2
    / \ / \
    9 6 3 1

    1. class Solution {
    2. public TreeNode invertTree(TreeNode root) {// 将整棵树的节点翻转
    3.    if (root == null) {// base case
    4.        return null;
    5.    }
    7.    /**** 前序遍历位置 ****/
    8.    // root 节点需要交换它的左右子节点
    9.    TreeNode tmp = root.left;
    10.    root.left = root.right;
    11.    root.right = tmp;
    13.    // 让左右子节点继续翻转它们的子节点
    14.    invertTree(root.left);
    15.    invertTree(root.right);
    17.    return root;
    18. }
    19. }

    104. 二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
    给定一个二叉树，找出其最大深度。
    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    说明: 叶子节点是指没有子节点的节点。
    示例：
    给定二叉树 [3,9,20,null,null,15,7]，
    3
    / \
    9 20
    / \
    15 7
    返回它的最大深度 3 。

    1. class Solution {
    2. public int maxDepth(TreeNode root) {
    3.    if(root==null) return 0;
    4.    int left=maxDepth(root.left);
    5.    int right=maxDepth(root.right);
    6.    return Math.max(left+1,right+1);
    7. }
    8. }

    283. 移动零

    https://leetcode-cn.com/problems/move-zeroes/solution/yi-dong-ling-by-leetcode-solution/
    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    示例:
    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]
    说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。
    1. class Solution {
    2.  public void moveZeroes(int[] nums) {
    3.      int n = nums.length, left = 0, right = 0;
    4.      while (right < n) {
    5.          //right遇到0可以跳过，到挨着的下一个非0数
    6.          //left遇到0不能跳过，直接指向这个0
    7.          //这样right和left交换，就能把非0移动到最后
    8.          //此方法不适合奇数与偶数的交换
    9.          if (nums[right] != 0) {
    10.              swap(nums, left, right);
    11.              left++;
    12.          }
    13.          right++;
    14.      }
    15.  }
    16.  public void swap(int[] nums, int left, int right) {
    17.      int temp = nums[left];  
    18.      nums[left] = nums[right];
    19.      nums[right] = temp;
    20.  }
    21. }

    101. 对称二叉树

    https://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode-solution/
    给定一个二叉树，检查它是否是镜像对称的。
    例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
    / \
    2 2
    / \ / \
    3 4 4 3
    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
    / \
    2 2
    \ \
    3 3
    进阶：
    你可以运用递归和迭代两种方法解决这个问题吗？
    1. //递归
    2. class Solution {
    3.  public boolean isSymmetric(TreeNode root) {
    4.      return temp(root,root);
    5.  }
    6.  private boolean temp(TreeNode node1,TreeNode node2){
    7.      if(node1==null&&node2==null) return true;
    8.      if(node1==null||node2==null) return false;
    9.      return (node1.val==node2.val)&&temp(node1.left,node2.right)&&temp(node1.right,node2.left);
    10.  }
    11. }
    12. //迭代
    13. class Solution {
    14.  public boolean isSymmetric(TreeNode root) {
    15.      return check(root, root);
    16.  }
    17.  public boolean check(TreeNode u, TreeNode v) {
    18.      Queue<TreeNode> q = new LinkedList<TreeNode>();
    19.      q.offer(u);
    20.      q.offer(v);
    21.      while (!q.isEmpty()) {
    22.          u = q.poll();
    23.          v = q.poll();
    24.          if (u == null && v == null) {
    25.              continue;
    26.          }
    27.          if ((u == null || v == null) || (u.val != v.val)) {
    28.              return false;
    29.          }
    30.          q.offer(u.left);
    31.          q.offer(v.right);
    32.          q.offer(u.right);
    33.          q.offer(v.left);
    34.      }
    35.      return true;
    36.  }
    37. }

    155. 最小栈

    https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:
输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); —> 返回 -3.
minStack.pop();
minStack.top(); —> 返回 0.
minStack.getMin(); —> 返回 -2.
提示：

  • pop、top 和 getMin 操作总是在 非空栈 上调用。
    1. //方式1
    2. class MinStack {
    3.   LinkedList<Integer> xStack;
    4.   LinkedList<Integer> minStack;
    5.   public MinStack() {
    6.       xStack = new LinkedList<>();
    7.       minStack = new LinkedList<>();
    8.       minStack.push(Integer.MAX_VALUE);//添加这个数的目的是为了第一个添加的时候，要比较峰值和当前要添加进来的值的大小时，不会出现空指针异常
    9.   }
    10.   public void push(int x) {
    11.       xStack.push(x);
    12.       minStack.push(Math.min(minStack.peek(), x));
    13.   }
    14.   public void pop() {
    15.       xStack.pop();
    16.       minStack.pop();
    17.   } 
    18.   public int top() {
    19.       return xStack.peek();
    20.   }
    21.   public int getMin() {
    22.       return minStack.peek();
    23.   }
    24. }
    25. //方式2
    26. class MinStack {
    27.   Stack<Integer> stoStk;
    28.   Stack<Integer> minStk;
    29.   public MinStack() {
    30.       stoStk=new Stack<>();
    31.       minStk=new Stack<>();
    32.   }
    33.   public void push(int x) {
    34.       stoStk.add(x);
    35.       if( minStk.empty() || minStk.peek()>=x)
    36.           minStk.add(x);
    37.   }
    38.   public void pop() {
    39.       if(stoStk.pop().equals(minStk.peek()))
    40.           minStk.pop();
    41.   } 
    42.   public int top() {
    43.        return stoStk.peek();
    44.   }
    45.   public int getMin() {
    46.        return minStk.peek();
    47.   }
    48. }

    121. 买卖股票的最佳时机

    https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
    给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
    你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

    示例 1：
    输入：[7,1,5,3,6,4]
    输出：5
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int minValue=Integer.MAX_VALUE;
  4.         int maxDiff=0;
  5.         for(int i=0;i<prices.length;i++){
  6.            if(prices[i]<minValue) {
  7.                 minValue=prices[i];
  8.            }else if(prices[i]-minValue>maxDiff){
  9.                maxDiff=prices[i]-minValue;
  10.            }
  11.         }
  12.         return maxDiff;
  13.     }
  14. }

53. 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

  1. //方法一：动态规划
  2. class Solution {
  3.     public int maxSubArray(int[] nums) {
  4.         int maxSum=nums[0];
  5.         int Fi1=nums[0];
  6.         for(int i=1;i<nums.length;i++){
  7.             Fi1=(Fi1+nums[i])>nums[i]?(Fi1+nums[i]):nums[i];
  8.             maxSum=maxSum>Fi1?maxSum:Fi1;
  9.         }
  10.         return maxSum;
  11.     }
  12. }
  13. //

543. 二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树
1
/ \
2 3
/ \
4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

  1. class Solution {
  2.     int ans;
  3.     public int diameterOfBinaryTree(TreeNode root) {
  4.         ans = 1;//ans记录该路径经过节点数的最大值
  5.         depth(root);
  6.         return ans - 1;
  7.     }
  8.     public int depth(TreeNode node) {
  9.         if (node == null) {
  10.             return 0; // 访问到空节点了，返回0
  11.         }
  12.         int L = depth(node.left); // 左儿子为根的子树的深度
  13.         int R = depth(node.right); // 右儿子为根的子树的深度
  14.         ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
  15.         return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
  16.     }
  17. }

70. 爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int f1=0,f2=1,temp=f1+f2;
  4.         for(int i=1;i<=n;i++){
  5.             temp=f1+f2;
  6.             f1=f2;
  7.             f2=temp;
  8.         }
  9.         return f2;
  10.     }
  11. }

141. 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：**pos** 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：
LeetCode题目 - 图3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
LeetCode题目 - 图4
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
LeetCode题目 - 图5
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。


提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。
    1. public class Solution {
    2. public boolean hasCycle(ListNode head) {
    3.    ListNode fast=head;//快指针
    4.    ListNode low=head;//慢指针
    5.    while(fast!=null&&fast.next!=null){//如果不是环形链表，则在不满足这两个条件中的任意一个条件时跳出
    6.        fast=fast.next.next;//此处不会空指针
    7.        low=low.next;
    8.        if(fast==low) break;//是环形链表时跳出
    9.    }
    10.    if(fast==null||fast.next==null) return false;//判断跳出循环的条件时哪个
    11.    return true;//到此处则一定有环存在
    12. }
    13. }

    20. 有效的括号

    https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。


    示例 1：
    输入：s = “()”
    输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([)]”
输出：false

示例 5：
输入：s = “{[]}”
输出：true

提示：

  • 1 <= s.length <= 104

  • s 仅由括号 '()[]{}' 组成

    1. class Solution {
    2.   public boolean isValid(String s) {
    3.       int len=s.length();
    4.       if(len%2==1) return false;
    5.       HashMap<Character,Character> map=new HashMap<>();
    6.       map.put(')','(');
    7.       map.put(']','[');
    8.       map.put('}','{');
    9.       Stack<Character> stack=new Stack<>();
    10.       for(int i=0;i<len;i++){
    11.           char ch=s.charAt(i);
    12.           if(map.containsKey(ch)){
    13.               if(stack.isEmpty()|| stack.peek()!=map.get(ch)){
    14.                   return false;
    15.               }
    16.               stack.pop(); 
    17.           }else{
    18.               stack.push(ch);
    19.           }
    20.       }
    21.       return stack.isEmpty();
    22.   }
    23. }

    700. 二叉搜索树中的搜索

    给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
    例如，
    给定二叉搜索树:
    4
    / \
    2 7
    / \
    1 3
    和值: 2
    你应该返回如下子树:
    2
    / \
    1 3
    在上述示例中，如果要找的值是5，但因为没有节点值为5，我们应该返回NULL。

    1. class Solution{
    2.   public TreeNode searchBST(TreeNode root, int val) {
    3.       if(root==null)
    4.           return null;
    5.       if(root.val==val){// 找到目标，做点什么
    6.           return root;//返回找到的节点
    7.       }
    8.       if(root.val<val){
    9.           return searchBST(root.right, val);
    10.       }
    11.       if(root.val>val){
    12.           return searchBST(root.left, val);
    13.       }
    14.       return null;//在整棵树中都没有找到目标值
    15.   }
    16. }
    17. 或
    18. //这只是两种值的不同的返回方式而已
    19. class Solution {
    20.   TreeNode res=null;
    21.   public TreeNode searchBST(TreeNode root, int val) {
    22.       dfs(root,val);
    23.       return res;
    24.   }
    25.   private void dfs(TreeNode root, int val) {
    26.       if(root==null)
    27.           return;
    28.       if(root.val==val){
    29.           res=root;
    30.       }
    31.       if(root.val<val){
    32.           dfs(root.right, val);
    33.       }
    34.       if(root.val>val){
    35.           dfs(root.left, val);
    36.       }
    37.   }
    38. }

    783. 二叉搜索树节点最小距离

    530. 二叉搜索树的最小绝对差

    给你一个二叉搜索树的根节点root，返回树中任意两不同节点值之间的最小差值。
    注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/相同
    LeetCode题目 - 图6
    示例 1：
    输入：root = [4,2,6,1,3]
    输出：1

    1. class Solution {
    2.   int preVal=-1;
    3.   int minusVal=Integer.MAX_VALUE;
    4.   public int minDiffInBST(TreeNode root) {
    5.       dfs(root);
    6.       return minusVal;
    7.   }
    8.   private void dfs(TreeNode node){
    9.       if(node==null)
    10.           return;
    11.       dfs(node.left);
    12.       if(preVal!=-1){
    13.           minusVal=Math.min(Math.abs(node.val-preVal), minusVal);
    14.           preVal=node.val;
    15.       }else{
    16.           preVal=node.val;
    17.       }
    18.       dfs(node.right);
    19.   }
    20. }

    501. 二叉搜索树中的众数

    给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
    假定 BST 有如下定义：

  • 结点左子树中所含结点的值小于等于当前结点的值

  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

例如：给定 BST[1,null,2,2],
1
\
2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

  1. class Solution {
  2.     List<Integer> res=new ArrayList<>();
  3.     int base,count,maxCount;
  4.     public int[] findMode(TreeNode root) {
  5.         dfs(root);
  6.         int[] result=new int[res.size()];
  7.         for(int i=0;i<result.length;i++){
  8.             result[i]=res.get(i);
  9.         }
  10.         return result;
  11.     }
  12.     private void dfs(TreeNode root){
  13.         if(root==null)
  14.             return;
  15.         dfs(root.left);
  16.         update(root.val);
  17.         dfs(root.right);
  18.     }
  19.     private void update(int x) {
  20.         if(base==x){
  21.             count++;
  22.         }else{
  23.             base=x;
  24.             count=1;
  25.         }
  26.         if(count==maxCount){
  27.             res.add(x);
  28.         }
  29.         if(count>maxCount){
  30.             maxCount=count;
  31.             res.clear();
  32.             res.add(x);
  33.         }
  34.     }
  35. }

938. 二叉搜索树的范围和

LeetCode题目 - 图7
给定二叉搜索树的根结点 root，返回值位于范围[low, high]之间的所有结点的值的和。
示例 1：
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

  1. class Solution {
  2.     public int rangeSumBST(TreeNode root, int low, int high) {
  3.         if(root==null)
  4.             return 0;
  5.         if(high<root.val){//root 节点的值大于high,无需考虑右子树
  6.             return rangeSumBST(root.left, low, high);
  7.         }
  8.         if(low>root.val){//root 节点的值小于 low,无需考虑左子树
  9.             return rangeSumBST(root.right, low, high);
  10.         }
  11.         //root 节点的值在 [low,high] 范围内,考虑上这三者的和
  12.         return root.val+rangeSumBST(root.left, low, high)+rangeSumBST(root.right, low, high);
  13.     }
  14. }

中等

15. 三数之和

https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
给你一个包含n个整数的数组 nums，判断 nums 中是否存在三个元素a，b，c ，使得 _a + b + c =_0 ？请你找出所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []输出：[]
示例 3：
输入：nums = [0]输出：[]
提示：

  • 0 <= nums.length <= 3000

  • -105<= nums[i] <= 105

    1. class Solution {
    2. public List<List<Integer>> threeSum(int[] nums) {
    3.    Arrays.sort(nums);//对数组排序后再查找
    4.    int len=nums.length;
    5.    List<List<Integer>> list=new ArrayList<>();
    6.    for (int first=0;first<len;first++) {// 枚举 first
    7.        if (first>0&&nums[first]==nums[first-1]) {//为了不重复，下一次枚举的first需要和上一次枚举的数不相同
    8.            continue;
    9.        }
    10.        int third=len-1;// third对应的指针初始指向数组的最右端
    11.        for (int second=first+1;second<len;second++) {//枚举second
    12.            if (second>first+1&&nums[second]==nums[second-1]) {//为了不重复，下一次枚举的second需要和上一次枚举的数不相同
    13.                continue;
    14.            }
    15.            //让这个循环while退出可能有两种情况，下面依次判断
    16.            while (second<third&&nums[second]+nums[third]>-nums[first]) {//需要保证second的指针在third的指针的左侧
    17.                third--;//因为是排序后的数，一定能满足 first<=second<=third
    18.            }
    19.            // 如果指针重合，随着second后续的增加,
    20.            // 就不会有满足 first+second+third=0 并且second<third的third了，可以退出循环
    21.            if (second==third) {
    22.                break;
    23.            }
    24.            //这是循环退出的第二种情况，如果满足条件，则添加
    25.            if (nums[second]+nums[third]==-nums[first]) {
    26.                list.add(Arrays.asList(nums[first],nums[second],nums[third]));
    27.            }
    28.            //走到这里说明是nums[second]+nums[third]<-nums[first],则让second++
    29.        }
    30.    }
    31.    return list;
    32. }
    33. }

    338. 比特位计数

    https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
    给定一个非负整数 num。对于 0 ≤ i ≤ num范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
    示例 1:
    输入: 2输出: [0,1,1]
    示例 2:
    输入: 5输出: [0,1,1,2,1,2]
    进阶:

  • 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？

  • 要求算法的空间复杂度为O(n)。

  • 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

    1. //方法二：动态规划——最高有效位
    2. class Solution {
    3. public int[] countBits(int num) {
    4.    int[] bits = new int[num + 1];
    5.    int highBit = 0;
    6.    for (int i = 1; i <= num; i++) {
    7.        if ((i & (i - 1)) == 0) {
    8.            highBit = i;
    9.        }
    10.        bits[i] = bits[i - highBit] + 1;
    11.    }
    12.    return bits;
    13. }
    14. }
    15. //方法三：动态规划——最低有效位
    16. class Solution {
    17. public int[] countBits(int num) {
    18.    int[] bits = new int[num + 1];
    19.    for (int i = 1; i <= num; i++) {
    20.        bits[i] = bits[i >> 1] + (i & 1);
    21.    }
    22.    return bits;
    23. }
    24. }
    25. //方法四：动态规划——最低设置位
    26. class Solution {
    27. public int[] countBits(int num) {
    28.    int[] bits = new int[num + 1];
    29.    for (int i = 1; i <= num; i++) {
    30.        bits[i] = bits[i & (i - 1)] + 1;
    31.    }
    32.    return bits;
    33. }
    34. }

    46. 全排列

    给定一个没有重复数字的序列，返回其所有可能的全排列。
    示例:
    输入: [1,2,3]输出: ```java class Solution { public List> permute(int[] nums) { List> res=new ArrayList<>(); List path=new ArrayList<>(); dfs(nums,0,path,res); return res; }

    private void dfs(int[] nums, int index, List path, List> res) { if(path.size()== nums.length){

    1.    res.add(new ArrayList<>(path));
    2.    return;

    } for(int i=0; i<nums.length;i++){

    1.    if(path.contains(nums[i])) continue;
    2.    path.add(nums[i]);
    3.    dfs(nums, index+1, path, res);
    4.    path.remove(path.size()-1);

    } }

}

  1. <a name="urbYu"></a>
  2. #### [22. 括号生成](https://leetcode-cn.com/problems/generate-parentheses/)
  3. 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。<br />示例 1：<br />输入：n = 3<br />输出：["((()))","(()())","(())()","()(())","()()()"]<br />示例 2：<br />输入：n = 1<br />输出：["()"]<br />提示：<br />1 <= n <= 8
  4. ```java
  5. class Solution {
  6.     public List<String> generateParenthesis(int n) {
  7.         List<String> res=new ArrayList<>();
  8.         if(n<1) return res;
  9.         dfs(n,"",res,0,0);
  10.         return res;
  11.     }
  12.     private void dfs(int n,String path,List<String> res,int open,int close){
  13.         if(close>open||open>n)
  14.             return;
  15.         if(2*n==path.length()){
  16.             res.add(path);
  17.             return;
  18.         }
  19.         dfs(n, path+"(", res,open+1,close);
  20.         dfs(n, path+")", res,open,close+1);
  21.     }
  22. }
  23. 或
  24. class Solution {
  25.     public List<String> generateParenthesis(int n) {
  26.         List<String> res=new ArrayList<>();
  27.         if(n<1) return res;
  28.         dfs(n,"",res,0,0);
  29.         return res;
  30.     }
  31.     private void dfs(int n,String path,List<String> res,int open,int close){
  32.         if(2*n==path.length()){
  33.             res.add(path);
  34.             return;
  35.         }
  36.         if(open<n)
  37.             dfs(n, path+"(", res,open+1,close);
  38.         if(close<open)
  39.             dfs(n, path+")", res,open,close+1);
  40.     }
  41. }

94. 二叉树的中序遍历

给定一个二叉树的根节点root，返回它的中序 遍历。

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res=new ArrayList<>();
  4.         Stack<TreeNode> stack=new Stack<>();
  5.         TreeNode node=root;
  6.         while (node!=null||!stack.isEmpty()){
  7.             if(node!=null){
  8.                 stack.add(node);
  9.                 node=node.left;
  10.             }else{
  11.                 node = stack.pop();
  12.                 res.add(node.val);
  13.                 node=node.right;
  14.             }
  15.         }
  16.         return res;
  17.     }
  18. }
  19. 或
  20. class Solution {
  21.     public List<Integer> inorderTraversal(TreeNode root) {
  22.         List<Integer> res=new ArrayList<>();
  23.         Stack<TreeNode> stack=new Stack<>();
  24.         TreeNode node=root;
  25.         while (node!=null||!stack.isEmpty()){
  26.             while (node!=null){
  27.                 stack.add(node);
  28.                 node=node.left;
  29.             }
  30.             node = stack.pop();
  31.             res.add(node.val);
  32.             node=node.right;
  33.         }
  34.         return res;
  35.     }
  36. }

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。 （即逐层地，从左到右访问所有节点）。

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> res=new ArrayList<>();
  4.         if(root==null) return res;
  5.         LinkedList<TreeNode> nodesList=new LinkedList<>();
  6.         nodesList.add(root);
  7.         while(!nodesList.isEmpty()){
  8.             List<Integer> temp=new ArrayList<>();
  9.             for(int i=nodesList.size();i>0;i--){
  10.                 TreeNode node = nodesList.removeFirst();
  11.                 temp.add(node.val);
  12.                 if(node.left!=null)
  13.                     nodesList.add(node.left);
  14.                 if(node.right!=null)
  15.                     nodesList.add(node.right);
  16.             }
  17.             res.add(new ArrayList<>(temp));
  18.         }
  19.         return res;
  20.     }
  21. }

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

根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]

  1. class Solution {
  2.     public TreeNode buildTree(int[] preorder,int[] inorder) {
  3.         HashMap<Integer,Integer> map=new HashMap<>();
  4.         for(int i=0;i<inorder.length;i++){
  5.             map.put(inorder[i],i);
  6.         }
  7.         return build(preorder, 0, preorder.length-1,inorder,0,inorder.length-1,map);
  8.     }
  9.     private TreeNode build(int[] preorder,int preLeft,int preRight,
  10.                            int[] inorder,int inLeft,int inRight,
  11.                            HashMap<Integer,Integer> map){
  13.         if(preLeft>preRight||inLeft>inRight)
  14.             return null;
  15.         // root 节点对应的值就是前序遍历数组的第一个元素
  16.         TreeNode root=new TreeNode(preorder[preLeft]);
  17.         int len=map.get(preorder[preLeft])-inLeft;// rootVal 在中序遍历数组中的索引
  18.          // 递归构造左右子树
  19.         root.left=build(preorder,preLeft+1,preLeft+len,inorder,inLeft,inLeft+len-1,map);
  20.         root.right=build(preorder,preLeft+len+1,preRight, inorder, inLeft+len+1, inRight,map);
  21.         return root;
  22.     }
  23. }

106. 从中序与后序遍历序列构造二叉树

难度中等496
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7

  1. class Solution {
  2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  3.         HashMap<Integer,Integer> map=new HashMap<>();
  4.         for(int i=0;i<inorder.length;i++){
  5.             map.put(inorder[i],i);
  6.         }
  7.         return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1,map);
  8.     }
  9.     private TreeNode build(int[] inorder,int inLeft,int inRight,
  10.                             int[] postorder,int postLeft,int postRight,
  11.                             HashMap<Integer,Integer> map){
  12.         if(inLeft>inRight||postLeft>postRight)
  13.             return null;
  14.         TreeNode root=new TreeNode(postorder[postRight]);
  15.         int len=map.get(postorder[postRight])-inLeft;
  16.         root.left=build(inorder, inLeft, inLeft+len-1, postorder, postLeft, postLeft+len-1, map);
  17.         root.right=build(inorder, inLeft+len+1, inRight, postorder, postLeft+len, postRight-1, map);
  18.         return root;
  19.     }
  20. }

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

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

  1. class Solution {
  2.     public ListNode removeNthFromEnd(ListNode head, int n) {
  3.         ListNode temp=new ListNode(0,head);
  4.         ListNode pre=head;
  5.         ListNode after=temp;
  6.         while(n>0){
  7.             pre=pre.next;
  8.             n--;
  9.         }
  10.         while(pre!=null){
  11.             pre=pre.next;
  12.             after=after.next;
  13.         }
  14.         after.next=after.next.next;
  15.         return temp.next;
  16.     }
  17. }

114. 二叉树展开为链表

给你二叉树的根结点root，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。
  • 展开后的单链表应该与二叉树先序遍历顺序相同。

LeetCode题目 - 图8
示例 1：
输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6]

  1. class Solution {
  2.     // 定义：将以 root 为根的树拉平为链表
  3.     public void flatten(TreeNode root) {
  4.         // base case
  5.         if (root == null) return;
  7.         flatten(root.left);
  8.         flatten(root.right);
  10.         /**** 后序遍历位置 ****/
  11.         // 1、左右子树已经被拉平成一条链表
  12.         TreeNode left = root.left;
  13.         TreeNode right = root.right;
  15.         // 2、将左子树作为右子树
  16.         root.left = null;
  17.         root.right = left;
  19.         // 3、将原先的右子树接到当前右子树的末端
  20.         TreeNode p = root;
  21.         while (p.right != null) {
  22.             p = p.right;
  23.         }
  24.         p.right = right;
  25.     }
  26. }

124. 二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点root，返回其最大路径和。

  1. class Solution {
  2.     int ans=Integer.MIN_VALUE;
  3.     public int maxPathSum(TreeNode root) {
  4.         dfs(root);
  5.         return ans;
  6.     }
  7.     private int  dfs(TreeNode node) {//找出每个节点最大路径
  8.         if(node==null) return 0;
  9.         int left=Math.max(0, dfs(node.left));
  10.         int right=Math.max(0, dfs(node.right));
  11.         ans=Math.max(ans,left+right+node.val);
  12.         return Math.max(left, right)+node.val;
  13.     }
  14. }

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。注意，pos仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：

  • 你是否可以使用O(1)空间解决此题？

示例 1：
LeetCode题目 - 图9
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.         ListNode fast=head;
  4.         ListNode slow=head;
  5.         while (fast!=null&&fast.next!=null){
  6.             fast=fast.next.next;
  7.             slow=slow.next;
  8.             if(fast==slow){
  9.                 break;
  10.             }
  11.         }
  12.         if(fast==null||fast.next==null)
  13.             return null;
  14.         fast=head;
  15.         while (fast!=slow){
  16.             slow=slow.next;
  17.             fast=fast.next;
  18.         }
  19.         return fast;
  20.     }
  21. }

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：“abc”输出：3解释：三个回文子串: “a”, “b”, “c”

  1. class Solution {
  2.     public int countSubstrings(String s) {
  3.         int[] res=new int[1];
  4.         for(int i=0;i<s.length();i++){
  5.             palindrome(s,i,i,res);
  6.             palindrome(s,i,i+1,res);
  7.         }
  8.         return res[0];
  9.     }
  10.     private void palindrome(String s,int i,int j,int[] res) {
  11.         while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)){
  12.             i--;
  13.             j++;
  14.             res[0]++;
  15.         }
  16.     }
  17. }

5. 最长回文子串

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484471&idx=1&sn=7c26d04a1f035770920d31377a1ebd42&chksm=9bd7fa3faca07329189e9e8b51e1a665166946b66b8e8978299ba96d5f2c0d3eafa7db08b681&mpshare=1&scene=23&srcid=0502skarllDchCXKriEMLVWp&sharer_sharetime=1619940584540&sharer_shareid=371aa2900d94d479c7e5122b7ae18619#rd
给你一个字符串s，找到s中最长的回文子串。
示例 1：
输入：s = “babad”输出：“bab”解释：“aba” 同样是符合题意的答案。

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         String res="";
  4.         for(int i=0;i<s.length();i++){
  5.             String result1=palindrome(s,i,i);//截取到的字符串是奇数个
  6.             String result2=palindrome(s,i,i+1);//截取到的字符串是偶数个
  7.             //获取到最大的回文字符串的长度
  8.             res=res.length()>result1.length()?res:result1;
  9.             res=res.length()>result2.length()?res:result2;
  10.         }
  11.         return res;
  12.     }
  13.     private String palindrome(String s,int i,int j) {
  14.         while (i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)){//防止索引越界
  15.             //从中间向两边扩展的情况
  16.             i--;
  17.             j++;
  18.         }//跳出这个循环时，要么是 i 刚越界，要么是 j 刚越界，要么是 s.charAt(i)!=s.charAt(j)
  19.         //无论是 i 越界还是 s.charAt(i)!=s.charAt(j)，都应该从 i+1 位置处开始截取字符串
  20.         //无论是 j 越界还是 s.charAt(i)!=s.charAt(j)，都应该从 j-1 位置处开始截取字符串
  21.         // 但 substring() 方法是左开右闭，则截取到 j 位置处
  22.         return s.substring(i+1,j);
  23.     }    
  24. }

1669. 合并两个链表

给你两个链表 list1和 list2 ，它们包含的元素分别为 n个和 m个。
请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 1：
LeetCode题目 - 图10

  1. class Solution {
  2.     public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
  3.         ListNode temp1=list1;
  4.         ListNode temp2=list1;
  5.         while(a-->1){
  6.             temp1=temp1.next;
  7.         }
  8.         while(b-->=0){
  9.             temp2=temp2.next;
  10.         }
  11.         temp1.next=list2;
  12.         while(temp1.next!=null){
  13.             temp1=temp1.next;
  14.         }
  15.         temp1.next=temp2;
  16.         return list1;
  17.     }
  18. }

143. 重排链表

给定一个单链表 L：L_0→_L_1→…→_Ln-1→L_n ，将其重新排列后变为：_L_0→_Ln→L_1→_Ln-1→L_2→_Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

  1. //注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
  2. class Solution {
  3.     public void reorderList(ListNode head) {
  4.         ListNode halfNode=halfNode(head);
  5.         ListNode l1=head;
  6.         ListNode l2=halfNode.next;
  7.         halfNode.next=null;//将链表分为两段
  8.         l2 = reverseList(l2);
  9.         mergeList(l1, l2);
  10.     }
  11.     private ListNode reverseList(ListNode node) {
  12.         ListNode pre=null;
  13.         ListNode cur=node;
  14.         while (cur!=null){
  15.             ListNode temp=cur.next;
  16.             cur.next=pre;
  17.             pre=cur;
  18.             cur=temp;
  19.         }
  20.         return pre;
  21.     }
  22.     private ListNode halfNode(ListNode head) {
  23.         ListNode fast=head;
  24.         ListNode slow=head;
  25.         while(fast!=null&&fast.next!=null){
  26.             fast=fast.next.next;
  27.             slow=slow.next;
  28.         }
  29.         return slow;
  30.     }
  31.     private ListNode mergeList(ListNode node1,ListNode node2){
  32.         ListNode temp1;
  33.         ListNode temp2;
  34.         while(node1!=null&&node2!=null){
  35.             temp1=node1.next;
  36.             temp2=node2.next;
  37.             node1.next=node2;
  38.             node1=temp1;
  39.             node2.next=node1;
  40.             node2=temp2;
  41.         }
  42.         return node1;
  43.     }
  44. }

1143. 最长公共子序列

给定两个字符串 text1和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。
一个字符串的 子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，”ace”是”abcde”的子序列，但”aec”不是”abcde”的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

  1. //动态规划
  2. class Solution {
  3.     public int longestCommonSubsequence(String text1, String text2) {
  4.         int len1=text1.length();
  5.         int len2=text2.length();
  6.         int[][] dp=new int[len1+1][len2+1];
  7.         for(int i=1;i<=len1;i++){
  8.             for(int j=1;j<=len2;j++){
  9.                 if(text1.charAt(i-1)==text2.charAt(j-1)){
  10.                     dp[i][j]=dp[i-1][j-1]+1;
  11.                 }else{
  12.                     dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);
  13.                 }
  14.             }
  15.         }
  16.         return dp[len1][len2];
  17.     }
  18. }
  19. //动态规划是有以下的递归方式优化而得，递归会超时
  20. class Solution{
  21.     public int longestCommonSubsequence(String text1, String text2) {
  22.         int len1=text1.length();
  23.         int len2=text2.length();
  24.         int[][] dp=new int[len1][len2];
  25.         return dfs(dp,len1-1,len2-1,text1,text2);
  26.     }
  27.     private int dfs(int[][] dp,int i,int j,String text1,String text2){
  28.         if(i==-1||j==-1)
  29.             return 0;
  30.         if(text1.charAt(i)==text2.charAt(j)){
  31.             return dfs(dp,i-1,j-1,text1,text2)+1;
  32.         }else{
  33.             return Math.max(dfs(dp,i-1,j,text1,text2),dfs(dp,i,j-1,text1,text2));
  34.         }
  35.     }
  36. }

322. 零钱兑换

难度中等1248
给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

  1. //动态规划
  2. class Solution {
  3.     public int coinChange(int[] coins, int amount) {
  4.         int[] dp=new int[amount+1];
  5.         Arrays.fill(dp, amount+1);
  6.         dp[0]=0;
  7.         for(int i=1;i<=amount;i++){
  8.             for(int coin:coins){// 内层 for 在求所有子问题 + 1 的最小值
  9.                 if(i-coin<0) continue;
  10.                 dp[i]=Math.min(dp[i],1+dp[i-coin]); 
  11.             }
  12.         }
  13.         return dp[amount]==amount+1?-1:dp[amount];
  14.     }
  15. }
  16. //带备忘录的递归，拥有O(NK)的时间复杂度
  17. class Solution {
  18.     public int coinChange(int[] coins, int amount) {
  19.         int[] memory=new int[amount+1];
  20.         Arrays.fill(memory, -2);//初始化备忘录为-2
  21.         return help(coins, amount,memory);
  22.     }
  23.     private int help(int[] coins, int amount,int[] memory) {
  24.         if (amount==0) return 0;
  25.         if (memory[amount]!=-2) return memory[amount];
  26.         int res=Integer.MAX_VALUE;
  27.         for (int coin:coins) {
  28.             //金额不可达
  29.             if(amount-coin<0) continue;
  30.             int sub=help(coins,amount-coin,memory);
  31.             //子问题无解
  32.             if(sub==-1) continue;
  33.             res=Math.min(res,sub+1);
  34.         }
  35.         //记录每个节点的答案
  36.         memory[amount]=(res==Integer.MAX_VALUE)?-1:res;
  37.         return memory[amount];
  38.     }
  39. }
  40. //纯递归，拥有O(N^K*K)的超高的时间复杂度，K是硬币的币种(向下递归成为树结构来查看)
  41. class Solution {
  42.     public int coinChange(int[] coins, int amount) {
  43.         if(amount==0) return 0;
  44.         int res=Integer.MAX_VALUE;
  45.         for(int coin:coins){
  46.             //金额不可达
  47.             if(amount-coin<0) continue;//如果当前节点不能凑整，则直接计算当前节点的同一层的相邻节点
  48.             int sub=coinChange(coins, amount-coin);//计算当前这个节点的能凑整的最小硬币数
  49.             //子问题无解
  50.             if(sub==-1) continue;//如果这个节点不能凑整，则跳过当前节点，计算当前节点的同一层的相邻节点
  51.             res=Math.min(res,sub+1);//比较得到每个节点的支路能凑整的最小硬币数，这个硬币数得加上当前节点的这个硬币
  52.         }
  53.         return(res==Integer.MAX_VALUE)?-1:res;//如果某个节点的所有支路都没法凑整(即在for循环里一直执行的是 if(amount-coin<0) continue; 这句话)，则返回-1
  54.     }
  55. }

300. 最长递增子序列

给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

  1. //动态规划
  2. class Solution {
  3.    public int lengthOfLIS(int[] nums) {
  4.         int[] dp=new int[nums.length];
  5.         Arrays.fill(dp, 1);//极端情况下，子序列至少有1个
  6.         int res=Integer.MIN_VALUE;
  7.         for(int i=0;i<nums.length;i++){//分别是以0-num.length长度结尾的字符串
  8.             for(int j=0;j<i;j++){//从0-i之间找能构成的最长子序列
  9.                 if(nums[j]<nums[i]){
  10.                     dp[i]=Math.max(dp[i],dp[j]+1);//每次都找0-i的字符串的最长升序子序列，必须要把num[i]这个字符串包进去，以num[i]结尾
  11.                 }
  12.             }
  13.             res=Math.max(res, dp[i]);//找最长的子序列
  14.         }
  15.         return res;
  16.     }
  17. }

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

  1. class Solution {
  2.     public int pathSum(TreeNode root, int targetSum) {//遍历二叉树的每一个节点,计算每个节点能有多少条路径
  3.         if(root==null) //递归结束条件
  4.             return 0;
  5.         int rootCount=count(root,targetSum);// 自己为开头的路径数
  6.         int leftCount=pathSum(root.left, targetSum);// 左边路径总数（相信他能算出来）
  7.         int rightCount=pathSum(root.right, targetSum);// 右边路径总数（相信他能算出来）
  8.         return rootCount+leftCount+rightCount;
  9.     }
  10.     private int count(TreeNode root, int targetSum) {//计算每一个节点能有多少条路径
  11.         if(root==null)
  12.             return 0;
  13.         int self=(root.val==targetSum)?1:0;// 我自己能不能独当一面，作为一条单独的路径呢？
  14.         int left=count(root.left, targetSum-root.val); // 左边的小老弟，你那边能凑几个 sum - node.val 呀？
  15.         int right=count(root.right, targetSum-root.val);// 右边的小老弟，你那边能凑几个 sum - node.val 呀？
  16.         return self+left+right;// 我这能凑这么多个
  17.     }
  18. }

62. 不同路径

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] dp=new int[m][n];
  4.         for(int i=0;i<m;i++){
  5.             for(int j=0;j<n;j++){
  6.                 if(i==0||j==0){
  7.                     dp[i][j]=1;
  8.                 }else{
  9.                     dp[i][j]=dp[i-1][j]+dp[i][j-1];
  10.                 }
  11.             }
  12.         }
  13.         return dp[m-1][n-1];
  14.     }
  15. }

64. 最小路径和

LeetCode题目 - 图11
给定一个包含非负整数的m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int m=grid.length;
  4.         int n=grid[0].length;
  5.         int[][] dp=new int[m][n];
  6.         dp[0][0]=grid[0][0];
  7.         for(int i=0;i<m;i++){
  8.             for(int j=0;j<n;j++){
  9.                 if(i==0&&j==0){
  10.                     continue;
  11.                 }else if(j==0){
  12.                     dp[i][0]=dp[i-1][0]+grid[i][0];
  13.                 }else if(i==0){
  14.                     dp[0][j]=dp[0][j-1]+grid[0][j];
  15.                 }else{
  16.                     dp[i][j]=Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
  17.                 }
  18.             }
  19.         }
  20.         return dp[m-1][n-1];
  21.     }
  22. }

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node left;
Node right;
Node next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为NULL。
初始状态下，所有 next 指针都被设置为NULL。
*进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：
LeetCode题目 - 图12
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’#’ 标志着每一层的结束。

  1. class Solution {
  2.     public Node connect(Node root) {
  3.         if(root==null) return null;
  4.         connectTwoNode(root.left,root.right);
  5.         return root;
  6.     }
  7.     // 定义：输入两个节点，将它俩连接起来
  8.     private void connectTwoNode(Node node1, Node node2) {
  9.         if (node1 == null || node2 == null) {
  10.             return;
  11.         }
  12.         /**** 前序遍历位置 ****/
  13.         // 将传入的两个节点连接
  14.         node1.next = node2;
  16.         // 连接相同父节点的两个子节点
  17.         connectTwoNode(node1.left, node1.right);
  18.         connectTwoNode(node2.left, node2.right);
  19.         // 连接跨越父节点的两个子节点
  20.         connectTwoNode(node1.right, node2.left);
  21.     }
  22. }

654. 最大二叉树

给定一个不含重复元素的整数数组nums。一个以此数组直接递归构建的最大二叉树定义如下：

  1. 二叉树的根是数组nums中的最大元素。
  2. 左子树是通过数组中最大值左边部分递归构造出的最大二叉树。
  3. 右子树是通过数组中最大值右边部分递归构造出的最大二叉树。

LeetCode题目 - 图13
返回有给定数组nums构建的最大二叉树。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

  1. class Solution {
  2.     public TreeNode constructMaximumBinaryTree(int[] nums) {
  3.         return dfs(nums,0,nums.length-1);
  4.     }
  5.     private TreeNode dfs(int[] nums,int left,int right){
  6.         if(left>right)
  7.             return null;
  8.         int max=Integer.MIN_VALUE;
  9.         int maxIndex=Integer.MIN_VALUE;
  10.         // 找到数组中的最大值和对应的索引
  11.         for(int i=left;i<=right;i++){
  12.             if(nums[i]>max){
  13.                 max=nums[i];
  14.                 maxIndex=i;
  15.             }
  16.         }
  17.         TreeNode root=new TreeNode(nums[maxIndex]);
  18.         // 递归调用构造左右子树
  19.         root.left=dfs(nums, left,maxIndex-1);
  20.         root.right=dfs(nums, maxIndex+1,right);
  21.         return root;
  22.     }
  23. }

652. 寻找重复的子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树：
2
/
4
和
4
因此，你需要以列表的形式返回上述重复子树的根结点。

  1. class Solution {
  2.     public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
  3.         HashMap<String,Integer> memory=new HashMap<>();//记录所有子树以及出现的次数
  4.         List<TreeNode> res=new ArrayList<>();//记录重复的子树根节点
  5.         dfs(root,memory,res);
  6.         return res;
  7.     }
  8.     private String dfs(TreeNode root,HashMap<String,Integer> memory,List<TreeNode> res) {
  9.         if(root==null)
  10.             return "#";
  11.         String left=dfs(root.left,memory,res);
  12.         String right=dfs(root.right,memory,res);
  13.         String subTree=left+","+right+","+root.val;
  14.         int freq = memory.getOrDefault(subTree, 0);
  15.         if(freq==1){// 多次重复也只会被加入结果集一次
  16.             res.add(root);
  17.         }
  18.         memory.put(subTree,freq+1);//给子树对应的出现次数加一
  19.         return subTree;
  20.     }
  21. }

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示:输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

  1. //前序遍历
  2. public class Codec {
  3.     String NULL="#";// 代表 null 空指针的字符
  4.     String SEP=",";// 代表分隔符的字符
  5.     public String serialize(TreeNode root) {
  6.         StringBuilder sb=new StringBuilder();
  7.         serialize(root,sb);
  8.         return sb.toString();
  9.     }
  10.     private void serialize(TreeNode root, StringBuilder sb) {
  11.         if(root==null){
  12.             sb.append(NULL).append(SEP);
  13.             return;
  14.         }
  15.         sb.append(root.val).append(SEP);//前序遍历代码
  16.         serialize(root.left,sb);
  17.         serialize(root.right,sb);
  18.     }
  20.     public TreeNode deserialize(String data) {
  21.         LinkedList<String> nodes=new LinkedList<>();
  22.         for(String node:data.split(SEP)){
  23.             nodes.addLast(node);
  24.         }
  25.         return deserialize(nodes);
  26.     }
  27.     private TreeNode deserialize(LinkedList<String> nodes) {
  28.         if(nodes.isEmpty())
  29.             return null;
  30.         // 列表最左侧就是根节点，从前往后取出元素
  31.         String node = nodes.removeFirst();
  32.         if(NULL.equals(node))
  33.             return null;
  34.         TreeNode root=new TreeNode(Integer.parseInt(node));
  35.         //先构造左子树，后构造右子树
  36.         root.left=deserialize(nodes);
  37.         root.right=deserialize(nodes);
  38.         return root;
  39.     }
  40. }
  41. //后序遍历
  42. public class Codec {
  43.     String NULL="#";// 代表 null 空指针的字符
  44.     String SEP=",";// 代表分隔符的字符
  45.     public String serialize(TreeNode root) {
  46.         StringBuilder sb=new StringBuilder();
  47.         serialize(root,sb);
  48.         return sb.toString();
  49.     }
  50.     private void serialize(TreeNode root, StringBuilder sb) {
  51.         if(root==null){
  52.             sb.append(NULL).append(SEP);
  53.             return;
  54.         }
  55.         serialize(root.left,sb);
  56.         serialize(root.right,sb);
  57.         sb.append(root.val).append(SEP);//后序遍历位置
  58.     }
  60.     public TreeNode deserialize(String data) {
  61.         LinkedList<String> nodes=new LinkedList<>();
  62.         for(String node:data.split(SEP)){
  63.             nodes.addLast(node);
  64.         }
  65.         return deserialize(nodes);
  66.     }
  67.     private TreeNode deserialize(LinkedList<String> nodes) {
  68.         if(nodes.isEmpty())
  69.             return null;
  70.         // 列表最右侧就是根节点，从后往前取出元素
  71.         String node = nodes.removeLast();
  72.         if(NULL.equals(node))
  73.             return null;
  74.         TreeNode root=new TreeNode(Integer.parseInt(node));
  75.         // 先构造右子树，后构造左子树
  76.         root.right=deserialize(nodes);
  77.         root.left=deserialize(nodes);
  78.         return root;
  79.     }
  80. }
  81. //中序遍历
  82. //中序遍历的方式行不通，序列化方法 serialize 依然容易，但无法实现反序列化方法 deserialize。
  83. //层序遍历
  84. public class Codec {
  85.     String NULL="#";// 代表 null 空指针的字符
  86.     String SEP=",";// 代表分隔符的字符
  87.     public String serialize(TreeNode root) {
  88.         if(root==null)
  89.             return "";
  90.         Queue<TreeNode> queue=new LinkedList<>();
  91.         StringBuilder sb=new StringBuilder();
  92.         // 初始化队列，将 root 加入队列
  93.         queue.add(root);
  94.         while(!queue.isEmpty()){
  95.             TreeNode node = queue.poll();
  96.             if(node==null){
  97.                 sb.append(NULL).append(SEP);
  98.                 continue;
  99.             }
  100.             sb.append(node.val).append(SEP);
  101.             queue.add(node.left);
  102.             queue.add(node.right);
  103.         }
  104.         return sb.toString();
  105.     }
  106.     public TreeNode deserialize(String data) {
  107.         if(data.isEmpty()) return null;
  108.         String[] nodes = data.split(SEP);
  109.         Queue<TreeNode> queue=new LinkedList<>();
  110.         // 第一个元素就是 root 的值
  111.         TreeNode root=new TreeNode(Integer.parseInt(nodes[0]));
  112.         // 队列 queue 记录父节点，将 root 加入队列
  113.         queue.add(root);
  114.         for(int i=1;i<nodes.length;){
  115.             // 队列中存的都是父节点
  116.             TreeNode node = queue.poll();
  117.             // 父节点对应的左侧子节点的值
  118.             String left=nodes[i++];
  119.             if(!NULL.equals(left)){
  120.                 node.left=new TreeNode(Integer.parseInt(left));
  121.                 queue.add(node.left);
  122.             }else{
  123.                 node.left=null;
  124.             }
  125.             // 父节点对应的右侧子节点的值
  126.             String right=nodes[i++];
  127.             if(!NULL.equals(right)){
  128.                 node.right=new TreeNode(Integer.parseInt(right));
  129.                 queue.add(node.right);
  130.             }else{
  131.                 node.right=null;
  132.             }
  133.         }
  134.         return root;
  135.     }
  136.     /**或：下面使用的是while循环搭配i++的反序列化二叉树
  137.     public TreeNode deserialize(String data) {
  138.         if(data.isEmpty()) return null;
  139.         String[] nodes = data.split(SEP);
  140.         Queue<TreeNode> queue=new LinkedList<>();
  141.         // 第一个元素就是 root 的值
  142.         int i=0;
  143.         TreeNode root=new TreeNode(Integer.parseInt(nodes[i++]));
  144.         // 队列 queue 记录父节点，将 root 加入队列
  145.         queue.add(root);
  146.         while (!queue.isEmpty()){
  147.             // 队列中存的都是父节点
  148.             TreeNode node = queue.poll();
  149.             // 父节点对应的左侧子节点的值
  150.             String left=nodes[i++];
  151.             if(!NULL.equals(left)){
  152.                 node.left=new TreeNode(Integer.parseInt(left));
  153.                 queue.add(node.left);
  154.             }else{
  155.                 node.left=null;
  156.             }
  157.             // 父节点对应的右侧子节点的值
  158.             String right=nodes[i++];
  159.             if(!NULL.equals(right)){
  160.                 node.right=new TreeNode(Integer.parseInt(right));
  161.                 queue.add(node.right);
  162.             }else{
  163.                 node.right=null;
  164.             }
  165.         }
  166.         return root;
  167.     }
  168.     */
  169. }

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

LeetCode题目 - 图14
给定一个二叉搜索树的根节点root，和一个整数k，请你设计一个算法查找其中第 k个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1

  1. class Solution {
  2.     int count=0;// 记录当前元素的排名
  3.     int res=0;// 记录结果
  4.     public int kthSmallest(TreeNode root, int k) {
  5.         dfs(root, k);
  6.         return res;
  7.     }
  8.     private void dfs(TreeNode root, int k){
  9.         if(root==null)
  10.             return;
  11.         dfs(root.left, k);
  12.         if(k==count){ // 找到第 k 小的元素
  13.             res=root.val;
  14.             return;
  15.         }
  16.         dfs(root.right, k);
  17.     }
  18. }

538. 把二叉搜索树转换为累加树

1038. 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键小于节点键的节点。
  • 节点的右子树仅包含键大于节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1：
LeetCode题目 - 图15
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

  1. class Solution {
  2.     public TreeNode bstToGst(TreeNode root) {
  3.         dfs(root);
  4.         return root;
  5.     }
  6.     int sum=0;// 记录累加和
  7.     private void dfs(TreeNode root){
  8.         if(root==null){
  9.             return;
  10.         }
  11.         dfs(root.right); // 先递归遍历右子树
  12.          // 中序遍历代码位置
  13.         sum+=root.val;// 维护累加和
  14.         root.val=sum; // 将 BST 转化成累加树
  15.         dfs(root.left);// 后递归遍历左子树
  16.     }
  17. }

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:
输入:
2
/ \
1 3
输出: true

  1. class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return isValidBST(root, null, null);
  4.     }
  5.     private boolean isValidBST(TreeNode root,TreeNode min,TreeNode max) {
  6.         if(root==null)
  7.             return true;
  8.         // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
  9.         if(min!=null&&root.val<=min.val) return false;
  10.         if(max!=null&&root.val>=max.val) return false;
  11.          // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
  12.         return isValidBST(root.left,min,root)&&isValidBST(root.right,root,max);
  13.     }
  14. }

701. 二叉搜索树中的插入操作

LeetCode题目 - 图16
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
示例 1：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
LeetCode题目 - 图17

  1. class Solution{
  2.     //因为涉及到要返回TreeNode类型，就要对递归调用的返回值进行接收。所以选择边递归边进行插入
  3.     public TreeNode insertIntoBST(TreeNode root, int val) {
  4.         if(root==null)// 找到空位置插入新节点
  5.             return new TreeNode(val);
  6.         // if (root.val == val)//     BST 中一般不会插入已存在元素
  7.         if(root.val>val){
  8.             root.left=insertIntoBST(root.left, val);
  9.         }
  10.         if(root.val<val){
  11.             root.right=insertIntoBST(root.right, val);
  12.         }
  13.         return root;
  14.     }
  15. }

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点root和一个值key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

说明：要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7

  1. class Solution {
  2.     public TreeNode deleteNode(TreeNode root, int key) {
  3.         if(root==null)
  4.             return null;
  5.         if(root.val==key){
  6.             if(root.right==null) return root.left;
  7.             if(root.left==null) return root.right;
  8.             //找到右子树的最小节点
  9.             TreeNode minNode=getMin(root.right);
  10.             // 把 root 改成 minNode
  11.             root.val=minNode.val;
  12.             // 转而去删除 minNode
  13.             root.right=deleteNode(root.right, minNode.val);
  14.         }
  15.         if(root.val>key){
  16.             root.left=deleteNode(root.left, key);
  17.         }
  18.         if(root.val<key){
  19.             root.right=deleteNode(root.right, key);
  20.         }
  21.         return root;
  22.     }
  23.     private TreeNode getMin(TreeNode root) {
  24.         // BST 最左边的就是最小的
  25.         while(root.left!=null)
  26.             root=root.left;
  27.         return root;
  28.     }
  29. }

96. 不同的二叉搜索树

LeetCode题目 - 图18
给你一个整数n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5

  1. class Solution {
  2.      public int numTrees(int n) {
  3.         int[][] memo=new int[n+1][n+1];
  4.         //计算闭区间 [1, n] 组成的 BST 个数
  5.         return count(1,n,memo);
  6.     }
  7.     //计算闭区间 [lo, hi] 组成的 BST 个数
  8.     private int count(int lo,int hi,int[][] memo) {
  9.         if(lo>hi)
  10.             return 1;
  11.         if(memo[lo][hi]!=0)
  12.             return memo[lo][hi];
  13.         int res=0;
  14.         for(int i=lo;i<=hi;i++){
  15.             // i 的值作为根节点 root
  16.             int left=count(lo,i-1,memo);
  17.             int right=count(i+1,hi,memo);
  18.             res+=left*right;// 左右子树的组合数乘积是 BST 的总数
  19.         }
  20.         memo[lo][hi]=res;
  21.         return res;
  22.     }
  23. }

95. 不同的二叉搜索树 II

给定一个整数n，生成所有由 1 … n为节点所组成的二叉搜索树。
示例：
输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

提示：

  • 0 <= n <= 8

    1. class Solution {
    2.   public List<TreeNode> generateTrees(int n) {
    3.       if (n == 0) return new ArrayList<>();
    4.       return build(1,n);
    5.   }
    6.   private List<TreeNode> build(int lo, int hi) {
    7.       List<TreeNode> res=new ArrayList<>();
    8.       if(lo>hi){
    9.           res.add(null);
    10.           return res;
    11.       }
    12.       // 1、穷举 root 节点的所有可能。
    13.       for(int i=lo;i<=hi;i++){
    14.           //2、递归构造出左右子树的所有合法 BST。
    15.           List<TreeNode> leftNodes=build(lo, i-1);
    16.           List<TreeNode> rightNodes=build(i+1, hi);
    17.           // 3、给 root 节点穷举所有左右子树的组合。
    18.           for(TreeNode left:leftNodes){
    19.               for(TreeNode right:rightNodes){
    20.                   TreeNode root=new TreeNode(i); // i 作为根节点 root 的值
    21.                   root.left=left;
    22.                   root.right=right;
    23.                   res.add(root);
    24.               }
    25.           }
    26.       }
    27.       return res;
    28.   }
    29. }

    148. 排序链表

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

  • 你可以在 O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？

LeetCode题目 - 图19
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

困难

32. 最长有效括号

给你一个只包含’(‘ 和’)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = “(()”输出：2解释：最长有效括号子串是 “()”

  1. //动规
  2. class Solution {
  3.    public int longestValidParentheses(String s) {
  4.         if(s.length()<1) return 0;
  5.         char[] charArray = s.toCharArray();
  6.         int[] dp=new int[s.length()];
  7.         int max=0;
  8.         for(int i=1;i<charArray.length;i++){
  9.             if(charArray[i]==')'){
  10.                 if(charArray[i-1]=='('){
  11.                     dp[i]=(i>=2?dp[i-2]:0)+2;
  12.                 }else if(i-1-dp[i-1]>=0&&s.charAt(i-1-dp[i-1])=='('){
  13.                     dp[i]=dp[i-1]+(i>=dp[i-1]+2?dp[i-dp[i-1]-2]:0)+2;
  14.                 }
  15.             }
  16.             max=Math.max(max, dp[i]);
  17.         }
  18.         return max;
  19.     }
  20. }
  21. 或
  22. //栈
  23. class Solution {
  24.    public int longestValidParentheses(String s) {
  25.         Stack<Integer> stack=new Stack<>();
  26.         stack.push(-1);//用于初始化，便于后续求差
  27.         int max=0;
  28.         for(int i=0;i<s.length();i++){
  29.             if(s.charAt(i)=='('){
  30.                 stack.push(i);
  31.             }else{
  32.                 stack.pop();
  33.                 if(stack.isEmpty()) {
  34.                     stack.push(i);//不断更新没有被匹配的右括号的位置，也就是不断扔掉右括号
  35.                 }
  36.                 else {
  37.                     max=Math.max(max, i-stack.peek());
  38.                 }
  39.             }
  40.         }
  41.         return max;
  42.     }
  43. }
  44. 或
  45. //利用两个计数器left 和 right
  46. class Solution {
  47.    public int longestValidParentheses(String s) {
  48.         int open=0,close=0,max=0;
  49.         for(int i=0;i<s.length();i++){
  50.             char ch=s.charAt(i);
  51.             if(ch=='(')
  52.                 open++;
  53.             else
  54.                 close++;
  55.             if(open==close)
  56.                 max=Math.max(max, open*2);
  57.             else if(close>open)
  58.                 open=close=0;
  59.         }
  61.         open=close=0;
  62.         for(int i=s.length()-1;i>=0;i--){
  63.             char ch=s.charAt(i);
  64.             if(ch=='(')
  65.                 open++;
  66.             else
  67.                 close++;
  68.             if(open==close)
  69.                 max=Math.max(max, open*2);
  70.             else if(open>close)
  71.                 open=close=0;
  72.         }
  73.         return max;
  74.     }
  75. }

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：

  • 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

LeetCode题目 - 图20
示例 1：
输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5]

  1. //迭代反转链表+递归分解子问题
  2. class Solution {
  3.     public ListNode reverseKGroup(ListNode head, int k) {//这个还是用的递归
  4.         if(head==null) return null;
  5.         ListNode a=head,b=head;
  6.         for(int i=0;i<k;i++){ // 区间 [a, b) 包含 k 个待反转元素
  7.             if(b==null) return head;//不足 k 个，不需要反转，base case
  8.             b=b.next;
  9.         }
  10.         ListNode reverseNode = reverse(a, b);//此处利用迭代反转链表,反转前 k 个元素
  11.         a.next=reverseKGroup(b,k);//递归分解为子问题,//递归反转后续链表并连接起来
  12.         return reverseNode;
  13.     }
  14.     //迭代反转链表，反转区间 [a, b) 的元素，注意是左闭右开
  15.     private ListNode reverse(ListNode a,ListNode b){//迭代反转链表
  16.         ListNode pre=null;
  17.         ListNode cur=a;
  18.         while (a!=b){//while 终止条件要注意
  19.             ListNode temp=a.next;
  20.             a.next=pre;
  21.             pre=a;
  22.             a=temp;
  23.         }
  24.         return pre;//返回反转后的头结点
  25.     }
  26. }
  27. 或
  28. //递归反转链表+递归分解子问题
  29. class Solution {
  30.     public ListNode reverseKGroup(ListNode head, int k) {//这个还是用的递归
  31.         if(head==null) return null;
  32.         ListNode a=head,b=head;
  33.         for(int i=0;i<k;i++){
  34.             if(b==null) return head;
  35.             b=b.next;
  36.         }
  37.         ListNode newNode = traverse(a, k);
  38.         a.next=reverseKGroup(b,k);//递归分解为子问题
  39.         return newNode;
  40.     }
  41.     ListNode after;
  42.     private ListNode traverse(ListNode head,int m) {//递归反转链表的前n个节点
  43.         if(m==1){
  44.             after=head.next;
  45.             return head;
  46.         }
  47.         ListNode last=traverse(head.next,m-1);
  48.         head.next.next=head;
  49.         head.next=after;
  50.         return last;
  51.     }
  52. }

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

  1. //动态规划(最优解)
  2. class Solution {
  3.     public int minDistance(String word1, String word2) {
  4.         int len1=word1.length();
  5.         int len2=word2.length();
  6.         int[][] dp=new int[len1+1][len2+1];//dp[i][j]代表修改s1[0..i-1]到s2[0...j-1]需要的次数
  7.         for(int i=1;i<=len1;i++){//行改变，代表从 s1[0..i-1]到成为 空串 需要删除的次数
  8.             dp[i][0]=i;
  9.         }
  10.         for(int j=1;j<=len2;j++){//列改变，代表从 空串 到 s2[0..j-1] 需要增加的次数
  11.             dp[0][j]=j;
  12.         }
  13.         for(int i=1;i<=len1;i++){
  14.             for(int j=1;j<=len2;j++){
  15.                 if(word1.charAt(i-1)==word2.charAt(j-1)){
  16.                     dp[i][j]=dp[i-1][j-1];
  17.                 }else{
  18.                     dp[i][j]=min(1+dp[i-1][j-1],1+dp[i-1][j],1+dp[i][j-1]);
  19.                 }
  20.             }
  21.         }
  22.         return dp[len1][len2];
  23.     }
  24.     private int min(int a,int b,int c){
  25.         return Math.min(Math.min(a, b), c);
  26.     }
  27. }
  28. //带备忘录的递归
  29. class Solution {
  30.      public int minDistance(String word1, String word2) {
  31.         int[][] memory=new int[word1.length()][word2.length()];
  32.         return dp(word1.length()-1,word2.length()-1,word1,word2,memory);
  33.     }
  34.     private int dp(int i, int j, String word1, String word2,int[][] memory) {
  35.         if(i==-1) return 1+j;
  36.         if(j==-1) return 1+i;
  37.         if(memory[i][j]!=0) return memory[i][j];
  38.         if(word1.charAt(i)==word2.charAt(j)){
  39.             memory[i][j]=dp(i-1, j-1, word1, word2,memory);
  40.         }else{
  41.             memory[i][j]=min(dp(i,j-1,word1,word2,memory)+1,
  42.                             dp(i-1,j,word1,word2,memory)+1,
  43.                             dp(i-1,j-1,word1,word2,memory)+1);
  44.         }
  45.         return  memory[i][j];
  46.     }
  47.     private int min(int a,int b,int c){
  48.         return Math.min(Math.min(a, b), c);
  49.     }
  50. }
  51. //递归：时间复杂度太大
  52. class Solution {
  53. public int minDistance(String word1, String word2) {
  54.         return dp(word1.length()-1,word2.length()-1,word1,word2);//从两个字符串的末尾开始比较
  55.     }
  56.     private int dp(int i, int j, String word1, String word2) {
  57.         if(i==-1) return 1+j;//s1先遍历到头部，则把s2剩余的都插入到s1的头部
  58.         if(j==-1) return 1+i;//s2先遍历到头部，则把s1剩余的全部都删除掉
  59.         if(word1.charAt(i)==word2.charAt(j)){
  60.             return dp(i-1, j-1, word1, word2);//直接跳过，啥都不做，操作数不变
  61.         }else{//求删除、替换和插入三者最小的，这三种都会导致操作数+1
  62.             return Math.min(Math.min(dp(i,j-1,word1,word2)+1,dp(i-1,j,word1,word2)+1),
  63.                             dp(i-1,j-1,word1,word2)+1);
  64.         }
  65.     }
  66. }

72.编辑距离拓展

计算最小编辑距离的路径是怎样的：即从s1变成s2针对s1字符的具体操作步骤
例如：都是按字符串的索引顺序进行操作的
从 horse 到 ros ，horse需要经过:替换 h ，跳过 o ，删除 r ,跳过 o，删除s
路径为 [3, 4, 2, 4, 2]
从 ros 到 horse，ros需要经过:替换 h ，跳过 o ，插入 r ,跳过 s，插入e
路径为 [3, 4, 1, 4, 1]
1代表插入; 2代表删除; 3代表替换; 4代表啥都不做

  1. class Soluton{    
  2.     public Node[][] minDistance(String word1, String word2) {
  3.         int len1=word1.length();
  4.         int len2=word2.length();
  5.         Node[][] dp=new Node[len1+1][len2+1];
  6.         for(int i=0;i<dp.length;i++){
  7.             for(int j=0;j<dp[0].length;j++){
  8.                 dp[i][j]=new Node();
  9.             }
  10.         }
  11.         for(int i=1;i<=len1;i++){
  12.             dp[i][0].val=i;
  13.             dp[i][0].choice=2;//删除
  14.         }
  15.         for(int j=1;j<=len2;j++){
  16.             dp[0][j].val=j;
  17.             dp[0][j].choice=1;//插入
  18.         }
  19.         for(int i=1;i<=len1;i++){
  20.             for(int j=1;j<=len2;j++){
  21.                 if(word1.charAt(i-1)==word2.charAt(j-1)){//跳过，啥也不做
  22.                     dp[i][j].val=dp[i-1][j-1].val;
  23.                     dp[i][j].choice=4;
  24.                 }else{
  25.                     dp[i][j].val=min(1+dp[i-1][j-1].val,1+dp[i-1][j].val,1+dp[i][j-1].val);
  26.                     if(dp[i][j].val==1+dp[i-1][j-1].val){//替换
  27.                         dp[i][j].choice=3;
  28.                     }else if(dp[i][j].val==1+dp[i-1][j].val){//删除i
  29.                         dp[i][j].choice=2;
  30.                     }else{//插入
  31.                         dp[i][j].choice=1;
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.         return dp;
  37.     }
  38.     private int min(int a,int b,int c){
  39.         return Math.min(Math.min(a, b), c);
  40.     }
  41.     private void path(Node[][] res,int len1, int len2,ArrayList<Integer> path) {
  42.         while (len1>0&&len2>0){
  43.             int choice=res[len1][len2].choice;
  44.             path.add(0,choice);
  45.             if(choice==1){
  46.                 len2--;
  47.             }else if(choice==2){
  48.                 len1--;
  49.             }else if(choice==3||choice==4){
  50.                 len1--;
  51.                 len2--;
  52.             }
  53.         }
  54.     }
  55. }
  56. class Node {
  57.     int val=0;
  58.     /** 1代表插入;  2代表删除;  3代表替换;  4代表啥都不做 */
  59.     int choice=0;
  60. }

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持’.’ 和 ‘*’ 的正则表达式匹配。

  • ‘.’匹配任意单个字符
  • ‘*’匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = “aa” p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

  1. //带备忘录的递归1
  2. class Solution{
  3.     public boolean isMatch(String s,String p) {
  4.         boolean[][] memory=new boolean[s.length()][p.length()];
  5.         return isMatch(0, 0, s, p, memory);
  6.     }
  7.     public boolean isMatch(int i,int j,String s,String p,boolean[][] memory) {
  8.         if(j==p.length())
  9.             return i==s.length();
  10.         if(i<s.length()&&j<p.length()&&memory[i][j])
  11.             return memory[i][j];
  12.         boolean firstMatch=(i<s.length())&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.');
  13.         boolean res;
  14.         if(p.length()>=j+2&&p.charAt(j+1)=='*'){
  15.             res=isMatch(i, j+2,s,p,memory) ||(firstMatch&&isMatch(i+1,j,s,p,memory));
  16.         }else{
  17.             res=firstMatch&&isMatch(i+1,j+1,s,p,memory);
  18.         }
  19.         if(i<s.length()&&j<p.length())
  20.             memory[i][j]=res;
  21.         return res;
  22.     }
  23. }
  24. //带备忘录的递归2
  25. class Solution {
  26.     HashMap<String,Boolean> map=new HashMap<>();
  27.     public boolean isMatch(String s, String p) {
  28.         int m=s.length(),n=p.length();
  29.         return isMatch(s,0,p,0);
  30.     }
  31.     private boolean isMatch(String s,int i,String p,int j){
  32.         if(j==p.length()){
  33.             return i==s.length();
  34.         }
  35.         if(i==s.length()){
  36.             if((p.length()-j)%2==1){//全都是*x*x的形式
  37.                 return false;
  38.             }
  39.             for(;j+1<p.length();j+=2){
  40.                 if(p.charAt(j+1)!='*'){
  41.                     return false;
  42.                 }
  43.             }
  44.             return true;
  45.         }
  46.         String key=i+","+j;
  47.         if(map.containsKey(key)){
  48.             return map.get(key);
  49.         }
  50.         boolean res;
  51.         if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){//匹配
  52.             if(j+1<p.length()&&p.charAt(j+1)=='*') {//匹配0次或多次
  53.                 res=isMatch(s, i,p,j+2)||isMatch(s, i+1,p,j);
  54.             }else{
  55.                 res=isMatch(s, i+1,p,j+1);
  56.             }
  57.         }else{//不匹配
  58.             if(j+1<p.length()&&p.charAt(j+1)=='*'){//只能匹配0次
  59.                 res=isMatch(s, i,p,j+2);
  60.             }else{
  61.                 res=false;
  62.             }
  63.         }
  64.         map.put(key, res);
  65.         return res;
  66.     }
  67. }
  68. 或
  69. //动态规划    
  70. class Solution{
  71.     public boolean isMatch2(String s, String p) {
  72.         int m=s.length()+1;
  73.         int n=p.length()+1;
  74.         boolean[][] dp=new boolean[m][n];
  75.         dp[0][0]=true;
  76.         for(int i=2;i<n;i+=2){//判断矩阵首行的比较结果，同样首列的结果也是固定的
  77.             dp[0][i]=dp[0][i-2]&&p.charAt(i-1)=='*';
  78.         }
  79.         for(int i=1;i<m;i++){ //因为*前面至少要有一个数，所以在p串中至少在第二位，所以 j-2 不会越界，同样的， i-1 也不会越界
  80.             for(int j=1;j<n;j++){
  81.                 if(p.charAt(j-1)=='*'){
  82.                     dp[i][j]=(dp[i][j-2])||(dp[i-1][j]&&s.charAt(i-1)==p.charAt(j-2))||(dp[i-1][j]&&p.charAt(j-2)=='.');
  83.                 }else{
  84.                     dp[i][j]=(dp[i-1][j-1]&&s.charAt(i-1)==p.charAt(j-1))||(dp[i-1][j-1]&&p.charAt(j-1)=='.');
  85.                 }
  86.             }
  87.         }
  88.         return dp[m-1][n-1];
  89.     }
  90. }
  91. 或
  92. //递归版的，还未优化
  93. class Solution{   
  94.     public boolean isMatch(String s, String p) {
  95.         if(p.length()==0)
  96.             return s.length()==0;
  97.         boolean firstMatch=(s.length()!=0)&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.');
  98.         if(p.length()>=2&&p.charAt(1)=='*'){
  99.             return isMatch(s, p.substring(2)) ||
  100.                     (firstMatch&&isMatch(s.substring(1),p));
  101.         }
  102.         return firstMatch&&isMatch(s.substring(1),p.substring(1));
  103.     }
  104. }

1373. 二叉搜索子树的最大键值和

给你一棵以 root 为根的 二叉树 ，请你返回任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下：

  • 任意节点的左子树中的键值都 小于 此节点的键值。
  • 任意节点的右子树中的键值都大于 此节点的键值。
  • 任意节点的左子树和右子树都是二叉搜索树。

示例 1：
LeetCode题目 - 图21
输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。

  1. class Solution{
  2.     // 全局变量，记录 BST 最大节点之和
  3.     int maxNum;
  4.     public int maxSumBST(TreeNode root) {
  5.         traverse(root);
  6.         return maxNum;
  7.     }
  8.     //0：是否是bst  1：最小值   2：最大值   3：树的和
  9.     // 函数返回 int[]{ isBST, min, max, sum}
  10.     private int[] traverse(TreeNode root) {
  11.         if(root==null){
  12.             return new int[]{1,Integer.MIN_VALUE,Integer.MAX_VALUE,0};
  13.         }
  14.         // 递归计算左右子树
  15.         int[] left=traverse(root.left);
  16.         int[] right=traverse(root.right);
  17.         int[] res=new int[4];
  18.         // 这个 if 在判断以 root 为根的二叉树是不是 BST
  19.         if(left[0]==1&&right[0]==1&&root.val>left[1]&&root.val<right[2]){
  20.             // 以 root 为根的二叉树是 BST
  21.             res[0]=1;
  22.             res[1]=Math.max(right[1], root.val);// 计算以 root 为根的这棵 BST 的最大值
  23.             res[2]=Math.min(left[2], root.val); // 计算以 root 为根的这棵 BST 的最小值
  24.             res[3]=root.val+left[3]+right[3];// 计算以 root 为根的这棵 BST 所有节点之和
  25.             maxNum=Math.max(maxNum, res[3]);// 更新全局变量
  26.         }else{
  27.             // 以 root 为根的二叉树不是 BST
  28.             res[0]=0; // 其他的值都没必要计算了，因为用不到
  29.         }
  30.         return res;
  31.     }
  32. }

系列问题

一、买卖股票

121. 买卖股票的最佳时机

给定一个数组prices，它的第 i个元素 prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
解题关键点：
关键不在于最大值还是最小值，而是数字的添加和减少。添加新数时，可以根据已有最值，推导出新的最值；而减少数字时，不一定能直接推出新的最值，不得不重新遍历。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices.length<1) return 0;
  4.         int res=0;
  5.         int curMin=prices[0];
  6.         for(int i=1;i<prices.length;i++){
  7.             curMin=Math.min(curMin, prices[i]);
  8.             res=Math.max(res, prices[i]-curMin);
  9.         }
  10.         return res;
  11.     }
  12. }

122. 买卖股票的最佳时机 II

给定一个数组prices，其中 prices[i]是一支给定股票第i天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
解题关键点：
遇到这种无穷 for 循环的情况，就是使用递归的强烈暗示。我们上一题的框架只能解决一次买卖的最大收益，现在的问题是，进行一次股票卖出后，下一次应该在什么时候交易呢？这个问题和原问题具有相同结构，规模减小，典型的递归场景。只要给原框架稍加改动即可。

  1. //贪心算法：时间复杂度为O(N)，能赚一点是一点
  2. class Solution {
  3.     public int maxProfit(int[] prices) {
  4.         int maxProfit=0;
  5.         for(int i=1;i<prices.length;i++){
  6.             if(prices[i]>prices[i-1])
  7.                 maxProfit+=(prices[i]-prices[i-1]);
  8.         }
  9.         return maxProfit;
  10.     }
  11. }
  12. //递归：时间复杂度为O(N^2),超时
  13. class Solution {
  14.     public int maxProfit(int[] prices) {
  15.         int[] memo=new int[prices.length];
  16.         Arrays.fill(memo, -1);
  17.         return dfs(prices, 0, prices.length-1,memo);
  18.     }
  19.     private int dfs(int[] prices,int lo,int hi,int[] memo) {
  20.         if(lo>hi)
  21.             return 0;
  22.         if(memo[lo]!=-1) return memo[lo];//代表在lo处买入能获得的最大利润
  23.         int res=0;
  24.         int curMin=prices[lo];
  25.         for(int i=lo+1;i<=hi;i++){
  26.             curMin=Math.min(curMin, prices[i]);
  27.             res=Math.max(res, dfs(prices,i+1,hi,memo)+prices[i]-curMin);
  28.         }
  29.         memo[lo]=res;
  30.         return res;
  31.     }
  32. }

123. 买卖股票的最佳时机 III

给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

  1. //递归：时间复杂度为O(2*N^2),超时
  2. class Solution {
  3.     public int maxProfit(int[] prices) {
  4.         int[][] memo=new int[prices.length][2];
  5.         for(int i=0;i<memo.length;i++){
  6.             Arrays.fill(memo[i],-1);
  7.         }
  8.         return dfs(prices, 0, prices.length-1, 1, memo);
  9.     }
  10.     private int dfs(int[] prices,int lo,int hi,int k,int[][] memo){
  11.         if(lo>hi)
  12.             return 0;
  13.         if(k==-1)
  14.             return 0;
  15.         if(memo[lo][k]!=-1)
  16.             return memo[lo][k];
  17.         int res=0;
  18.         int curMin=prices[lo];
  19.         for(int i=lo+1;i<=hi;i++){
  20.             curMin=Math.min(curMin, prices[i]);
  21.             res=Math.max(res, dfs(prices, i+1, hi, k-1, memo)+prices[i]-curMin);
  22.         }
  23.         memo[lo][k]=res;
  24.         return res;
  25.     }
  26. }

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices，它的第i个元素 prices[i]是一支给定的股票在第i天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

  1. //递归：时间复杂度为O(K*N^2),没超时
  2. class Solution {
  3.     public int maxProfit(int k, int[] prices) {
  4.         int[][] memo=new int[prices.length][k];
  5.         for(int i=0;i<memo.length;i++){
  6.             Arrays.fill(memo[i],-1);
  7.         }
  8.         return dfs(prices, 0, prices.length-1, k-1, memo);
  9.     }
  10.     private int dfs(int[] prices,int lo,int hi,int k,int[][] memo){
  11.         if(lo>hi)
  12.             return 0;
  13.         if(k==-1)
  14.             return 0;
  15.         if(memo[lo][k]!=-1)
  16.             return memo[lo][k];
  17.         int res=0;
  18.         int curMin=prices[lo];
  19.         for(int i=lo+1;i<=hi;i++){
  20.             curMin=Math.min(curMin, prices[i]);
  21.             //需要加上共买k次的约束
  22.             res=Math.max(res, dfs(prices, i+1, hi, k-1, memo)+prices[i]-curMin);
  23.         }
  24.         memo[lo][k]=res;
  25.         return res;
  26.     }
  27. }

309. 最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

  1. //递归：时间复杂度为O(N^2),没超时
  2. class Solution {
  3.     public int maxProfit(int[] prices) {
  4.         int[] memo=new int[prices.length];
  5.         Arrays.fill(memo, -1);
  6.         return dfs(prices, 0, prices.length-1, memo);
  7.     }
  8.     private int dfs(int[] prices,int lo,int hi,int[] memo){
  9.         if(lo>hi)
  10.             return 0;
  11.         if(memo[lo]!=-1)
  12.             return memo[lo];
  13.         int res=0;
  14.         int curMin=prices[lo];
  15.         for(int i=lo+1;i<=hi;i++){
  16.             curMin=Math.min(curMin, prices[i]);
  17.             //要隔一天买入：修改下次的买入时间为i+2即可
  18.             res=Math.max(res, dfs(prices, i+2, hi, memo)+prices[i]-curMin);
  19.         }
  20.         memo[lo]=res;
  21.         return res;
  22.     }
  23. }

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

  1. //递归：时间复杂度为O(N^2),超时
  2. class Solution {
  3.     public int maxProfit(int[] prices, int fee) {
  4.         int[] memo=new int[prices.length];
  5.         Arrays.fill(memo, -1);
  6.         return dfs(prices, 0, prices.length-1, memo,fee);
  7.     }
  8.     private int dfs(int[] prices,int lo,int hi,int[] memo,int fee){
  9.         if(lo>hi)
  10.             return 0;
  11.         if(memo[lo]!=-1)
  12.             return memo[lo];
  13.         int res=0;
  14.         int curMin=prices[lo];
  15.         for(int i=lo+1;i<=hi;i++){
  16.             curMin=Math.min(curMin, prices[i]);
  17.             //每次卖出需要手续费，套进框架，把手续费从利润中减掉即可。
  18.             res=Math.max(res, dfs(prices, i+1, hi, memo,fee)+prices[i]-curMin-fee);
  19.         }
  20.         memo[lo]=res;
  21.         return res;
  22.     }
  23. }

二、双指针技巧(快慢指针、左右子针、滑动窗口)

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int left=0;
  4.         int right=nums.length-1;
  5.         while (left<=right){
  6.             int sum=nums[left]+nums[right];
  7.             if(sum==target)
  8.                 return new int[]{nums[left],nums[right]};
  9.             else if(sum<target)
  10.                 left++;
  11.             else if(sum>target)
  12.                 right--;
  13.         }
  14.         return new int[]{-1,-1};
  15.     }
  16. }

148. 排序链表

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

  • 你可以在 O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？

LeetCode题目 - 图22
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

  1. class Solution {
  2.      public ListNode sortList(ListNode head) {
  3.         return sortList(head, null);
  4.     }
  5.     public ListNode sortList(ListNode head,ListNode tail) {//排序链表
  6.         //细分链表到一个节点或者为空时就返回
  7.         if(head==null)
  8.             return head;
  9.         if(head.next==tail){
  10.             head.next=null;
  11.             return head;
  12.         }
  13.         ListNode mid=halfNode(head, tail);
  14.         //不断排序链表
  15.         ListNode list1=sortList(head,mid);
  16.         ListNode list2=sortList(mid,tail);
  17.         //归并链表
  18.         ListNode merged=mergeList(list1,list2);
  19.         return merged;
  20.     }
  21.     private ListNode halfNode(ListNode node,ListNode tail){//找链表的中点
  22.         ListNode fast=node;
  23.         ListNode slow=node;
  24.         while (fast!=tail&&fast.next!=tail){
  25.             fast=fast.next.next;
  26.             slow=slow.next;
  27.         }
  28.         return slow;
  29.     }
  30.     private ListNode mergeList(ListNode list1,ListNode list2){//合并两个链表
  31.         ListNode newNode=new ListNode(-1);
  32.         ListNode temp=newNode;
  33.         while (list1!=null&&list2!=null){
  34.             if(list1.val<list2.val){
  35.                 temp.next=list1;
  36.                 list1=list1.next;
  37.                 temp=temp.next;
  38.             }else {
  39.                 temp.next=list2;
  40.                 list2=list2.next;
  41.                 temp=temp.next;
  42.             }
  43.         }
  44.         temp.next=(list1==null?list2:list1);
  45.         return newNode.next;
  46.     }
  47. }

26. 删除有序数组中的重复项

给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         if(nums.length==0)
  4.             return 0;
  5.         int fast=0,slow=0;
  6.         while(fast<nums.length){
  7.             // 维护 nums[0..slow] 无重复
  8.             if(nums[fast]!=nums[slow]){
  9.                 slow++;
  10.                 nums[slow]=nums[fast];
  11.             }
  12.             fast++;
  13.         }
  14.         //数组长度为索引 + 1
  15.         return slow+1;
  16.     }
  17. }

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

LeetCode题目 - 图23
存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]

  1. class Solution {
  2.     public ListNode deleteDuplicates(ListNode head) {
  3.         if(head==null)
  4.             return null;
  5.         ListNode fast=head,slow=head;
  6.         while(fast!=null){
  7.             if(fast.val!=slow.val){
  8.                 slow.next=fast;//类似 nums[slow] = nums[fast];
  9.                 slow=slow.next;//类似 slow++;
  10.             }
  11.             //类似 fast++
  12.             fast=fast.next;
  13.         }
  14.         // 断开与后面重复元素的连接
  15.         slow.next=null;
  16.         return head;
  17.     }
  18. }

27. 移除元素

给你一个数组nums和一个值val，你需要原地移除所有数值等于 val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         int fast=0,slow=0;
  4.         while(fast<nums.length){
  5.             if(nums[fast]!=val){
  6.                 nums[slow]=nums[fast];
  7.                 slow++;
  8.             }
  9.             fast++;
  10.         }
  11.         return slow;
  12.     }
  13. }

283. 移动零

给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。

  2. 尽量减少操作次数。

    1. class Solution {
    2.  public void moveZeroes(int[] nums) {
    3.      // 去除 nums 中的所有 0, 返回去除 0 之后的数组长度
    4.      int p=removeElement(nums,0);
    5.      // 将 p 之后的所有元素赋值为 0
    6.      for(;p<nums.length;p++)
    7.          nums[p]=0;
    8.  }
    9.  //借用第27. 移除元素
    10.  private int removeElement(int[] nums, int val) {
    11.      int fast=0,slow=0;
    12.      while(fast<nums.length){
    13.          if(nums[fast]!=val){
    14.              nums[slow]=nums[fast];
    15.              slow++;
    16.          }
    17.          fast++;
    18.      }
    19.      return slow;
    20.  }
    21. }
    22. 或
    23. //更优一点的方式
    24. class Solution {
    25.  public void moveZeroes(int[] nums) {
    26.      int fast=0,slow=0;
    27.      while(fast<nums.length){
    28.         if(nums[fast]!=0){
    29.          swap(nums,slow,fast);
    30.          slow++;
    31.         }
    32.      fast++;
    33.     }
    34.  }
    35.  private void swap(int[] nums,int i,int j){
    36.      int temp=nums[i];
    37.      nums[i]=nums[j];
    38.      nums[j]=temp;
    39.  }
    40. }

    2Sum 3Sum 4Sum 问题(快慢双指针)

    两数之和I(剑指 Offer 57. 和为s的两个数字)

    输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
    示例 1：
    输入：nums = [2,7,11,15], target = 9
    输出：[2,7] 或者 [7,2]

    1. class Solution {
    2.  public int[] twoSum(int[] nums, int target) {
    3.       // 先对数组排序
    4.      Arrays.sort(nums);
    5.      // 左右指针
    6.      int lo=0,hi=nums.length-1;
    7.      while (lo<hi){
    8.          int sum=nums[lo]+nums[hi];
    9.           // 根据 sum 和 target 的比较，移动左右指针
    10.          if(sum<target){
    11.              lo++;
    12.          }else if(sum>target){
    13.              hi--;
    14.          }else{
    15.              return new int[]{nums[lo],nums[hi]};
    16.          }
    17.      }
    18.      return new int[]{};
    19.  }
    20. }

    两数之和ii

    nums中可能有多对儿元素之和都等于target，请你的算法返回所有和为target的元素对儿，其中不能出现重复。
    比如说输入为nums = [1,3,1,2,2,3], target = 4，那么算法返回的结果就是：[[1,3],[2,2]]。
    对于修改后的问题，关键难点是现在可能有多个和为target的数对儿，还不能重复，比如上述例子中[1,3]和[3,1]就算重复，只能算一次。

    1. class Solution{
    2.  public List<List<Integer>> twoSumTarget(int[] nums, int target) {
    3.      List<List<Integer>> res=new ArrayList<>();
    4.      Arrays.sort(nums);
    5.      int lo=0,hi=nums.length-1;
    6.      while (lo<hi){
    7.          int sum=nums[lo]+nums[hi];
    8.          int left=nums[lo],right=nums[hi];
    9.          if(sum<target){
    10.              while (lo<hi&&nums[lo]==left) lo++;
    11.          }else if(sum>target){
    12.              while (lo<hi&&nums[hi]==right) hi--;
    13.          }else{
    14.              ArrayList<Integer> temp=new ArrayList<>();
    15.              temp.add(nums[lo]);
    16.              temp.add(nums[hi]);
    17.              res.add(temp);
    18.              while (lo<hi&&nums[lo]==left) lo++;
    19.              while (lo<hi&&nums[hi]==right) hi--;
    20.          }
    21.      }
    22.      return res;
    23.  }
    24. }

    15. 三数之和

    给你一个包含n个整数的数组 nums，判断 nums 中是否存在三个元素a，b，c ，使得 _a + b + c =_0 ？请你找出所有和为0且不重复的三元组。
    注意：答案中不可以包含重复的三元组。
    示例 1：
    输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]

    1. class Solution {
    2.  public List<List<Integer>> threeSum(int[] nums) {
    3.      return threeSumTarget(nums,0);
    4.  }
    5.  public List<List<Integer>> threeSumTarget(int[] nums,int target) {
    6.      // 数组得排个序
    7.      Arrays.sort(nums);
    8.      List<List<Integer>> res=new ArrayList<>();
    9.      // 穷举 threeSum 的第一个数
    10.      for(int i=0;i<nums.length;i++){
    11.           // 对 target - nums[i] 计算 twoSum
    12.          List<List<Integer>> twoSum = twoSumTarget(nums, i + 1, target - nums[i]);
    13.           // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
    14.          for(List<Integer> temp:twoSum){
    15.              temp.add(nums[i]);
    16.              res.add(temp);
    17.          }
    18.           // 跳过第一个数字重复的情况，否则会出现重复结果
    19.          while(i<nums.length-1&&nums[i]==nums[i+1]) i++;
    20.      }
    21.      return res;
    22.  }
    23.  //nums 中所有和为 target 的二元组
    24.  public List<List<Integer>> twoSumTarget(int[] nums, int start,int target) {
    25.      List<List<Integer>> res=new ArrayList<>();
    26.      // 左指针改为从 start 开始，其他不变
    27.      int lo=start,hi=nums.length-1;
    28.      while (lo<hi){
    29.          int sum=nums[lo]+nums[hi];
    30.          int left=nums[lo],right=nums[hi];
    31.          if(sum<target){
    32.              while (lo<hi&&nums[lo]==left) lo++;
    33.          }else if(sum>target){
    34.              while (lo<hi&&nums[hi]==right) hi--;
    35.          }else{
    36.              ArrayList<Integer> temp=new ArrayList<>();
    37.              temp.add(nums[lo]);
    38.              temp.add(nums[hi]);
    39.              res.add(temp);
    40.              while (lo<hi&&nums[lo]==left) lo++;
    41.              while (lo<hi&&nums[hi]==right) hi--;
    42.          }
    43.      }
    44.      return res;
    45.  }
    46. }

    18. 四数之和

    给定一个包含 n个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素a，b，c 和d ，使得 a+b+c+d 的值与 target 相等？找出所有满足条件且不重复的四元组。
    注意：答案中不可以包含重复的四元组。
    示例 1：
    输入：nums = [1,0,-1,0,-2,2], target = 0
    输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

    1. class Solution {
    2.  public List<List<Integer>> fourSum(int[] nums, int target) {
    3.       // 数组需要排序
    4.      Arrays.sort(nums);
    5.      List<List<Integer>> res=new ArrayList<>();
    6.       // 穷举 fourSum 的第一个数
    7.      for(int i=0;i<nums.length;i++){
    8.           // 对 target - nums[i] 计算 threeSum
    9.          List<List<Integer>> threeSum = threeSumTarget(nums, i + 1, target - nums[i]);
    10.           // 如果存在满足条件的三元组，再加上 nums[i] 就是结果四元组
    11.          for(List<Integer> temp:threeSum){
    12.              temp.add(nums[i]);
    13.              res.add(temp);
    14.          }
    15.          // fourSum 的第一个数不能重复
    16.          while(i<nums.length-1&&nums[i]==nums[i+1]) i++;
    17.      }
    18.      return res;
    19.  }
    20.  public List<List<Integer>> threeSumTarget(int[] nums,int start,int target) {
    21.      List<List<Integer>> res=new ArrayList<>();
    22.       // i 从 start 开始穷举，其他都不变
    23.      for(int i=start;i<nums.length;i++){
    24.          List<List<Integer>> twoSum = twoSumTarget(nums, i + 1, target - nums[i]);
    25.          for(List<Integer> temp:twoSum){
    26.              temp.add(nums[i]);
    27.              res.add(temp);
    28.          }
    29.          while(i<nums.length-1&&nums[i]==nums[i+1]) i++;
    30.      }
    31.      return res;
    32.  }
    33.  public List<List<Integer>> twoSumTarget(int[] nums, int start,int target) {
    34.      List<List<Integer>> res=new ArrayList<>();
    36.      int lo=start,hi=nums.length-1;
    37.      while (lo<hi){
    38.          int sum=nums[lo]+nums[hi];
    39.          int left=nums[lo],right=nums[hi];
    40.          if(sum<target){
    41.              while (lo<hi&&nums[lo]==left) lo++;
    42.          }else if(sum>target){
    43.              while (lo<hi&&nums[hi]==right) hi--;
    44.          }else{
    45.              ArrayList<Integer> temp=new ArrayList<>();
    46.              temp.add(nums[lo]);
    47.              temp.add(nums[hi]);
    48.              res.add(temp);
    49.              while (lo<hi&&nums[lo]==left) lo++;
    50.              while (lo<hi&&nums[hi]==right) hi--;
    51.          }
    52.      }
    53.      return res;
    54.  }
    55. }

    1两数之和(补充的：这里是返回角标，不是返回数值，所以解法与上面是不同的)

    给定一个整数数组nums 和一个整数目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
    你可以按任意顺序返回答案。
    示例 1：
    输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

    1. class Solution {
    2.  public int[] twoSum(int[] nums, int target) {
    3.      HashMap<Integer,Integer> map=new HashMap<>();
    4.      for(int i=0;i<nums.length;i++){
    5.          map.put(nums[i],i);
    6.      }
    7.      for(int i=0;i<nums.length;i++){
    8.          if(map.containsKey(target-nums[i])&&map.get(target-nums[i])!=i) 
    9.              return new int[]{i,map.get(target-nums[i])};
    10.      }
    11.      return new int[]{};
    12.  }
    13. }

    三、滑动窗口算法(双指针的高级应用部分)

    76. 最小覆盖子串

    给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串””。
    注意：如果s中存在这样的子串，我们保证它是唯一的答案。
    示例 1：
    输入：s = “ADOBECODEBANC”, t = “ABC”
    输出：“BANC”

    1. class Solution {
    2.  public String minWindow(String s, String t) {
    3.      int left=0,right=0;
    4.      HashMap<Character,Integer> window=new HashMap<>();
    5.      HashMap<Character,Integer> needs=new HashMap<>();
    6.      for(int i=0;i<t.length();i++){
    7.          needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0)+1);
    8.      }
    9.      int valid=0;
    10.      // 记录最小覆盖子串的起始索引及长度
    11.      int start=0,len=Integer.MAX_VALUE;
    12.      while (right<s.length()) {
    13.          // c 是将移入窗口的字符
    14.          char c = s.charAt(right);
    15.          // 右移窗口
    16.          right++;
    17.          // 进行窗口内数据的一系列更新
    18.          if (needs.containsKey(c)) {
    19.              window.put(c, window.getOrDefault(c, 0) + 1);
    20.              if (window.get(c) .equals(needs.get(c)) )
    21.                  valid++;
    22.          }
    23.          // 判断左侧窗口是否要收缩
    24.          while (valid == needs.size()) {
    25.              // 在这里更新最小覆盖子串
    26.              if (right - left < len) {
    27.                  len = right - left;
    28.                  start = left;
    29.              }
    30.              // d 是将移出窗口的字符
    31.              char d = s.charAt(left);
    32.              // 左移窗口
    33.              left++;
    34.              // 进行窗口内数据的一系列更新
    35.              if (needs.containsKey(d)) {
    36.                  if (window.get(d).equals(needs.get(d)))
    37.                      valid--;
    38.                  window.put(d, window.getOrDefault(d, 0) - 1);
    39.              }
    40.          }
    41.      }
    42.      // 返回最小覆盖子串
    43.      return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    44.  }
    45. }

    567. 字符串的排列

    给定两个字符串 s1 和 s2，写一个函数来判断s2是否包含s1的排列。
    换句话说，第一个字符串的排列之一是第二个字符串的子串。
    示例 1：
    输入: s1 = “ab” s2 = “eidbaooo”
    输出: True
    解释: s2 包含 s1 的排列之一 (“ba”).

    1. class Solution {
    2.  public boolean checkInclusion(String s1, String s2) {
    3.      HashMap<Character,Integer> window=new HashMap<>();
    4.      HashMap<Character,Integer> needs=new HashMap<>();
    5.      for(int i=0;i<s1.length();i++){
    6.          needs.put(s1.charAt(i), needs.getOrDefault(s1.charAt(i), 0)+1);
    7.      }
    8.      int left=0,right=0;
    9.      int valid=0;
    10.      while(right<s2.length()){
    11.          char c=s2.charAt(right);
    12.          right++;
    13.          // 进行窗口内数据的一系列更新
    14.          if(needs.containsKey(c)){
    15.              window.put(c, window.getOrDefault(c, 0)+1);
    16.              if(window.get(c).equals(needs.get(c)))
    17.                  valid++;
    18.          }
    19.          // 判断左侧窗口是否要收缩
    20.          while(right-left>=s1.length()){// 这句写为while(right-left==s1.length()){也可以
    21.              // 在这里判断是否找到了合法的子串
    22.              if(valid==needs.size()){
    23.                  return true;
    24.              }
    25.              char d=s2.charAt(left);
    26.              left++;
    27.              // 进行窗口内数据的一系列更新
    28.              if(needs.containsKey(d)){
    29.                  if(needs.get(d).equals(window.get(d)))
    30.                      valid--;
    31.                  window.put(d, window.getOrDefault(d,0 )-1);
    32.              }
    33.          }
    34.      }
    35.      // 未找到符合条件的子串
    36.      return false;
    37.  }
    38. }

    438. 找到字符串中所有字母异位词

    给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
    字符串只包含小写英文字母，并且字符串 s 和p 的长度都不超过 20100。
    说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 1:
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         List<Integer> res=new ArrayList<>();// 记录结果
  4.         HashMap<Character,Integer> window=new HashMap<>();
  5.         HashMap<Character,Integer> need=new HashMap<>();
  6.         for(int i=0;i<p.length();i++){
  7.             need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0)+1);
  8.         }
  9.         int left=0,right=0,valid=0;
  10.         while(right<s.length()){
  11.             char c=s.charAt(right);
  12.             right++;
  13.              // 进行窗口内数据的一系列更新
  14.             if(need.containsKey(c)){
  15.                 window.put(c, window.getOrDefault(c, 0)+1);
  16.                 if(need.get(c).equals(window.get(c)))
  17.                     valid++;
  18.             }
  19.             // 判断左侧窗口是否要收缩
  20.             while(right-left>=p.length()){
  21.                  // 当窗口符合条件时，把起始索引加入 res
  22.                 if(valid==need.size()){
  23.                     res.add(left);
  24.                 }
  25.                 char d=s.charAt(left);
  26.                 left++;
  27.                  // 进行窗口内数据的一系列更新
  28.                 if(need.containsKey(d)){
  29.                     if(need.get(d).equals(window.get(d)))
  30.                         valid--;
  31.                     window.put(d, window.getOrDefault(d, 0)-1);
  32.                 }
  33.             }
  34.         }
  35.         return res;
  36.     }
  37. }

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

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

  1. class Solution {
  2.    public int lengthOfLongestSubstring(String s) {
  3.         int res=0;// 记录结果
  4.         HashMap<Character,Integer> window=new HashMap<>();
  5.         int left=0,right=0;
  6.         while(right<s.length()){
  7.             char c=s.charAt(right);
  8.             right++;
  9.             //进行窗口内数据的一系列更新
  10.             window.put(c, window.getOrDefault(c, 0)+1);
  11.             // 判断左侧窗口是否要收缩
  12.             while (window.get(c)>1){
  13.                 char d=s.charAt(left);
  14.                 left++;
  15.                 // 进行窗口内数据的一系列更新
  16.                 window.put(d, window.getOrDefault(d, 0)-1);
  17.             }
  18.              // 在这里更新答案
  19.             res=Math.max(res, (right-left));
  20.         }
  21.         return res;
  22.     }
  23. }

四、BFS算法框架

111. 二叉树的最小深度

LeetCode题目 - 图24
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null)
  4.             return 0;
  5.         LinkedList<TreeNode> queue=new LinkedList<>();
  6.         queue.offerLast(root);
  7.         int res=1;//root 本身就是一层，depth 初始化为 1
  8.         while(!queue.isEmpty()){
  9.             //将当前队列中的所有节点向四周扩散
  10.             for(int i=queue.size();i>0;i--){
  11.                 TreeNode node = queue.pollFirst();
  12.                 //判断是否到达终点
  13.                 if(node.left==null&&node.right==null)
  14.                     return res;
  15.                 //将 cur 的相邻节点加入队列
  16.                 if(node.left!=null)
  17.                     queue.add(node.left);
  18.                 if(node.right!=null)
  19.                     queue.add(node.right);
  20.             }
  21.             //这里增加步数
  22.             res++;
  23.         }
  24.         return res;
  25.     }
  26. }

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：’0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’。每个拨轮可以自由旋转：例如把’9’变为 ‘0’，’0’变为’9’。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为’0000’，一个代表四个拨轮的数字的字符串。
列表deadends包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串target代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例 1:
输入：deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
输出：6
解释：
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，
因为当拨动到 “0102” 时这个锁就会被锁定。

  1. class Solution {
  2.    String plusOne(String s,int i){//往上拨
  3.         char[] ch = s.toCharArray();
  4.         if(ch[i]=='9'){
  5.             ch[i]='0';
  6.         }else{
  7.             ch[i]+=1;
  8.         }
  9.         return new String(ch);
  10.     }
  11.     String minusOne(String s,int i){//往下拨
  12.         char[] ch = s.toCharArray();
  13.         if(ch[i]=='0'){
  14.             ch[i]='9';
  15.         }else{
  16.             ch[i]-=1;
  17.         }
  18.         return new String(ch);
  19.     }
  20.     public int openLock(String[] deadends, String target) {
  21.         // 记录已经穷举过的密码，防止走回头路
  22.         HashSet<String> visited=new HashSet<>();
  23.         // 记录需要跳过的死亡密码
  24.         HashSet<String> deads=new HashSet<>();
  25.         for(String dead:deadends)
  26.             deads.add(dead);
  27.         LinkedList<String> queue=new LinkedList<>();
  28.         queue.offerLast("0000");
  29.         visited.add("0000");
  30.         // 从起点开始启动广度优先搜索
  31.         int step=0;
  32.         while(!queue.isEmpty()){
  33.             int size=queue.size();
  34.             //将当前队列中的所有节点向周围扩散
  35.             for(int i=0;i<size;i++){
  36.                 String cur = queue.pollFirst();
  37.                 //判断是否到达终点
  38.                 if(deads.contains(cur))
  39.                     continue;
  40.                 if(cur.equals(target))
  41.                     return step;
  42.                 //将一个节点的未遍历相邻节点加入队列
  43.                 for(int j=0;j<4;j++){
  44.                     String up=plusOne(cur, j);
  45.                     if(!visited.contains(up)){
  46.                         queue.offerLast(up);
  47.                         visited.add(up);
  48.                     }
  49.                     String down=minusOne(cur, j);
  50.                     if(!visited.contains(down)){
  51.                         queue.offerLast(down);
  52.                         visited.add(down);
  53.                     }
  54.                 }
  55.             }
  56.             //在这里增加步数
  57.             step++;
  58.         }
  59.        //如果穷举完都没找到目标密码，那就是找不到了
  60.         return -1;
  61.     }
  62. }

773. 滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字1~5来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
提示：

  1. class Solution {
  2.     public int slidingPuzzle(int[][] board) {
  3.         int m=2,n=3;
  4.         String start="";
  5.         String target="123450";
  6.         // 将 2x3 的数组转化成字符串
  7.         for(int i=0;i<m;i++){
  8.             for(int j=0;j<n;j++){
  9.                 start=start.concat(board[i][j]+"");
  10.             }
  11.         }
  12.           // 记录一维字符串的相邻索引
  13.         int[][] neighbor={
  14.                 {1,3},
  15.                 {0,2,4},
  16.                 {1,5},
  17.                 {0,4},
  18.                 {1,3,5},
  19.                 {2,4}
  20.         };
  21.         LinkedList<String> queue=new LinkedList<>();
  22.         queue.offerLast(start);
  23.         HashSet<String> visited=new HashSet<>();
  24.         visited.add(start);
  25.         int step=0;
  26.         while(!queue.isEmpty()){
  27.             int size=queue.size();
  28.             for(int i=0;i<size;i++){
  29.                 String cur = queue.pollFirst();
  30.                 // 判断是否达到目标局面
  31.                 if(cur.equals(target))
  32.                     return step;
  33.                 int index0=0;//找出当前0的位置
  34.                 for(;cur.charAt(index0)!='0';index0++);
  35.                 // 将数字 0 和相邻的数字交换位置
  36.                 for(int j=0;j<neighbor[index0].length;j++){
  37.                     String newCur=swap(cur,index0,neighbor[index0][j]);
  38.                       // 防止走回头路
  39.                     if(!visited.contains(newCur)){
  40.                         queue.offerLast(newCur);
  41.                         visited.add(newCur);
  42.                     }
  43.                 }
  44.             }
  45.             step++;
  46.         }
  47.         return -1;
  48.     }
  49.     private String swap(String cur, int i, int j) {
  50.         char[] ch = cur.toCharArray();
  51.         char temp=ch[i];
  52.         ch[i]=ch[j];
  53.         ch[j]=temp;
  54.         return new String(ch);
  55.     }
  56. }

五、区间相关问题

1288. 删除被覆盖区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b)被区间 [c,d)覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。
示例：
输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

  1. //labuladong完整版
  2. class Solution {
  3.     public int removeCoveredIntervals(int[][] intervals) {
  4.         // 按照起点升序排列，起点相同时降序排列
  5.         Arrays.sort(intervals, (a, b) -> {
  6.             if (a[0] == b[0]) {
  7.                 return b[1] - a[1];
  8.             }
  9.             return a[0] - b[0];
  10.         });
  11.         // 记录合并区间的起点和终点
  12.         int left = intervals[0][0];
  13.         int right = intervals[0][1];
  14.         int res = 0;
  15.         for (int i = 1; i < intervals.length; i++) {
  16.             int[] intv = intervals[i];
  17.             // 情况一，找到覆盖区间
  18.             if (left <= intv[0] && right >= intv[1]) {
  19.                 res++;
  20.             }
  21.             // 情况二，找到相交区间，合并
  22.             if (right >= intv[0] && right <= intv[1]) {
  23.                 right = intv[1];
  24.             }
  25.             // 情况三，完全不相交，更新起点和终点
  26.             if (right < intv[0]) {
  27.                 left = intv[0];
  28.                 right = intv[1];
  29.             }
  30.         }
  31.         return intervals.length - res;
  32.     }
  33. }
  34. //我的简化版本
  35. class Solution {
  36.    public int removeCoveredIntervals(int[][] intervals) {
  37.        // 按照起点升序排列，起点相同时降序排列
  38.         Arrays.sort(intervals, (a,b)->{
  39.                 if(a[0]==b[0]){
  40.                     return b[1]-a[1];
  41.                 }
  42.                 return a[0]-b[0];
  43.          });
  44.          // 记录合并区间的起点和终点
  45.         int left=intervals[0][0];
  46.         int right=intervals[0][1];
  47.         int res=0;
  48.         for(int i=1;i<intervals.length;i++){
  49.             int[] intv=intervals[i];
  50.             if(left<=intv[0]&&right>=intv[1]){ // 情况一，找到覆盖区间
  51.                 res++;
  52.             }else{//合并其余情况
  53.                 // 情况二，找到相交区间，合并
  54.                  // 情况三，完全不相交，更新起点和终点
  55.                 left=intv[0];
  56.                 right=intv[1];
  57.             }
  58.         }
  59.         return intervals.length-res;
  60.     }
  61. }

56. 合并区间

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         if(intervals.length==0)
  4.             return new int[0][];
  5.         //按区间的 start 升序排列
  6.         Arrays.sort(intervals,(a,b)->a[0]-b[0]);
  7.         List<int[]> res=new ArrayList<>();
  8.         res.add(intervals[0]);
  9.         for(int i=1;i<intervals.length;i++){
  10.             int[] cur=intervals[i];
  11.             //res 中最后一个元素的引用来比较
  12.             if(cur[0]<=res.get(res.size()-1)[1])
  13.                 res.get(res.size()-1)[1]=Math.max(res.get(res.size()-1)[1],cur[1]);
  14.             else
  15.                 //直接添加进结果，作为下一个待合并区间
  16.                 res.add(cur);
  17.         }
  18.         return res.toArray(new int[res.size()][]);
  19.     }
  20. }

986. 区间列表的交集

LeetCode题目 - 图25
给定两个由一些闭区间组成的列表，firstList和secondList，其中firstList[i] = [starti, endi]而 secondList[j] = [startj, endj]。每个区间列表都是成对不相交的，并且已经排序。
返回这两个区间列表的交集。
形式上，闭区间[a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。
两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3]和[2, 4]的交集为[2, 3]。
示例 1：
输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

  1. class Solution {
  2.     public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
  3.         List<int[]> res=new ArrayList<>();
  4.         int i=0,j=0;
  5.         while(i<firstList.length&&j<secondList.length){
  6.             //取出两端区间的端点
  7.             int a1=firstList[i][0],a2=firstList[i][1];
  8.             int b1=secondList[j][0],b2=secondList[j][1];
  9.             //算出交集，加入 res
  10.             if(a2>=b1&&b2>=a1){
  11.                 int[] temp=new int[]{Math.max(a1,b1),Math.min(a2,b2)};
  12.                 res.add(temp);
  13.             }
  14.             //i与j进行递增的时机
  15.             int test=(b2<a2)?j++:i++;
  16.         }
  17.     return res.toArray(new int[res.size()][]);
  18.     }
  19. }

六、单调栈

496. 下一个更大元素 I

给你两个没有重复元素的数组 nums1和 nums2 ，其中nums1 是 nums2 的子集。
请你找出nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x大的元素。如果不存在，对应位置输出-1。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

  1. class Solution {
  2.     public int[] nextGreaterElement(int[] nums1, int[] nums2) {
  3.         HashMap<Integer,Integer> map=new HashMap<>();
  4.         Stack<Integer> s=new Stack<>();
  5.         // 倒着往栈里放
  6.         for(int i=nums2.length-1;i>=0;i--){
  7.             // 判定个子高矮
  8.             while(!s.isEmpty()&&s.peek()<=nums2[i]){
  9.                  // 矮个起开，反正也被挡着了。。。
  10.                 s.pop();
  11.             }
  12.             // nums[i] 身后的 next great number
  13.             map.put(nums2[i],s.isEmpty()?-1:s.peek());
  14.             s.push(nums2[i]);
  15.         }
  16.         int[] res=new int[nums1.length];
  17.         for(int i=0;i<nums1.length;i++){
  18.             res[i]=map.getOrDefault(nums1[i],-1);
  19.         }
  20.         return res;
  21.     }
  22. }

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

  1. class Solution {
  2.     public int[] nextGreaterElements(int[] nums) {
  3.         Stack<Integer> s=new Stack<>();
  4.         int n=nums.length;
  5.         int[] res=new int[n];
  6.         //把这个循环数组「拉直」(复制该序列的前 n 个元素拼接在原序列的后面。)
  7.         //求得最后一个元素后的 next great number
  8.         for(int i=2*n-1;i>=0;i--){
  9.             while(!s.isEmpty()&&s.peek()<=nums[i%n]){
  10.                 s.pop();
  11.             }
  12.             res[i%n]=s.isEmpty()?-1:s.peek();
  13.             s.push(nums[i%n]);
  14.         }
  15.         return res;
  16.     }
  17. }

556. 下一个更大元素 III

给你一个正整数 n，请你找出符合条件的最小整数，其由重新排列n中存在的每位数字组成，并且其值大于n。如果不存在这样的正整数，则返回-1。
注意，返回的整数应当是一个32 位整数，如果存在满足题意的答案，但不是32 位整数，同样返回-1。
示例 1：
输入：n = 12
输出：21

739. 每日温度

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

  1. class Solution {
  2.     public int[] dailyTemperatures(int[] temperatures) {
  3.         // 这里放元素索引，而不是元素
  4.         Stack<Integer> s=new Stack<>();
  5.         int[] res=new int[temperatures.length];
  6.         for(int i=res.length-1;i>=0;i--){
  7.             while(!s.isEmpty()&&temperatures[s.peek()]<=temperatures[i]){
  8.                 s.pop();
  9.             }
  10.              // 得到索引间距
  11.             res[i]=s.isEmpty()?0:(s.peek()-i);
  12.             // 将索引入栈，而不是元素
  13.             s.push(i);
  14.         }
  15.         return res;
  16.     }
  17. }

七、随机读取元素相关

380. 常数时间插入、删除和获取随机元素

设计一个支持在平均 时间复杂度O(1) 下，执行以下操作的数据结构。

  1. insert(val)：当元素 val 不存在时，向集合中插入该项。
  2. remove(val)：元素 val 存在时，从集合中移除该项。

  3. getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

    1. class RandomizedSet {
    2.  HashMap<Integer,Integer> map; // 记录每个元素对应在 map 中的索引
    3.  List<Integer> nums; // 存储元素的值
    4.  Random rand;//获取随机数
    5.  public RandomizedSet() {
    6.      map=new HashMap<>();
    7.      nums=new ArrayList<>();
    8.      rand=new Random();
    9.  }
    10.  public boolean insert(int val) {
    11.      if(map.containsKey(val)){// 若 val 已存在，不用再插入
    12.          return false;
    13.      }
    14.      map.put(val,nums.size()); // 记录 val 对应的索引值
    15.      nums.add(val);// 若 val 不存在，插入到 nums 尾部，
    16.      return true;
    17.  }
    18.  public boolean remove(int val) {
    19.      if(!map.containsKey(val)){ // 若 val 不存在，不用再删除
    20.          return false;
    21.      }
    22.      int index=map.get(val); // 先拿到 val 的索引
    23.      int lastNum=nums.get(nums.size()-1);
    24.      nums.set(index,lastNum);// 将最后一个元素放到索引index的位置处
    25.      nums.remove(nums.size()-1);// 在数组中删除最后一个元素
    26.      map.put(lastNum,index);//记得修改哈希表的索引值
    27.      map.remove(val);// 删除元素 val 对应的索引
    28.      return true;
    29.  }
    30.  public int getRandom() {
    31.      return nums.get(rand.nextInt(nums.size()));
    32.  }
    33. }

    381. O(1) 时间插入、删除和获取随机元素 - 允许重复

    设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。
    注意: 允许出现重复元素。

  4. insert(val)：向集合中插入元素 val。

  5. remove(val)：当 val 存在时，从集合中移除一个 val。

  6. getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

    1. class RandomizedCollection {
    2.  HashMap<Integer,HashSet<Integer>> map;
    3.  Random rand;
    4.  List<Integer> nums;//可以存放重复元素
    5.  public RandomizedCollection() {
    6.      map=new HashMap<>();
    7.      nums=new ArrayList<>();
    8.      rand=new Random();
    9.  }
    10.  public boolean insert(int val) {
    11.      nums.add(val);
    12.      HashSet<Integer> set=map.getOrDefault(val,new HashSet<>());
    13.      set.add(nums.size()-1);//存入当前val所在的角标
    14.      map.put(val,set);//把val及其对应的角标集合放进map中，方便查找
    15.      return set.size()==1;
    16.  }
    17.  public boolean remove(int val) {
    18.      if(!map.containsKey(val)){
    19.          return false;
    20.      }
    21.      //先获取到val对应的脚标集合
    22.      HashSet<Integer> set=map.get(val);
    23.      Iterator<Integer> it=set.iterator();
    24.      //取出Set集合中遍历到的第一个角标并移除
    25.      int index=it.next();
    26.      set.remove(index);
    27.      //取到nums列表里的最后一个元素,并从移除
    28.      int lastNum=nums.get(nums.size()-1);
    29.      map.get(lastNum).remove(nums.size()-1);
    30.      //交换最后一个元素，其实就是单方面的覆盖
    31.      nums.set(index,lastNum);
    32.      //这里保证如果删除的是最后一个，则不再把角标添加进去
    33.      if(index<nums.size()-1){
    34.          map.get(lastNum).add(index);
    35.      }
    36.      //如果某个数对应的角标已经没有了，删除key
    37.      if(set.size()==0){
    38.          map.remove(val); 
    39.      }
    40.      nums.remove(nums.size()-1);
    41.      return true;
    42.  }
    43.  public int getRandom() {
    44.      return nums.get(rand.nextInt(nums.size()));
    45.  }
    46. }

    710. 黑名单中的随机数

    给定一个包含[0，n)中不重复整数的黑名单blacklist，写一个函数从[0, n)中返回一个不在blacklist中的随机整数。
    对它进行优化使其尽量少调用系统方法Math.random()。
    提示:

  7. 1 <= n <= 1000000000

  8. 0 <= blacklist.length < min(100000, N)
  9. [0, n) 不包含n，详细参见 interval notation) 。

示例 1：
输入：
[“Solution”,”pick”,”pick”,”pick”]
[[1,[]],[],[],[]]
输出：[null,0,0,0]

  1. class Solution {
  2.     Random rand;
  3.     int sz;
  4.     HashMap<Integer,Integer> map;
  5.     public Solution(int n, int[] blacklist) {
  6.         rand=new Random();
  7.         sz=n-blacklist.length;
  8.         map=new HashMap<>();
  9.         for(int black:blacklist){
  10.             map.put(black,666);
  11.         }
  12.         int last=n-1;
  13.         for(int black:blacklist){
  14.             if(black>=sz)
  15.                 continue;
  16.             while(map.containsKey(last)){
  17.                 last--;
  18.             }
  19.             map.put(black,last);
  20.             last--;
  21.         }
  22.     }
  23.     public int pick() {
  24.         int num=rand.nextInt(sz);
  25.         if(map.containsKey(num)){
  26.             return map.get(num);
  27.         }
  28.         return num;
  29.     }
  30. }

382. 链表随机节点

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

  1. class Solution {
  2.     ListNode head;
  3.     public Solution(ListNode head) {
  4.         this.head=head;
  5.     }
  6.     public int getRandom() {
  7.         Random rand=new Random();
  8.         ListNode temp=head;
  9.         int i=0;
  10.         int res=0;
  11.         // while 循环遍历链表
  12.         while(temp!=null){
  13.             // 生成一个 [0, i) 之间的整数,这个整数等于 0 的概率就是 1/i
  14.             if(rand.nextInt(++i)==0){
  15.                 res=temp.val;
  16.             }
  17.             temp=temp.next;
  18.         }
  19.         return res;
  20.     }
  21. }

382. 链表随机节点(拓展)

如果要随机选择k个数，只要在第i个元素处以k/i的概率选择该元素，以1 - k/i的概率保持原有选择即可。
代码如下：

  1. class Solution{
  2.      public int[] getRandom(ListNode head, int k) {
  3.         Random r = new Random();
  4.         int[] res = new int[k];
  5.         ListNode p = head;
  6.         // 前 k 个元素先默认选上
  7.         for (int j = 0; j < k && p != null; j++) {
  8.             res[j] = p.val;
  9.             p = p.next;
  10.         }
  11.         int i = k;
  12.         // while 循环遍历链表
  13.         while (p != null) {
  14.             // 生成一个 [0, i) 之间的整数
  15.             int j = r.nextInt(++i);
  16.             // 这个整数小于 k 的概率就是 k/i
  17.             if (j < k) {
  18.                 res[j] = p.val;
  19.             }
  20.             p = p.next;
  21.         }
  22.         return res;
  23.     }
  24. }

398. 随机数索引

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

  1. class Solution {
  2.     int[] nums;
  3.     public Solution(int[] nums) {
  4.         this.nums=nums;
  5.     }
  6.     public int pick(int target) {
  7.         Random rand=new Random();
  8.         int res=0;
  9.         int count=0;
  10.         //遍历这个数组
  11.         for(int i=0;i<nums.length;i++){
  12.             //一旦目标数有多个，则要让它取到每个索引值的概率相等
  13.             if(nums[i]==target){
  14.                 count++;
  15.                 if(rand.nextInt(count)==0){
  16.                     res=i;
  17.                 }
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. }

384. 打乱数组

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

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

示例：
输入
[“Solution”, “shuffle”, “reset”, “shuffle”]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

  1. class Solution {
  2.     int[] nums;
  3.     int[] temp;
  4.     Random rand;
  5.     int n;
  6.     public Solution(int[] nums) {
  7.         this.nums=nums;
  8.         n=nums.length;
  9.         this.temp=nums.clone();
  10.         rand=new Random();
  11.     }
  12.     public int[] reset() {
  13.         nums=temp;
  14.         temp=temp.clone();
  15.         return temp;
  16.     }
  17.     public int[] shuffle() {
  18.         for(int i=0;i<n;i++){
  19.             int index=rand.nextInt(n-i)+i;//生成i到n范围内的随机数
  20.             swap(i,index);
  21.         }
  22.         return nums;
  23.     }
  24.     private void swap(int i,int j){
  25.         int temp=nums[i];
  26.         nums[i]=nums[j];
  27.         nums[j]=temp;
  28.     }
  29. }