LeetCode Hot100
Top100
- 善用map
- 少用sort，但是如果不涉及角标且不重复可以sort，这样可以跳过
- 「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法
- 单调栈
- 数组滑动窗口思路
- 单调队列
- 矩阵旋转问题可以试试剥洋葱以及翻转
- 链表题的dummy node哑巴结点，可用统一操作逻辑，在删除头节点，插入到空链表，合并链表时第一个节点的选择的时候不需要额外的判断，并且可以很好的返回头节点，一般配合双指针。
- 二叉树一般就是递归，广度搜索
- 二叉搜索树的中序遍历是递增
- 回溯的一般操作
- 回溯函数
- 结束条件
- 添加结果
- return
- 数据处理
- 递归
- 取消数据处理
- 栈：如果是匹配类型的，就存入栈的角标，存位置
:santa:表示需要重新写
01 两数之和
- 9.13
给定一个整数数组 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- 只会存在一个有效答案
进阶： 你可以想出一个时间复杂度小于 O(n2) 的算法吗？
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0] = i;
result[1] = map.get(target - nums[i]);
break;
} else {
map.put(nums[i], i);
}
}
return result;
}
}
采用一个 haspmap 来快速的找到已存在的数值，一次遍历
基础写法为 for 嵌套
49 字母异位分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 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 <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
//49,字母异位分组
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(int i = 0 ; i < strs.length ; i++){
char[] count = new char[26];
for (char c : strs[i].toCharArray()) {
count[c - 'a']++;
}
String key = String.valueOf(count);
if(map.containsKey(key)){
map.get(key).add(strs[i]);
}else{
map.put(key,new ArrayList<>(Collections.singleton(strs[i])));
}
}
return new ArrayList<>(map.values());
}
第一版为借鉴 ZSET，为 set 中的每一个元素加上一个分数来解决类似 eddd, eeed 这样的
第二版为使用 Array.sort()对字符数组进行一次排序，然后转为 string 字符串，这样当作 key，但是时间复杂度还是高
第三版为采用一个计数来排序，也算是 ZSET 的一种简单实现
128 最长连续序列
给定一个未排序的整数数组 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) {
if(nums.length == 0){
return 0;
}
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxCount = 1;
for (Integer num : set) {
if(!set.contains(num - 1)){
int count = 1;
int currentNum = num;
while(set.contains(currentNum + 1)){
count++;
currentNum++;
}
maxCount = Math.max(maxCount,count);
}
}
return maxCount;
}
第一版采用排序sort，确实是通过了，但是尽量少用sort对于数组来说
第二版采用set集合，关键点在于找到这个元素是否是连续子序列的开头，要善于用set和map
283 移动零
给定一个数组 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
**进阶：**你能尽量减少完成的操作次数吗？
public void moveZeroes(int[] nums) {
int count = 0;
int length = nums.length;
for(int i = 0 ; i < length ; i++){
if(nums[i] == 0){
count++;
}else{
nums[i - count] = nums[i];
}
}
for(int i = length - count ; i < length ; i++){
nums[i] = 0;
}
}
一次过
11 盛水最多的容器
给定一个长度为 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.length2 <= n <= 1050 <= height[i] <= 104
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxTemp;
int minHeight;
int maxArea = 0;
while(left < right){
if(height[left] < height[right]){
minHeight = height[left];
maxTemp = minHeight * (right - left);
left++;
}else{
minHeight = height[right];
maxTemp = minHeight * (right - left);
right--;
}
if(maxTemp > maxArea){
maxArea = maxTemp;
}
}
return maxArea;
}
双指针遍历，一次过
15 三数之和
给你一个整数数组 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>> result = new ArrayList<>();
for(int i = 0 ; i < nums.length ; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
if(nums[i] + nums[j] + nums[k] > 0){
k--;
} else if (nums[i] + nums[j] + nums[k] < 0) {
j++;
}else{
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
result.add(list);
while(j < k && nums[j] == nums[j + 1]) {
j++;
}
while(j < k && nums[k] == nums[k - 1]) {
k--;
}
j++;
k--;
}
}
}
return result;
}
第一次是想着不重复就使用set集合，但是set集合的这个操作导致超时了
第二版看来题解之后，发现可以先排序，这样就可以跳过重复，并且可以使用双指针来操作
结论：
- 如果最后的返回结果不包含角标并且不能重复的话可以先排序
- 「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法
42 接雨水:star::star::star:
给定 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.length1 <= n <= 2 * 1040 <= height[i] <= 105
public int trap(int[] height) {
List<Integer> leftMax = new ArrayList<>();
List<Integer> rightMax = new ArrayList<>();
leftMax.add(height[0]);
rightMax.add(height[height.length - 1]);
for(int i = 1 ; i < height.length ; i++){
leftMax.add(Math.max(leftMax.get(i - 1),height[i]));
}
for(int i = height.length - 2 ; i >= 0 ; i--){
rightMax.add(Math.max(rightMax.get(height.length - i - 2),height[i]));
}
int count = 0;
for(int i = 0 ; i < height.length ; i++){
count += Math.min(leftMax.get(i),rightMax.get(height.length - i - 1)) - height[i];
}
return count;
}
动态规划：
先左到右循环一次，找到这条路径的最优
再右到左循环一次，同理
最后比较
public int trap(int[] height) {
//单调栈
int count = 0;
Deque<Integer> stack = new LinkedList<>();
for(int i = 0 ; i < height.length ; i++){
while(!stack.isEmpty() && height[i] > height[stack.peek()]){
int pop = stack.pop();
if(stack.isEmpty()){
break;
}
count += (i - stack.peek() - 1) * (Math.min(height[i],height[stack.peek()]) - height[pop]);
}
stack.push(i);
}
return count;
}
采用单调栈来简化上面动态规划的操作，只需要遍历一次（在想这个题的时候，第一直觉就是接雨水肯定是一个下降再上升的过程，先存下降的角标，当出现上升就开始计算）
要学习单调栈的这个思想，太牛了
public int trap(int[] height) {
//双指针
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int count = 0;
while(left < right){
leftMax = Math.max(leftMax,height[left]);
rightMax = Math.max(rightMax,height[right]);
if(height[left] < height[right]){
count += leftMax - height[left];
left++;
}else{
count += rightMax - height[right];
right--;
}
}
return count;
}
双指针可以这样想，填满雨水之后，在最高位置的左侧，是递增的，右侧是递减的，这就可以从左侧来找局部最优，右侧找局部最优。同时找到全局最优（移动左右指针的目的就是找到全局最优，就是这个最高位置）
3 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
public int lengthOfLongestSubstring(String s) {
int count = 1;
Set<Character> set = new HashSet<>();
if(s.length() == 0 || s.isEmpty()){
return 0;
}
int right = -1;
for(int i = 0 ; i < s.length(); i++){
if(i != 0){
set.remove(s.charAt(i - 1));
}
while(right + 1 < s.length() && !set.contains(s.charAt(right + 1))){
set.add(s.charAt(right + 1));
right++;
}
count = Math.max(count,set.size());
}
return count;
滑动窗口问题：依次以每一个字母为开头，找到最大子串长度
public int lengthOfLongestSubstring(String s) {
int[] arr = new int[128];
int i = 0;
int res = 0;
for(int j = 0; j < s.length(); j++){
char ch = s.charAt(j);
i = Math.max(i, arr[ch]);
arr[ch] = j + 1;
res = Math.max(res, j - i + 1);
}
return res;
}
滑动窗口的改进，这里的思想和第一眼看见这个题的思路一样，但是由于没想起来怎么实现所以放弃了，这段算法主要就是利用一个char类型的数组来记录每一个字符的位置，当出现重复字符的时候，直接就从上一次出现该字符的位置再次开始，节省了时间，但是我觉得这个算法是有问题的，因为该题写的既可以是字符，又可以是数字和空格，那这个数组的长度不止128吧。
438 找到字符串中所有字母异位词 :star2:
给定两个字符串 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 * 104s和p仅包含小写字母
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLen; ++i) {
++sCount[s.charAt(i) - 'a'];
++pCount[p.charAt(i) - 'a'];
}
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s.charAt(i) - 'a'];
++sCount[s.charAt(i + pLen) - 'a'];
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
这道题一个很经典的滑动窗口，学习一下这个思路，不要再想着循环的那种
560 和为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 count = 0;
for(int start = 0 ; start < nums.length ; start++){
int sum = 0;
for(int end = start ; end >= 0 ; end--){
sum += nums[end];
if(sum == k){
count++;
}
}
}
return count;*/
int preSum = 0;
int count = 0;
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
for(int i = 0 ; i < nums.length ; i++){
preSum += nums[i];
if(map.containsKey(preSum - k)){
count++;
}
}
return count;
}
前缀和；对于数组中的任何位置 j，前缀和 pre[j] 是数组中从第一个元素到第 j 个元素的总和。这意味着如果你想知道从元素 i+1 到 j 的子数组的和，你可以用 pre[j] - pre[i] 来计算。
239 滑动窗口最大值 :star::star::star:
给你一个整数数组 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] <= 1041 <= k <= nums.length
public int[] maxSlidingWindow(int[] nums, int k) {
/*PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];
}
});
for(int i = 0 ; i < k ; i++){
queue.offer(new int[]{nums[i] , i});
}
int[] result = new int[nums.length - k + 1];
result[0] = queue.peek()[0];
for(int i = k ; i < nums.length ; i++){
queue.offer(new int[]{nums[i] , i});
while(queue.peek()[1] <= i - k){
queue.poll();
}
result[i - k + 1] = queue.peek()[0];
}
return result;*/
Deque<Integer> deque = new LinkedList<>();
for(int i = 0 ; i < k ; i++){
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
deque.pollLast();
}
deque.offerLast(i);
}
int[] result = new int[nums.length - k + 1];
result[0] = nums[deque.peekFirst()];
for(int i = k ; i < nums.length ; i++){
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
deque.pollLast();
}
deque.offerLast(i);
while(deque.peekFirst() < i - k + 1){
deque.pollFirst();
}
result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}
这里注释用到了一个大顶堆的概念，每次来新的元素更新堆，同时判断元素是否以及被滑动窗口滑出，这里默认创建的是小顶堆，因此要重写compare方法
下面的这一部分采用的是一个单调队列，即随着角标的增大，值保持一个单调性，如果现在有3，2，-1，又来了一个5，这就不是单调的了，把之前的全部清空，5的角标添加进去，维护的不再是值，而是角标。
76 最小覆盖子串 :santa:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 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.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
此题看不太懂，有待后面再次看
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。
53 最大子数组和
给你一个整数数组 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
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
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(maxAns, pre);
}
return maxAns;
}
这就是前缀和，动态规划的思想
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].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
public int[][] merge(int[][] intervals) {
if(intervals.length == 0){
return new int[0][2];
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
List<int[]> merge = new ArrayList<int[]>();
for (int[] interval : intervals) {
int left = interval[0];
int right = interval[1];
if (merge.isEmpty() || merge.get(merge.size() - 1)[1] < left) {
merge.add(new int[]{left, right});
} else {
merge.get(merge.size() - 1)[1] = Math
.max(merge.get(merge.size() - 1)[1], right);
}
}
return merge.toArray(new int[merge.size()][]);
}
这里思想就是按照左边界先进行一个排序，这样在进行合并的时候就可以只考虑右边界了
189 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
public void rotate(int[] nums, int k) {
int[] temp = new int[k];
k = k % nums.length;
if(k < nums.length) {
for (int i = 0; i < k; i++) {
temp[i] = nums[nums.length - k + i];
}
for (int i = nums.length; i > k; i--) {
nums[i - 1] = nums[i - k - 1];
}
for (int i = 0; i < k; i++) {
nums[i] = temp[i];
}
}
}
这是方法一，额外的数组
238 除自身以外数组的乘积
给你一个整数数组 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]
public int[] productExceptSelf(int[] nums) {
int[] right = new int[nums.length];
//right[0] = nums[nums.length - 1];
right[0] = 1;
int left = 1;
int c = 1;
for(int i = nums.length - 1; i > 0; i--){
right[c] = right[c - 1] * nums[i];
c++;
}
int[] result = new int[nums.length];
for(int i = 0; i < nums.length; i++){
result[i] = left * right[nums.length - 1 - i];
left *= nums[i];
}
return result;
}
左边乘积以及右边乘积分别保存一下
41 缺失的第一个正数
给你一个未排序的整数数组 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 没有出现。
public int firstMissingPositive(int[] nums) {
/*int max = nums.length ;
for(int i = 0 ; i < max ; i++){
if(nums[i] <= 0){
nums[i] = max + 1;
}
}
for(int i = 0 ; i < max ; i++){
int index = Math.abs(nums[i]);
if(index <= max){
nums[index - 1] = -Math.abs(nums[index - 1]);
}
}
for(int i = 0 ; i < max ; i++){
if(nums[i] > 0){
return i + 1;
}
}
return max + 1;*/
int num = nums.length;
for(int i = 0 ; i < nums.length ; i++){
while(nums[i] > 0 && nums[i] < num && nums[nums[i] - 1] != nums[i]){
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for(int i = 0 ; i < nums.length ; i++){
if(nums[i] != i + 1){
return i + 1;
}
}
return num + 1;
}
首先本题要知道，这个最小的缺失正数一定会在【1，N+1】之中
/* 1.范围收缩（抽屉原理）:长度为 n 的数组里，最小缺失正整数一定落在 [1, n+1]。 1.1如果 1..n 都在，那答案就是 n+1； 1.2否则就是其中某个缺失的数。 → 所以我们只需关注 1..n 这些“有用数”，其他（≤0 或 >n）都可以视为“垃圾”。 2.用数组当哈希桶（原地哈希 / 置换）:把每个在 [1..n] 范围内的数 x 放到“它的家”——下标 x-1 的位置： 2.1想让 nums[x-1] == x； 2.2通过不断交换把数放回家； 2.3处理过程中忽略 ≤0、>n、以及 重复 的数（避免死循环）。 3.最终一遍扫描：第一个不在家（nums[i] != i+1）的位置 i，答案就是 i+1；若都在家，答案是 n+1。 */
73 矩阵置零
给定一个 *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]]
public void setZeroes(int[][] matrix) {
/*int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
for(int i = 0 ; i < matrix.length ; i++){
for(int j = 0 ; j < matrix[i].length ; j++){
if(matrix[i][j] == 0){
row[i] = 1;
column[j] = 1;
}
}
}
for(int i = 0 ; i < matrix.length ; i++){
for(int j = 0 ; j < matrix[i].length ; j++){
if(row[i] == 1 || column[j] == 1){
matrix[i][j] = 0;
}
}
}*/
int m = matrix.length;
int n = matrix[0].length;
boolean flagCol = false;
boolean flagRow = false;
for(int i = 0 ; i < m ; i++){
if(matrix[i][0] == 0){
flagCol = true;
}
}
for(int i = 0 ; i < n ; i++){
if(matrix[i][0] == 0){
flagRow = true;
}
}
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(flagCol){
for(int i = 0 ; i < n ; i++){
matrix[0][i] = 0;
}
}
if(flagRow){
for(int i = 0 ; i < m ; i++){
matrix[i][0] = 0;
}
}
}
第一个方法：使用标记，来标记哪一个位置需要置零
第二个方法相较于第一个方法空间复杂度更低，大概就是使用第一行和第一列来存储是否需要置零的标记。
54 螺旋矩阵
给你一个 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]
public List<Integer> spiralOrder(int[][] matrix) {
/*List<Integer> list = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return list;
}
int rows = matrix.length;
int cols = matrix[0].length;
boolean[][] visited = new boolean[rows][cols];
int directionIndex = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int row = 0, col = 0;
for(int i = 0 ; i < rows * cols ; i++){
list.add(matrix[row][col]);
visited[row][col] = true;
int nextRow = row + directions[directionIndex][0];
int nextCol = col + directions[directionIndex][1];
if(nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols || visited[nextRow][nextCol] == true){
directionIndex = (directionIndex + 1) % 4;
}
row += directions[directionIndex][0];
col += directions[directionIndex][1];
}
return list;*/
int n = matrix.length;
int m = matrix[0].length;
List<Integer> list = new ArrayList<Integer>();
int left = 0, right = m - 1, top = 0, bottom = n - 1;
while(left <= right && top <= bottom){
for(int i = left ; i <= right ; i++){
list.add(matrix[top][i]);
}
for(int i = top + 1 ; i <= bottom ; i++){
list.add(matrix[i][right]);
}
if(left < right && top < bottom){
for(int i = right - 1 ; i > left ; i--){
list.add(matrix[bottom][i]);
}
for(int i = bottom ; i > top ; i--){
list.add(matrix[i][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return list;
}
第一种方法：定义四个方向，当到达边界的时候，变换方向，这个方向可以同理为x，y坐标的+-，这个循环的条件就是矩阵的总长度
第二种方法：可以发现，这个就是剥洋葱一样，一层一层的进行读取元素，所以就定义四个指针，左边界，右，上，下四个指针，依次移动变换指针的值。
48 旋转图像
给定一个 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]]
public void rotate(int[][] matrix) {
int n = matrix.length;
int left = 0 , right = n-1;
while(left<=right){
for(int j=left;j<right;j++){
int tmp=matrix[left][j];
matrix[left][j]=matrix[right-j+left][left];
matrix[right-j+left][left]=matrix[right][right-j+left];
matrix[right][right-j+left]=matrix[j][right];
matrix[j][right]=tmp;
}
left++;
right--;
}
}
本题我采用的是和上面的螺旋矩阵相似的思路，剥洋葱一样一层一层的处理，矩阵的题主要是数学变换，要进行数学推理
还要其他的方案：
一是空间复杂度最高的，就是采用一个相同大小的辅助矩阵来
二是将旋转的问题转换为翻转的问题，顺时针旋转一次就相当于是上下折叠再主对角线折叠
240 搜素二维矩阵Ⅱ
编写一个高效的算法来搜索 *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
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int 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;
}
三种解法：
1：依次遍历，直接查找，直接遍历
2：因为行增，列增，所以可以采用二分查找
3：将起点放在右上角，这样左边就是比当前值小，下边就是比当前值大，这样类似一个搜索树
160 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表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 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/*Set<ListNode> set = new HashSet<ListNode>();
ListNode temp = headA;
while(temp != null){
set.add(temp);
temp = temp.next;
}
temp = headB;
while(temp != null){
if(set.contains(temp)){
return temp;
}
temp = temp.next;
}
return null;*/
if(headA == null || headB == null){
return null;
}
ListNode temp = headA;
ListNode temp1 = headB;
while(temp1 != temp){
temp = temp == null ? headB : temp.next;
temp1 = temp1 == null ? headA : temp1.next;
}
return temp;
}
1：采用一个set来存储，然后第二个列表如果在set中存在，则返回
2：如果有两个列表A，B，那么定义两个指针搜索路径为一个为AB，一个为BA
206 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
public ListNode reverseList(ListNode head) {
/*ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;*/
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
要明白链表的基础概念，如果有一个链表为A->B->C，那么head头节点：head = A,head.next指向节点B的内存地址。必须记好，然后再来进行反转。
第一种方法就是找一个临时变量来存当前节点的下一个节点，不然就会丢失，因为需要断开这个连接
第二种方法就是递归，首先需要到底链表的最后一个节点，然后依次翻转
141 环形链表
给你一个链表的头节点 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
解释：链表中没有环。
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
还是快慢指针，如果有环的话，快的指针一定可以和慢的指针相重合
142 环形链表Ⅱ
给定一个链表的头节点 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
解释：链表中没有环。
这一题一般的思想就是找一个set集合，存入访问过的点的Pos值，当下次访问到的Pos在set中存在的时候就是环的起点。
第二种思想是，快慢指针的问题，快指针的移动距离永远都是满指针的两倍，利用这个找到一般的等式关系。
21 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 <= 100l1和l2均按 非递减顺序 排列
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//递归
/*if(list1 == null){
return list2;
} else if (list2 == null) {
return list1;
} else if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}else{
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}*/
//哨兵
ListNode pre = new ListNode(-1);
ListNode prev = pre;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
prev.next = list1;
list1 = list1.next;
}else{
prev.next = list2;
list2 = list2.next;
}
prev = prev.next;
}
prev.next = list1 == null ? list2 : list1;
return pre.next;
}
第一种方式：递归，如果l1<l2，则l1.next = mergewoLists(l1.next,l2)
第二种方式：采用一个哨兵机制
2 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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]
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int flag = 0;
ListNode result = l1;
ListNode prev = null;
while(l1 != null && l2 != null){
int temp = (l1.val + l2.val + flag) % 10;
flag = (l1.val + l2.val + flag) / 10;
l1.val = temp;
prev = l1;
l1 = l1.next;
l2 = l2.next;
}
if(l2 != null){
prev.next = l2;
while(l2 != null){
int temp = (l2.val + flag) % 10;
flag = (l2.val + flag) / 10;
l2.val = temp;
prev = l2;
l2 = l2.next;
}
} else if(l1 != null){
while(l1 != null){
int temp = (l1.val + flag) % 10;
flag = (l1.val + flag) / 10;
l1.val = temp;
prev = l1;
l1 = l1.next;
}
}
if(flag != 0){
prev.next = new ListNode(flag);
}
return result;
}
这个就是注意最后的进位
19 删除链表的倒数第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 <= 300 <= Node.val <= 1001 <= n <= sz
**进阶：**你能尝试使用一趟扫描实现吗？
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
// fast先走n步
for (int i = 0; i < n; i++) {
if (fast.next == null) return head; // n大于链表长度
fast = fast.next;
}
// fast和slow一起走，直到fast到达末尾
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 删除slow.next节点
slow.next = slow.next.next;
return dummy.next;
}
采用双指针的思想，fast和slow相差n，注意这个dummy node的使用，这个可用处理头节点的问题。
24 两两交换链表中的节点 :star:
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode slow = pre.next;
ListNode dummy = pre;
while (slow != null && slow.next != null) {
ListNode fast = slow.next;
slow.next = fast.next;
fast.next = slow;
// 这里需要更新 pre 的 next 指向 fast
pre.next = fast;
// 更新 pre 和 slow 指针
pre = slow;
slow = slow.next;
}
return dummy.next;
}
这里主要就是头节点的位置，以及各个指针的变化，这个题学习链表的概念很重要
25 K个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
public ListNode reverseKGroup(ListNode head, int k) {
//栈的方式
/*Stack<ListNode> stack = new Stack<>();
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
ListNode curr = head;
while(true){
ListNode temp = curr;
int count = 0;
while(temp != null && count < k){
stack.push(temp);
temp = temp.next;
count++;
}
if(count < k){
tail.next = curr;
break;
}
while(!stack.isEmpty()){
tail.next = stack.pop();
tail = tail.next;
}
tail.next = temp;
curr = temp;
}
return dummy.next;*/
//不采用栈
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while(head != null){
ListNode tail = pre;
for(int i = 0 ; i < k ; i++){
tail = tail.next;
if(tail == null){
return dummy.next;
}
}
ListNode next = tail.next;
ListNode[] reverse = myReverse(head, tail);
head = reverse[0];
tail = reverse[1];
pre.next = head;
tail.next = next;
pre = tail;
head = tail.next;
}
return dummy.next;
}
public ListNode[] myReverse(ListNode head,ListNode tail){
ListNode prev = tail.next;
ListNode p = head;
while(tail != prev){
ListNode next = p.next;
p.next = prev;
prev = p;
p = next;
}
return new ListNode[]{tail,head};
}
}
第一种方式就是stack栈。
第二种方式就是把k个划分开，划分的段翻转，之后拼接回去，依次进行
138 随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
//138，随机链表的复制
public Node copyRandomList(Node head) {
if(head==null){
return null;
}
Map<Node, Node> map = new HashMap<>();
Node p = head;
//创建新节点建立与原始节点的映射关系，map用于解决random节点的链接问题
while (p != null) {
map.put(p, new Node(p.val));
p = p.next;
}
p = head;
//将各个节点连接起来
while (p != null) {
Node newNode = map.get(p);
newNode.next = map.get(p.next);
newNode.random = map.get(p.random);
p = p.next;
}
return map.get(head);//返回新的头节点
}
这一题我觉得就上面的这个方法就不错，主要就是创建一个map来创建新节点的建立与原始节点的映射关系
148 排序链表 :star::star:
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
//148，排序链表
public ListNode sortList(ListNode head) {
return sortList(head,null);
}
//148，辅助函数（归并算法）
public ListNode sortList(ListNode head,ListNode tail){
if(head == null){
return head;
}
if(head.next == tail){
head.next = null;
return head;
}
ListNode slow = head;
ListNode fast = head;
while(fast != tail){
slow = slow.next;
fast = fast.next;
if(fast != tail){
fast = fast.next;
}
}
ListNode mid = slow;
ListNode list1 = sortList(head,mid);
ListNode list2 = sortList(mid,tail);
return merge_148(list1,list2);
}
//148，辅助函数（合并两个有序链表）
public ListNode merge_148(ListNode head1, ListNode head2){
ListNode dummy = new ListNode(-1);
ListNode prev = dummy, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null){
if(temp1.val < temp2.val){
prev.next = temp1;
temp1 = temp1.next;
}else{
prev.next = temp2;
temp2 = temp2.next;
}
prev = prev.next;
}
if(temp1 != null){
prev.next = temp1;
} else if (temp2 != null) {
prev.next = temp2;
}
return dummy.next;
}
此处采用归并算法，掌握好合并两个有序链表的基础
23 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
//23，合并K个升序链表
//创建一个优先队列（大顶堆或者小顶堆）
PriorityQueue<Status> queue = new PriorityQueue<Status>();
public ListNode mergeKLists(ListNode[] lists) {
//顺序合并
/*ListNode result = null;
for(int i = 0 ; i < lists.length ; i++){
result = merge2Lists(result, lists[i]);
}
return result;*/
//分治合并
/*return merge_23(lists, 0, lists.length - 1);*/
//优先队列
for(ListNode list : lists){
if(list != null){
queue.offer(new Status(list.val, list));
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while(!queue.isEmpty()){
Status s = queue.poll();
tail.next = s.node;
tail = tail.next;
if(s.node.next != null){
queue.offer(new Status(s.node.next.val, s.node.next));
}
}
return head.next;
}
//23，辅助函数（分治）
public ListNode merge_23(ListNode[] lists, int start, int tail){
if(start == tail){
return lists[start];
}
if(start > tail){
return null;
}
int mid = (start + tail) >> 1;
return merge2Lists(merge_23(lists, start, mid), merge_23(lists, mid + 1, tail));
}
//23，辅助函数（合并两个升序链表）
private ListNode merge2Lists(ListNode result, ListNode list) {
if(result == null || list == null){
return result != null ? result : list;
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy, temp1 = result, temp2 = list;
while(temp1 != null && temp2 != null){
if(temp1.val < temp2.val){
tail.next = temp1;
temp1 = temp1.next;
}else{
tail.next = temp2;
temp2 = temp2.next;
}
tail = tail.next;
}
tail.next = temp1 != null ? temp1 : temp2;
return dummy.next;
}
//23，辅助比较类（比较链表值）
class Status implements Comparable<Status>{
int val;
ListNode node;
Status(int val, ListNode node){
this.val = val;
this.node = node;
}
public int compareTo(Status o) {
return this.val - o.val;
}
}
三种方法，1、顺序排序；2、分治排序；3、小顶堆排序；本题的基础还是合并两个有序链表
146 LRU缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
class LRUCache {
class DLinkedNode{
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode(){};
public DLinkedNode(int key, int value){
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> map = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head,tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode dLinkedNode = map.get(key);
if(dLinkedNode == null){
return -1;
}
moveToHead(dLinkedNode);
return dLinkedNode.value;
}
public void put(int key, int value) {
DLinkedNode dLinkedNode = map.get(key);
if(dLinkedNode == null){
DLinkedNode newNode = new DLinkedNode(key, value);
map.put(key, newNode);
addToHead(newNode);
++size;
if(size > capacity){
DLinkedNode removetail = removetail();
map.remove(removetail.key);
--size;
}
}else{
dLinkedNode.value = value;
moveToHead(dLinkedNode);
}
}
public void moveToHead(DLinkedNode dLinkedNode){
removeNode(dLinkedNode);
addToHead(dLinkedNode);
}
public void removeNode(DLinkedNode dLinkedNode){
dLinkedNode.prev.next = dLinkedNode.next;
dLinkedNode.next.prev = dLinkedNode.prev;
}
public void addToHead(DLinkedNode dLinkedNode){
dLinkedNode.prev = head;
dLinkedNode.next = head.next;
head.next.prev = dLinkedNode;
head.next = dLinkedNode;
}
public DLinkedNode removetail(){
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
LRU是最近最久未使用，主要思想是哈希表来处理get操作，put操作采用双向链表来处理，如果节点被使用就先删除（如果存在）再添加到头节点，这样尾节点的就是最近最久未使用，有几个辅助函数就是添加节点到头部，移除节点，移动节点到头部，移除尾节点。
104 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
public int maxDepth(TreeNode root){
//深度优先递归算法
/*int count = 1;
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
count = 1;
}
int temp = count;
if(root.left != null){
count += maxDepth(root.left);
}
if(root.right != null){
temp += maxDepth(root.right);
}
return Math.max(count, temp);*/
//广度优先算法
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int ans = 0;
while(!queue.isEmpty()){
int size = queue.size();
while(size > 0){
TreeNode node = queue.poll();
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
两种方法：一个是深度优先递归，一个是广度优先
226 翻转二叉树
给你一棵二叉树的根节点 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 = []
输出：[]
public TreeNode invertTree(TreeNode root){
//递归
/*if(root == null){
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;*/
//广度优先
if(root == null){
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
while(size > 0){
TreeNode node = queue.poll();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
size--;
}
}
return root;
}
还是深度优先递归和广度优先
101 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
public boolean isSymmetric(TreeNode root){
//递归
/*if(root == null){
return true;
}
if(root.left != null && root.right != null){
return isSymmetric_101(root.left, root.right);
}else return root.left == null && root.right == null;*/
//迭代
return check_101(root, root);
}
//辅助函数——101-递归
public boolean isSymmetric_101(TreeNode t1, TreeNode t2){
if(t1.val == t2.val){
boolean left = true;
boolean right = true;
if(t1.left != null && t2.right != null){
left = isSymmetric_101(t1.left, t2.right);
}else left = t1.left == null && t2.right == null;
if(t1.right != null && t2.left != null ){
right = isSymmetric_101(t1.right, t2.left);
}else right = t1.right == null && t2.left == null;
return left && right;
}
return false;
}
//辅助函数-101-迭代
public boolean check_101(TreeNode t1, TreeNode t2){
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(t1);
queue.offer(t2);
while(!queue.isEmpty()){
t1 = queue.poll();
t2 = queue.poll();
if(t1 == null && t2 == null){
continue;
}
if((t1 == null || t2 == null) || (t1.val != t2.val)){
return false;
}
queue.offer(t1.left);
queue.offer(t2.right);
queue.offer(t1.right);
queue.offer(t2.left);
}
return true;
}
对于递归：我觉得关键点就是找到什么时候开始递归，递归条件结束之后，改怎么操作
对于迭代：主要就是队列和栈这些的应用，一般都需要辅助函数
102 二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
//543，二叉树的直径
int maxDiameter = 0; // 全局变量记录最大直径
public int diameterOfBinaryTree(TreeNode root){
maxDiameter = 0; // 重置全局变量
diameterOfBinaryTree_543(root);
return maxDiameter;
}
//辅助函数——543-递归（返回树的深度）
public int diameterOfBinaryTree_543(TreeNode root){
if(root == null){
return 0;
}
// 递归计算左右子树的深度
int leftDepth = diameterOfBinaryTree_543(root.left);
int rightDepth = diameterOfBinaryTree_543(root.right);
// 更新最大直径（经过当前节点的路径长度）
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
// 返回当前节点的深度
return Math.max(leftDepth, rightDepth) + 1;
}
还是递归的思想，不太熟练
102 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return Collections.emptyList();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
List<List<Integer>> res = new ArrayList<>();
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> temp = new ArrayList<>();
while(size > 0){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
size--;
}
res.add(temp);
}
return res;
}
迭代，基础，
108 将有序数组转换为二叉搜索树
给你一个整数数组 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] 都是高度平衡二叉搜索树。
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST_108(nums, 0, nums.length - 1);
}
//辅助函数-108-递归
public TreeNode sortedArrayToBST_108(int[] nums, int low, int high) {
if(low > high){
return null;
}
int mid = (low + high) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST_108(nums, low, mid - 1);
root.right = sortedArrayToBST_108(nums, mid + 1, high);
return root;
}
递归，递归不一定是处理子树，也可以是递归找值
98 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
public boolean isValidBST(TreeNode root) {
//递归
List<Integer> validBST98 = isValidBST_98(root);
return isValidBST_98_2(validBST98);
}
//辅助函数-98-中序遍历
public List<Integer> isValidBST_98(TreeNode root){
List<Integer> list = new ArrayList<>();
isValidBST_98_1(root, list);
return list;
}
//辅助函数-98-递归
public void isValidBST_98_1(TreeNode root, List<Integer> list){
if(root.left != null){
isValidBST_98_1(root.left, list);
}
list.add(root.val);
if(root.right != null){
isValidBST_98_1(root.right, list);
}
}
//辅助函数-98-判断是否递增
public boolean isValidBST_98_2(List<Integer> list){
for (int i = 0; i < list.size() - 1; i++) {
if(list.get(i) >= list.get(i + 1)){
return false;
}
}
return true;
}
中序递增，根据这个来判断
230 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 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
public int kthSmallest(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
kthSmallest_230_1(root, list);
return list.get(k - 1);
}
//辅助函数-230-中序
public void kthSmallest_230_1(TreeNode root, List<Integer> list){
if(root.left != null){
kthSmallest_230_1(root.left, list);
}
list.add(root.val);
if(root.right != null){
kthSmallest_230_1(root.right, list);
}
}
中序遍历来找
199 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
**输入：**root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
public List<Integer> rightSideView(TreeNode root) {
//广度搜索，找到每一层最后一个节点
/*if(root == null){
return Collections.emptyList();
}
List<Integer> res = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()){
int size = deque.size();
for(int i = 0; i < size; i++){
TreeNode node = deque.poll();
if(i == size - 1){
res.add(node.val);
}
if(node.left != null){
deque.offer(node.left);
}
if(node.right != null){
deque.offer(node.right);
}
}
}
return res;*/
//递归（深度搜索）
List<Integer> list = new ArrayList<>();
rightSideView_199_1(root, 1, list);
return list;
}
//辅助函数-199-递归（深度搜索）
public void rightSideView_199_1(TreeNode root, int k, List<Integer> list){
if(root == null) return;
if(list.size() < k){
list.add(root.val);
}
rightSideView_199_1(root.right, ++k, list);
rightSideView_199_1(root.left, k, list);
}
广度搜索的每一层的最后一个就是要添加到列表的
深度搜索当探到右的时候来添加进去
114 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
public void flatten(TreeNode root) {
//先序链表
/*List<Integer> list = new ArrayList<>();
flatten_114(root, list);
TreeNode curr = root;
for (int i = 1; i < list.size(); i++) {
curr.right = new TreeNode(list.get(i));
curr.left = null;
curr = curr.right;
}*/
//原树操作
TreeNode cur = root;
while(cur != null){
if(cur.left != null){
TreeNode next = cur.left;
TreeNode predecessor = next;
while(predecessor.right != null){
predecessor = predecessor.right;
}
predecessor.right = cur.right;
cur.left = null;
cur.right = next;
}
cur = cur.right;
}
}
//辅助函数（先序）
public void flatten_114(TreeNode root, List<Integer> list){
if(root == null) return;
list.add(root.val);
flatten_114(root.left, list);
flatten_114(root.right, list);
}
第一种方法就是先序得列表，然后开始重新构建
第二种方法就是找左子树的最右节点，令其指向父节点的右子树，一直遍历，循环条件为遍历每一个节点是否有左节点
105 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
//105，从前序和中序遍历序列构建二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {
/*int n = preorder.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(inorder[i], i);
}
return buildTree_105(preorder, 0, n - 1, inorder, 0, n - 1, map);*/
//迭代
if(preorder == null || preorder.length == 0){
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
int index = 0;
for(int i = 1; i < preorder.length; i++){
int preval = preorder[i];
TreeNode node = stack.peek();
if(node.val != inorder[index]){
node.left = new TreeNode(preval);
stack.push(node.left);
}else{
while(!stack.isEmpty() && stack.peek().val == inorder[index]){
node = stack.pop();
index++;
}
node.right = new TreeNode(preval);
stack.push(node.right);
}
}
return root;
}
//辅助函数-105-递归
public TreeNode buildTree_105(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd,
Map<Integer, Integer> map) {
if(preStart > preEnd){
return null;
}
int preorder_root = preStart;
int inorder_root = map.get(preorder[preorder_root]);
TreeNode root = new TreeNode(preorder[preorder_root]);
int size_left_subtree = inorder_root - inStart;
root.left = buildTree_105(preorder, preStart + 1, preStart + size_left_subtree,
inorder, inStart, inorder_root - 1, map);
root.right = buildTree_105(preorder, preStart + size_left_subtree + 1, preEnd,
inorder, inorder_root + 1, inEnd, map);
return root;
}
第一中方法是递归，主要就是边界问题的判断
第二种方法是迭代，迭代主要的难点就是找到当前节点是哪个节点的右孩子
437 路径总和Ⅲ
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
//437，路径总和 III
public int pathSum(TreeNode root, long targetSum) {
/*if(root == null){
return 0;
}
int ret = rootSum(root, targetSum);
ret += pathSum(root.left, targetSum);
ret += pathSum(root.right, targetSum);
return ret;*/
//深度搜索-前缀和
Map<Long,Integer> map = new HashMap<>();
map.put(0L,1);
return dfs(root, map, 0, targetSum);
}
//辅助函数-深度搜索
public int dfs(TreeNode root, Map<Long,Integer> map, long sum, long targetSum){
if(root == null){
return 0;
}
int ret = 0;
sum += root.val;
ret = map.getOrDefault(sum - targetSum, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
ret += dfs(root.left, map, sum, targetSum);
ret += dfs(root.right, map, sum, targetSum);
map.put(sum, map.getOrDefault(sum, 0) - 1);
return ret;
}
//辅助函数-437-从节点出发计算路径和
public int rootSum(TreeNode root, long targetSum){
if(root == null){
return 0;
}
int val = root.val;
int ret = 0;
if(val == targetSum){
ret++;
}
ret += rootSum(root.left, targetSum - val);
ret += rootSum(root.right, targetSum - val);
return ret;
}
第一种方法就是求每一个节点当头节点，到每一个节点的和是不是等于目标和
第二种方法就是采用前缀和的思想，避免重复的运算，这里需要注意最后的去除操作，这样可以避免当前路径的节点对其他节点结果的影响。
236 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
//236，二叉树的最近公共祖先
TreeNode ans_236 = null;
Map<Integer,TreeNode> map_236 = new HashMap<>();
Set<Integer> set_236 = new HashSet<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/*dfs_236(root, p, q);
return ans_236;*/
dfs_236_2(root);
while(p != null){
set_236.add(p.val);
p = map_236.get(p.val);
}
while(q != null){
if(set_236.contains(q.val)){
return q;
}
q = map_236.get(q.val);
}
return null;
}
//辅助函数236-2
public void dfs_236_2(TreeNode root){
if(root.left != null){
map_236.put(root.left.val, root);
dfs_236_2(root.left);
}
if(root.right != null){
map_236.put(root.right.val, root);
dfs_236_2(root.right);
}
}
//辅助函数-236-1
public boolean dfs_236(TreeNode root, TreeNode p, TreeNode q){
if(root == null){
return false;
}
boolean lson = dfs_236(root.left, p, q);
boolean rson = dfs_236(root.right, p, q);
if((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))){
ans_236 = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
第一种方法还是递归，这个递归主要是要分清楚这个条件，判断左子树或者右子树是否包含目标节点，并且判断当前节点是不是目标节点
第二种方法将所有的父子关系存到一个map当中
124 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
//124，二叉树中的最大路径和
int max_124 = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
return maxPathSum_124(root);
}
public int maxPathSum_124(TreeNode root) {
if(root == null){
return 0;
}
int left = Math.max(0, maxPathSum_124(root.left));
int right = Math.max(0, maxPathSum_124(root.right));
max_124 = Math.max(max_124, left + right + root.val);
return Math.max(left, right) + root.val;
}
这个思想就是递归来处理每一个节点，后序遍历，注意负数以及节点只能取左右节点的较大者，这样才能继续进行延展
200 岛屿数量
给你一个由 '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
//200，岛屿数量
public int numIslands(char[][] grid) {
//深度搜索DFS
/*int count = 0;
int m = grid.length;
int n = grid[0].length;
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(grid[i][j] == '1'){
count++;
dfs_200(grid, i, j);
}
}
}
return count;*/
//广度搜索BFS
/*int count = 0;
int m = grid.length;
int n = grid[0].length;
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(grid[i][j] == '1'){
count++;
Queue<Integer> queue = new LinkedList<>();
queue.offer(i * n + j);
while(!queue.isEmpty()){
Integer id = queue.remove();
int row = id / n;
int col = id % n;
if(row - 1 >= 0 && grid[row - 1][col] == '1'){
queue.offer((row - 1) * n + col);
grid[row - 1][col] = '0';
}
if(row + 1 < m && grid[row + 1][col] == '1'){
queue.offer((row + 1) * n + col);
grid[row + 1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col - 1] == '1'){
queue.offer(row * n + col - 1);
grid[row][col - 1] = '0';
}
if(col + 1 < n && grid[row][col + 1] == '1'){
queue.offer(row * n + col + 1);
grid[row][col + 1] = '0';
}
}
}
}
}
return count;*/
//并查集
if(grid == null || grid.length == 0){
return 0;
}
int m = grid.length;
int n = grid[0].length;
UnionFind uf = new UnionFind(grid);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
grid[i][j] = '0';
if(i - 1 >= 0 && grid[i - 1][j] == '1'){
uf.union(i * n + j, (i - 1) * n + j);
}
if(i + 1 < m && grid[i + 1][j] == '1'){
uf.union(i * n + j, (i + 1) * n + j);
}
if(j - 1 >= 0 && grid[i][j - 1] == '1'){
uf.union(i * n + j, i * n + j - 1);
}
if(j + 1 < n && grid[i][j + 1] == '1'){
uf.union(i * n + j, i * n + j + 1);
}
}
}
}
return uf.getCount();
}
//辅助函数-200-深度优先
public void dfs_200(char[][] grid, int i, int j){
int m = grid.length;
int n = grid[0].length;
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != '1'){
return;
}
grid[i][j] = '0';
dfs_200(grid, i + 1, j);
dfs_200(grid, i - 1, j);
dfs_200(grid, i, j + 1);
dfs_200(grid, i, j - 1);
}
//辅助函数-200-并查集
class UnionFind{
int count;
int[] parent;
int[] rank;
public UnionFind(char[][] grid){
int m = grid.length;
int n = grid[0].length;
count = 0;
parent = new int[m * n];
rank = new int[m * n];
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(grid[i][j] == '1'){
count++;
parent[i * n + j] = i * n + j;
}
rank[i * n + j] = 0;
}
}
}
public int find(int i){
if(parent[i] != i){
parent[i] = find(parent[i]);
}
return parent[i];
}
public void union(int i, int j){
int rootx = find(i);
int rooty = find(j);
if(rootx != rooty){
if(rank[rootx] > rank[rooty]){
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
}else{
parent[rooty] = rootx;
rank[rootx]++;
}
count--;
}
}
public int getCount(){
return count;
}
}
第一种方法就是深度优先，每次找到1，就往上下左右依次查找周围是否为1，如果为1就置0
第二种方法就是光度搜索，这样可以只需要一个队列就可以，节约空间
第三种方法是并查集，并查集主要就是如果是两个相邻的1，则第二个节点的父节点指向第一个节点，并且将第一个节点的rank+1，这样就使得各个不相连的区域分隔开了，这样就找到了独立的岛屿。
994 腐烂的橘子
在给定的 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 。
//994，腐烂的橘子
int[] dr_994 = new int[]{-1, 0, 1, 0};
int[] dc_994 = new int[]{0, 1, 0, -1};
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<Integer> queue = new LinkedList<>();
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 2){
int code = i * n + j;
queue.offer(code);
map.put(code, 0);
}
}
}
int ans = 0;
while(!queue.isEmpty()){
int code = queue.poll();
int row = code / n;
int col = code % n;
for(int i = 0 ; i < 4 ; i++){
int newRow = row + dr_994[i];
int newCol = col + dc_994[i];
if(newRow >= 0 && newRow < m && newCol >= 0 && newCol < n){
if(grid[newRow][newCol] == 1){
grid[newRow][newCol] = 2;
int newCode = newRow * n + newCol;
queue.offer(newCode);
map.put(newCode, map.get(code) + 1);
ans = map.get(newCode);
}
}
}
}
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(grid[i][j] == 1){
return -1;
}
}
}
return ans;
}
这里主要是多源BFS广度搜索，而且采用队列的先进先出，这样最后一次操作就是最终的结果
207 课程表
你这个学期必须选修 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 。这是不可能的。
//207，课程表
List<List<Integer>> edges_207;
int[] visited_207;
boolean valid_207 = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges_207 = new ArrayList<List<Integer>>();
visited_207 = new int[numCourses];
for(int i = 0; i < numCourses; i++){
edges_207.add(new ArrayList<>());
}
for(int[] info : prerequisites){
edges_207.get(info[1]).add(info[0]);
}
for(int i = 0 ; i < numCourses && valid_207; i++){
if(visited_207[i] == 0){
dfs_207(i);
}
}
return valid_207;
}
//辅助函数-207
public void dfs_207(int u){
visited_207[u] = 1;
for(int i : edges_207.get(u)){
if(visited_207[i] == 0){
dfs_207(i);
if(!valid_207){
return;
}
} else if (visited_207[i] == 1) {
valid_207 = false;
return;
}
}
visited_207[u] = 2;
}
采用的是深度搜索的方法，并且伴随有三个状态，未使用，在使用，已使用，在深度搜索的过程中如果遇到了已使用直接返回，如果遇到在使用，更深入
208 实现前缀树
前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 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
//208，实现Trie（前缀树）
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for(int i = 0 ; i < word.length() ; i++){
int index = word.charAt(i) - 'a';
if(node.children[index] == null){
node.children[index] = new Trie();
}
node = node.children[index];
}
node.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){
Trie node = this;
for(int i = 0 ; i < prefix.length() ; i++){
int index = prefix.charAt(i) - 'a';
if(node.children[index] == null){
return null;
}
node = node.children[index];
}
return node;
}
}
这里采用一个字典的思想，读取一个字符如果在字典中不存在就创建一个节点，然后指向一个全新的字典，一层一层的
46 全排列
给定一个不含重复数字的数组 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]]
//46，全排列
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
for(int num : nums){
path.add(num);
}
backtrack_46(res, path, 0);
return res;
}
//辅助函数-46-回溯
public void backtrack_46(List<List<Integer>> res, List<Integer> path, int start){
if(start == path.size()){
res.add(new ArrayList<>(path));
return ;
}
for(int i = start ; i < path.size() ; i++){
Collections.swap(path, i, start);
backtrack_46(res, path, start + 1);
Collections.swap(path, i, start);
}
}
回溯我觉得是递归加上一个状态恢复，依次查找所有的可能的解
一般的伪代码为：
递归函数：
if 符合条件：
添加结果
return
开始循环：
处理节点
递归
撤销处理节点
78 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
//78，子集
List<List<Integer>> res_78 = new ArrayList<>();
List<Integer> path_78 = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
//二进制位按位运算
/*List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int n = nums.length;
for(int mask = 0 ; mask < (1 << n) ; mask++){
path.clear();
for(int i = 0 ; i < n ; i++){
if((mask & (1 << i)) != 0){
path.add(nums[i]);
}
}
res.add(new ArrayList<>(path));
}
return res;*/
//递归，回溯，每一个都有两种状态，选择和未选择
res_78 = new ArrayList<>();
path_78 = new ArrayList<>();
backtrack_78(nums, 0);
return res_78;
}
//辅助函数-78-回溯
public void backtrack_78(int[] nums, int start){
if(start == nums.length){
res_78.add(new ArrayList<>(path_78));
return ;
}
//选择当前位置
path_78.add(nums[start]);
backtrack_78(nums, start + 1);
//不选择当前位置
path_78.remove(path_78.size() - 1);
backtrack_78(nums, start + 1);
}
第一种方法就是二进制的按位运算，如果该位为1，则将这个元素放入临时答案列表
第二种方法主要是每一个元素都只会有两种操作，选择和不选择，这就可以使用回溯的方法
17 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "2"
输出：["a","b","c"]
//17，电话号码的字母组合
List<String> res_17 = new ArrayList<>();
StringBuilder path_17 = new StringBuilder();
String[] phone_17 = new String[]{
"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
backtrack_17(digits, 0);
return res_17;
}
//辅助函数-17-回溯
public void backtrack_17(String digits, int index){
if(index == digits.length()){
if(path_17.length() != 0){
res_17.add(path_17.toString());
}
return ;
}
char digit = digits.charAt(index);
String letters = phone_17[digit - '0' - 1];
for(int i = 0 ; i <letters.length() ; i++){
path_17.append(letters.charAt(i));
backtrack_17(digits, index + 1);
path_17.deleteCharAt(path_17.length() - 1);
}
}
还是回溯的问题，记好一般的模板思路
39 组合总和
给你一个 无重复元素 的整数数组 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
输出: []
//39，组合总和
List<List<Integer>> res_39 = new ArrayList<>();
List<Integer> path_39 = new ArrayList<>();
int sum_39 = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtrack_39(candidates, target, 0);
return res_39;
}
//辅助函数-39-回溯
public void backtrack_39(int[] candidates, int target, int index){
if(sum_39 >= target){
if(sum_39 == target){
res_39.add(new ArrayList<>(path_39));
}
return ;
}
for(int i = index ; i < candidates.length ; i++){
sum_39 += candidates[i];
path_39.add(candidates[i]);
backtrack_39(candidates, target, i);
sum_39 -= candidates[i];
path_39.remove(path_39.size() - 1);
}
}
这个题要注意的点就是再后面递归的时候需要加上这个当前的index，不然这样会存在相同的解
22 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
//22，括号生成
List<String> res_22 = new ArrayList<>();
StringBuilder path_22 = new StringBuilder();
public List<String> generateParenthesis(int n) {
backtrack_22(n, 0, 0);
return res_22;
}
//辅助函数-22-回溯
public void backtrack_22(int n, int open, int close){
if(path_22.length() == 2 * n){
res_22.add(path_22.toString());
return ;
}
if(open < n){
path_22.append('(');
backtrack_22(n, open + 1, close);
path_22.deleteCharAt(path_22.length() - 1);
}
if(close < open){
path_22.append(')');
backtrack_22(n, open, close + 1);
path_22.deleteCharAt(path_22.length() - 1);
}
}
回溯法另一个关键就是i什么时候开始回溯，这个题就是抓住合法的序列的规则，来设置回溯的条件
79 单词搜索
给定一个 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
//79，单词搜索
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
int[][] visited = new int[m][n];
for(int i = 0 ; i < board.length ; i++){
for(int j = 0 ; j < board[0].length ; j++){
boolean flag = backtrack_79(board, word, visited, i, j, 0);
if(flag) {
return true;
}
}
}
return false;
}
//辅助函数-79-回溯
public boolean backtrack_79(char[][] board, String word, int[][] visited, int i, int j, int index){
if(board[i][j] != word.charAt(index)){
return false;
}else if(index == word.length() - 1){
return true;
}
visited[i][j] = 1;
boolean result = false;
int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for(int[] dir : directions){
int newI = i + dir[0];
int newJ = j + dir[1];
if(newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length){
if(visited[newI][newJ] == 0){
boolean flag = backtrack_79(board, word, visited, newI, newJ, index + 1);
if(flag){
result = true;
break;
}
}
}
}
visited[i][j] = 0;
return result;
}
注意回溯也是可以添加返回值的，还要就是注意这个标记是否已经访问过该数组
131 分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
//131，分割回文串
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
backtrack_131(res, path, s, 0);
return res;
}
//辅助函数-131-回溯
public void backtrack_131(List<List<String>> res, List<String> path, String s, int index){
if(index == s.length()){
res.add(new ArrayList<>(path));
return;
}
for(int i = index ; i < s.length() ; i++){
if(isPalindrome_131(s, index, i)){
path.add(s.substring(index, i + 1));
backtrack_131(res, path, s, i + 1);
path.remove(path.size() - 1);
}
}
}
//辅助函数-131-判断回文
public boolean isPalindrome_131(String s, int left, int right){
while(left < right){
if(s.charAt(left++) != s.charAt(right--)){
return false;
}
}
return true;
}
这里就是分割源字符串，判断前面的是不是回文子串，注意传递的这个索引调教，以及这个终止条件
51 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"]]
//51，N皇后
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
int[] path = new int[n];
Arrays.fill(path, -1);
Set<Integer> col = new HashSet<>();
Set<Integer> left_to_right = new HashSet<>();
Set<Integer> right_to_left = new HashSet<>();
backtrack_51(res, path, n, col, left_to_right, right_to_left, 0);
return res;
}
//辅助函数-51-回溯
public void backtrack_51(List<List<String>> res, int[] path, int n, Set<Integer> col,
Set<Integer> left_to_right, Set<Integer> right_to_left, int row){
if(row == n){
List<String> board = generateBoard(path, n);
res.add(board);
}else{
for(int i = 0 ; i < n ; i++){
if(col.contains(i)){
continue;
}
int left_diagonal = row - i;
if(left_to_right.contains(left_diagonal)){
continue;
}
int right_diagonal = row + i;
if(right_to_left.contains(right_diagonal)){
continue;
}
path[row] = i;
col.add(i);
left_to_right.add(left_diagonal);
right_to_left.add(right_diagonal);
backtrack_51(res, path, n, col, left_to_right, right_to_left, row + 1);
path[row] = -1;
col.remove(i);
left_to_right.remove(left_diagonal);
right_to_left.remove(right_diagonal);
}
}
}
//辅助函数-51-生成棋盘
public List<String> generateBoard(int[] path, int n){
List<String> board = new ArrayList<>();
for(int i = 0 ; i < n ; i++){
char[] row = new char[n];
Arrays.fill(row, '.');
row[path[i]] = 'Q';
board.add(new String(row));
}
return board;
}
本题难点我觉得是如何判断当前的这个皇后的位置合法，这个斜线集合的思路需要学习
35 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
//35，搜索插入位置
public int searchInsert(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while(low < high){
int mid = (high + low) / 2;
if(nums[mid] == target){
return mid;
} else if (nums[mid] < target) {
low = mid + 1;
}else{
high = mid - 1;
}
}
if(nums[low] < target){
return low + 1;
}else{
return low;
}
}
基础的二分查找
74 搜索二维矩阵
给你一个满足下述两条属性的 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
//74，搜索二维矩阵
public boolean searchMatrix_74(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int low = 0;
int high = m * n - 1;
while(low <= high){
int mid = (low + high) / 2;
int i = mid / n;
int j = mid % n;
if(target == matrix[i][j]){
return true;
}else if(target < matrix[i][j]){
high = mid - 1;
}else if(target > matrix[i][j]){
low = mid + 1;
}
}
return false;
}
本题就是两次二分和一次二分的区别，两次二分就是先对列再对行，一次二分就是整体都是一个递增序列，直接整体来进行二分，但是时间复杂度是一样的
34 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 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]
//34，在排序数组中查找元素的第一个和最后一个位置
public int[] searchRange(int[] nums, int target) {
int low = 0;
int i = 0;
int high = nums.length - 1;
int[] res = new int[]{-1, -1};
if(nums.length == 0){
return res;
}
while(low <= high){
int mid = (low + high) / 2;
if(nums[mid] == target){
int left = mid - 1;
int right = mid + 1;
while(left >= 0 && nums[left] == target){
left--;
}
res[i++] = left;
while(right < nums.length && nums[right] == target){
right++;
}
res[i] = right;
return new int[]{left + 1, right - 1};
} else if (nums[mid] < target) {
low = mid + 1;
}else{
high = mid - 1;
}
}
return res;
}
当前的这个解法，会存在最坏的情况是O(n),最优做法应该是依次找左边界和右边界
33 搜索旋转排序数组
整数数组 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
//33，搜索旋转排序数组
public int search(int[] nums, int target) {
int n = nums.length;
if(n == 0) return -1;
if(n == 1) return nums[0] == target ? 0 : -1;
int l = 0,r = n - 1;
while(l <= r){
int mid = (l + r) / 2;
if(nums[mid] == target) return mid;
if(nums[0] <= nums[mid]){
if(nums[0] <= target && target < nums[mid]){
r = mid - 1;
}else{
l = mid + 1;
}
}else{
if(nums[mid] < target && target <= nums[n - 1]){
l = mid + 1;
}else{
r = mid - 1;
}
}
}
return -1;
}
这里首先判断左右那一部分是有序的，再判断目标和mid处于哪一个区间，这也是二分的一种，只是判断条件较为复杂
153 寻找旋转排序数组中的最小值
已知一个长度为 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 次得到输入数组。
//153，寻找旋转排序数组中的最小值
public int findMin(int[] nums) {
int n = nums.length;
if(n == 1) return nums[0];
int l = 0 , r = n - 1;
while(l < r){
if(r - l == 1){
return Math.min(nums[l], nums[r]);
}
int mid = (l + r) / 2;
if(nums[mid] >= nums[r]){
l = mid;
}else{
r = mid;
}
}
return 0;
}
二分查找的思想就是每次都排除一半的内容
4 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//4，寻找两个正序数组的中位数
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int totallength = m + n;
if(totallength % 2 == 1){
int minIndex = totallength / 2;
double res = getKthElement_4(nums1, nums2, minIndex + 1);
return res;
}else{
int minIndex1 = totallength / 2 + 1,mixIndex2 = totallength / 2;
double res = (getKthElement_4(nums1, nums2, minIndex1) + getKthElement_4(nums1, nums2, mixIndex2)) / 2.0;
return res;
}
}
//辅助函数-4-获取第k个元素
public double getKthElement_4(int[] nums1, int[] nums2, int k){
int m = nums1.length;
int n = nums2.length;
int index1 = 0, index2 = 0;
while(true){
//边界情况
if(index1 == m){
return nums2[index2 + k - 1];
}
if(index2 == n){
return nums1[index1 + k - 1];
}
if(k == 1){
return Math.min(nums1[index1], nums2[index2]);
}
//正常情况
int half = k / 2;
int newIndex1 = Math.min(index1 + half, m) - 1;
int newIndex2 = Math.min(index2 + half, n) - 1;
int pivot1 = nums1[newIndex1],pivot2 = nums2[newIndex2];
if(pivot1 <= pivot2){
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
}else{
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
通俗思想就是，想要查找第k个元素（中位数），这就意味着抛弃K - 1个元素，这就意味着对比两个元素的抛弃k - 1个元素，注意一些边界情况
20 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
**输入：**s = "()"
**输出：**true
示例 2：
**输入：**s = "()[]{}"
**输出：**true
示例 3：
**输入：**s = "(]"
**输出：**false
示例 4：
**输入：**s = "([])"
**输出：**true
示例 5：
**输入：**s = "([)]"
**输出：**false
//20，有效的括号
public boolean isValid(String s) {
int n = s.length();
if(n % 2 == 1){
return false;
}
Map<Character, Character> map = new HashMap<>(){{
put(')', '(');
put('}', '{');
put(']', '[');
}};
Deque<Character> stack = new LinkedList<>();
for(int i = 0 ; i < n ; i++){
char c = s.charAt(i);
if(map.containsKey(c)){
if(stack.isEmpty() || stack.peek() != map.get(c)){
return false;
}
stack.pop();
}else{
stack.push(c);
}
}
return stack.isEmpty();
}
栈的基本应用，但是注意在写代码的时候要注意对扩展可见，对修改不可见
155 最小栈
设计一个支持 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.
//155，最小栈
class MinStack {
//队列实现栈，采用一个辅助栈来实现最小值的获取
/*Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack() {
this.minStack = new LinkedList<>();
this.stack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(minStack.peek(), val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}*/
//第一直觉就是链表
private Node top;
private class Node{
int val;
int min;
Node next;
//构造函数
Node(int val, int min){
this.val = val;
this.min = min;
this.next = null;
}
}
public MinStack() {
top = null;
}
public void push(int val) {
if(top == null){
top = new Node(val, val);
}else{
Node newNode = new Node(val, Math.min(top.min, val));
newNode.next = top;
top = newNode;
}
}
public void pop() {
if(top == null){
return;
}
top = top.next;
}
public int top() {
return top.val;
}
public int getMin() {
return top.min;
}
}
第一种方法是链表，采用尾插法来进行新增，同时节点有一个min属性，这样就可以实现最小值的查找
第二种方法是采用一个辅助队列来实现最小栈
739 每日温度
给定一个整数数组 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]
//739，每日温度
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i = 0 ; i < n ; i++){
while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
int index = stack.pop();
res[index] = i - index;
}
stack.push(i);
}
return res;
}
单调栈的思想，始终保持栈中的元素升序或者降序，如果新来的元素不符合就出栈，直到符合，还要就是这题栈中存储的是角标来找到位置。
84 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
//84，柱状图中最大的矩形
public int largestRectangleArea(int[] heights) {
//单调栈-左右边界
/*int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i = 0 ; i < n ; i++){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for(int i = 0 ; i < n ; i++){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[n - 1 - i]){
stack.pop();
}
right[n - i - 1] = stack.isEmpty() ? n : stack.peek();
stack.push(n - 1 - i);
}
int ans = 0;
for(int i = 0 ; i < n ; i++){
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;*/
//单调栈-哨兵
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0 ; i < n ; i++){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
right[stack.pop()] = i;
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
int ans = 0;
for(int i = 0 ; i < n ; i++){
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
还是单调栈，在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景
215 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
//215，数组中的第K个最大元素
public int findKthLargest(int[] nums, int k) {
//快速排序
/*int n = nums.length;
return quickSelect_215(nums, 0, n - 1, n- k);*/
//堆排序
int n = nums.length;
buildMaxHeap_215(nums, n);
for(int i = n - 1 ; i >= nums.length - k + 1 ; i--){
swap_215(nums, 0, i);
n--;
maxHeapify_215(nums, 0, n);
}
return nums[0];
}
//辅助函数-215-建堆
public void buildMaxHeap_215(int[] nums, int heapSize){
for(int i = heapSize / 2 - 1; i >= 0 ; i--){
maxHeapify_215(nums, i, heapSize);
}
}
//辅助函数-215-堆化
public void maxHeapify_215(int[] nums, int i, int heapSize){
int left = 2 * i + 1, right = 2 * i + 2;
int largest = i;
if(left < heapSize && nums[left] > nums[largest]){
largest = left;
}
if(right < heapSize && nums[right] > nums[largest]){
largest = right;
}
if(largest != i){
swap_215(nums, i, largest);
maxHeapify_215(nums, largest, heapSize);
}
}
//辅助函数-215-交换
public void swap_215(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
//辅助函数-215-快速选择
public int quickSelect_215(int[] nums, int left, int right, int k){
if(left == right){
return nums[left];
}
int x = nums[left];
int i = left - 1, j = right + 1;
while(i < j){
do i++; while(nums[i] < x);
do j--; while(nums[j] > x);
if(i < j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
if(k <= j){
return quickSelect_215(nums, left, j, k);
}else{
return quickSelect_215(nums, j + 1, right, k);
}
}
第一种方式就是快速排序：快速排序是对于一个序列，随机选取一个元素，使得这个元素左边都是小于该元素，右边的都大于该元素，具体实现是有两个指针，左指针从左往右找大于该元素的值，右指针从右往左找大于该元素的值，然后交换左右指针，直到左指针不小于右指针（位置），然后再递归更新其他的区间，每一次都会使得一个元素到达最终的位置，所以查找第K个也就只需要循环K次，时间复杂度o（nlogn）
第二种方式是大根堆，每次都删除最大的根，循环k次之后堆顶就是目标值，对与堆，主要有建堆，调整堆和交换元素三部分,最主要的就是调整堆，调整堆就是每次将最大值放到数组的第1个元素，依次递归
374 前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
**输入：**nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
**输入：**nums = [1], k = 1
输出：[1]
示例 3：
**输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
//347，前K个高频元素
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int n = freq.size();
int[] heap = new int[n];
int idx = 0;
for (int key : freq.keySet()) {
heap[idx++] = key;
}
// 建最大堆（按频次）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify_347(heap, n, i, freq);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
swap_347(heap, 0, n - 1);
res[i] = heap[n - 1]; // 取堆顶被换到末尾的最大频次元素
n--;
heapify_347(heap, n, 0, freq);
}
return res;
}
// 辅助函数-347-堆化（按频次）
public void heapify_347(int[] heap, int heapSize, int i, Map<Integer, Integer> freq) {
int largest = i;
while (true) {
int left = 2 * largest + 1, right = 2 * largest + 2;
int candidate = largest;
if (left < heapSize && freq.get(heap[left]) > freq.get(heap[candidate])) {
candidate = left;
}
if (right < heapSize && freq.get(heap[right]) > freq.get(heap[candidate])) {
candidate = right;
}
if (candidate == largest) break;
swap_347(heap, largest, candidate);
largest = candidate;
}
}
// 辅助函数-347-交换
public void swap_347(int[] res, int i, int j) {
int temp = res[i];
res[i] = res[j];
res[j] = temp;
}
还是用大顶堆
195 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
//295，数据流的中位数
class MedianFinder {
//左边大顶堆，右边小顶堆，平衡左右堆
/*PriorityQueue<Integer> maxHeap;
PriorityQueue<Integer> minHeap;
public MedianFinder() {
minHeap = new PriorityQueue<Integer>((a, b) -> (b - a));
maxHeap = new PriorityQueue<Integer>((a, b) -> (a - b));
}
public void addNum(int num) {
if(minHeap.isEmpty() || num <= minHeap.peek()){
minHeap.offer(num);
if(minHeap.size() > maxHeap.size() + 1){
maxHeap.offer(minHeap.poll());
}
}else{
maxHeap.offer(num);
if(maxHeap.size() > minHeap.size()){
minHeap.offer(maxHeap.poll());
}
}
}
public double findMedian() {
if(maxHeap.size() < minHeap.size()){
return minHeap.peek();
}
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}*/
//利用红黑树使其有序，然后利用双指针来指向中位数的位置
TreeMap<Integer, Integer> treeMap;
int count;
int[] left;
int[] right;
public MedianFinder() {
treeMap = new TreeMap<Integer, Integer>();
count = 0;
left = new int[2];
right = new int[2];
}
public void addNum(int num) {
treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
if(count == 0){
left[0] = right[0] = num;
left[1] = right[1] = 1;
} else if ((count & 1) != 0){
if(num < left[0]){
decrease_295(left);
}else{
increase_295(right);
}
}else{
if(num > left[0] && num < right[0]){
increase_295(left);
decrease_295(right);
} else if (num >= right[0]) {
increase_295(left);
}else{
decrease_295(right);
System.arraycopy(right, 0, left, 0, 2);
}
}
count++;
}
public double findMedian() {
return (left[0] + right[0]) / 2.0;
}
private void decrease_295(int[] iterator){
iterator[1]--;
if(iterator[1] == 0){
iterator[0] = treeMap.floorKey(iterator[0] - 1);
iterator[1] = treeMap.get(iterator[0]);
}
}
private void increase_295(int[] iterator){
iterator[1]++;
if(iterator[1] > treeMap.get(iterator[0])){
iterator[0] = treeMap.ceilingKey(iterator[0] + 1);
iterator[1] = 1;
}
}
}
第一个方法是中位数左侧为大顶堆，右侧为小顶堆
第二个方法首先需要是有序序列，双指针指向决定中位数的两个数，调整这两指针的位置
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, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
//121，买卖股票的最佳时机
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int maxProfit = 0;
for(int price : prices){
if(price < min){
min = price;
}
if(price - min > maxProfit){
maxProfit = price - min;
}
}
return maxProfit;
}
贪心算法的核心思想：
- 每一步选择中都采取当前状态下最优的选择，希望通过一系列局部最优的选择，最终达到全局最优解
特点：
- 不回溯，一旦做出选择，就不再回头修改，因此效率高，但不一定总能得到最优解
55 跳跃游戏
给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。
//55，跳跃游戏
public boolean canJump(int[] nums) {
int n = nums.length;
int farthest = 0;
for(int i = 0 ; i < n ; i++){
if(i > farthest){
return false;
}
farthest = Math.max(farthest, i + nums[i]);
if(farthest >= n - 1){
return true;
}
}
return false;
}
判断每一步是否可以到达，记录一个最大值，和当前位置+当前位置的值和来比较，相当于就是没走一步，记录的最大值减1和当前值比较
45 跳跃游戏Ⅱ
给定一个长度为 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
//45，跳跃游戏II
public int jump(int[] nums) {
int n = nums.length;
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for(int i = 0 ; i < n - 1 ; i++){
farthest = Math.max(farthest, i + nums[i]);
if(i == currentEnd){
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
这个算法是【start，start能到达的最远位置】记录这个区间之间的元素可以到达的最远位置，当走到尾部边界的时候就更新尾端为之前找到的最远位置。
763 划分字母区间
给你一个字符串 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]
//763，划分字母区间
public List<Integer> partitionLabels(String s) {
int n = s.length();
int[] last = new int[26];
for(int i = 0 ; i < n ; i++){
last[s.charAt(i) - 'a'] = i;
}
List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for(int i = 0 ; i < n ; i++){
end = Math.max(end, last[s.charAt(i) - 'a']);
if(i == end){
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
和上面的一题是一样的，主要就在于这次需要先遍历一下当前序列，找到元素的最远位置，相当于最多跳多远
70 爬楼梯
假设你正在爬楼梯。需要 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 阶
//70，爬楼梯
public int climbStairs(int n) {
int a = 1, b = 2;
if(n == 1){
return a;
}
if(n == 2){
return b;
}
for(int i = 3 ; i <= n ; i++){
int temp = b;
b = a + b;
a = temp;
}
return b;
}
动态规划的五步：
- 确定状态：用什么变量来表示子问题
- 确定递推关系：如何由子问题推出原问题
- 初始化：最小子问题的解是什么
- 确定遍历顺序：从小到大还是倒序
- 返回结果：最终要求是什么
118 杨辉三角
给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。
在**「杨辉三角」**中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
//118，杨辉三角
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for(int i = 0 ; i < numRows ; i++){
List<Integer> list = new ArrayList<>();
for(int j = 0 ; j <= i ; j++){
if(j == 0 || j == i){
list.add(1);
}else{
list.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
}
res.add(list);
}
return res;
}
这个还是动态规划，唯一不一样的就是这里的边界值比较多
198 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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 。
//198，打家劫舍
public int rob(int[] nums) {
int n = nums.length;
if(n == 0){
return 0;
}
int[] dp = new int[n];
dp[0] = nums[0];
if(n == 1){
return dp[0];
}
dp[1] = Math.max(nums[0], nums[1]);
for(int i = 2 ; i < n ; i++){
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}
问题dp【i】可以划分为dp【i-1】和dp【i-2】+nums[i]两者的最大值
279 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
//279，完全平方数
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];
}
f(i) = 1 + min(j=0,根号i)(f(i - j * j)) 这种问题主要就是找到子问题
322 零钱兑换
给你一个整数数组 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
//322，零钱兑换
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 0;
for(int i = 1 ; i <= amount ; i++){
dp[i] = amount + 1;
for(int coin : coins){
if(i >= coin){
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
拆问题，拆成f(i) = min(f(i), min(coin1:coinn)(f(i - coinn)) + 1)
139 单词拆分
给你一个字符串 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
//139，单词拆分
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j < i ; j++){
if(dp[j] && wordSet.contains(s.substring(j, i))){
dp[i] = true;
break;
}
}
}
return dp[n];
}
这一题我觉得主要是这个判断元素在不在这个里面的比较难一点，学一下substring
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 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
//300，最长递增子序列
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < i ; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxLen = 0;
for(int len : dp){
maxLen = Math.max(maxLen, len);
}
return maxLen;
}
每次右边界变化都需要左边界置零
152 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
//152，乘积最大子数组
public int maxProduct(int[] nums) {
int n = nums.length;
long max = nums[0];
long min = nums[0];
int ans = nums[0];
for(int i = 1 ; i < n ; i++){
long mx =max;
long mn = min;
max = Math.max(mx * nums[i], Math.max(min * nums[i], nums[i]));
min = Math.min(mn * nums[i], Math.min(mx * nums[i], nums[i]));
if(min < -1 << 31){
min = nums[i];
}
ans = Math.max(ans, (int) max);
}
return ans;
}
这个题不能简单的f(i) = max{f(i-1) * nums[i], nums[i]}，因为可能存在负数，导致不单调，所以这里维护两个变量，max和min分别表示，i位置能实现的最大值和最小值，这样就可以处理负值的出现
416 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
//416，分割等和子集
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];
}
这个题有个关键地方就是将这个划分问题等价为找是否存在一个子序列的和为全部元素的和的一半，这样就变为了一个0-1背包问题
32 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
//32，最长有效括号
public int longestValidParentheses(String s) {
//动态规划
/*int n = s.length();
char[] c = s.toCharArray();
int[] dp = new int[n];
int maxAns = 0;
for(int i = 1 ; i < n ; i++){
if(c[i] == ')'){
if(c[i - 1] == '('){
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
}else{
if(i - dp[i - 1] - 1 >= 0 && c[i - dp[i - 1] - 1] == '('){
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
}
}
maxAns = Math.max(maxAns, dp[i]);
}
return maxAns;*/
//栈
int n = s.length();
Deque<Integer> stack = new LinkedList<>();
stack.push(-1);
int maxAns = 0;
for(int i = 0 ; i < n ; 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;
}
第一种方法就是动态规划，这里的动态规划是如果当前位置的字符是），则开始判断当前位置的dp【i】，主要分为两种情况
- 如果dp[i-1]是（，这样就能够闭合，dp【i】 = dp【i-1】 + 2
- 如果dp【i- 1】不是，判断一下这个i-1位置减去dp【i-1】的长度再减去2的位置是不是（即dp【i】 = dp【i-1】+dp【i-dp【i-1】-2】+2
第二种方式就是栈：这里的栈存入的不是元素，而是元素的位置，如果再存在有位置匹配结合的要注意栈要存入角标
62 不同路径
一个机器人位于一个 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
//62，不同路径
public int uniquePaths(int m, int n) {
//二维数组
/*int[][] dp = new int[m][n];
for (int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
dp[0][j] = 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];*/
//滚动数组
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i = 1 ; i < m ; i++){
for(int j = 1 ; j < n ; j++){
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
简单的二维动态规划，两个维度，dp【i】【j】 =dp【i-1】【j】+dp【i】【j-1】 ，这里有一个优化方法就是滚动数组
64 最小路径和
给定一个包含非负整数的 *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
//64，最小路径和
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(i == 0 && j == 0){
dp[i][j] = grid[i][j];
}
if(i == 0 && j > 0){
dp[i][j] = dp[i][j - 1] + grid[i][j];
}
if(j == 0 && i > 0){
dp[i][j] = dp[i - 1][j] + grid[i][j];
}
if(i > 0 && j > 0){
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1];
}
经典的动态规划，dp【i】[j] = Math.min(dp【i - 1】[j], dp【i】[j - 1]) + grid【i】[j];
5 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
//5，最长回文字串
public String longestPalindrome(String s) {
int len = s.length();
if(len < 2){
return s;
}
int maxLen = 1;
int begin = 0;
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] chars = s.toCharArray();
//这里注意遍历顺序，先枚举子串长度，再枚举左边界
for(int L = 2 ; L <= len ; L++){
//枚举左边界
for(int i = 0 ; i < len ; i++){
//由L和i可以确定右边界
int j = L + i - 1;
if(j >= len){
break;
}
if(chars[i] != chars[j]){
dp[i][j] = false;
}else{
if(j - i < 3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i + 1][j - 1];
}
}
if(dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
这种计算长度的要记录角标或者边界，本题在循环的时候要先循环长度，再循环左边界，这样可以计算出右边界的值，转移方程：
dp【i】【j】 = dp【i + 1】【j - 1】
1143 最长公共子序列
给定两个字符串 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 。
//1143，最长公共子序列
public int longestCommonSubsequence(String text1, String text2) {
int m =text1.length();
int n = text2.length();
int[][] dp = new int[m][n];
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(text1.charAt(i) == text2.charAt(j)){
dp[i][j] = (i > 0 && j > 0) ? dp[i - 1][j - 1] + 1 : 1;
}else{
dp[i][j] = Math.max((i > 0) ? dp[i - 1][j] : 0, (j > 0) ? dp[i][j - 1] : 0);
}
}
}
return dp[m - 1][n - 1];
}
两个来比较就拼成一个二维dp，转移方程为：如果两个字符相同就左上角的值加1，如果不同就找上面和左边的值的最大值作为当前值
72 编辑距离
给你两个单词 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')
//72，编辑距离
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for(int i = 0 ; i <= m ; i++){
dp[i][0] = i;
}
for(int j = 0 ; j <= n ; j++){
dp[0][j] = j;
}
for(int i = 1 ; i <= m ; i++){
for(int j = 1 ; j <= n ; j++){
int left = dp[i - 1][j] + 1;
int down = dp[i][j - 1] + 1;
int leftDown = dp[i - 1][j - 1];
if(word1.charAt(i - 1) != word2.charAt(j - 1)){
leftDown += 1;
}
dp[i][j] = Math.min(left, Math.min(down, leftDown));
}
}
return dp[m][n];
}
这里主要是要知道一点，
对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge，单词 B 为 dog 时，我们既可以删除单词 A 的最后一个字符 e，得到相同的 dog，也可以在单词 B 末尾添加一个字符 e，得到相同的 doge；
同理，对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的；
对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为 cat 时，我们修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。
这样以来，本质不同的操作实际上只有三种：
在单词 A 中插入一个字符；
在单词 B 中插入一个字符；
修改单词 A 的一个字符。
这样以来，我们就可以把原问题转化为规模较小的子问题。我们用 A = horse，B = ros 作为例子，来看一看是如何把这个问题转化为规模较小的若干子问题的。
在单词 A 中插入一个字符：如果我们知道 horse 到 ro 的编辑距离为 a，那么显然 horse 到 ros 的编辑距离不会超过 a + 1。这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串，只需要额外的 1 次操作，在单词 A 的末尾添加字符 s，就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串；
在单词 B 中插入一个字符：如果我们知道 hors 到 ros 的编辑距离为 b，那么显然 horse 到 ros 的编辑距离不会超过 b + 1，原因同上；
修改单词 A 的一个字符：如果我们知道 hors 到 ro 的编辑距离为 c，那么显然 horse 到 ros 的编辑距离不会超过 c + 1，原因同上。
那么从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1）
状态转移方程：
136 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
**输入：**nums = [2,2,1]
**输出：**1
示例 2 ：
**输入：**nums = [4,1,2,1,2]
**输出：**4
示例 3 ：
**输入：**nums = [1]
**输出：**1
//136，只出现一次的数字
public int singleNumber(int[] nums) {
int res = 0;
for(int num : nums){
res ^= num;
}
return res;
}
这里技巧是采用位运算的异或运算，即^=
169 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
//169，多数元素
public int majorityElement(int[] nums) {
//hashmap实现
/*Map<Integer, Integer> map = countNums_169(nums);
for(int num : nums){
if(map.get(num) > nums.length / 2){
return num;
}
}
return 0;*/
//排序
/*Arrays.sort(nums);
return nums[nums.length / 2];*/
//随机化
/*Random random = new Random();
int majority = nums.length / 2;
while(true){
int candidate = nums[randRange(random, 0, nums.length)];
if(count0ccurences_169(nums, candidate) > majority){
return candidate;
}
}*/
//分治递归
/*return majorityElementRec_169(nums, 0, nums.length - 1);*/
//Boyer-Moore 投票算法
int count = 0;
int candidate = 0;
for(int num : nums){
if(count == 0){
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
//辅助函数-169-递归
public int majorityElementRec_169(int[] nums, int left, int right){
if(left == right){
return nums[left];
}
int mid = left + (right - left) / 2;
int leftMajor = majorityElementRec_169(nums, left, mid);
int rightMajor = majorityElementRec_169(nums, mid + 1, right);
if(leftMajor == rightMajor){
return leftMajor;
}
int leftCount = countInRange_169(nums, leftMajor, left, right);
int rightCount = countInRange_169(nums, rightMajor, left, right);
return leftCount > rightCount ? leftMajor : rightMajor;
}
//辅助函数-169-区间计数
public int countInRange_169(int[] nums, int candidate, int left, int right){
int count = 0;
for(int i = left ; i <= right ; i++){
if(nums[i] == candidate){
count++;
}
}
return count;
}
//辅助函数-169-随机数
public int randRange(Random random, int min, int max){
return random.nextInt(max - min) + min;
}
//辅助函数-169-计数
public int count0ccurences_169(int[] nums, int candidate){
int count = 0;
for(int num : nums){
if(num == candidate){
count++;
}
}
return count;
}
//辅助函数-169-Map
public Map<Integer, Integer> countNums_169(int[] nums){
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
if(!map.containsKey(num)){
map.put(num, 1);
}else{
map.put(num, map.get(num) + 1);
}
}
return map;
}
五种方法：
- hashMap
- 排序
- 随机数
- 分治递归
- Boyer-Moore 投票算法
75 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
//75，颜色分类
public void sortColors(int[] nums) {
//冒泡排序:相邻两个元素交换
/*int n = nums.length;
for(int i = 0 ; i < n - 1 ; i++){
for(int j = i + 1 ; j < n ; j++){
if(nums[i] > nums[j]){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}*/
//选择排序:每次选择最小的元素放在前面
/*int n = nums.length;
for(int i = 0 ; i < n ; i++){
int minIndex = i;
for(int j = i + 1 ; j < n ; j++){
if(nums[j] < nums[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}*/
//插入排序:每次将当前元素插入到前面已经排序好的序列中
/*int n = nums.length;
for(int i = 1 ; i < n ; i++){
int key = nums[i];
int j = i - 1;
while(j >= 0 && nums[j] > key){
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}*/
//希尔排序：间隔插入排序
/*int n = nums.length;
for(int gap = n / 2 ; gap > 0 ; gap /= 2){
for(int i = gap ; i < n ; i++){
int key = nums[i];
int j = i - gap;
while(j >= 0 && nums[j] > key){
nums[j + gap] = nums[j];
j -= gap;
}
nums[j + gap] = key;
}
}*/
//单指针
/*int n = nums.length;
int ptr = 0;
for(int i = 0 ; i < n ; i++){
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[ptr];
nums[ptr] = temp;
ptr++;
}
}
for(int i = ptr ; i < n ; i++){
if(nums[i] == 1){
int temp = nums[i];
nums[i] = nums[ptr];
nums[ptr] = temp;
ptr++;
}
}*/
//双指针
/*int n = nums.length;
int p0 = 0;
int p1 = 0;
for(int i = 0 ; i < n ; i++){
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
if(p0 < p1){
temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
p0++;
p1++;
}else if(nums[i] == 1){
int temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
p1++;
}
}*/
//双指针简洁版
int n = nums.length;
int p0 = 0;
int p2 = n - 1;
for(int i = 0 ; i <= p2 ; i++){
while(i <= p2 && nums[i] == 2){
int temp = nums[i];
nums[i] = nums[p2];
nums[p2] = temp;
p2--;
}
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
p0++;
}
}
}
不难理解，排序问题，后几种都可以
31 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须**原地**修改，只允许使用额外常数空间。
//31，下一个排列
public void nextPermutation(int[] nums) {
int n = nums.length;
int ptrLeft = n - 2;
int ptrRight = n - 1;
while(ptrLeft >= 0 && nums[ptrLeft] >= nums[ptrLeft + 1]){
ptrLeft--;
}
if(ptrLeft >= 0){
while(ptrRight >= 0 && nums[ptrRight] <= nums[ptrLeft]){
ptrRight--;
}
swap_31(nums, ptrLeft, ptrRight);
}
reverse_31(nums, ptrLeft + 1, n - 1);
}
//辅助函数-31-交换
public void swap_31(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
//辅助函数-31-反转
public void reverse_31(int[] nums, int start, int end){
while(start < end){
swap_31(nums, start, end);
start++;
end--;
}
}
思想是使得每次排列都是幅度最小的，对于左边界，从后往前找第一个非升序的，右边界找第一个大于左边界的，交换位置之后翻转后边的，注意边界值
287 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3 :
输入：nums = [3,3,3,3,3]
输出：3
//287，寻找重复数
public int findDuplicate(int[] nums) {
//双重循环
/*for(int i = 0 ; i < nums.length ; i++){
for(int j = 0 ; j < nums.length ; j++){
if(i != j && nums[i] == nums[j]){
return nums[i];
}
}
}
return -1;*/
//二分查找
/*int n = nums.length;
int l = 1;
int r = nums.length - 1;
int ans = -1;
while(l <= r){
int count = 0;
int mid = (l + r) >> 1;
for (int num : nums) {
if (num <= mid) {
count++;
}
}
if(count <= mid){
l = mid + 1;
}else{
r = mid - 1;
ans = mid;
}
}
return ans;*/
//快慢指针
int slow = nums[0];
int fast = nums[0];
do{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);
slow = nums[0];
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
首先想到的肯定是暴力解，但是超时了
第二种方法主要体现在如果重复的值是target，那么在【1，target - 1】的这个区间里面的每一个数一定是count【i】 <=i，这里的count表示原数组中小于等于i的元素的个数，而对于【target，n-1】这个区间中，由于重复元素的原因，存在count【i】>i，根据这个性质，就可以使用二分查找来确定，目标值在哪个区间了
第三种方法是快慢指针，结合角标和值，看成是一个链表，i->nums[i]，这样的话，重复元素的位置一定会存在入度大于等于2，这样就可以先使用一次快慢指针来找到在环中相遇的位置，然后再次将slow变为起点，每次快指针和慢指针都移动一次，这时如果快慢指针再次相遇就是环的起点了。
数学证明：假设起点到环的入口长度为a，环的入口到环中相遇点的位置是b，环的长度为L，当快慢指针相遇的时候，慢指针走了a+b+kL，快指针走了2（a+b+kL）,可以有a+b+kL = 2(a+b+kL),有a = kL - b;a = (k - 1)L + (L - b)