00算法

算法

hash

两数之和

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

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

字母异位词分组

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

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [“”]

输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

public List<List<String>> groupAnagrams(String[] strs) {
  Map<String, List<String>> map = new HashMap<>();

  for (String str : strs) {
    char[] keyArray = str.toCharArray();
    Arrays.sort(keyArray);
    String key = new String(keyArray);
    List<String> value = map.getOrDefault(key, new ArrayList<>());
    value.add(str);
    map.put(key,value);
  }

  return map.values().stream().toList();
}

最长连续序列

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

public int longestConsecutive(int[] nums) {
  Set<Integer> num_set = new HashSet<Integer>();
  for (int num : nums) {
    num_set.add(num);
  }

  int longestStreak = 0;

  for (int num : num_set) {
    if (!num_set.contains(num - 1)) {
      int currentNum = num;
      int currentStreak = 1;

      while (num_set.contains(currentNum + 1)) {
        currentNum += 1;
        currentStreak += 1;
      }

      longestStreak = Math.max(longestStreak, currentStreak);
    }
  }

  return longestStreak;
}

双指针

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

public List<List<Integer>> threeSum(int[] nums) {
  Arrays.sort(nums); // 先排序
  List<List<Integer>> res = new ArrayList<>();

  for (int i = 0; i < nums.length; i++) {
    // 跳过重复元素
    if (i > 0 && nums[i] == nums[i - 1]) continue;

    // 双指针，目标是找到 nums[l] + nums[r] = -nums[i]
    int l = i + 1, r = nums.length - 1;
    int target = -nums[i];

    while (l < r) {
      int sum = nums[l] + nums[r];
      if (sum == target) {
        res.add(Arrays.asList(nums[i], nums[l], nums[r]));
        l++;
        r--;
        // 跳过重复元素
        while (l < r && nums[l] == nums[l - 1]) l++;
        while (l < r && nums[r] == nums[r + 1]) r--;
      } else if (sum < target) {
        l++;
      } else {
        r--;
      }
    }
  }

  return res;

}

移动零

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

// left 左边为非0
// left ~ i 全是0
public void moveZeroes(int[] nums) {
  int left = 0;
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] != 0) {
      if (i == left) {
        left++;
        continue;
      }
      int temp = nums[left];
      nums[left] = nums[i];
      nums[i] = temp;
      left++;
    }
  }
}

盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

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

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

public int trap(int[] height) {
  int ans = 0;
  int left = 0, right = height.length - 1;
  int leftMax = 0, rightMax = 0;
  while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    if (height[left] < height[right]) {
      ans += leftMax - height[left];
      ++left;
    } else {
      ans += rightMax - height[right];
      --right;
    }
  }
  return ans;
}

滑动窗口

无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

public int lengthOfLongestSubstring(String s) {
  int max = 0;
  Queue<Character> queue = new LinkedList<>();

  char[] charArray = s.toCharArray();
  for (int i = 0; i < charArray.length; i++) {
    while (queue.contains(charArray[i])){
      queue.poll();
    }
    queue.offer(charArray[i]);
    max = Math.max(max,queue.size());
  }
  return max;

}

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

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

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

public List<Integer> findAnagrams(String s, String p) {
  List<Integer> res = new ArrayList<>();
  if(s.length()<p.length()){
    return new ArrayList<>();
  }
  int[] sCount = new int[26];
  int[] pCount = new int[26];
  for (int i = 0; i < p.length(); i++) {
    ++sCount[s.charAt(i)-'a'];
    ++pCount[p.charAt(i)-'a'];
  }


  if(Arrays.equals(sCount,pCount)){
    res.add(0);
  }

  for (int i = 0; i < s.length()-p.length(); i++) {
    --sCount[s.charAt(i)-'a'];
    ++sCount[s.charAt(i+p.length())-'a'];

    if(Arrays.equals(sCount,pCount)){
      res.add(i+1);
    }
  }
  return res;

}

子串

和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

public int subarraySum(int[] nums, int k) {
       int res = 0;
       int pre = 0;
       Map<Integer, Integer> map = new HashMap<>();
       map.put(0, 1);
       for (int num : nums) {
           pre += num;
           if (map.containsKey(pre - k)) {
               res += map.get(pre - k);
           }
           map.put(pre, map.getOrDefault(pre, 0) + 1);
       }
       return res;
   }

考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标 j 的个数，其中 0≤j≤i 且 [j..i] 这个子数组的和恰好为 k 。

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

public int[] maxSlidingWindow(int[] nums, int k) {
  int n = nums.length;
  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);

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

  int[] ans = new int[n - k + 1];
  ans[0] = pq.peek()[0];
  for (int i = k; i < n; i++) {
    pq.offer(new int[]{nums[i], i});
    while (pq.peek()[1] <= i - k) {
      pq.poll();
    }
    ans[i - k + 1] = pq.peek()[0];
  }
  return ans;
}

public int[] maxSlidingWindow(int[] nums, int k) {
  int n = nums.length;
  Deque<Integer> deque = new LinkedList<>();

  for (int i = 0; i < k; i++) {
    while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
      deque.pollLast();
    }
    deque.offerLast(i);
  }

  int[] ans = new int[n - k + 1];
  ans[0] = nums[deque.peekFirst()];

  for (int i = k; i < n; i++) {
    while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
      deque.pollLast();
    }
    deque.offerLast(i);
    while (deque.peek() <= i - k) {
      deque.pollFirst();
    }
    ans[i - k + 1] = nums[deque.peek()];
  }
  return ans;

}

最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

public String minWindow(String s, String t) {
  Map<Character,Integer> need = new HashMap<>();
  Map<Character,Integer> window = new HashMap<>();

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

  int left = 0, right = 0;
  int valid = 0;
  int start = 0, len = Integer.MAX_VALUE;

  while(right < s.length()){

    char c = s.charAt(right);
    right++;

    if(need.containsKey(c)){
      window.put(c, window.getOrDefault(c,0)+1);

      if(window.get(c).equals(need.get(c))){
        valid++;
      }
    }

    while(valid == need.size()){

      if(right - left < len){
        start = left;
        len = right - left;
      }

      char d = s.charAt(left);
      left++;

      if(need.containsKey(d)){
        if(window.get(d).equals(need.get(d))){
          valid--;
        }
        window.put(d, window.get(d)-1);
      }
    }
  }

  return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
}

普通数组

最大子数组和

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

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

public int maxSubArray(int[] nums) {
  int pre = 0;
  int maxAns = nums[0];
  for (int num : nums) {
    pre = Math.max(pre+num,num);
    maxAns = Math.max(pre,maxAns);
  }
  return maxAns;
}

合并区间

以数组 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].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

public int[][] merge(int[][] intervals) {
  Arrays.sort(intervals,(a,b)-> a[0]- b[0]);
  List<int[]> res = new ArrayList<>();
  int left = intervals[0][0];
  int right = intervals[0][1];
  for (int[] interval : intervals) {
    if(interval[0]>right){
      res.add(new int[]{left,right});
      left = interval[0];
      right = interval[1];
    }
    if(interval[1]>right){
      right = interval[1];
    }
  }
  res.add(new int[]{left,right});
  return res.toArray(new int[][]{});
}

除了自身以外数组乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位 整数范围内

public int[] productExceptSelf(int[] nums) {
  int[] ans = new int[nums.length];
  Arrays.fill(ans, 1);
  int l = 0;
  int lp = 1; //左边的乘积
  int rp = 1; //右边的乘积
  while (l < nums.length) {
    int r = nums.length - l - 1;
    ans[l] = lp * ans[l];
    ans[r] = rp * ans[r];
    lp = lp * nums[l];
    rp = rp * nums[r];
    l++;
  }
  return ans;
}

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数

• 将数组中所有小于等于 0 的数修改为 N+1；

• 遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；

• 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1

public int firstMissingPositive(int[] nums) {
  int n = nums.length;
  for (int i = 0; i < n; ++i) {
    if (nums[i] <= 0) {
      nums[i] = n + 1;
    }
  }
  for (int i = 0; i < n; ++i) {
    int num = Math.abs(nums[i]);
    if (num <= n) {
      nums[num - 1] = -Math.abs(nums[num - 1]);
    }
  }
  for (int i = 0; i < n; ++i) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  return n + 1;
}

矩阵

矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。

在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

public void setZeroes(int[][] matrix) {
  int m = matrix.length;
  int n = matrix[0].length;

  boolean firstRowZero = false;
  boolean firstColZero = false;

  for (int i = 0; i < m; i++) {
    if (matrix[i][0] == 0) {
      firstColZero = true;
      break;
    }
  }

  for (int i = 0; i < n; i++) {
    if (matrix[0][i] == 0) {
      firstRowZero = true;
      break;
    }
  }


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

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

  if (firstRowZero) {
    for (int i = 0; i < n; i++) {
      matrix[0][i] = 0;
    }
  }
  
  if (firstColZero) {
    for (int i = 0; i < m; i++) {
      matrix[i][0] = 0;
    }
  }

}

旋转矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

public List<Integer> spiralOrder(int[][] matrix) {
  int m = matrix.length;
  int n = matrix[0].length;
  int left = 0;
  int right = n-1;
  int top = 0;
  int down = m-1;
  int size = m*n;

  List<Integer> res = new ArrayList<>(size);

  while (true){
    for (int i = left; i <= right ; i++) {
      res.add(matrix[top][i]);
    }
    top++;
    if(res.size()==size) return res;

    for (int i = top; i <= down  ; i++) {
      res.add(matrix[i][right]);
    }
    right--;
    if(res.size()==size) return res;

    for (int i = right; i >=left; i--) {
      res.add(matrix[down][i]);
    }
    down--;
    if(res.size()==size) return res;

    for (int i = down; i >= top ; i--) {
      res.add(matrix[i][left]);
    }
    left++;
    if(res.size()==size) return res;

  }


}

旋转图像

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

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

旋转

循环的范围

偶数

奇数

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

水平+对角翻转

public void rotate1(int[][] matrix) {
  int n = matrix.length;
  // 水平翻转
  for (int i = 0; i < n / 2; ++i) {
    for (int j = 0; j < n; ++j) {
      int temp = matrix[i][j];
      matrix[i][j] = matrix[n - i - 1][j];
      matrix[n - i - 1][j] = temp;
    }
  }
  // 主对角线翻转
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      int temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
}

搜索二维矩阵

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

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

链表

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
    val = x;
    next = null;
  }
}

ListNode pa = headA;
ListNode pb = headB;
while (pa!=pb){
  pa = pa==null? headB:pa.next;
  pb = pb==null? headA:pb.next;
}
return pa;

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public ListNode reverseList(ListNode head) {
  ListNode pre = null;
  ListNode current = head;
  while (current != null) {
    ListNode next = current.next;
    current.next = pre;
    pre = current;
    current = next;

  }
  return pre;
}

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

ListNode font;

public boolean isPalindrome(ListNode head) {
  font = head;
  return isPalindromeRecur(head);
}

private boolean isPalindromeRecur(ListNode node){
  if(node==null){
    return true;
  }
  if(!isPalindromeRecur(node.next)){
    return false;
  }
  if(node.val != font.val){
    return false;
  }
  font = font.next;
  return true;
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

class ListNode {
  int val;
  ListNode next;

  ListNode(int x) {
    val = x;
    next = null;
  }
}

public boolean hasCycle(ListNode head) {
  if(head ==null || head.next == null){
    return false;
  }
  // 将pos -1 作为起点
  // 跳一步后  slow = haed  fast = head.next
  ListNode slow = head;
  ListNode fast = head.next;
  while (slow!=fast){
    if(slow.next==null){
      return false;
    }
    if(fast.next==null || fast.next.next==null){
      return false;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
}

环形链表2

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

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

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

class ListNode {
  int val;
  ListNode next;

  ListNode(int x) {
    val = x;
    next = null;
  }
}

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

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

    }
  }
}

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

public class ListNode {
  int val;
  ListNode next;

  ListNode() {
  }

  ListNode(int val) {
    this.val = val;
  }

  ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  if (list1 == null) {
    return list2;
  }
  if (list2 == null) {
    return list1;
  }

  ListNode p = new ListNode();
  ListNode head = p;
  ListNode p1 = list1;
  ListNode p2 = list2;

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

  if (p2!=null){
    p.next = p2;
  }
  return head.next;
}

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

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

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  ListNode p1 = l1;
  ListNode p2 = l2;
  int plus1 = 0;
  ListNode head = new ListNode();
  ListNode p3 = head;
  while (p1!=null || p2!=null){
    int v1 = 0;
    int v2 = 0;
    if(p1!=null){
      v1 = p1.val;
      p1 = p1.next;
    }
    if(p2!=null){
      v2 = p2.val;
      p2 = p2.next;
    }

    int tmp = v1+ v2+plus1;

    plus1 = tmp/10;
    p3.next = new ListNode(tmp%10);
    p3 = p3.next;
  }
  if(plus1>0){
    p3.next = new ListNode(plus1);
  }
  return head.next;
}

删除链表的倒数第n个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

public class ListNode {
  int val;
  ListNode next;

  ListNode() {
  }

  ListNode(int val) {
    this.val = val;
  }

  ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

public ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode dummy = new ListNode(0,head);
  ListNode first = head;
  ListNode second = dummy;
  for (int i = 0; i < n; i++) {
    first = first.next;
  }

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

  second.next = second.next.next;
  return dummy.next;

}

二叉树

中序遍历

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  recur(root,res);
  return res;
}

private void recur(TreeNode node,List<Integer> res){
  if(node==null){
    return;
  }
  recur(node.left,res);
  res.add(node.val);
  recur(node.right,res);
}

最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public int maxDepth(TreeNode root) {
  if(root ==null){
    return 0;
  }
  return  Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

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

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode() {
  }

  TreeNode(int val) {
    this.val = val;
  }

  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public boolean isSymmetric(TreeNode root) {
  return recur(root.left, root.right);
}

private boolean recur(TreeNode left, TreeNode right) {
  if (left == null && right == null) {
    return true;
  }
  if (left == null || right == null) {
    return false;
  }

  if (left.val != right.val) {
    return false;
  }
  return recur(left.left, right.right)
    && recur(left.right, right.left);


}

二叉树直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示：

• 树中节点数目在范围 [1, 104] 内
• -100 <= Node.val <= 100

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
  depth(root);
  return max;
}

private int depth(TreeNode root){
  if(root == null) return 0;

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

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

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

二叉树层序遍历

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode() {
  }

  TreeNode(int val) {
    this.val = val;
  }

  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    List<Integer> line = new ArrayList<>();
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      TreeNode poll = queue.poll();
      line.add(poll.val);
      if (poll.left != null) {
        queue.offer(poll.left);
      }
      if (poll.right != null) {
        queue.offer(poll.right);
      }
    }
    res.add(line);
  }
  return res;
}

有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public TreeNode sortedArrayToBST(int[] nums) {
  return recur(nums,0,nums.length-1);
}

private TreeNode recur(int[] arr,int l , int r){
  if(l>r) return null;
  if(l==r){
    return new TreeNode(arr[l]);
  }
  // 0,1,2,3
  int mid = (l+r)/2;
  TreeNode nodeL = recur(arr, l, mid-1);
  TreeNode nodeR = recur(arr, mid + 1, r);
  return new TreeNode(arr[mid],nodeL,nodeR);
}

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public boolean isValidBST(TreeNode root) {
  return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode node, long lower, long upper) {
  if (node == null) {
    return true;
  }
  if (node.val <= lower || node.val >= upper) {
    return false;
  }
  return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}

二叉搜索树中第k小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

• 树中的节点数为 n 。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

int visited = 0;
int res = -1;
boolean find = false;

public int kthSmallest(TreeNode node, int k) {
  if (node == null || find) {
    return res;
  }

  kthSmallest(node.left, k);
  visited++;
  if (visited == k) {
    res = node.val;
    find = true;
  }
  kthSmallest(node.right, k);
  return res;
}

public int kthSmallest(TreeNode root, int k) {
  Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  while (root != null || !stack.isEmpty()) {
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    --k;
    if (k == 0) {
      break;
    }
    root = root.right;
  }
  return root.val;
}

图论

岛屿数量

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

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出：1

示例 2：

输入：grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

void dfs(char[][] grid, int r, int c) {
  int nr = grid.length;
  int nc = grid[0].length;

  if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
    return;
  }

  grid[r][c] = '0';
  dfs(grid, r - 1, c);
  dfs(grid, r + 1, c);
  dfs(grid, r, c - 1);
  dfs(grid, r, c + 1);
}

public int numIslands(char[][] grid) {
  if (grid == null || grid.length == 0) {
    return 0;
  }

  int nr = grid.length;
  int nc = grid[0].length;
  int num_islands = 0;
  for (int r = 0; r < nr; ++r) {
    for (int c = 0; c < nc; ++c) {
      if (grid[r][c] == '1') {
        ++num_islands;
        dfs(grid, r, c);
      }
    }
  }

  return num_islands;
}

public int numIslands(char[][] grid) {
  int m = grid.length;
  int n = grid[0].length;

  int lands = 0;
  Queue<Integer> queue = new LinkedList<>();

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if(grid[i][j]=='1'){
        lands++;
        queue.offer(i*n+j);
        while (!queue.isEmpty()){
          Integer poll = queue.poll();
          int i1 = poll/n;
          int j1 = poll%n;
          grid[i1][j1]='0';
          if(i1-1>=0 && grid[i1-1][j1]=='1'){
            queue.offer((i1-1)*n+j1);
          }
          if(i1+1<m && grid[i1+1][j1]=='1'){
            queue.offer((i1+1)*n+j1);
          }
          if(j1-1>=0 && grid[i1][j1-1]=='1'){
            queue.offer(i1*n+j1-1);
          }
          if(j1+1<n && grid[i1][j1+1]=='1'){
            queue.offer(i1*n+j1+1);
          }
        }
      }
    }
  }
  return lands;
}

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

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

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] 仅为 0、1 或 2

public int orangesRotting(int[][] grid) {
  int m = grid.length;
  int n = grid[0].length;
  int res = 0;
  int orangesCount = 0;
  Queue<Integer> queue = new LinkedList<>();
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (grid[i][j] == 2) {
        queue.add(i * n + j);
      }
      if (grid[i][j] == 1) {
        orangesCount++;
      }
    }
  }

  while (!queue.isEmpty()) {
    int size = queue.size();
    boolean changed = false;
    for (int k = 0; k < size; k++) {
      Integer poll = queue.poll();
      int i1 = poll / n;
      int j1 = poll % n;
      if (i1 - 1 >= 0 && grid[i1 - 1][j1] == 1) {
        grid[i1 - 1][j1] = 2;
        orangesCount--;
        queue.offer((i1 - 1) * n + j1);
        changed = true;
      }
      if (i1 + 1 < m && grid[i1 + 1][j1] == 1) {
        grid[i1 + 1][j1] = 2;
        orangesCount--;
        queue.offer((i1 + 1) * n + j1);
        changed = true;
      }
      if (j1 - 1 >= 0 && grid[i1][j1 - 1] == 1) {
        grid[i1][j1 - 1] = 2;
        orangesCount--;
        queue.offer(i1 * n + j1 - 1);
        changed = true;
      }
      if (j1 + 1 < n && grid[i1][j1 + 1] == 1) {
        grid[i1][j1 + 1] = 2;
        orangesCount--;
        queue.offer(i1 * n + j1 + 1);
        changed = true;
      }

    }
    if (changed) res++;
  }

  return orangesCount == 0 ? res : -1;


}

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

List<List<Integer>> edges;
int[] indeg;

public boolean canFinish(int numCourses, int[][] prerequisites) {
  edges = new ArrayList<List<Integer>>();
  for (int i = 0; i < numCourses; ++i) {
    edges.add(new ArrayList<Integer>());
  }
  indeg = new int[numCourses];
  for (int[] info : prerequisites) {
    edges.get(info[1]).add(info[0]);
    ++indeg[info[0]];
  }

  Queue<Integer> queue = new LinkedList<Integer>();
  for (int i = 0; i < numCourses; ++i) {
    if (indeg[i] == 0) {
      queue.offer(i);
    }
  }

  int visited = 0;
  while (!queue.isEmpty()) {
    ++visited;
    int u = queue.poll();
    for (int v: edges.get(u)) {
      --indeg[v];
      if (indeg[v] == 0) {
        queue.offer(v);
      }
    }
  }

  return visited == numCourses;
}

前缀树

Trie 发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

class Trie {
  private Trie[] child = new Trie[26];
  private boolean isEnd = false;

  public Trie() {

  }

  public void insert(String word) {
    char[] charArray = word.toCharArray();
    Trie current  = this;
    for (int i = 0; i < charArray.length; i++) {
      int i1 = charArray[i] - 'a';
      if(current.child[i1]==null){
        current.child[i1] = new Trie();
      }
      current = current.child[i1];
    }
    current.isEnd=true;
  }

  public boolean search(String word) {
    Trie trie = searchPrefix(word);
    return trie!=null && trie.isEnd;
  }

  public boolean startsWith(String prefix) {
    Trie trie = searchPrefix(prefix);
    return trie!=null;
  }

  private Trie searchPrefix(String prefix){
    char[] charArray = prefix.toCharArray();
    Trie current = this;
    for (int i = 0; i < charArray.length; i++) {
      int i1 = charArray[i] - 'a';
      Trie trie = current.child[i1];
      if(trie==null){
        return null;
      }
      current = trie;
    }
    return current;
  }

}

回溯

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

public List<List<Integer>> permute(int[] nums) {
  List<List<Integer>> res = new ArrayList<>();
  dfs(nums,0,res);
  return res;
}

private void dfs(int[] nums, int index, List<List<Integer>> res){
  if(nums.length-1 == index){
    res.add(Arrays.stream(nums).boxed().toList());
  }
  for (int i = index ; i < nums.length ; i++) {
    swap(nums,index,i);
    dfs(nums,index+1,res);
    swap(nums,i,index);
  }
}


private void swap(int[] nums, int index1,int index2){
  if(index1 == index2){
    return;
  }
  int temp = nums[index1];
  nums[index1] = nums[index2];
  nums[index2] = temp;
}

子集

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

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

List<Integer> t = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();

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


private void dfs(int[] nums, int index) {
  if(index == nums.length){
    res.add(new ArrayList<>(t));
    return;
  }
  // 考虑选择当前位置
  t.add(nums[index]);
  dfs(nums,index+1);
  t.remove(t.size()-1);
  // 考虑不选择当前位置
  dfs(nums,index+1);

}

电话号码的字母组合

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 1 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

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

public List<String> letterCombinations(String digits) {
  ArrayList<String> res = new ArrayList<>();
  dfs(0,digits,new StringBuffer(),res);
  return res;
}

private void dfs(int index,String digits,StringBuffer buffer,List<String> res){
  if(index == digits.length()){
    res.add(buffer.toString());
    return;
  }

  char k = digits.charAt(index);
  String s = map.get(k);
  char[] charArray = s.toCharArray();
  for (char c : charArray) {
    buffer.append(c);
    dfs(index+1,digits,buffer,res);
    buffer.deleteCharAt(buffer.length()-1);
  }
}

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combinationSum(int[] candidates, int target) {
  Arrays.sort(candidates);  // 排序方便剪枝
  dfs(candidates, target, 0, 0);
  return res;
}

private void dfs(int[] candidates, int target, int sum, int start) {

  if (sum == target) {
    res.add(new ArrayList<>(path));
    return;
  }

  for (int i = start; i < candidates.length; i++) {

    //  剪枝（关键优化）
    if (sum + candidates[i] > target) {
      break;
    }

    path.add(candidates[i]);

    //  可以重复选，所以传 i
    dfs(candidates, target, sum + candidates[i], i);

    path.remove(path.size() - 1);
  }
}

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

public List<String> generateParenthesis(int n) {
  List<String> ans = new ArrayList<String>();
  backtrack(ans, new StringBuilder(), 0, 0, n);
  return ans;
}

private void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
  if (cur.length() == max * 2) {
    ans.add(cur.toString());
    return;
  }
  if (open < max) {
    cur.append('(');
    backtrack(ans, cur, open + 1, close, max);
    cur.deleteCharAt(cur.length() - 1);
  }
  if (close < open) {
    cur.append(')');
    backtrack(ans, cur, open, close + 1, max);
    cur.deleteCharAt(cur.length() - 1);
  }
}

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

Set<Integer> used = new HashSet<>();
int m = -1;
int n = -1;
boolean existFlag = false;


public boolean exist(char[][] board, String word) {
  m = board.length ;
  n = board[0].length;
  for (int i = 0; i < m *n; i++) {
    if(existFlag) return true;
    used.add(i);
    dfs(board, word, 0, i);
    used.remove(i);
  }

  return existFlag;
}

private void dfs(char[][] board, String word, int index, int curPos) {
  if (existFlag) {
    return;
  }


  int m1 = curPos / n;
  int n1 = curPos % n;

  if (word.length() == used.size() && board[m1][n1] == word.charAt(index)) {
    existFlag = true;
    return;
  }

  if (board[m1][n1] == word.charAt(index)) {
    if (m1 > 0 && !used.contains(curPos - n)) {
      used.add(curPos - n);
      dfs(board, word, index + 1, curPos - n);
      used.remove(curPos - n);
    }
    if (m1+1 < m && !used.contains(curPos + n)) {
      used.add(curPos + n);
      dfs(board, word, index + 1, curPos + n);
      used.remove(curPos + n);
    }

    if (n1 > 0 && !used.contains(curPos - 1)) {
      used.add(curPos - 1);
      dfs(board, word, index + 1, curPos - 1);
      used.remove(curPos - 1);
    }

    if (n1+1 < n && !used.contains(curPos + 1)) {
      used.add(curPos + 1);
      dfs(board, word, index + 1, curPos + 1);
      used.remove(curPos + 1);
    }

  }

}

分割回文串

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

public List<List<String>> partition(String s) {
  char[] charArray = s.toCharArray();
  int len = s.length();

  // dp[i][j] 表示 s[i][j] 是否是回文
  boolean[][] dp = new boolean[len][len];
  for (int right = 0; right < len; right++) {
    for (int left = 0; left <= right; left++) {
      if(charArray[left] == charArray[right] && (right-left<=2 || dp[left+1][right-1])){
        dp[left][right] = true;
      }
    }
  }
  List<List<String>> res = new ArrayList<>();
  dfs(s,0,len,dp,new LinkedList<>(),res);
  return res;

}

private void dfs(String s , int index, int len, boolean[][] dp , Deque<String> path , List<List<String>> res){
  if(index == len){
    res.add(new ArrayList<>(path));
    return ;
  }

  for (int i = index; i < len ; i++) {
    // 如果 [index,i] 是回文, 则递归处理[i+1,len-1] 的字符串
    if(dp[index][i]){
      path.addLast(s.substring(index,i+1));
      dfs(s,i+1,len,dp,path,res);
      path.removeLast();
    }
  }
}

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

List<List<String>> res = new ArrayList<>();

public List<List<String>> solveNQueens(int n) {
  dfs(n,0,new ArrayList<>());
  return res;
}


private void dfs(int n ,int row,List<Integer> queues){
  if(row == n){
    List<String> board = new ArrayList<>();
    for (Integer queue : queues) {
      int n1 = queue%n;
      StringBuilder builder = new StringBuilder();
      for (int i = 0; i < n; i++) {
        if(n1==i){
          builder.append("Q");
        }else{
          builder.append(".");
        }
      }
      board.add(builder.toString());
    }
    res.add(board);
  }

  for (int i = 0; i < n ; i++) {
    int index = n*row+i;
    if(check(index,n,queues)){
      queues.add(index);
      dfs(n,row+1,queues);
      queues.remove(queues.size()-1);
    }

  }

}

private boolean check(int index,int n , List<Integer> queues){
  int m1 = index/n;
  int n1 = index%n;
  for (Integer queue : queues) {
    int m2 = queue/n;
    int n2 = queue%n;
    if(m1==m2 || n1==n2){
      return false;
    }
    if(Math.abs(m1-m2) == Math.abs(n1-n2)){
      return false;
    }
  }
  return true;
}

二分查找

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

public int searchInsert(int[] nums, int target) {
  int n = nums.length;
  int l = 0;
  int r = n-1;
  while (l<=r){
    int mid = l+(r-l)/2;
    if(nums[mid]<target){
      l=mid+1;
    }else{
      r = mid-1;
    }
  }
  return l;
}

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

public boolean searchMatrix(int[][] matrix, int target) {
  int m = matrix.length;
  int n = matrix[0].length;
  int len = m*n;
  int l = 0;
  int r = len-1;
  while (l<=r){
    int mid = l+(r-l)/2;
    if(matrix[mid/n][mid%n] == target){
      return true;
    }else if(matrix[mid/n][mid%n] < target){
      l = mid+1;
    }else{
      r = mid-1;
    }

  }
  return false;
}

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

public int[] searchRange(int[] nums, int target) {
  int n = nums.length;
  int left = 0;
  int right = n-1;
  int index = -1;
  while (left<=right){
    int mid = left + (right-left)/2;
    if(nums[mid] == target){
      index = mid;
      break;
    } else if (nums[mid]> target) {
      right = mid-1;
    }else{
      left = mid+1;
    }
  }
  if(index==-1){
    return new int[]{-1,-1};
  }
  int startIndex = -1;
  int endIndex = -1;
  for (int i = index; i >=0 ; i--) {
    if(nums[i]==target){
      startIndex=i;
    }
    if(nums[i]<target){
      break;
    }
  }
  for (int i = index; i <n ; i++) {
    if(nums[i]==target){
      endIndex=i;
    }
    if(nums[i]>target){
      break;
    }
  }
  return new int[]{startIndex,endIndex};
}

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

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

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

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

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

public int search(int[] nums, int target) {
  int len = nums.length;
  int l = 0;
  int r = len-1;

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

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

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

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

public int findMin(int[] nums) {
  int n = nums.length;
  int l = 0;
  int r = n-1;
  while (l<r){
    int mid = l+(r-l)/2;
    if(nums[mid]<nums[r]){
      r = mid;  // mid 可能是最小值 不能mid-1
    }else{
      l=mid+1;
    }
  }
  return nums[l];
}

找确定值，用 ±1
找边界值，不丢 mid

第一种情况是 nums[pivot]<nums[high]。如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

栈

有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

示例 5：

输入：s = “([)]”

输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

public boolean isValid(String s) {
  char[] charArray = s.toCharArray();
  Map<Character,Character> map = new HashMap<>(){{
    put('}','{');
    put(')','(');
    put(']','[');
  }};
  Deque<Character> stack = new LinkedList<>();
  for (char c : charArray) {
    if(map.containsKey(c)){
      if(stack.isEmpty()){
        return false;
      }
      if (!stack.pollFirst().equals(map.get(c))) {
        return false;
      }
    }else{
      stack.offerFirst(c);
    }
  }

  return stack.isEmpty();

}

最小栈

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["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.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

class MinStack {
  Deque<Integer> xStack;
  Deque<Integer> minStack;

  public MinStack() {
    xStack = new LinkedList<Integer>();
    minStack = new LinkedList<Integer>();
    minStack.push(Integer.MAX_VALUE);
  }

  public void push(int x) {
    xStack.push(x);
    minStack.push(Math.min(minStack.peek(), x));
  }

  public void pop() {
    xStack.pop();
    minStack.pop();
  }

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

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

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

public String decodeString(String s) {
  Deque<Integer> countStack = new LinkedList<>();
  Deque<String> stringStack = new LinkedList<>();
  String currentString = "";
  int k = 0;

  for (char c : s.toCharArray()) {
    if(Character.isDigit(c)){
      k = k*10 + (c-'0');
    }else if(c=='['){
      countStack.push(k);
      k = 0;
      stringStack.push(currentString);
      currentString ="";
    }else if(c==']'){
      StringBuilder builder = new StringBuilder(stringStack.pop());
      int repeatTimes = countStack.pop();
      for (int i = 0; i < repeatTimes; i++) {
        builder.append(currentString);
      }
      currentString = builder.toString();
    }else{
      currentString+=c;
    }
  }
  return currentString;

}

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

public int[] dailyTemperatures(int[] temperatures) {
  int length = temperatures.length;
  int[] ans = new int[length];
  Deque<Integer> stack = new LinkedList<Integer>();
  for (int i = 0; i < length; i++) {
    int temperature = temperatures[i];
    while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
      int prevIndex = stack.pop();
      ans[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }
  return ans;
}

贪心算法

买卖股票最佳时机

给定一个数组 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。

public int maxProfit(int[] prices) {
  int min = prices[0];
  int res =0;

  for (int price : prices) {
    min = Math.min(min, price);
    if (res < price - min) {
      res = price - min;
    }
  }
  return res;
}

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

public boolean canJump(int[] nums) {
  int rightMost = 0;
  for (int i = 0; i < nums.length; i++) {
    if(rightMost>=i){
      rightMost = Math.max(rightMost,i+nums[i]);
      if(rightMost>=nums.length-1){
        return true;
      }
    }
  }
  return false;
}

跳跃游戏2

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

• 0 <= j <= nums[i] 且
• i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达 n - 1

public int jump(int[] nums) {
  int end = 0;
  int maxPosition = 0;
  int step = 0;
  for (int i = 0; i < nums.length; i++) {
    maxPosition = Math.max(maxPosition,nums[i]+i);
    if(i==end){
      end = maxPosition;
      step++;
    }
  }
  return step;
}

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

public List<Integer> partitionLabels(String s) {
  int[] last = new int[26];

  char[] charArray = s.toCharArray();
  for (int i = 0; i < charArray.length; i++) {
    last[charArray[i]-'a'] = i;
  }

  List<Integer> res = new ArrayList<>();
  int start =0;
  int end = 0;
  for (int i = 0; i < charArray.length; i++) {
    end = Math.max(end,last[charArray[i]-'a']);
    if(i==end){
      res.add(end-start+1);
      start=end+1;
    }
  }
  return res;
}

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

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

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

public int climbStairs(int n) {
  int p = 0, q = 0, r = 1;
  for (int i = 1; i <= n; ++i) {
    p = q; 
    q = r; 
    r = p + q;
  }
  return r;
}

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

public List<List<Integer>> generate(int numRows) {
  List<List<Integer>> ret = new ArrayList<List<Integer>>();
  for (int i = 0; i < numRows; ++i) {
    List<Integer> row = new ArrayList<Integer>();
    for (int j = 0; j <= i; ++j) {
      if (j == 0 || j == i) {
        row.add(1);
      } else {
        row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
      }
    }
    ret.add(row);
  }
  return ret;
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

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

  int first = nums[0];
  int second = Math.max(nums[0],nums[1]);
  for (int i = 2; i < nums.length; i++) {
    int temp = second;
    second = Math.max(nums[i]+first,second);
    first = temp;
  }
  return second;
}

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

  }
  return dp[nums.length-1];
}

完全平方数

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

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

public int numSquares(int n) {
  int[] dp = new int[n+1];
  for (int i = 1; i <=n; i++) {
    int minn = Integer.MAX_VALUE;
    for (int j = 1; j*j <=i ; j++) {
      minn = Math.min(minn,dp[i-j*j]);
    }
    dp[i] = minn+1;
  }
  return dp[n];
}

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

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

public int coinChange(int[] coins, int amount) {
  int max = amount + 1;
  int[] dp = new int[amount + 1];
  Arrays.fill(dp, max);
  dp[0] = 0;
  for (int i = 1; i <= amount; i++) {
    for (int j = 0; j < coins.length; j++) {
      if (coins[j] <= i) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

单词拆分

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

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

public boolean wordBreak(String s, List<String> wordDict) {
  char[] wordArray = s.toCharArray();
  List<char[]> wordArrayDict = wordDict.stream().map(x->x.toCharArray()).toList();
  int[] dp = new int[s.length()+1];
  dp[0] = 1;
  for (int i = 1; i <= wordArray.length; i++) {
    for (char[] w : wordArrayDict) {
      if(w.length<=i && dp[i] ==0 && eq(wordArray,i-1,w)){
        dp[i] =  dp[i-w.length];
      }
    }
  }
  return dp[s.length()]>0;
}

private boolean eq(char[] wordArray , int endIndex , char[] w){
  for (int i = w.length-1; i >=0 ; i--) {
    if(wordArray[endIndex--] != w[i]){
      return false;
    }
  }
  return true;
}

最长递增子序列

给你一个整数数组 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 。

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

public int lengthOfLIS(int[] nums) {
  int len  = nums.length;
  int[] dp = new int[len];
  int max = 1;

  for (int i = 0; i < len; i++) {
    int l = 1;
    for (int j = 0; j < i; j++) {
      if(nums[i]>nums[j]){
        l = Math.max(l,dp[j]+1);
      }
    }
    dp[i]=l;
    max = Math.max(max,l);
  }
  return max;
}

乘积最大子数组

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

测试用例的答案是一个 32-位 整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• nums 的任何子数组的乘积都 保证 是一个 32-位 整数

public int maxProduct(int[] nums) {
  int len = nums.length;
  int[] maxDp = new int[len+1];
  int[] minDp = new int[len+1];
  maxDp[0] =1;
  minDp[0] = 1;
  int ans = Integer.MIN_VALUE;
  for (int i = 0; i < len; i++) {
    if(nums[i]>=0){
      maxDp[i+1] = Math.max(maxDp[i]*nums[i],nums[i]);
      minDp[i+1] = Math.min(minDp[i]*nums[i],nums[i]);
    }else{
      maxDp[i+1] = Math.max(minDp[i]*nums[i],nums[i]);
      minDp[i+1] = Math.min(maxDp[i]*nums[i],nums[i]);
    }
    ans = Math.max(ans,maxDp[i+1]);
  }
  return ans;
}

分割等和子集

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

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

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

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

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

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

}

public int longestValidParentheses(String s) {
  int maxans = 0;
  Deque<Integer> stack = new LinkedList<Integer>();
  stack.push(-1);
  for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.isEmpty()) {
        stack.push(i);
      } else {
        maxans = Math.max(maxans, i - stack.peek());
      }
    }
  }
  return maxans;
}

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

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

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

最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

public int minPathSum(int[][] grid) {
  int m = grid.length;
  int n = grid[0].length;
  int[][] dp = new int[m][n];
  int temp = 0;
  for (int i = 0; i < m; i++) {
    temp+=grid[i][0];
    dp[i][0] = temp;
  }
  temp = 0;
  for (int i = 0; i < n; i++) {
    temp+=grid[0][i];
    dp[0][i] = temp;
  }

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

最长回文子串

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

public String longestPalindrome(String s) {
  char[] charArray = s.toCharArray();
  int len = charArray.length;

  boolean[][] dp = new boolean[len][len];
  int maxL = 0;
  int maxR = 0;
  for (int i = 0; i < len; i++) {
    for (int j = 0; j <=i; j++) {
      if(charArray[i] == charArray[j] && (i-j <2 || dp[j+1][i-1])){
        dp[j][i] = true;
        if (i-j>maxR-maxL) {
          maxR = i;
          maxL = j;
        }
      }
    }
  }
  StringBuilder builder = new StringBuilder();
  for (int i = maxL; i <=maxR ; i++) {
    builder.append(charArray[i]);
  }
  return builder.toString();
}

最长公共子序列

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

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

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

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

public int longestCommonSubsequence(String text1, String text2) {
  int len1 = text1.length();
  int len2 = text2.length();

  int[][] dp = new int[len1+1][len2+1];

  for (int i = 1; i <= len1 ; i++) {
    for (int j = 1; j <=len2; j++) {
      if(text1.charAt(i-1) == text2.charAt(j-1)){
        dp[i][j] = dp[i-1][j-1] +1;
      }else{
        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
      }
    }
  }
  return dp[len1][len2];
}

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

public int minDistance(String word1, String word2) {
  int n = word1.length();
  int m = word2.length();

  // 有一个字符串为空串
  if (n  == 0 || m ==0) {
    return n + m;
  }

  // DP 数组
  int[][] D = new int[n + 1][m + 1];

  // 边界状态初始化
  for (int i = 0; i < n + 1; i++) {
    D[i][0] = i;
  }
  for (int j = 0; j < m + 1; j++) {
    D[0][j] = j;
  }

  // 计算所有 DP 值
  for (int i = 1; i < n + 1; i++) {
    for (int j = 1; j < m + 1; j++) {
      int left = D[i - 1][j] + 1;
      int down = D[i][j - 1] + 1;
      int left_down = D[i - 1][j - 1];
      // 如果两个字符不相等 min(left+1,down+1,left_down+1)
      // 如果两个字符相等 left_down 步数不用变
     	// min(min(left+1,down+1), left_down)
      if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
        left_down += 1;
      }
      D[i][j] = Math.min(left, Math.min(down, left_down));
    }
  }
  return D[n][m];
}