LeetCode逐题笔记

发表于2022-11-15|更新于2023-05-03|LeetCode

|字数总计:52.2k|阅读时长:228分钟|阅读量:

1、两数之和

length的使用

length

length是属性，是数组的长度，使用时的形式是：数组.length不加括号

例如：
1
2
String[] cp;
int n = cpdomains.length;
length()

length()是字符串自带的方法，是求字符串长度的，使用形式是：str.length()
size()

size()是列表的自带方法，求的是列表的长度，使用形式是：list.size()

2. 两数相加

中等题，考察链表的操作和构造。代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode();
        ListNode p = root;
        int add = 0;
        while (l1!=null || l2!=null || add!=0) {
            int k = add;
            if (l1!=null) {
                k += l1.val;
                l1 = l1.next;
            }
            if (l2!=null) {
                k += l2.val;
                l2 = l2.next;
            }
            if (k > 9) {
                k -= 10;
                add = 1;
            }
            else {
                add = 0;
            }
            ListNode temp = new ListNode(k);
            p.next = temp;
            p = p.next;
        }
        return root.next;
    }
}

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

考察： #滑动窗口 #双指针 #Set

中等题。注意审题，因为 s 由英文字母、数字、符号和空格组成，所以不能使用位运算。这里使用 hashset。代码如下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] sc = s.toCharArray();
        int n = s.length();
        HashSet<Character> set = new HashSet<Character>();
        int i = 0, j = i;
        int res = 0;
        
        while (i<n && j<n) {    // j表示待判断的，i表示起点
            if (i == j && i < n-1) {
                set.add(sc[i]);
                j = i+1;
            }
            if (!set.contains(sc[j])) {    // 表示过去没有
                set.add(sc[j]);     // 当前j可以加入
                res = Math.max(res, j-i+1);
                j++;
            }
            else {     // j下标的元素已经有了，不能继续处理了，需要删i
                set.remove(sc[i]);
                i++;
            }
        }
        return res;
    }
}

4、寻找两个正序数组的中位数

5、最长回文子串

方法一、中心扩张法

注意

注意出现“aaaa”、“aaa”这样相同字符的回文子串，因此需要在第一个while循环中判断从当前i开始左右是否相同。
在完成相同字符的判断后，进行left-1和right+1同时判断，查找回文数。
时间复杂度：O(n^2)

空间复杂度：O(1)

时间换空间

替换

将字符串转为数组的方式有：
1
char[] str = s.toCharArray();
提取字符串中某一下标的字符：
1
char st = s.charAt(3);

方法二、动态规划

二维数组是动态规划最常用的方法

注意

此方法核心在于按照子串长度进行遍历，判断l长度的子串是否为回文子串，即判断除去两个端点的子串是否为回文子串
1中至少要有三个元素。在只有1个元素时，回文子串就是它自己；有两个元素时，如果两个元素相等则为回文子串。
时间复杂度：O(n^2)

空间复杂度：O(n^2)

11、盛最多水的容器

逻辑性很强的题目！！

双指针，一个指向最左边，一个指向最右边，这两个指针所指的相对长的板后面称为长板，相对短的板称为短板。

对于左右指针逼近，容器的底边长度一定是在减小。

容器的盛水量取决于底边长度和短板。

所以！如果移动短板，可能会遇到更短或者相等的板，那是不幸，容量变小；如果遇到长一些的板子，容量可能变小也可能不变也可能变大。

如果移动长板，底边长度一定减小，如果遇到的是长板，因为容器的高取决于短板，且底边变短，所以容量一定减小；如果遇到比自己短，比短板长的板子，和刚刚一样的道理，也是容量变小；如果遇到比短板还短的板子，那更不用说了，短边变成它自己了，容量一定减小。

因此！富贵险中求！如果移动长板，那容量是一定减少的！如果移动短板，有几率容量变大！

所以设置一个max值，每次移动都记录一下容量，当i与j相遇就说明遍历结束，最后返回max即可。

15、三数之和

Listconst<List<Integer>> 的定义

1	List<List<Integer>> result = new ArrayList<List<Integer>>();

List<Integer>的定义

1	List<Integer> r = new ArrayList<Integer>();

List的添加操作

1	list1.add(r); //r必须是list的<>内的类型，在尾部插入

List的搜索操作

1	list1.get(index); //获取list下标为index的数值

List查找某个元素是否在其中

1	list.contains(s); //查找s这个元素是否在list中

int转为Integer
1
2
int a;
Integer b = Integer.valueOf(a);

数组的排序

1	Arrays.sort(nums); //原地修改nums数组

20. 有效的括号

考察： #栈

简单题，利用栈即可。

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

双指针思路

31、下一个排列

思路很强，考验找规律的能力。

例：

对于 123465：

第一步，从后往前找到第一对升序的两个数，也就是46

第二步，从结尾开始到6，找到第一个大于4的数，也就是5

第三步，将4和5对换位置，变成123564

第四步，将6开始到结尾变成升序，变成123546

简化：

第一步，从后往前找到第一对升序的两个数，也就是46

第二步，从6开始到结尾，升序排列，变成123456

第三步，在刚刚升序的部分找到第一个大于4的数，即5，将4和5对换位置，变成123546

其他：

对于已经是最大的数，即从头到尾是越来越小的，它的下一个数是最小的，也就是从头到尾是越来越大的，因此只要对数组进行排序即可。

33、搜索旋转排序数组

遇到时间复杂度O(log n)，二话不说，直接二分查找！

方法一、暴力（不满足log(n)）

方法二、二分法（不完全满足log(n)）

先求出向左移动的次数k，然后再用二分法判定，每次结果也便宜k。

方法三、二分法优化（满足log(n)）

这个方法简单又巧妙。

正常二分后，先判断mid的值是不是target，再看左边和右边哪个是顺序的。

如果nums[left] <= nums[mid]，说明左边是顺序的。再看target是不是再左边区间里，如果是则right = mid-1；否则，left = mid+1，继续在右边找。

如果nums[left] > nums[mid]，说明左边是不规则的，那么右边一定是顺序的。再看target是不是再右边区间里，如果是则left = mid+1；否则，right = mid-1，继续在左边找。

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

遇到时间复杂度O(log n)，二话不说，直接二分查找！

方法一、二分+扩张

先找到值为target的数组的元素的位置，再向两边扩张，找到左右边界。

方法二、二分查找性质

这种方法的思路很妙，要想找到数组中值为target的范围，只要找到数组中>=target和target+1的第一个值的下标。

例：

nums = [5,7,7,8,8,10], target = 8

先找target=8的第一个位置：

left = 0，right = 6，mid = 3，找到了一个，往左边找
left = 0，right = 3，mid = 1，小了
left = 2，right = 3，mid = 2，小了
left = 3，right = 3，mid = 3，当left==right，结束，此时left就是第一个

再找target=9的第一个位置：

left = 0，right = 6，mid = 3，小了
left = 4，right = 6，mid = 5，大了
left = 4，right = 5，mid = 4，小了
left = 5，right = 5，mid = 5，当left==right，结束，此时left就是第一个的位置

除此之外，我们还需要判断target=8的时候到底有没有这个值哦~

注意：

本题的right初始值为n，后来right更新为mid，和我们过去使用的二分法略有不同，因为如果mid就是我需要的那个值，且它就是第一个出现的，按照过去的算法，right=mid-1，最后可能会丢失了这个mid。但是新的算法一直用right保存mid，只要一直在找左区间，就需要将我们的目标范围不停往左边移动，就应该用right保存mid，最后一定会出现left、right、mid相等的情况，也就是左区间。

35. 搜索插入位置

考察： #二分查找

简单题，相当于找>=target 的第一个元素的下标。

39、组合总和⭐

方法一、双端队列+DFS

候选数组里有 2，如果找到了组合总和为 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合。同理考虑 3，如果找到了组合总和为 7 - 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。

	第一个元素 (头部)		最后一个元素 (尾部)
	抛出异常	特殊值	抛出异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

Queue方法	等效Deque方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

堆栈方法	等效Deque方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

方法二、剪枝叶

在一开始就对数组进行排序，因为在分支中，如果target-candidates[i] < 0，那么这个分支之后的更大的i就更不可能了。直接break即可。

for (int i=begin;i<len;i++) {
    if (target-candidates[i]<0) {
        break;
    }
    path.addLast(candidates[i]);     //双端队列在结尾增加
    DFS(candidates,i,len,target-candidates[i],path,res);
    path.removeLast();    //双端队列删去刚刚在上一个DFS中加入的值，继续进入循环，判断下一个分支
}

40、组合总和II

和39题是同样的思路

唯一的不同是每次begin是从下一个更大的数开始。

注意：

在剪枝中，注意要两次剪枝。

第一次剪枝和39题一样：

//第一次剪枝
if (target - candidates[i] < 0) {
	break;
}

第二次剪枝是为了消除一样的结果，注意在i>begin时，candidates[i]==candidates[i-1]表示是在同一级有相同元素。

//第二次剪枝
if (i>begin && candidates[i]==candidates[i-1]) {
	continue;
}

45、跳跃游戏II⭐

方法一、动态规划+数组

原理和 55、跳跃游戏 一致，但是是利用 dp 数组记录到达下标为 i 的节点的最短步数。

遍历数组，在遍历中，对下标为i+nums[i]进行判断，步数为dp[i]+1，取最小的dp存入。最后输出dp[n-1]

方法二、优化

例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。

从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

思想是上面那样，但是操作起来需要一些技巧：

对于上面的第一个部分0~2，虽然我们可以通过max知道谁能跳多远，但是我们还是需要走到边界end，也就是下标为2的地方，在这里我们可以更新步数+1，同时将新的边界end更新为刚刚走完的那一段中能走的最远的max。再继续上面的步骤。

代码真的很巧妙！！！

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;   
        int end = 0;        // 上次跳跃可达范围右边界（下次的最右起跳点）
        int max_border = 0;        // 目前能跳到的最远位置
        int step = 0;
        for (int i=0;i<n-1;i++) {
            max_border = Math.max(max_border,i+nums[i]);
            // 到达上次跳跃能到达的右边界了
            if (i == end) {
                end = max_border;    // 目前能跳到的最远位置变成了下次起跳位置的有边界
                step++;    // 进入下一次跳跃
            }
        }
        return step;
    }
}

46、全排列

本题的思路来自31、下一个排列，找当前数组的下一个排列，对于 123465：

从后向前找到第一对升序的相邻的两个数，即46；
从6开始到结尾升序排列，变成123456；
在刚刚升序的子序列中，即56中，从左到右找到一个大于4的数，即5，与4交换，变成123546。

因此，本题的思路很简单了：

将数组升序排列
调用此方法
直到整个数组为逆序为止，也就是当i定位第一对升序组合的较小值时，已经定位到-1了，则退出。

拓展

Stream流

49. 字母异位词分组

考察： #哈希

中等题，hash 存储即可。代码如下：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,ArrayList<String>> hash = new HashMap<String,ArrayList<String>>();
        for (int i=0;i<strs.length;i++) {
            char[] sc = strs[i].toCharArray();
            Arrays.sort(sc);
            String key = new String(sc);
            ArrayList<String> temp = hash.getOrDefault(key,new ArrayList<String>());
            temp.add(strs[i]);
            hash.put(key, temp);
        }
        List<List<String>> res = new ArrayList<>();
        for (ArrayList<String> v : hash.values()) {
            res.add(v);
        }
        return res;
    }
}

53、最大子数组和

简单动态规划~写过很多次啦！

55、跳跃游戏

方法一、动态规划+dp数组

利用dp数组记录某个点是否能到达，能到达记为1，随时判断下标为n-1即可。

方法二、优化——动态更新最大长度

在能跳跃的区域内遍历，不断更新能跳跃的最大长度，如果能覆盖下标为n-1则为true。

只用遍历一遍即可。

class Solution {
    public boolean canJump(int[] nums) {
        //不断更新能跳的最大长度，这样只要遍历一次就行
        int n = nums.length;
        int max = 0;
        for (int i=0;i<n;i++) {
            if (i>max) {
                return false;
            }
            if (max>=n-1) {
                return true;
            }
            max = Math.max(max,i+nums[i]);
        }
        return false;
    }
}

56. 合并区间

考察： #数组 #数组排序

中等题，但是简单。代码如下：

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a1, int[] a2) {
                if (a1[0]!=a2[0]) {
                    return a1[0]-a2[0];
                }
                return a1[1]-a2[1];
            }
        });

        List<List<Integer>> al = new ArrayList<>();

        int start = intervals[0][0], end = intervals[0][1];
        
        for (int i=0;i<intervals.length;i++) {
            if (intervals[i][0]<=end) {
                end = Math.max(end,intervals[i][1]);
            }
            else {
                List<Integer> temp = new ArrayList<>();
                temp.add(start);
                temp.add(end);
                al.add(temp);
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }

        List<Integer> temp = new ArrayList<>();
        temp.add(start);
        temp.add(end);
        al.add(temp);

        int[][] res = new int[al.size()][2];

        for (int i=0;i<al.size();i++) {
            res[i][0] = al.get(i).get(0);
            res[i][1] = al.get(i).get(1);
        }
        return res;

    }
}

68、文本左右对齐

方法一、枚举各种情况

_1.java文件为精简版（将很多重复的代码放入函数）

_2.java文件更容易理解

_3.java文件思路一致，但是更加精简，且易懂⭐

70、爬楼梯

方法一、动态规划

如果使用递归——妥妥的时间超时！！！

所以只有正着推。可以得到规律：

dp[0] = 1;
dp[1] = 1;

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

简单优化

int a = 1, b = 1, temp = 0;
for (int i=2;i<=n;i++) {
    temp = a + b;
    a = b;
    b = temp;
}
return b;

74. 搜索二维矩阵

中等题。两次二分查找，先查找行，再查找列。代码如下。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (target < matrix[0][0]) {
            return false;
        }
        int r = findrow(matrix,target);
        System.out.println(r);
        return find(matrix[r],target);
        
    }
    public int findrow(int[][] matrix, int target) {    // 找第一个小于等于target的
        int l = 0, r = matrix.length-1;
        while (l<r) {
            int m = (l + r + 1)/2;
            if (matrix[m][0]<=target) {
                l = m;
            }
            else {
                r = m - 1;
            }
        }
        return l;
    }
    public boolean find(int[] arr, int target) {
        int l = 0, r = arr.length-1;
        while(l <= r) {
            int m = (l + r) / 2;
            if (arr[m]==target) {
                return true;
            }
            else if (arr[m] < target) {
                l = m + 1;
            }
            else {
                r = m - 1;
            }
        }
        return false;
    }
}

78. 子集⭐⭐

考察： #回溯

题解：题解

方法一

中等题，代码如下：

class Solution {
    public List<List<Integer>> res;
    public List<Integer> ans;
    public int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        ans = new ArrayList<>();
        this.nums = nums;
        find(0);
        return res;
    }

    public void find(int i) {
        if (i==nums.length) {
            res.add(new ArrayList<>(ans));
            return;
        }

        // 不选nums[i]，直接进入下一个
        find(i+1);

        // 选择nums[i]，添加进入ans，再进入下一个
        ans.add(nums[i]);
        find(i+1);
        // 回退场景
        ans.remove(ans.size()-1);
    }
}

方法二、更通用的回溯⭐（框架）

思路比较抽象，需要思考。代码如下：

class Solution {
    public List<List<Integer>> res;
    public List<Integer> ans;
    public int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        ans = new ArrayList<>();
        this.nums = nums;
        find(0);
        return res;
    }

    public void find(int i) {
        res.add(new ArrayList<>(ans));
        for (int j=i;j<nums.length;j++) {
            // 第一种情况：nums[j]在
            ans.add(nums[j]);
            find(j+1);

            // 第二种情况：nums[i]-nums[j]都不在
            ans.remove(ans.size()-1);
        }
    }
}

89. 格雷编码 ⭐

题解

方法一、规律

总结了如下规律：
1. 0 位格雷码有 1 个码字；1 位格雷码有 2 个码字 2. (n+1) 位格雷码中的前 2^n 个码字（前一半）等于 n 位格雷码的全部码字，按顺序书写，加前缀 0（意味着如果 n 位的所有码字已经加入 res，就不用操作了） 3. (n+1) 位格雷码中的后 2^n 个码字 (后一半）等于 n 位格雷码的全部码字按逆序书写，并加前缀 1（相当于把 n 位的所有码字逆序遍历，并加上一个头 1） 4. n+1 位格雷码的集合 = n 位格雷码集合 (顺序) 加前缀 0 + n 位格雷码集合 (逆序) 加前缀 1

详细代码如下：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);     

        if (n==0) {
            return res;
        }

        int head = 1;

        for (int i=1;i<=n;i++) {      //表示从1位到n位
            int l = res.size();
            for (int j=l-1;j>=0;j--) {      //遍历在上一轮之后存的i-1位二进制码
                res.add(res.get(j)+head);
            }
            head = head << 1;
        }
        return res;
    }
}

方法二、格雷编码

实现公式如下：

举个🌰：n=4 时，当十进制为 7，现在最高位加个 0，所以其对应的二进制位 00111，可以通过上图的例子进行演算。
从右往左推算 00111 对应的格雷码的每一位：
1 ⊕ 1 = 0
1 ⊕ 1 = 0
0 ⊕ 1 = 1
0 ⊕ 0 = 0
所以其对应的格雷码为 0100

再举个🌰：n=4 时，当十进制为 12，现在最高位加个 0，所以其对应的二进制位 01100，可以通过上图的例子进行演算。
从右往左推算 01100 对应的格雷码的每一位：
0 ⊕ 0 = 0
1 ⊕ 0 = 1
1 ⊕ 1 = 0
0 ⊕ 1 = 1
所以其对应的格雷码为 1010

不难发现，对于十进制为 i 的数，其格雷码就是 i ^ (i>>1)，根据这个思路很容易得到代码：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();  

        for (int i=0;i<(1<<n);i++) {  
            res.add(i ^ (i>>1));
        }

        return res;
    }
}

90. 子集 II⭐

考察： #回溯

基础题/框架题：78（子集）

中等题，在 78 题的基础上多了一步去重。需要先对 nums 进行排序，将相同的聚在一起。在 find 函数中，如果遇到连续的相同的数，只取其中的第一个。因为在同一个 find 下的 for 循环内是属于同一级别的，比如：[1, 2, 2] 分解为 [1, 2] 和 [1, 2] 是一样的，同级别的相同的去重即可。

代码如下：

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> ans = new ArrayList<>();
    public int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        find(0);
        return res;
    }

    public void find(int i) {
        res.add(new ArrayList<>(ans));
        for (int j=i;j<nums.length;j++) {
            if (j>i && nums[j]==nums[j-1]) {
                continue;
            }
            ans.add(nums[j]);
            find(j+1);

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

94. 二叉树的中序遍历

考察： #树

简单题，考察树的中序遍历，模板如下：

public void midfind(TreeNode r) {
	if (r == null) {
		return;
	}
	midfind(r.left);
	res.add(r.val);
	midfind(r.right);
}

101. 对称二叉树😭

考察： #树

简单题，但是思路很妙。

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。如果同时满足下面的条件，两个树互为镜像： - 它们的两个根结点具有相同的值 - 每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    public boolean check(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null) {
            return true;
        }
        if (r1 == null || r2 == null) {
            return false;
        }
        return r1.val == r2.val && check(r1.left, r2.right) && check(r1.right, r2.left);
    }
}

102. 二叉树的层序遍历

简单题。但是要注意 List<List<Integer>> 对象的构造方法。

1	List<List<Integer>> list = new ArrayList<>();

104. 二叉树的最大深度

简单题，遍历即可，同步 level 层级。

118. 杨辉三角

考察： #动态数组

简单题。但是需要注意，对于同一个 arraylist 对象，如果之前已经加入了嵌套的外层 list 中，之后再改变这个对象，嵌套在里面的也会改变，类似于一个指针。

121、买卖股票的最佳时机

思路与1014、最佳观光组合相同。

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

这题很容易想复杂了，其实这题的目的就是为了始终不亏钱。所以只要是相邻两个升序的就买了就卖，一定能赚一笔！

128. 最长连续序列⭐

考察： #Set

中等题。题目要求在 \(O(n)\) 的时间内找到最长的连续序列，思路是找到每个连续序列的第一个数，然后再一直++，就能找到这个长度。那么问题是如何找到第一个数，或者说会不会出现中间的数重复判断。第一个数有一个特性是非第一个数没有的，就是 num-1 是不存在数组中。现在问题是如何快速判断一个数在不在数组中，这里选择使用 HashSet，它是 \(O(n)\) 的时间复杂度。

代码如下：

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int res = 0;
        for (int n : nums) {
            set.add(n);
        }
        for (int s : set) {
            if (!set.contains(s-1)) {    // 我们要找的就是一个连续序列的开头数字，它的特征就是没有s-1这个值
                // s就是连续序列的开头数字
                int k = 1;
                while (set.contains(s+1)) {    // 判断下一个在不在set中
                    k++;    // 计数
                    s++;    // 判断下一个数，这里++的结果是存在与set的
                }
                res = Math.max(res, k);
            }
        }
        return res;
    }
}

135、分发糖果

方法一、递归

思想：相邻的两个值中，更大的糖果=更小的糖果+1，如果比左右都大则取其max。如果比左右都小，则糖果数为1。用数组记录数值，可以提高时间效率（如果不设置数组，则会超时）。

方法二、左右遍历

思想：从左向右遍历一遍，设置第一个值为1，如果当前值比上一个值大，则糖果数=上一个的糖果数+1，反之将其置为1。此时从左到右的糖果大小关系已经明确。再从右往左遍历一遍，此时只需要一个temp变量记录即可，设置第一个的temp为1，如果当前值比上一个值大，则糖果数=temp+1，对于每一个小朋友都会对他从左遍历和从右遍历取最大值，也就是他最后得到的糖果值。

对于 [1,2,87,87,87,2,1]

从左向右：1，2，3，1，1，1，1

从右向左：1，1，1，1，3，2，1

综合：1，2，3，1，3，2，1

136. 只出现一次的数字

方法一、HashSet

简单题，利用 set 记录，最后遍历。注意 set 的删除为 remove()。

方法二、位运算👍

思路：元素只出现两次，而相同元素异或为 0。0 和某个只出现一次的元素异或为这个元素。代码如下：

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

152、乘积最大子数组⭐

动态规划经典题

本题和53、最大子数组和有异曲同工之处。但是值得注意的是乘法中，两个负数相乘就会得到正数。

所以我们不能只用一个last记录以当前元素结尾的最大值，我们需要用lastmax记录当前元素结尾的最大值、用lastmin记录当前元素结尾的最小值。

最大值和最小值实时动态更新。如果当前元素<0，那么最大值就是上一个元素的最小值*nums[i]和它自身判断，最小值就是上一个元素的最大值*nums[i]和它自身判断。nums[i]>0就很简单了。

为了更广泛操作（装逼），我们可以提前计算：

1 2	int a = lastmaxnums[i]; int b = lastminnums[i];

那么每次更新的时候只需要：

1 2	lastmax = Math.max(Math.max(a,b),nums[i]); lastmin = Math.min(Math.min(a,b),nums[i]);

其实不难理解，如果nums[i]<0，如果上一个值的max>0、min<0，那么取的是b；如果max<0、min<0，那么取的也还是b；如果max>0、min>0，那么取得还是b。但是如果nums[i]>0，那么一切都恰恰相反，都取a。所以我们只需要用a、b得最大值和它自身比较就能得到新的lastmax。

lastmin同理。

每次循环都用变量min找到最大值。

完整代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        int lastmax = nums[0];
        int lastmin = nums[0];
        int max = nums[0];
        
        for (int i=1;i<nums.length;i++) {
            
            int a = lastmax*nums[i];
            int b = lastmin*nums[i];

            lastmax = Math.max(Math.max(a,b),nums[i]);
            lastmin = Math.min(Math.min(a,b),nums[i]);

            // if (nums[i]<0) {
            //     lastmax = Math.max(b,nums[i]);
            //     lastmin = Math.min(a,nums[i]);
            // }
            // else {
            //     lastmax = Math.max(a,nums[i]);
            //     lastmin = Math.min(b,nums[i]);
            // }

            max = Math.max(max,lastmax);
        }
        return max;
    }
}

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

中等题，但是很简单。代码如下：

class Solution {
    public int findMin(int[] nums) {
        for (int i=0;i<nums.length-1;i++) {
            if (nums[i]>nums[i+1]) {
                return nums[i+1];
            }
        }
        return nums[0];
    }
}

189. 轮转数组

方法一、开辟额外空间

中等题。最后利用了深拷贝。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n];

        k = k % n;

        int i = 0;
        for (int j=n-k;j<n;j++,i++) {
            res[i] = nums[j];
        }
        for (int j=0;j<n-k;j++,i++) {
            res[i] = nums[j];
        }
        // for (i=0;i<n;i++) {
        //     System.out.println(res[i]);
        // }
        System.arraycopy(res, 0, nums, 0, n);
    }
}

方法二、原地翻转👍

思路：

代码如下：

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums,0,n-1);
        reverse(nums,0,k-1);
        reverse(nums,k,n-1);
        
    }
    public void reverse(int[] nums, int start, int end) {    // 将nums数组的[start,end]原地逆置
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

198、打家劫舍（模板题）⭐⭐

典型的动态规划入门题

思路198. 打家劫舍 - 力扣（Leetcode）

优化前

注意：

dp[0]表示没有房间，不对应nums中任何值

dp[i]对应的应该是第i-1个屋子的最大收益。

优化后（理论上更优的）

208. 实现 Trie (前缀树)⭐

考察： #前缀树

拓展：1032. 字符流

前缀和介绍思路：【图解算法】字典树

代码如下：

class TreeNode {
    boolean isEnd;
    TreeNode[] Children;

    public TreeNode() {
        isEnd = false;
        Children = new TreeNode[26];
    }
}

class Trie {

    TreeNode root;
    
    public Trie() {
        root = new TreeNode();        
    }
    
    public void insert(String word) {
        TreeNode r = root;
        char[] sc = word.toCharArray();
        for (int i=0;i<word.length();i++) {
            if (r.Children[sc[i]-'a']==null) {
                r.Children[sc[i]-'a'] = new TreeNode();
            }
            r = r.Children[sc[i]-'a'];
        }
        r.isEnd = true;    // 表示这是单词的结尾
    }
    
    public boolean search(String word) {
        TreeNode r = root;
        char[] sc = word.toCharArray();
        for (int i=0;i<word.length();i++) {
            if (r.Children[sc[i]-'a']==null) {
                return false;
            }
            r = r.Children[sc[i]-'a'];
        }
        return r.isEnd;     // 需要完整搜索，如果单词都有，需要判断最后一个是不是结尾
    } 
    
    public boolean startsWith(String prefix) {
        TreeNode r = root;
        char[] sc = prefix.toCharArray();
        for (int i=0;i<prefix.length();i++) {
            if (r.Children[sc[i]-'a']==null) {
                return false;
            }
            r = r.Children[sc[i]-'a'];
        }
        return true;  

    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

213、打家劫舍 II⭐

动态规划

相比198、打家劫舍，我们可以将题目拆解为：

n (0~n-1) 个屋子分别在 0~n-2 和 1~n-1 中取最大值，这样就能保证首位不会同时出现

226. 翻转二叉树

考察： #树

简答题，只要类似后序遍历，每次返回更改过左右节点的根即可。

283. 移动零

简单题。使用双指针，i 指向第一个 0，j 指向 i+1 位置。之后遍历 j，每次如果 j 位置的元素不是 0，则将其赋值到 i 的位置，i 再++。最后将 i 及其之后的元素置为 0 即可。

300. 最长递增子序列⭐

考察： #动态规划 #最长递增子序列

拓展：1626. 无矛盾的最佳球队

中等题。这是最长递增子序列的最基础的题目！dp 保存的是以当前数组结尾的最长的个数。代码如下：

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

    }
}

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

考察： #滑动窗口

中等题。因为可能会出现重复单词，所以不能使用位运算。

代码如下：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();
        int n = s.length();
        int pn = p.length();
        List<Integer> res = new ArrayList<>();
        int[] map = new int[26];
        int[] test = new int[26];

        if (n<pn) {
            return res;
        }
        
        for (char c : pc) {
            map[c-'a']++;
        }

        for (int i=0;i<pn;i++) {
            test[sc[i]-'a']++;
        }
        if (Arrays.equals(map,test)) {
            res.add(0);
        }

        for (int i=1;i<=n-pn;i++) {
            test[sc[i-1]-'a']--;
            test[sc[i+pn-1]-'a']++;
            if (Arrays.equals(map,test)) {
                res.add(i);
            }
        }

        return res;

    }
}

453. 最小操作次数使数组元素相等

思路：n-1 个小的加 1，相当于最大的减 1。详细代码如下：

class Solution {
    public int minMoves(int[] nums) {
        int n = nums.length;
        int mi = Integer.MAX_VALUE;
        for (int i=0;i<n;i++) {
            mi = Math.min(mi,nums[i]);
        }
        int res = 0;
        for (int i=0;i<n;i++) {
            res += (nums[i]-mi);
        }
        return res;
    }
}

462. 最小操作次数使数组元素相等 II

先对 nums 排序，只要选择的相等数 x ∈ [nums[i], nums[j]]，对于左右指针所指向的数，其操作数是固定的，即 nums[j] - nums[i]，指针所指向数的差值。

class Solution {
    public int minMoves2(int[] nums) {
        // 最终大家汇集的点一定在这些数之间的
        Arrays.sort(nums);
        int i = 0, j = nums.length-1;
        int res = 0;
        while (i<=j) {
            res += (nums[j]-nums[i]);
            i++;
            j--;
        }
        return res;

    }
}

494. 目标和⭐

方法一、二维数组（纯暴力）

类似于树的递归调用，很愚蠢。代码如下：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int[][] res = new int[n][1<<n];
        res[0][0] = -nums[0];
        res[0][1] = nums[0];
        for (int i=1;i<n;i++) {
            for (int j=0;j<(1<<i);j++) {
                res[i][j*2] = res[i-1][j] - nums[i];
                res[i][j*2+1] = res[i-1][j] + nums[i];
            }
        }
        int sum = 0;
        for (int i=0;i<(1<<n);i++) {
            if (res[n-1][i]==target) {
                sum++;
            }
        }

        // for (int i=0;i<n;i++) {
        //     for (int j=0;j<(1<<n);j++) {
        //         System.out.print(res[i][j]);
        //         System.out.print(" ");
        //     }
        //     System.out.println("");
        // }
        
        return sum;
    }
}

方法二、数学+动态规划

题解：题解

注意：不能添加以下的代码段，可能有多个 0，+0 和-0 效果一样，所以不一定是 1。
1
2
3
if (sum == target) {    
	return 1;
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        //提前退出
        if (sum < target || (sum-target)%2!=0) {
            return 0;
        }
        
        int neg = (sum-target)/2;

        // 对于nums的每一个数，我选或者不选，使得最后的结果为target的搭配数量
        int [][] dp = new int [n+1][neg+1];    //我们要找到就是最终neg的数量，即dp[n][neg]的值
        dp[0][0] = 1;     //表示初始状态没有任何元素选取，和为0，有1种方案。

        for (int i=1;i<n+1;i++) {
            int num = nums[i-1];
            for (int j=0;j<neg+1;j++) {
                if (j<num) {       // 如果加上num得到的结果j还比num小，这是不可能的，所以不能加
                    dp[i][j] = dp[i-1][j];
                }
                else {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-num];     // 结果应该是不加num的个数+加上num的个数之和
                }
            }
        }
        return dp[n][neg];

    }
}

优化、用一维数组进行动态规划

需要注意：如果正向操作可能在 j>=num 时将原本的 dp[j]覆盖，在之后的调用原本的dp[j]时会出错，所以一维的动态规划需要从后向前逆序进行。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        //提前退出
        if (sum < target || (sum-target)%2!=0) {
            return 0;
        }

        int neg = (sum-target)/2;

        // 对于nums的每一个数，我选或者不选，使得最后的结果为target的搭配数量
        int[] dp = new int[neg+1];   
        dp[0] = 1;     

        for (int num : nums) {
            for (int j=neg;j>=num;j--) {
                dp[j] += dp[j-num];
            }
        }
        return dp[neg];

    }
}

其他

栈

超时，理论上不应该，已经进行了小优化了，但是还是会超时。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        Deque<Integer> dq = new LinkedList<>();
        dq.addLast(0);
        for (int i=0;i<n;i++) {     //轮数
            int size = dq.size();
            for (int j=0;j<size;j++) {
                int k = dq.pollFirst();
                dq.addLast(k-nums[i]);
                dq.addLast(k+nums[i]);
            }
        }
        int sum = 0;
        while(dq.size()!=0) {
            if (dq.pollFirst()==target) {
                sum++;
            }
        }
        return sum;
    }
}

509、斐波那契数

简单哦~

524、通过删除字母匹配到字典里最长单词

方法一：排序后操作

先对List进行排序，重写排序规则：

Collections.sort(dictionary,new Comparator<String>() {
    public int compare(String s1, String s2) {
        if (s1.length() == s2.length()) {
            if (s1.compareTo(s2)>0) {
                return 1;
            }
            else {
                return -1;
            }
        }
        return s1.length()-s2.length();
    }
});

先对字符串List进行排序操作，根据题目要求，需要找到最长的且字典序最小的结果，所以依次遍历每一个字符串，如果当前字符串成立，则与它相同长度的字符串无需验证。

方法二、不排序操作

这种思路无需先排序，只要记录已经匹配成功的字符串的长度，如果在接下来的字符串长度比它小，那就无需验证；如果长度更长，则进行验证，如果验证成功，更新匹配成功的字符串长度；如果字符串长度和记录的相同，将当前字符串和这个已经匹配成功的字符串比较，只有字典序更小才进行验证。

注意

字符串的比较

1	s1.compareTo(s2); //如果s1>s2，返回1；如果s1<s2，返回-1；如果相等，返回0

543. 二叉树的直径

考察： #树

简单题，但是思路很重要。

root 的直径 = root.left 的高度 + root.right 的高度
root 的高度 = Math.max(root.left的高度, root.right的高度) + 1

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

// 
class Solution {
    public int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {   
        findd(root);    
        return res;
    }
    // root为根的最大直径
    public void findd(TreeNode root) {
        if (root == null) {
            return;
        }
        res = Math.max(res, height(root.left)+height(root.right));
        findd(root.left);
        findd(root.right);
    }
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left),height(root.right)) + 1;
    }
}

560. 和为 K 的子数组

考察：前缀和

方法一、前缀和

利用前缀和+两层 for 循环，比较简单易想。代码如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] map = new int[n+1];     // map[i]表示nums[0~i-1]
        map[0] = 0;
        for (int i=1;i<=n;i++) {
            map[i] = map[i-1] + nums[i-1];
        }
        int res = 0;
        for (int i=1;i<=n;i++) {
            for (int j=0;j<i;j++) {
                if (map[i]-map[j]==k) {
                    res++;
                }
            }
            
        }
        return res;
    }
}

方法二、前缀和+hash 优化⭐

思路： 同样先构造一个 map 数组记录前缀和，再构造一个 hash，在遍历 map 时，记录当前 map[i]-k 的值 d，也就是我们需要在 map[0, i) 找到下标为 j，满足 map[j]为 d，那么 map[i]-map[j]和就是 k。

注意： 在下面代码实现中，一定要先更新 res，再更新 hash。举个例子：如果 k 是 0，那么 d 就是 map[i]，如果我先更新 hash，假设 key 为 d 的开始没有，那么就在 hash 中加入的 {d, 1}，再更新 res 即为 res+1。但是这样是对的吗？显然不对！我要找的 k 是 0，但是我再 i 之前的 map 没有任何值是和 map[i]相等，理论上以 map[i]结尾是构造不了符合条件的子串，但是这里却+1，这是不对的。

代码如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] map = new int[n+1];     // map[i]表示nums[0~i-1]
        map[0] = 0;
        for (int i=1;i<=n;i++) {
            map[i] = map[i-1] + nums[i-1];
        }
        int res = 0;
        HashMap<Integer,Integer> hash = new HashMap<Integer, Integer>();     
        hash.put(0, 1);    // 表示和为k的本身就有1
        for (int i=1;i<=n;i++) {
            int d = map[i]-k;    // 当前值和k之间的差距，现在就看在[0,i]之间有没有和为d的，已经存进去的都是有端下标小于i的
            res += hash.getOrDefault(d, 0);      // hash中key为d的val：表示[0,i)中前缀和为d的数量。如果map[j]=d，那么意思是(j,i]的和为k
            hash.put(map[i], hash.getOrDefault(map[i],0)+1);
        }
        return res;
    }
}

621. 任务调度器⭐

中等题，思路很妙！思路：

将任务按类型分组，正好 A-Z 用一个 int[26]保存任务类型个数
对数组进行排序（因为我们实际上对到底是 A5 个还是 B5 个不感兴趣，我们只需要有某个单词出现 5 次即可），优先排列个数（count）最大的任务，如题得到的时间至少为 res =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A (X 为其他任务或者待命)。
再排序下一个任务，如果下一个任务 B 个数和最大任务数一致，则 res++ ==> A->B->X->A->B->X->A->B
对于空位还满足的，直接插进去即可。（你可能会觉得，如果剩下的空位不能满足 n 的条件怎么办，就像在 n=2 的情况下，在 ABCABCABCAxxA 时候还有 2 个 D，但是剩下的空间不能满足，这时候只需要稍微调整已经排序的位置即可，也就是变成 ABCBACBABxACx，那么两个 D 就能顺利插进去）
如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于 n，在这种情况下就是任务的总数是最小所需时间
最后返回的实际上就是 res 和所有单词的个数的最大值，所有单词个数实际上就是 tasks 的长度。

代码如下：

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] words = new int[26];
        for (char c : tasks) {
            words[c-'A']++;
        }
        Arrays.sort(words);
        int res = (words[25] - 1) * (n+1) + 1;
        int j = 24;
        while (j>=0 && words[j]==words[25]) {
            res++;
            j--;
        }
        return Math.max(res,tasks.length); 
    }
}

647. 回文子串⭐

中心扩张法

中等题，其实思路很简单，就是确定一个中间，两边同时扩张。

中心需要分类讨论，如果中心是 1 个元素，那么扩张后的元素个数都是奇数；如果中心是 2 个元素，那么扩张后的元素个数都是偶数。代码如下：

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        char[] sc = s.toCharArray();
        int n = sc.length;
        for (int i=0;i<n;i++) {    //中心
            int start = i, end = i;
            while (start>=0 && end<n) {
                if (sc[start] == sc[end]) {
                    res++;
                    start--;
                    end++;
                }
                else {
                    break;
                }
            }
        }

        for (int i=0;i<n-1;i++) {
            int start = i, end = i+1;
            while (start>=0 && end<n) {
                if (sc[start] == sc[end]) {
                    res++;
                    start--;
                    end++;
                }
                else {
                    break;
                }
            }

        }
        return res;
    }
}

532、数组中的 k-diff 数对

本题思路，先将数组升序。

设置一个i和j，注意 i 如果遇到重复的就跳过，j是找 nums[i]+k 的值，对于越来越大的i，如果他的j存在，那么一定再前一个i的j的后面。

但是需要注意的是i可能会跑到j后面，所以每次要对j做判断是否需要更新位置。

671、二叉树中第二小的节点

方法一、替换法

更新新的最小值，实际上也是遍历整个数，逻辑相对复杂一些。

核心代码：

if (isLeaf(root)) {
    return root.val;
}

if (a == temp && b == temp) {
    return temp;
}
else if (a == temp) {
    return b;
}
else if (b == temp) {
    return a;
}
else {
    return Math.min(a,b);
}

方法二、DFS

利用DFS深度优先搜索，提前设置好全局变量记录最小和第二小的值，DFS遍历整个树，找到第二小的值。

DFS的使用方法：void函数，当root==null时return;，否则调用dfs(root.left)和dfs(root.right)，当全部遍历完后，全局变量也被修改了

707、设计链表

Java语言使用链表格式：

class MyLinkedList {
    static class Node {
        int val;
        Node pre;
        Node next;
        public Node() {
        }
        public Node(int val) {
            this.val = val;
        }
    }

    Node head;
    int size=0;

    public MyLinkedList() {
        head = new Node();
        head.next = head;
        head.pre = head;
    }
    
    public int get(int index) {
        Node node = head;
        //......
    }
    //......
}

//调用
MyLinkedList linkedList = new MyLinkedList();
linkedList.get(1);

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

方法一、贪心

比较晦涩难懂，对left的定义很重要，特别是在prices[i]>left+fee情况的left改变比较难。看代码理解吧。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;

        int left = prices[0];
        int sum = 0;
        for (int i=1;i<n;i++) {
            if (prices[i]<left) {   // prices[i]+fee < left+fee
                left = prices[i];
            }
            else if (prices[i]>left+fee) {    //如果后面的减去left和fee依然有收益，那就可以尝试将股票卖出
                sum += prices[i]-left-fee;

                //但是为了防止遇到的是局部最优：
                // left       prices[i]          prices[i+1]
                //实际上的真实收益应该是：prices[i+1]-left-free
                // prices[i]-left-free    + 一个收益   =   prices[i+1]-left-free
                // 解得这个收益为：prices[i+1]-prices[i]
                // 但是 sum += prices[i+1]-prices[i]-fee;，所以left应该设定为prices[i]-fee

                left = prices[i]-fee;    
            }
        }
        return sum;
    }
}

方法二、动态规划

唉，动态规划，容易理解

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;

        //dp[i][0]表示i天结束后手上没有股票的最大收益
        //dp[i][1]表示i天结束后手上有一张股票的最大收益

        int[][] dp = new int[n][2];    
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i=1;i<n;i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}

优化

动态规划常规优化喽~

739. 每日温度

方法一、单调栈⭐

如果本题使用从后往前进行遍历，每次循环内嵌套循环，必然会超出时间复杂度，因此不能只用简单得线性查找，需要使用新的查找技术——单调栈。

应用场景： 在一个一维数组中，找到某个数得左边或者右边第一个最小或者最大得元素位置。

题解：题解

本题需要找右边第一个大于它的元素与它的距离。如果栈为空，则直接放入当前元素的下标；如果不为空，我们需要拿当前元素依次与栈顶元素的进行比较，如果当前元素比栈顶元素大，表示它是栈顶元素之后第一个大于栈顶元素的值，那么栈顶元素出栈，他们俩之间的距离就是栈顶元素下标的结果，再继续循环上述步骤，直到当前元素比栈顶元素小，则表示栈顶元素之后的都更小，那么直接将当前元素下标入栈。当全部遍历完后，如果栈内还有元素，表示这些元素没有遇到比他们更大的，那么依次出栈，并在对应值上设置为 0。

代码如下：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> dq = new LinkedList<>();
        int n = temperatures.length;
        int[] res = new int[n];
        for (int i=0;i<n;i++) {
            int k = temperatures[i];
            while (dq.size()!=0) {
                int j = dq.peekLast();
                if (temperatures[j] < k) {
                    res[j] = i - j;
                    dq.pollLast();
                }
                else {
                    break;
                }
            }
            dq.addLast(i);
        }
        while (dq.size()!=0) {
            res[dq.pollLast()] = 0;
        }
        return res;
    }
}

740、删除并获得点数⭐

题目中说的是如果选取i值，就不能选取所有的i-1和i+1。

这看似是涉及到左右，但是实际上只要考虑左边就行了。

考虑每个值选还是不选即可（变成了198、打家劫舍小偷问题）。

746、使用最小花费爬楼梯

方法一、动态规划

注意找到规律：

dp[0] = 0;
dp[1] = 0;

dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

尝试优化空间

int a = 0, b = 0, temp = 0;
for (int i=2;i<=n;i++) {
    temp = Math.min(b+cost[i-1],a+cost[i-2]);
    a = b;
    b = temp;
}
return b;

但是奇怪的是更慢了

769、最多能完成排序的块⭐

思路：769. 最多能完成排序的块 - 力扣（Leetcode）

注意题干：它表示在 [0, n - 1] 范围内的整数的排列，表示这n个数是0~n-1。

思路：所以这个数组的下标就是整体排序好的数值。

因此我们可以从头到尾遍历，记录最左边的值和最右边的值，记录在这一段中的max和min，当且仅当max==当前块的最右边值的下标且min==当前块的最左值的下标时，这一块结束。

此时最左边的下标更新为max的值+1，再将min和max都初始化。

777、在LR字符串中交换相邻字符⭐

思路：

由题意可以知道，L是可以穿过X向左移动，R可以穿过X向右移动，但是L和R都无法互相穿过。因此，单纯地觉得只要将start和end去掉所有的X只要相等就返回true，像下面代码所示：

class Solution {
    public boolean canTransform(String start, String end) {
        if (start.length() != end.length()) {
            return false;
        }
        int n = start.length();
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for (int i=0;i<n;i++) {
            if (start.charAt(i) != 'X' ) {
                sb1.append(start.charAt(i));
            }
            if (end.charAt(i) != 'X' ) {
                sb2.append(end.charAt(i));
            }
        }
        return sb1.toString().equals(sb2.toString());
    }
}

然而出现了一个不可忽略的错误：

例：

"LXXLXRLXXL"

"XLLXRXLXLX"

题意是：XL ==> LX；RX ==> XR 。

按照上面代码所述，不仅可以XL变为LX，也可以LX变为XL，这是不合题意的！

因此需要增加一个限定条件，即start中的L要比end中对应的L的下标要大，start中的R要比end中对应的R的下标要小。

所以，不能使用一次循环，需要使用双指针进行判断。

新代码思路是：

对于i和j分别指向start和end字符串，每次分别找一个非X字符，如果相同且满足i和j的关系的，则i++和j++；如果不满足直接返回false。这样的匹配规则，如果是可以完成匹配的，应该是i和j在某一次循环内同时到达终点，不会存在i卡在某个非X字符，j已经到了终点，如果是这种情况（即只有一个到了终点的），则之间判断i和j是否相等，如果相等，则返回true，不相等则返回false。

779、第K个语法符号

本题使用递归思想，不算很难，但是需要找到规律。

第一行：0

第二行：01

第三行：0110

第四行：01101001

第五行：0110100110010110

发现什么了！

每一行的前一半字符是上一行的完整字符。

每一行的后一半字符是前一半字符的取反，也就是上一行的完整字符取反。

那结果很明显了！

使用递归的思想，找到k在这一行的位置，用位运算轻松得到每一行的len。在前半段，它的值就等于上一行的k的位置；在后半段，那它的值就等于上一行的(k-len/2)的位置的值的取反。当然这里不是二进制，取反有风险，if判断一下喽！

完美解决~

788、旋转数字

792、匹配子序列的单词数

方法一、暴力+微优化

Screenshot_20221117_093435_com.huawei.browser 对words中的每个字符进行判断，加入一定的提前跳出判断，勉强不超时（不推荐）。

方法二、首字母+队列

Screenshot_20221117_094650_com.huawei.browser

很妙！直接看代码：

class Solution { 
	// 将words中的每个word根据首字母进行分类 
	// 设计一个容器，存储以26个字母开头的字符串，这里选择用队列 
	public int numMatchingSubseq(String s, String[] words) { 
		Deque<String>[] dq = new Deque[26]; 
		int sum = 0; 
	
		// 初始化 
		for (int i=0;i<26;i++) { 
			dq[i] = new ArrayDeque<>(); 
		} 
		
		// 初始化加入，将所有字符串根据首字母分类 
		for (String word : words) { 
			dq[word.charAt(0)-'a'].addLast(word); 
		} 
		
		for (char sc : s.toCharArray()) { // 顺序遍历s的每个字母 
			int k = dq[sc-'a'].size(); 
			for (int i=0; i<k; i++) { 
				// 对以当前字母开头的字符串判断 
				String p = dq[sc-'a'].pollFirst(); 
				if (p.length()==1) { // 表示只有它本身 
					sum++; 
				} 
				else { 
					dq[p.charAt(1)-'a'].addLast(p.substring(1)); //将除去第一个字符的剩下的字符串再次根据首字母加入 
				} 
			} 
		} 
		return sum; 
	} 
}

796、旋转字符串

最长对的思路就是：两个字符串合并，如果在其中contains()，那么就存在。

799、香槟塔

方法一、动态规划（模拟）

虽然是动态规划，确实不好想，但是想通了很简单。

我们可以假设第一次将所有的香槟都倒在第一层的杯里，然后从第一层开始遍历，对于每一个多出来的部分，分给它下面的两个杯子。

直接构建一个二维数组即可。

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] dp = new double[101][101];
        dp[0][0] = (double)poured;

        for (int i=0; i<=query_row; i++) {
            for (int j=0; j<=i; j++) {       //i行j列（都是从0开始）
                if (dp[i][j] > 1) {
                    double half = (dp[i][j]-1)/2.0;
                    dp[i][j] = 1.0;
                    dp[i+1][j] += half;
                    dp[i+1][j+1] += half;
                }
            }
        }
  
        return dp[query_row][query_glass];
    }
}

优化

也就是将二维数组变成一维数组。

我们可以发现每一层的结构都是依赖上层的结果，所以可以直接设置一维数组。

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[] dp = {poured};
        
        for (int i=1; i<=query_row; i++) {
            double[] temp = new double[i+1];
            for (int j=0; j<i; j++) {       //i行j列（都是从0开始）
                if (dp[j] > 1) {
                    double half = (dp[j]-1)/2.0;
                    temp[j] += half;
                    temp[j+1] += half;
                }
            }
            dp = temp;              // 直接指针指向
        }

        return Math.min(1, dp[query_glass]);     //可能要求输出的不是最后一层
    }
}

801、使序列递增的最小交换次数⭐⭐

难题！

方法一、分类讨论+动态规划

本题题目是问要使得两边都是递增，且同下标交换需要的最小的次数。

所以一共有三种情况： 第一种情况：下标为i的nums1和nums2的值，只比其对应的下标为i-1的nums1和nums2值大。

1	(nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]) && !(nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1])

第二种情况：下标为i的nums1和nums2的值，只比其对应的下标为i-1的nums2和nums1值大。

1	(nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1]) && !(nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1])

第三种情况：下标为i的nums1和nums2的值，比其对应的下标为i-1的nums1和nums2值大，且比其对应的下标为i-1的nums2和nums1值大。

1	(nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]) && (nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1])

构建dp数组：int[][] dp = new int[n][2];

第一列对应的是如果这一组不交换所需要的最小次数，第二列对应的是这一组交换所对应的最小次数。

根据这三种情况分别分析对应的操作：

第一种情况：下标为i的nums1和nums2的值，只比其对应的下标为i-1的nums1和nums2值大。如果选择不交换，那么万事大吉，直接dp[i][0] = dp[i-1][0];；如果要交换，为了满足题目的要求，i-1下标的两个值也要交换，所以dp[i][1] = dp[i-1][1] + 1;。

第二种情况：下标为i的nums1和nums2的值，只比其对应的下标为i-1的nums2和nums1值大。如果选择不交换，为了满足题目意思，需要将i-1下标的两个值交换，所以dp[i][0] = dp[i-1][1];；如果要交换，为了满足题目的要求，i-1下标的就不用交换，所以dp[i][1] = dp[i-1][0] + 1;。

第三种情况：下标为i的nums1和nums2的值，比其对应的下标为i-1的nums1和nums2值大，且比其对应的下标为i-1的nums2和nums1值大。如果选择不交换，只需要取i-1下标交换或者不交换的更小值即可，即dp[i][0] = Math.min(dp[i-1][0],dp[i-1][1]);；如果要交换，取i-1下标交换或者不交换的更小值，再+1即可，即dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]) + 1;。

dp[0][0] = 0;
dp[0][1] = 1;

for (int i=1;i<n;i++){
    if ((nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]) && (nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1])) {
        dp[i][0] = Math.min(dp[i-1][0],dp[i-1][1]);
        dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]) + 1;
    }
    else if ((nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]) && !(nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1])) {
        dp[i][0] = dp[i-1][0];
        dp[i][1] = dp[i-1][1] + 1;
    }
    else if (!(nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]) && (nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1])) {
        dp[i][0] = dp[i-1][1];
        dp[i][1] = dp[i-1][0] + 1;
    }
}

方法二、方法一dp数组改变

将方法一的int[][] dp = new int[n][2];变成int[][] dp = new int[2][n];，其他思路一致。

空间换时间的操作。

方法三、优化

只保存i-1状态的两个值即可。

808、分汤⭐

方法一、DFS+记忆化

注意到四种分汤情况都是25的倍数，所以可以先对n进行简化

然后进行dfs，当i≤0 && j≤0时，表示两种汤都分配完了，此时应该返回 0.5；当 i≤0 时，表示汤 A 先分配完了，此时应该返回 1；当 j≤0 时，表示汤 B 先分配完了，此时应该返回 0。

double ans = 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3));

但是需要注意，之这样写一定会显示时间超出

优化1

加入记忆化方式，也就是加入一个数组，记录在A有i和B有j的情况下的概率信息。

if (memo[i][j]==0) {
	double sum = 0.25 * (dfs(i-4,j) + dfs(i-3,j-1) + dfs(i-2,j-2) + dfs(i-1,j-3));
	memo[i][j] = sum;
}

但是仍然会出现空间超出

优化2

借助数学的方式，在n=4800时，结果为0.999994994426，而题目要求的精度为\(10^{-5}\)，并且随着n的增大，结果越来越接近1，因此，当n>4800时，直接返回1即可。

1
2
3

if (n>=4800) {
	return 1;
}

完整代码

class Solution {  
  
    double[][] memo;  
  
    public double dfs(int i, int j) {  
        if (i<=0 && j<=0) {    //表示都分配完了  
            return 0.5;  
        }  
        if (i<=0) {  
            return 1;  
        }  
        if (j<=0) {  
            return 0;  
        }  
  
        //记忆化（否则会超出时间）  
        if (memo[i][j]==0) {  
            double sum = 0.25 * (dfs(i-4,j) + dfs(i-3,j-1) + dfs(i-2,j-2) + dfs(i-1,j-3));  
            memo[i][j] = sum;  
        }  
        return memo[i][j];  
    }  
  
    public double soupServings(int n) {  
  
        // 在 10-5 下接近1，所以直接输出1即可（否则会超出空间）  
        if (n>=4800) {  
            return 1;  
        }  
        n = (n+24)/25;     //如果一开始给的汤不是25的倍数，就向上取整（多出来的一部分也可以分配）  
        memo = new double[n+1][n+1];  
        return dfs(n,n);  
    }  
}

方法二、动态规划

动态规划难在初始化。本题需要一个二维数组进行动态规划。

表示A和B都没有了
1
dp[0][0] = 0.5;

表示A没有了

1
2
3

for (int i=1;i<=n;i++) {
	dp[0][i] = 1;     //表示A没有 
}

表示B没有了（B没有返回0，所以根据初始化自动为0）

完整代码

class Solution {
    public double soupServings(int n) {
        if (n>=4800) {
	        return 1;
        }
        n = (n+24)/25;

        double[][] dp = new double[n+1][n+1];
        dp[0][0] = 0.5;     //表示A和B都没有了

        for (int i=1;i<=n;i++) {
            dp[0][i] = 1;     //表示A没有 
        }

        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {      //当j=0时就是0，而数组初始化时自动为0
                dp[i][j] = 0.25 * (dp[Math.max(0,i-4)][j] + dp[Math.max(0,i-3)][Math.max(0,j-1)] + dp[Math.max(0,i-2)][Math.max(0,j-2)] + dp[Math.max(0,i-1)][Math.max(0,j-3)]);
            }
        }
        return dp[n][n];
    }
}

809、情感丰富的文字

方法一、逐字对比+长度加速

对每个字符串进行检索，找到当前字符连续的长度。

class Solution {
    public int expressiveWords(String s, String[] words) {
        int sum = 0;
        char[] sc = s.toCharArray();
        for (String w : words) {
            if (w.length() > s.length()) {
                continue;
            }
            char[] wc = w.toCharArray();
            int i = 0, j = 0;
            boolean isFind = true;
            while (i<s.length() && j<w.length()) {    // i定位s，j定位w
                if (sc[i] == wc[j]) {    //如果字符相等
                    char t = sc[i];
                    int l1 = 1;
                    int l2 = 1;
                    while ((i+1)<s.length() && sc[i+1]==t) {
                        l1++;
                        i++;
                    }
                    while ((j+1)<w.length() && wc[j+1]==t) {
                        l2++;
                        j++;
                    }
                    if (l1==l2 || (l1 > l2 && l1 >= 3)) {
                        i++;
                        j++;
                    }
                    else {
                        isFind = false;
                        break;
                    }
                }
                else {
                    isFind = false;
                    break;
                }
            }
            if (i==s.length() && j == w.length() && isFind) {
                sum ++;
            }
        }
        return sum;
    }
}

811、子域名访问计数

本题逻辑简单，但是涉及很多java语法知识。

HashMap（散列表）

创建

HashMap<String,Integer> hash = new HashMap<String,Integer>();

添加键值对

```java
hash.put("abc",2);

查找值

1	hash.get("abc"); //输出2

更新值

1	hash.replace("abc",3); //以后hash里面"abc"对应的value就是3

1	hash.replace("abc",2,3); //只对hash键值对为"abc"-2的修改value为3，如果键值对不符合则返回false

查找键值对数量

1	hash.size()

判断是否为空

1	hash.isEmpty() //如果为空返回true

判断是否有某个key

1	hash.containsKey("abc") //如果有则返回true

判断是否有某个value

1	hash.containsValue(3) //如果有则返回true

遍历

//方法一、forEach
hash.forEach((key,value)-> {
    //对于每一组key和value的操作
    String s = value.toString() + key;
    res.add(s);
});    //不要忘记分号

//方法二、最推荐，遍历entey获取key和value
for (Map.Entry<String,Integer> entry : map.entrySet()) {  //entrySet()返回hashMap中所有映射项的集合集合视图。
    String key = entry.getKey();
    Integer value = entry.getValue();
}

//方法三、单独取出key和value
for (String key : hash.KeySet()) {    //keySet()返回hashMap中所有key组成的集合视图。
    //对key操作
}
for (String value : hash.values()) {    //values()返回hashMap中所有value组成的集合视图。
    //对key操作
}

删除所有键值对

1	hash.clear();

字符串按空格分割

对于String s = "a b c d e f g"

分割单个空格

String[] sa = s.split(" ");
//遍历输出后：
//a
//
//b
//
//
//
//
//c
//
//d
//e
//f
//
//
//
//
//
//g
//

分割多个连续空格

String[] sa = s.split("\\s+");    //正则
//遍历后：
//a
//b
//c
//d
//e
//f
//g

字符串转为整数

使用Integer.parseInt(s)

1 2	String s = "12345"; int b = Integer.parseInt(s);

长度函数

length：数组长度
length()：字符串长度
size()：列表长度

List的构建

对于单个List

1	List<String> l = new ArrayList<String>();

对于嵌套List

1	List<List<String>> ll = new ArrayList<>();

817、链表组件

先用一个容器将nums里的所有数值全都存储起来，之后在遍历链表判断当前值是否在nums数组中。

什么样的容器具有这样的功能呢？String？Map？对！Map最合适！

所以我们选择HashMap,和他的containsKey（也可以使用containsValue）：

HashMap<Integer,Boolean> hash = new HashMap<Integer,Boolean>();
for (int num : nums) {
    hash.put(num,true);
}
//...
if (hash.containsKey(p.val)) {
    
}

然后再判断有多少个组件，常规思路。

831. 隐藏个人信息

中等题，简单构造题。

855. 考场就座⭐

题解

方法一、有序集合

考察有序集合 TreeSet 的应用。

思路其实并不复杂，对于 leave 其实就是 remove () 函数；对于 seat 其实就是判断每一段之间的距离的一半和最左边与左端点的距离和最右边与右端点的距离的最大值。如果是段之间的距离更大，那么点就在段中点；如果左边的距离更大，那么点就在 0；如果右边距离更大，那么点就在 n-1。

此外还需要注意局部变量和全局变量之间的转换。

代码如下：

class ExamRoom {

    // 定义全局变量
    TreeSet<Integer> ts;
    int n;

    public ExamRoom(int n) {
        ts = new TreeSet<>();
        this.n = n;      //将局部变量转为全局变量
    }
    
    public int seat() {
        if (ts.size()==0) {
            ts.add(0);
            return 0;
        }
        //当有一个时，第二个需要放在最后
        //但是需要考虑如果一开始放了两个，但是把第一个leave，只有最后一个了，应该怎么处理
        
        //从左向右遍历每一段之间的最短（暂时不考虑两端）
        int left = ts.first();
        int disl = ts.first()-0;           //初始为最左边离左端点的距离，变量表示两个向量之间的距离
        int inx = 0;                     //要放置的位置，初始是0，是考虑到端点没有放，但是中间有值
        for (int x : ts) {
            if (disl < (x-left)/2) {
                disl = (x-left)/2;
                inx = (x+left)/2;
            }
            left = x;
        }
        //此时得到的disl表示 左边距离左端点 和 每一段之间若放置的两边的距离的最大值

        int disr = n-1-ts.last();        //表示最右边距离右端点的距离

        if (disl < disr) {    //表示最右边距离右端点的距离最大，应该放置在右端点处
            inx = n-1;
        }

        ts.add(inx);

        return inx;
    }
    
    public void leave(int p) {
        ts.remove(p);
    }
}

方法二、有序集合+优先队列

见题解。

856、括号的分数

方法一、栈

遇到括号匹配，第一时间想到什么？——栈！！

但是Java没有栈，只能用Deque双端队列代替。

需要多次使用的方法：

//创建
Deque<String> dq = new LinkedList<>();

//增加
dq.addLast(st);

//弹出并返回
String temp = dq.pollLast();

拓展：

String的相等操作：

1	s1.equals(s2);

char的相等操作

c1 == c2;

char转为String

1	String st = String.valueOf('a');

char转为int

1	int n = '5' - '0';

String转为int

1	sum = Integer.parseInt('23');

方法二、一次遍历⭐

这个方法思路真的很妙！

首先，所有的()都是1，所以用replace将()换成1
对s进行遍历，遇到1个(，则对于后面的1乘以2，遇到)，则对后面的1除以2
例子：((())(())())

可以看出这题的结果时：(1*2 + 1*2 + 1)*2 = 1*2*2 + 1*2*2 + 1*2
1. 替换：((1)(1)1)
2. 从左遍历，第一个1左边有2个(、0个)，所以对于1*2*2
  
  第二个1左边有3个(、1个)，所以对于1*2*2*2/2 = 1*2*2
  
  第三个1左边有3个(、2个)，所以对于1*2*2*2/2/2 = 1*2

注意：连续乘以n个2的操作，可以用number << n表示。

862、和至少为K的最短子数组⭐⭐

很难且恶心人的一题。

贴上我的心路历程：

一开始我是这样的：

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        if (n==1) {
            if (nums[0]>=k) {
                return 1;
            }
            else {
                return -1;
            }
        }
        int i=0, j=1;
        int temp = nums[i];
        int step = 1;
        int min = 100001;
        while (i<n) {
            if (j<n) {
                if (temp>=k) {
                    min = Math.min(min,step);
                    temp -= nums[i];
                    i++;
                    step--;
                }
                else {
                    temp += nums[j];
                    step++;
                    j++;
                }
            }
            else {
                if (temp>=k) {
                    min = Math.min(min,step);
                    temp -= nums[i];
                    i++;
                    step--;
                }
                else {
                    temp -= nums[i];
                    i++;
                    step--;
                }
            }
            
        }
        return min==100001 ? -1 : min;
    }
}

后来发现，如果出现 k=5， 1, -2, 2, 7这种情况就没法找到真正的最短。

然后我使用双层for循环：

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int[] preadd = new int[n+1];    //记录当前i以前的元素的和
        for (int i=1;i<n+1;i++) {
            preadd[i] = preadd[i-1] + nums[i-1];
        }
        int min = 100001;
        for (int i=0;i<n;i++) {
            if (nums[i]<=0) {
                continue;
            }
            for (int j=i+1;j<n+1;j++) {
                if (j-i>=min) {
                    break;
                }
                if (preadd[j]-preadd[i]>=k) {
                    min = Math.min(min,j-i);
                    break;
                }
            }
        }
        return min==100001 ? -1 : min;
    }
}

最后，根据题解……我转换了思路。⭐

以每个元素为开始的最短的长度是一定的

preadd的作用看代码能懂吧，所以以i为开始的满足条件的数组的长度就是preadd[j]-preadd[i]，长度就是j-i。

利用一个for循环控制结束的字符，用一个队列控制开始的字符。（其实数组也可，但是会慢些）

第一个while是确定结束位置，依次更新初始位置。

第二个while是对结束位置的左边进行筛选，为了减少复杂度，如果它的相邻左边的preadd比它的preadd要大，根据preadd[j]-preadd[i]，如果preadd[i]要比preadd[i-1]小，那么以某个j结尾的，一定会选择i而不会以i-1开头，所以在这里可以删掉i-1了。

每次都将当前j加入队列。

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] preadd = new long[n+1];    //记录当前i以前的元素的和
        for (int i=1;i<n+1;i++) {
            preadd[i] = preadd[i-1] + nums[i-1];     //存的是当前值之前的所有的和
        }
        int min = n+1;
        Deque<Integer> dq = new ArrayDeque<Integer>();    //dq存的是需要查询的起始位置
        for (int j=0;j<n+1;j++) {     //以i为结尾，以dq.pollFirst()为开始
            while (!dq.isEmpty() && preadd[j]-preadd[dq.peekFirst()]>=k) {
                int i = dq.pollFirst();
                min = Math.min(min,j-i);
            }
            while (!dq.isEmpty() && preadd[dq.peekLast()]>=preadd[j]) {
                dq.pollLast();
            }
            dq.addLast(j);
        }
        return min==n+1 ? -1 : min;
    }
}

870、优势洗牌⭐

本题思路简单，但是操作困难，需要知道如何保证不动nums2的前提下，根据其值对其下标进行排序的方法

这里涉及到sort的匿名函数表达式的知识点：

Integer[] index = new Integer[n];
for (int i=0;i<n;i++) {
    index[i] = i;     //此时index的值对应nums2的每个值的下标
}

//重点：对index排序，排序的规则是对于index的值a和b，如果nums2[a]>nums2[b]，则a在b后面
Arrays.sort(index,(a,b)->nums2[a]-nums[b]);
//这里的意思是，如果nums[a]-nums[b]>0，返回的是1，表示前者更大，按照我们的约定，应该将b放在a前面

这里需要注意的是：

使用匿名表达式的数组必须是原始数组，也就在这里index数组是不能是int，只能是Integer
Arrays.sort(index,(a,b)->function);表示的是对于index数组而言，只有当function>0时，会将(a,b)变成(b,a)

关于sort函数复写排序规则，还有一种更加常规的方法

Arrays.sort(index, new Comparator<Integer>() {       //注意index一定要是Integer（不能是int）
    public int compare(Integer a, Integer b) {       //注意是和上面的In'te'g
        if (nums2[a] > nums2[b]) {    //按照要求，a应该在b后面，也就是要从(a,b)变成(b,a)
            return 1;         //return 1表示调换
        }
        else {
            return -1;       //return -1表示保持不变
        }
    }
});

878、第N个神奇数字⭐🌟

这题思路很巧妙，我们会第一时间想到找到所有的满足条件的数，直到第ｎ个，但是这样的工作量真的太大了，应为涉及到加法和乘法。

所以我们不妨换个思路，在很大的范围内，找到这个符合条件的数。

首先确定搜索方法，一般查找都会选择二分查找，效率高。
再确定范围，起点范围0，终点范围呢？其实用max(a,b)*n或者min(a,b)*n都可以。但是通过测试，我们的目标值其实更接近min(a,b)*n，但是正因为这样，如果使用min(a,b)*n，需要更多步骤才能找到，所以我们选择max(a,b)*n。

那判断是否为目标数值的条件呢？

我们通过小数找规律，可以发现，第n个符合规则的数一定是

num/a + num/b - num/gbs(a,b) == n，可以好好揣摩一下这个规则。

但是并不是只有我们目标的那个第n个符合规则的数满足，第n和第n+1个数之间的数都满足，所以我们需要找到符合这个条件的最左值。

while (left<right) {
    long mid = left + (right-left)/2;

    //核心代码，判断一个数是不是我们要的第n个数
    if (mid/a + mid/b - mid/gbs_num < n) {
        left = mid + 1;
    }
    else {    //注意：当在第n~n+1个数之间的所有数都满足这个条件（因为/只保留了商），因此我们需要找到第一个满足这个条件的数
        right = mid;
    }
}

最后返回left%MOD即可。

（找最小公倍数，需要找到最小公因数，这个很简单。）

完整代码

class Solution {
    public static int gys(int a, int b) {
        if (b==0) {
            return a;
        }
        else {
            return gys(b,a%b);
        }
    }
    public static int gbs(int a, int b) {
        return a*b/gys(a,b);
    }
    public int nthMagicalNumber(int n, int a, int b) {
        int MOD = 1_000_000_007;
        long left = 0;
        //这里使用max或者min都行，但是max内存消耗更少，因为右边界越大，目标就月靠近中间，能更快找到。如果使用min，反而目标靠近边界，复杂度更高。
        long right = (long) Math.max(a,b)*n;      // 注意Math库返回的是int类型
        long gbs_num = gbs(a,b);    //找到最小公倍数
        // System.out.println(gbs_num);
        while (left<right) {
            long mid = left + (right-left)/2;

            //核心代码，判断一个数是不是我们要的第n个数
            if (mid/a + mid/b - mid/gbs_num < n) {     
                left = mid + 1;
            }
            else {    //注意：当在第n~n+1个数之间的所有数都满足这个条件（因为/只保留了商），因此我们需要找到第一个满足这个条件的数
                right = mid;
            }
        }
        return (int) (left%MOD);    //需要注意：(int)只对后面相邻的数有效，所以别忘了括号。

    }
}

tips

一定要注意Math库返回的都是int类型，本题需要转为long型

882、细分图中的可到达节点

1
2
3

891、子序列宽度之和

典型数学题目

Screenshot_20221118_105117_com.huawei.browser

仔细分析题目，可以发现子序列只与最大值和最小值有关，和序列的顺序无关。

所以可以先对数组进行排序。

再按照下面思路进行：

直接看代码更容易理解：

class Solution {

    int MOD = 1000000007;

    public int sumSubseqWidths(int[] nums) {
        Arrays.sort(nums);
        long k = 1;
        long sum = 0;
        long temp = 0;
        for (int i=1;i<nums.length;i++) {
            k = (k << 1)%MOD;
            temp = (temp*2%MOD + nums[i-1])%MOD;
            sum = (sum + (nums[i]*(k-1) - temp)%MOD)%MOD;
        }

        return (int)sum;
    }
}

901、股票价格跨度⭐

方法一、栈⭐

题目翻译

返回每一天的比这一天的股票价格小于或者等于的连续天数。

思路

构造一个二元栈：

class Stock {
    public int price;
    public int day;
    public Stock(int price, int day) {
        this.price = price;
        this.day = day;
    } 
}

对于输入的每一个节点，默认day是1。题解

public int next(int price) {
    int day = 1;
    if (!st.isEmpty()){
        while (!st.isEmpty()) {
            Stock temp = st.peekLast();
            if (price>=temp.price) {
                st.pollLast();
                day = day + temp.day;
            }
            else {
                break;
            }
        }
    }
    st.addLast(new Stock(price,day));
    return day;
}

完整代码

（面向对象的写法，注意结构体的构造等知识）

class StockSpanner {

    Deque<Stock> st;

    class Stock {
        public int price;
        public int day;
        public Stock(int price, int day) {
            this.price = price;
            this.day = day;
        } 
    }

    public StockSpanner() {
        st = new ArrayDeque<Stock>();
    }
    
    public int next(int price) {
        int day = 1;
        if (!st.isEmpty()){
            while (!st.isEmpty()) {
                Stock temp = st.peekLast();
                if (price>=temp.price) {
                    st.pollLast();
                    day = day + temp.day;
                }
                else {
                    break;
                }
            }
        }
        st.addLast(new Stock(price,day));
        return day;
    }
}

方法二、数组

思路一致。

我们还需要两个指针，分别是index指针，用来指向“待输入股票”；p指针，index指针的前一个指针，用来与“待输入股票”进行price对比用的，如果它的price小于等于“待输入股票”的price，p就会向前移动。

关于p向前移动还有一点需要注意的就是，p向前移动格子的数量，就是days的具体值；当days等于1时，就向前移动1个格子；如果days等于2时，就向前移动2个格子（因为days等于2，说明已经是两个格子聚合过的值了，就不需要重复统计了）。

初始化时注意：

public StockSpanner() {
    index = 0;
    prices = new int[100010];
    days = new int[100010];
}

方法三、List

思路一致。

902、最大为 N 的数字组合⭐⭐

非常难的一题，难在实现上！

904、水果成篮

构建两个数组，分别记录某一个连续值的值和出现的次数，比较简单。（当然可以将两个数组并为一个二维数组）

907、子数组的最小值之和⭐⭐

方法一、单调栈+动态规划

维护两个数组，分别维护左边界和右边界（对于下标为i的辐射左范围为left[i]+1（left[i]不在范围内））。

建立一个单调栈，两次遍历数组，更新左边界和右边

3 4 1 2 5 6

对于1的辐射范围，左边范围长度为3，右边为4 1, 41, 12, 341, 412, 125, 3412, 4125, 1256, 34125, 41256, 341256，共12个

对于4的辐射范围，左边范围长度为1，右边为1 4，共1个

对于6的辐射范围，左边范围长度为1，右边为1 6，共1个

看代码

class Solution {
    public static int MOD = 1000000007;
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];    //对于下标为i的辐射左范围为left[i]+1（left[i]不在范围内）
        int[] right = new int[n];
        
        Deque<Integer> dq = new ArrayDeque<Integer>();
        
        for (int i=0;i<n;i++) {
            while (!dq.isEmpty() && arr[i]<arr[dq.peekLast()]) {
                dq.pollLast();
            }
            if (dq.isEmpty()) {
                left[i] = -1;
            }
            else {
                left[i] = dq.peekLast();
            }
            dq.addLast(i);
        }

        dq.clear();
        for (int i=n-1;i>=0;i--) {
            while (!dq.isEmpty() && arr[i]<=arr[dq.peekLast()]) {
                dq.pollLast();
            }
            if (dq.isEmpty()) {
                right[i] = n;
            }
            else {
                right[i] = dq.peekLast();
            }
            dq.addLast(i);
        }

        // 3 4 1 2 5 6
        // 对于1的辐射范围，左边范围长度为3，右边为4
        // 1, 41, 12, 341, 412, 125, 3412, 4125, 1256, 34125, 41256, 341256，共12个
        // 对于4的辐射范围，左边范围长度为1，右边为1
        // 4，共1个
        // 对于6的辐射范围，左边范围长度为1，右边为1
        // 6，共1个

        long sum =0;
        for (int i=0;i<n;i++) {
            sum = (sum + (long)arr[i] * (i-left[i]) * (right[i]-i)) % MOD;
        }

        return (int)sum;
    }
}

915、分割数组

方法一、最小值分割

先找到数组的最小值，最小值包括左边的部分和右边的部分一定需要分开的，如果左边的最大值<=右边的最小值，那么ok，否则对右边部分继续找最小值，继续划分。

方法二、两次遍历

先从后向前遍历一遍，用min[i]表示i位置及其以后区域的最小值。

再从前往后遍历一遍，用max记录以当前元素结尾的区域的最大值。

第二次遍历过程中，如果某一次遍历时发现max <= min[i+1]，则i就是分隔符，返回i+1个元素。

918、环形子数组的最大和⭐

本题是53、最大子数组和的加强版。使用的仍然是动态规划的内容。

分析

本题因为是环形，所以需要考虑两种情况。

情况1：我们的最终答案是53题中的不考虑环的情况。

情况2：我们的答案包含nums的尾部和nums的首部。

思路

情况1很简单，直接仿照53题进行即可。

情况2复杂，需要考虑首位，但是首位又是动态的，很麻烦。但是我们能不能换种思路，我们要找到nums的最小子数组和min。那么最长的首位组合就是整个nums之和减去这个最小子数组和。

特殊

我们需要考虑，如果情况一得到的max小于0，说明整个nums中没有一个元素是>0的，那么直接输出max（矮子当中选将军），它就是最大的那个了。否则表示数组中存在正数，那么输出max和sum-min中的最大值

927、三等分

思路有点复杂，实现不难：

先判断每一组有多少个1，把每个1的下标都放在一个新的数组中，然后判断三组之间对应的1和1之间的距离是否相等，再判断最后一组的最后一个1后的空格其他组是否能满足。

934、最短的桥⭐

比较难的一题，题目难懂，方法难想到。

思路

代码

详细的思路看代码更好理解

class Solution {

    int[][] step = {{1,0},{-1,0},{0,1},{0,-1}};

    Deque<int[]> edge;

    public int shortestBridge(int[][] grid) {
        boolean isFind = false;

        edge = new ArrayDeque<>();

        //通过找到一个岛屿的一块，利用DFS找到这个岛屿的所有块，并标记为2
        //并找到它的边源水域，也标记成为2，并加入edge队列
        for (int i=0;i<grid.length;i++) {
            if (isFind) {
                break;
            }
            for (int j=0;j<grid[0].length;j++) {
                if (isFind) {
                    break;
                }
                if (grid[i][j]==1) {    //表示已经找到了第一个岛屿的一块了
                    isFind = true;
                    Mark(grid,i,j);     //对当前块进行标记为2（通过DFS岛屿标记）
                }
            }
        }

        int result = 1;    //目前已经扩充一波水域

        //此时第一轮扩充已经完成
        while (!edge.isEmpty()) {

            int n = edge.size();    //获取第一个岛屿的边缘水域
            for (int i=0;i<n;i++) {
                int[] loc = edge.pollFirst();    //第一个区域的边缘位置
                for (int[]s : step) {    //对当前位置的四个方向进行扩充
                    int x = loc[0]+s[0], y = loc[1]+s[1];    
                    if (!isLegal(x,y,grid.length)) {       //如果位置不合法
                        continue;
                    }
                    if (grid[x][y] == 2) {
                        continue;
                    }
                    if (grid[x][y] == 1) {    //表示已经找到了另一个岛屿
                        return result;
                    }
                    if (grid[x][y] == 0) {    //扩充水域
                        grid[x][y] = 2;
                        edge.addLast(new int[]{x,y});
                    }
                }
            }
            result++;
        }
        return result;
    }

    public void Mark(int[][] grid, int i, int j) {
        if (!isLegal(i,j,grid.length)) {    //如果不是合法位置，退出
            return;
        }
        if (grid[i][j]==2) {    //如果是同一个岛屿且已经被标记，退出
            return;
        }
        if (grid[i][j]==1) {     //如果是同一个岛屿但是还没有被标记
            grid[i][j] = 2;
            for (int[]s : step) {
                Mark(grid,i+s[0],j+s[1]);
            }
        }
        if (grid[i][j]==0) {     //如果遇到水域，则表示已经到了这个岛屿的边界了，将这个水也变成岛屿的一部分，在存储边界水域的edge中添加
            grid[i][j] = 2;
            edge.addLast(new int[]{i,j});
        }
    }

    public boolean isLegal(int i, int j, int n) {    //判断是否在合法区域（没有超过边界）
        if (i<0 || i>=n || j<0 || j>=n) {
            return false;
        }
        return true;
    }
}

970. 强整数

中等题，但是比较简单。代码如下：

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> set = new HashSet<>();
        List<Integer> x_list = new ArrayList<>();
        List<Integer> y_list = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        int sum = 1;
        if (x==1) {
            x_list.add(x);
        }
        while (x!=1 && sum <= bound) {
            x_list.add(sum);
            sum = sum*x;
        }
        sum = 1;
        if (y==1) {
            y_list.add(y);
        }
        while (y!=1 && sum <= bound) {
            y_list.add(sum);
            sum = sum*y;
        }
        for (int i=0;i<x_list.size();i++) {
            for (int j=0;j<y_list.size();j++) {
                if (x_list.get(i)+y_list.get(j)<=bound) {
                    set.add(x_list.get(i)+y_list.get(j));
                }
                else {
                    break;
                }
            }
        }

        for (int n : set) {
            res.add(n);
        }

        return res;
    }
}

982. 按位与为零的三元组

我们可以先枚举任意两个数 x 和 y，用数组统计它们的按位与结果 x&y出现的次数。然后枚举 x 和 y 的按位与结果 xy，再枚举 z，如果 xy&z=0，则将 cnt[xy] 的值加入答案。

常识：两个数相与的结果一定是小于等于这两个数

class Solution {
    public int countTriplets(int[] nums) {
        // 两个数相与的结果一定是小于等于这个数
        int max_n = 0;
        for (int n : nums) {
            max_n = Math.max(max_n, n);
        }

        int[] re = new int[max_n+1];
        for (int a : nums) {
            for (int b : nums) {
                re[a & b]++;
            }
        }

        int res = 0;
        for (int i=0;i<max_n+1;i++) {
            if (re[i]!=0) {
                for (int n : nums) {
                    if ((i & n) == 0) {
                        res += re[i];
                    }
                }
            }
        }

        return res;
    }
}

1003. 检查替换后的词是否有效

方法一、字符串操作

不断对 s 删除"abc"字符串，如果最后能删除干净，那么返回 true，否则返回 false。代码如下：

class Solution {
    public boolean isValid(String s) {
        if (s.length()%3!=0) {
            return false;
        }
        while (s.length()!=0) {
            // System.out.println(s);
            int i = 0;
            boolean isFind = false;
            for (i=0;i<s.length()-2;i++) {
                if (s.substring(i,i+3).compareTo("abc")==0) {
                    s = s.substring(0,i) + s.substring(i+3);
                    isFind = true;
                }
            }
            if (!isFind) {
                System.out.println(s);
                return false;
            }
        }
        return true;
    }
}

方法二、栈

其实思路与上面一致，但是上面的方法每次都要重新构造 s，会有很大的时间和空间开销，所以用栈将字符串的每个字符依次入栈，如果遇到"abc"，弹出去，依次进行，如果栈空则 true。代码如下：

class Solution {
    public boolean isValid(String s) {
        if (s.length()%3!=0) {
            return false;
        }
        Deque<Character> dq = new LinkedList<>();
        char[] sc = s.toCharArray();
        for (int i=0;i<s.length();i++) {
            dq.addLast(sc[i]);
            while (dq.size()>=3 && dq.peekLast()=='c') {
                char c = dq.pollLast();
                char b = dq.pollLast();
                char a = dq.pollLast();
                if (a!='a' || b!='b' || c!='c') {
                    dq.addLast(a);
                    dq.addLast(b);
                    dq.addLast(c);
                    break;
                }
            }
        }
        if (dq.size()==0) {
            return true;
        }
        return false;
    }
}

方法三、StringBuilder

这是上面两种方法的结合。代码如下：

class Solution {
    public boolean isValid(String s) {
        if (s.length()%3!=0) {
            return false;
        }
        StringBuilder sb = new StringBuilder();
        char[] sc = s.toCharArray();
        for (int i=0;i<s.length();i++) {
            sb.append(sc[i]);
            if (sb.length()>=3 && "abc".equals(sb.substring(sb.length()-3))) {
                sb.delete(sb.length()-3,sb.length());
            }
        }
        if (sb.length()==0) {
            return true;
        }
        return false;
    }
}

1105. 填充书架⭐

考察： #动态规划

中等题，思路难。

题解：题解

这里 dp[i] 表示在放到第 i 本书的时候的总高度最优解，但这并不一定是放到最后一本书的最优解。要想找到第 i 本书的最优解，需要从后往前依次判断，如果第 [j, i] 本书都放在同一层（前提是厚度不超过）, 那么总高度会不会变小。这样判断直到 i 所在的这一层的厚度到顶了，将最优解的高度存入 dp[i]，表示我放到 i 这本书的时候的高度最优解。

代码如下：

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, 1000*1000);
        dp[0] = 0;

        // dp[i]表示在放到第i本书的时候的最优解
        
        for (int i=1; i<=n; i++) {
            int h = 0, w = 0;
            for (int j=i; j>0; j--) {
                if (w + books[j-1][0] <= shelfWidth) {   // 表示第j本书放入新的一层
                    w += books[j-1][0];
                    h = Math.max(h, books[j-1][1]);
                    dp[i] = Math.min(dp[i], dp[j-1]+h);
                }
                else {
                    break;
                }
            }
        }
        return dp[n];
    }
}

1014、最佳观光组合⭐

动态规划

数学的正则运算。

values[i] + values[j] + i - j == (values[i] + i) + (values[j] - j)

完整代码，思路很清晰：

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int res = 0;
        int maxi = values[0];    //记录最大的values[i]+i
        //找最大的values[j]-j
        for  (int j=1;j<values.length;j++) {
            //以当前节点为j，将它和前面的最大的i对应的值相加，和原有的res比较
            res = Math.max(res, maxi+values[j]-j);
            //判断如果当前节点不是j而是i，和原本的maxi进行比较更新maxi
            maxi = Math.max(maxi, values[j]+j);
        } 
        return res;
    }
}

1017. 负二进制转换⭐

考察： #位运算

思路：构建 bits 数组，bits[i] 表示需要 \((-2)^i\) 的次数。但是此时只需要对每个元素进行计数，有以下的规律。

对于 \(2^i\)，如果 i 为偶数时，此时 \(2^i = (-2)^i\)；
对于 \(2^i\)，如果 i 为奇数时，此时 \(2^i = (-2)^{i+1} + (-2)^i\)

if (i % 2 == 0) {     // 如果i是偶数
	bits[i] += 1;
}
else {      // 如果i是奇数
	bits[i+1] += 1;
	bits[i] += 1;
}

对已经构造好的 bits 数组处理，要求每个值只能是 0 或者-1。

如果 h[i]>=2： - 如果 h[i+1]>0，那么 h[i]的两份可以抵消 h[i+1]的一份（因为他们是异号）。 - 否则，h[i]的两份等价于 h[i+1]的一份和 h[i+2]的一份的和。

for (i=0;i<32;i++) {
	while (bits[i]>=2 && bits[i+1]>0) {
		bits[i] -= 2;
		bits[i+1] -= 1;
	}
	while (bits[i]>=2) {
		bits[i] -= 2;
		bits[i+1] += 1;
		bits[i+2] += 1;
	}
}

题解：负二进制转换题解

代码如下：

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) {
            return "0";
        }
        int[] bits = new int[32];
        int i = 0;
        while (n!=0) {
            if ((n & 1) == 1) {
                if (i % 2 == 0) {
                    bits[i] += 1;
                }
                else {
                    bits[i+1] += 1;
                    bits[i] += 1;
                }
            }
            n = n >> 1;
            i++;
        }
        for (i=0;i<32;i++) {
            while (bits[i]>=2 && bits[i+1]>0) {
                bits[i] -= 2;
                bits[i+1] -= 1;
            }
            while (bits[i]>=2) {
                bits[i] -= 2;
                bits[i+1] += 1;
                bits[i+2] += 1;
            }
        }
        boolean isstart = false;
        StringBuilder sb = new StringBuilder();
        for (i=31;i>=0;i--) {
            if (bits[i]!=0) {
                isstart = true;
            }
            if (isstart) {
                sb.append(String.valueOf(bits[i]));
            }
        }
        return sb.toString();

    }
}

1019. 链表中的下一个更大节点

中等题。思路：将链表先变成数组，然后利用栈的原理找到第一个大于的元素，存入栈的是元素在数组的下标。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        ListNode t = head;
        int len = 0;
        while (t!=null) {
            len++;
            t = t.next;
        }
        int[] nums = new int[len];
        t = head;
        int i = 0;
        while (t!=null) {
            nums[i] = t.val;
            t = t.next;
            i++;
        }

        Deque<Integer> dq = new LinkedList<Integer>();
        int[] res = new int[len];
        
        for (i=0;i<len;i++) {
            while (dq.size()!=0) {
                if (nums[dq.peekLast()]<nums[i]) {
                    res[dq.pollLast()] = nums[i];
                }
                else {
                    break;
                }
            }
            dq.addLast(i);
        }
        while (dq.size()!=0) {
            res[dq.pollFirst()] = 0;
        }

        return res;
    }
}

1023. 驼峰式匹配

中等题，但是很简单，直接对应遍历即可。代码如下：

class Solution {
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        int n = queries.length;
        char[] pc = pattern.toCharArray();
        int pl = pc.length;
        ArrayList<Boolean> res = new ArrayList<Boolean>();
        for (int i=0;i<n;i++) {
            String s = queries[i];
            char[] sc = s.toCharArray();
            int k = 0;
            boolean isTrue = true;
            for (int j=0;j<sc.length;j++) {
                if (k<pl && sc[j]==pc[k]) {
                    k++;
                    continue;
                }
                else {
                    if (sc[j]>='A' && sc[j]<='Z') {
                        isTrue = false;
                        break;
                    }
                }
            }
            if (isTrue && k==pl) {
                res.add(true);
            }
            else {
                res.add(false);
            }
        }
        return res;

    }
}

1026. 节点与其祖先之间的最大差值

考察： #树 #前序遍历

中等题，需要认真审题。要注意得是：A、B 必须在一条枝上，但不一定是相邻得。这里使用得前序遍历。

前序遍历核心代码：

public void find(TreeNode r) {
	if (r==null) {
		return;
	}
	System.out.println(r.val);
	find(r.left);
	find(r.right);
	return ;
}

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int res = 0;
    public int maxAncestorDiff(TreeNode root) {
        dfs(root,-1,100001);
        return res;
    }

    // 左右中
    public void dfs(TreeNode r, int max, int min) {
        if (r==null) {
            return;
        }
        int d = r.val;
        max = Math.max(max, d);
        min = Math.min(min, d);
        res = Math.max(res, Math.abs(max-min));
        dfs(r.left, max, min);
        dfs(r.right, max, min);
        return ;
    }
}

1027. 最长等差数列⭐⭐

考察： #动态规划 #递归

题解：题解

方法一、递归

思路在题解，代码有注释。代码如下：

class Solution {
    public HashMap<Integer, Integer>[] maxLen;    // 这是一个hash数组，长度为n。每个元素为一个hash表，key为方差，value为在这个方差下的长度
    public int[] nums;
    public int res  = 0;
    public int longestArithSeqLength(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        maxLen = new HashMap[n];
        for (int i=1;i<n;i++) {
            dfs(i);
        }
        return res;
    }
    public HashMap<Integer,Integer> dfs(int i) {
        // 之前已经计算过了以i下标元素为结尾的hash表了，直接返回
        if (maxLen[i] != null) {
            return maxLen[i];
        }

        // 初始化
        maxLen[i] = new HashMap<Integer, Integer>();

        // 填充以nums[i]为结尾的hash表
        for (int j=i-1;j>=0;j--) {
            int d = nums[i] - nums[j];    // 这两个数之间的方差
            if (!maxLen[i].containsKey(d)) {    // 如果这个方差没有计算过就放进去，如果已经计算过说明在j~i之间出现过一样的数字，这里就不要考虑了
                maxLen[i].put(d, dfs(j).getOrDefault(d,1)+1);    // 如果以j为结尾的方差为d的长度没有，那么j位置算1个，i位置算一个，一共2个
                res = Math.max(res, maxLen[i].get(d));
            }
        }

        return maxLen[i];
    }
}

优化

将代码合并在一个函数内。代码如下：

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer>[] maxLen = new HashMap[n];
        int res = 0;
        for (int i=0;i<n;i++) {    // 从0开始，方便初始化
            maxLen[i] = new HashMap<Integer, Integer>();
            for (int j=i-1;j>=0;j--) {
                int d = nums[i] - nums[j];    // 这两个数之间的方差
                if (!maxLen[i].containsKey(d)) {    // 如果这个方差没有计算过就放进去，如果已经计算过说明在j~i之间出现过一样的数字，这里就不要考虑了
                    maxLen[i].put(d, maxLen[j].getOrDefault(d,1)+1);    // 如果以j为结尾的方差为d的长度没有，那么j位置算1个，i位置算一个，一共2个
                    res = Math.max(res, maxLen[i].get(d));
                }
            }
        }
        return res;
    }
}

方法二、动态规划

关键是区间映射。代码如下：

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][1001];      // nums[i]的范围为[0,500]，所以d最小为-500，最大为500。把[-500,500]映射到[0,1000]中
        int res = 0;
        for (int i=1;i<n;i++) {   
            for (int j=i-1;j>=0;j--) {
                int d = nums[i] - nums[j] + 500;    // 区间映射到[0,1000]
                if (dp[i][d]==0) {   
                    dp[i][d] = dp[j][d] + 1;    // 注意这里是不包括i位置自己的
                    res = Math.max(res, dp[i][d]);
                }
            }
        }
        return res + 1;
    }
}

1031. 两个非重叠子数组的最大和

考察： #滑动窗口

中等题，但是比较简单，注意审题。代码如下：

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] pre = new int[n];    // pre[i]表示i之前的元素再firstlen长度的总和
        int[] end = new int[n];      // end[i]表示i及其之后的firstlen长度的总和
        int res = 0;

        if (firstLen+secondLen>n) {
            return 0;
        }

        int sum = 0;
        // 0 1 2 3 4 5   len=2
        for (int i=0;i<n;i++) {
            if (i<firstLen-1) {
                pre[i] = 0;
                sum += nums[i];
            }
            else if (i == firstLen-1) {
                sum += nums[i];
                pre[i] = sum;
            } 
            else {
                sum += nums[i];
                sum -= nums[i-firstLen];
                pre[i] = Math.max(pre[i-1], sum);
            }
        }

        sum = 0;
        // 0 1 2 3 4 5   len=2
        for (int i=n-1;i>=0;i--) {
            sum += nums[i];
            if (i>n-firstLen) {
                end[i] = 0;
            }
            else if (i==n-firstLen) {
                end[i] = sum;
            }
            else {
                sum -= nums[i+firstLen];
                end[i] = Math.max(end[i+1],sum);
            }
        }

        sum = 0;
        for (int i=0;i<n;i++) {
            sum += nums[i];
            if (i<secondLen-1) {
                continue;
            }
            else {
                if (i-secondLen>=0) {
                    sum -= nums[i-secondLen];
                    res = Math.max(res, sum + pre[i-secondLen]);
                }
                if (i+1<n) {
                    res = Math.max(res, sum + end[i+1]);
                }
            }
        }

        // for (int i=0;i<n;i++) {      // 表示i之前的 和 i及其之后的
        //     System.out.print(pre[i]);
        //     System.out.print(" ");
        //     System.out.println(end[i]);
        // }
        return res;

    }
}

1032. 字符流⭐

考察： #前缀树

基础：208. 实现 Trie (前缀树)

典型的前缀树题，写这一题前一定要先写 208 题。本题实际上就是前缀树的反思路，是以当前输入的字符为结尾，往前找。而存储 word 的时候是将每个 word 倒着存。

优化：注意条件 1 <= words[i].length <= 200，所以在遍历时可以设置提前退出条件，否则会超时。

代码如下：

class TreeNode {
    TreeNode[] children;
    boolean isStart;
    public TreeNode() {
        children = new TreeNode[26];
        isStart = false;
    }
}


class StreamChecker {
    TreeNode root = new TreeNode();    
    StringBuilder sb = new StringBuilder();

    public StreamChecker(String[] words) {    //后缀树
        TreeNode r;
        for (String word : words) {
            r = root;
            char[] sc = word.toCharArray();
            for (int i=word.length()-1;i>=0;i--) {
                int idx = sc[i]-'a';
                if (r.children[idx]==null) {
                    r.children[idx] = new TreeNode();
                }
                r = r.children[idx];
            }
            r.isStart = true;
        }
    }
    
    public boolean query(char letter) {
        sb.append(letter);
        TreeNode r = root;

        for (int i=sb.length()-1,j=0; i>=0 && j<201; i--,j++) {
            int idx = sb.charAt(i)-'a';
            if (r.children[idx]==null) {
                return false;
            }
            else {
                r = r.children[idx];
                if (r.isStart==true) {
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker obj = new StreamChecker(words);
 * boolean param_1 = obj.query(letter);
 */

1033. 移动石子直到连续👍

思路：

代码如下：

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] map = new int[]{a,b,c};
        Arrays.sort(map);
        if (map[2]-map[0]==2) {
            return new int[]{0,0};
        }
        else {
            if (map[1]-map[0]<=2 || map[2]-map[1]<=2) {
                return new int[]{1, map[2]-map[0]-2};
            }
            else {
                return new int[]{2, map[2]-map[0]-2};
            }
        }
    }
}

1039. 多边形三角剖分的最低得分⭐

考察： #动态规划 #记忆搜索

中等题，有难度，但是只要思路对了那就好算。

动态规划（递推）的思路。dp[i][j]表示从第 i 节点到第 j 节点的最短乘积和。转换为子问题，遍历 i 和 j 中的点 k，k 将整个图形分割为三部分，分别是 dp[i][k]、dp[k][j]、以 ijk 为顶点的三角形。按照这样的思路配合利用数组记录 dp[i][j]，可以快速求出 dp[0][n-1]。值得注意的是：如果 k == i + 1，那么直接返回 0，如果 j == i + 2 直接表示 i 到 j 就是一个三角形，直接返回他们的乘积。return 之前都别忘了保存，搜索之前别忘了记忆化查找。

完整代码如下：

class Solution {
    public int[][] dp;
    public int[] values;

    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        this.values = values;
        this.dp = new int[n][n];
        return find(0,n-1);

    }
    public int find(int start, int end) {
        if (dp[start][end]!=0) {
            return dp[start][end];
        }
        if (end - start <= 1) {
            dp[start][end] = 0;
            return 0;
        }
        if (end - start == 2) {
            dp[start][end] = values[start]*values[start+1]*values[end];
            return dp[start][end];
        }
        int min = Integer.MAX_VALUE;
        for (int i = start+1; i <= end-1; i++) {
            min = Math.min(min, find(start,i) + find(i,end) + values[start]*values[i]*values[end]);
        }
        dp[start][end] = min;
        return min;
    }
}

1040. 移动石子直到连续 II⭐

考察： #滑动窗口 #双指针

基础：1033

题解：题解

代码如下：

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        int e1 = stones[n-2]-stones[0]-1-(n-3); 
        int e2 = stones[n-1]-stones[1]-1-(n-3);
        int MaxMove = Math.max(e1,e2);
        int MinMove = 0;
        if (e1==0 || e2==0) {     // 需要端点一个作为跳板移动过来，再将另一个端点跳过去
            MinMove = Math.min(2, MaxMove);
        }
        else {
            int MaxCount = 0;   
            int left = 0;   // 定义左端点
            for (int right = 0; right < n; right++) {    // right点一定位于一个石子上
                // 目标是找到一个窗口，它的起点和终点都一定是有石子的
                while (stones[right] - stones[left] + 1 > n) {    // 窗口大小大于n（石子的数量），这能让窗口一直维持在n的长度以内
                    left++;
                }
                MaxCount = Math.max(MaxCount, right-left+1);   // right-left+1表示这个窗口内已经放了多少的石子
            }
            // 此时MaxCount为最大，则空位有n-MaxCount
            MinMove = n - MaxCount;
        }
        return new int[]{MinMove,MaxMove};
    }
}

1041. 困于环中的机器人

简单的中等题，代码如下：

class Solution {
    public boolean isRobotBounded(String instructions) {
        char[] ic = instructions.toCharArray();
        int[] loc = new int[4];
        int face = 0;
        for (int k=0;k<4;k++) {
            for (int i=0;i<ic.length;i++) {
                if (ic[i]=='G') {
                    loc[face]++;
                }
                else if (ic[i]=='L') {
                    face = (face+1)%4;
                }
                else if (ic[i]=='R') {
                    face = (face+4-1)%4;
                }
            }
            if (loc[0]==loc[2] && loc[1]==loc[3]) {
                return true;
            }
        }
        return false;

    }
}

1042. 不邻接植花⭐

中等题。题解：题解。思路如下：

代码如下：

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] al = new List[n];
        for (int i=0;i<n;i++) {
            al[i] = new ArrayList<Integer>();
        }
        for (int i=0;i<paths.length;i++) {
            al[paths[i][0]-1].add(paths[i][1]-1);
            al[paths[i][1]-1].add(paths[i][0]-1);
        }
        int[] color = new int[n];      // 表示n个花园的颜色，初始化时为0表示没有颜色
        for (int i=0;i<n;i++) {
            boolean[] tc = new boolean[5];     // 表示4中颜色是否可以选，0表示初始化，默认为false，表示都能选

            // 相邻的花园的颜色都设置为true，表示不可选择了
            for (int k : al[i]) {
                tc[color[k]] = true;
            }
            for (int j=1;j<=4;j++) {
                if (!tc[j]) {    // 表示颜色没有选
                    color[i] = j;
                    break;
                }
            }
        }
        return color;
    }
}

1043. 分隔数组以得到最大和⭐

考察： #递归 #动态规划

题解：题解

方法一、递归+记忆化搜索⭐

中等题。思路：构造一个函数 dfs (i)，表示以位置 i 为结尾的前面的结果。代码如下：

class Solution {
    public int[] arr;
    public int k;
    public int[] memo;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        this.arr = arr;
        this.k = k;

        int n = arr.length;

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

        return dfs(n-1);
    }

    public int dfs(int i) {    // 从右往左进行
        if (i<0) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        int max = 0;
        int res = 0;    // 表示以[0,i]这段的最大结果
        for (int j=i; j>=0 && j>=i-k+1; j--) {
            max = Math.max(max, arr[j]);    // 表示在[j,i]这段中，最大值为max，长度为i-j+1
            res = Math.max(res, dfs(j-1) + max*(i-j+1));
        }
        memo[i] = res;
        return memo[i];
    }
}

方法二、动态规划

从左向右正向判断，每次直接计算出以 i 结尾的结果。最终结果就是 dp[n]。代码如下：

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n+1];     // dp[i]存的是以i-1结尾的前面段
        for (int i=0; i<n; i++) {
            int max = 0;
            for (int j=i; j>=0 && j>=i-k+1; j--) {
                max = Math.max(max, arr[j]);
                dp[i+1] = Math.max(dp[i+1], dp[j] + max*(i-j+1));
            }
        }
        return dp[n];
    }
}

优化空间

我们可以发现在动态规划中，计算 i 值只需要 [i-k+1, i] 区间的结果，长度为 k。代码如下：

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[k+1];     // dp[i]存的是以i-1结尾的前面段
        for (int i=0; i<n; i++) {
            int max = 0;
            int res = 0;
            for (int j=i; j>=0 && j>=i-k+1; j--) {
                max = Math.max(max, arr[j]);
                // 注意在循环结束前，f[(i+1)%k] 是需要用到的，不能提前覆盖
                res = Math.max(res, dp[j%k] + max*(i-j+1));
            }
            dp[(i+1)%k] = res;
        }
        return dp[n%k];
    }
}

1048. 最长字符串链

考察： #动态规划 #双指针

中等题。比较简单，只需要先将数组按照长度排序，然后遍历每个数组，将它与比它长度少 1 的字符串比较，比较时用一个指针即可，当 i 指针是两个字符串不同的位置，那么长字符串 i 之后的元素一定是与短字符串 i 及其之后的元素是相等的。代码如下：

class Solution {
    public int longestStrChain(String[] words) {
        int n = words.length;
        Arrays.sort(words, new Comparator<String>() {
            public int compare(String a, String b) {
                return a.length()-b.length();
            }
        });

        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int res = 0;
        for (int i=0;i<n;i++) {
            for (int j=i-1;j>=0;j--) {
                if (words[j].length() < words[i].length()-1) {
                    break;
                }
                else if (words[j].length() == words[i].length()-1) {
                    if (isTrue(words[i],words[j])==0) {    // 前面长，后面短
                        dp[i] = Math.max(dp[i],dp[j]+1);
                    } 
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int isTrue(String a, String b) {
        char[] ac = a.toCharArray();
        char[] bc = b.toCharArray();
        int i = 0;
        while (i<b.length()) {
            if (ac[i]!=bc[i]) {
                break;
            }
            i++;
        }
        if (i==b.length()) {
            return 0;
        }
        // i位置是a新加入的
        return a.substring(i+1).compareTo(b.substring(i));
    }
}

1053. 交换一次的先前排列

中等题，实际上就是找规律。本题实际上找的是比当前数字组合更小的最大数字组合，但是只能交换一组数。通过规律定义如下步骤：

从右往左找降序（包括相等），找到第一个不是降序的数字位置，记作 loc1。
- 如果 loc1 还是初始值（定义为-1），表示整个数字组合都是升序，所以直接返回 arr 即可。
- 如果 loc1 不是初始值，那么继续下面步骤。
在 loc1 后面找比它小一点点的数，这里不要求数一定更靠左还是靠右，只要找到比它小的最大数的第一次出现位置，记作 loc2。
交换 loc1 的数字和 loc2 的数字。

代码如下：

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        
        int loc1 = -1;
        for (int i=n-2;i>=0;i--) {
            if (arr[i]>arr[i+1]) {
                loc1 = i;       // 这个loc1后面一定有比它更小的，如果都比它大，那它还是在升序里
                break;
            }
        }
        if (loc1 == -1) {
            return arr;
        }

        int loc2 = loc1 + 1;
        for (int i=loc1+1;i<n;i++) {
            if (arr[i]<arr[loc1] && arr[i]>arr[loc2]) {
                loc2 = i;
            }
        }

        int temp = arr[loc1];
        arr[loc1] = arr[loc2];
        arr[loc2] = temp;
        return arr;
    }
}

1092. 最短公共超序列⭐⭐

考察： #递归

困难题。题解：题解

思路：利用 dfs 检索以 s1 的 i 下标结尾和 s2 的 j 下标结尾的结果的最短长度。利用 FindStr 按照 dfs 正确的顺序进行查找。

最终代码：

class Solution {
    public int[][] map;
    public String s1, s2;

    public String shortestCommonSupersequence(String str1, String str2) {
        s1 = str1;
        s2 = str2;
        map = new int[s1.length()][s2.length()];
        return FindStr(s1.length()-1,s2.length()-1);
    }

    public int dfs(int i, int j) {     // 表示在s1[0,i]和s2[0,j]的情况下，返回结果的最短长度
        if (i<0) {
            return j+1;
        }
        if (j<0) {
            return i+1;
        }
        if (map[i][j]>0) {
            return map[i][j];
        }

        if (s1.charAt(i) == s2.charAt(j)) {
            map[i][j] = dfs(i-1,j-1) + 1;
            return map[i][j];
        }

        map[i][j] = Math.min(dfs(i-1,j), dfs(i,j-1)) + 1;

        return map[i][j];
    }

    public String FindStr(int i, int j) {
        if (i<0) {
            return s2.substring(0,j+1);
        }
        if (j<0) {
            return s1.substring(0,i+1);
        }
        if (s1.charAt(i) == s2.charAt(j)) {
            return FindStr(i-1,j-1) + s1.charAt(i);
        }
        if (dfs(i,j) == dfs(i-1,j) + 1) {
            return FindStr(i-1,j) + s1.charAt(i);
        }
        else {
            return FindStr(i,j-1) + s2.charAt(j);
        }
    }
}

1096. 花括号展开 II⭐

困难题，实际上就是找规律题。通过阅读题目，发现如下的规律：

如果当前字符为 { ： - 如果前面有字母或者 }，则先入栈 *，再入栈 {。 - 否则直接入栈 {。

如果当前字符为字母：找到以此字母为首的连续字母串，将这个串存入 Treeset 中。

如果当前字符为 , : - 如果栈顶为 *，为了保证乘法优先级更高，先取 Treeset 中的两个和此 * 进行处理……直到栈顶不是 *，再将 + 入栈。 - 否则直接将 + 入栈。

如果当前字符为 } ：取栈顶运算符和两个 set 中的元素进行处理，直到遇到 {，直接将 { 出栈。

在遍历数组之后，如果栈中还有运算符，则依次出栈并处理。

这里注意运用的 TreeSet 数据结构，不能使用 HashSet，因为答案是有序的，只能使用 TreeSet 按照其默认顺序即可。

在操作时也要注意两个操作数的前后顺序，如果顺序相反则结果也会出错。

详细代码如下：

class Solution {
    Deque<Character> dq = new LinkedList<Character>();
    List<TreeSet<String>> lss = new ArrayList<TreeSet<String>>();    // set()避免重复

    public void Option(char t) {
        if (t == '+') {
            TreeSet<String> set1 = lss.get(lss.size()-1);
            TreeSet<String> set2 = lss.get(lss.size()-2);
            set1.addAll(set2);
            lss.remove(lss.size()-1);
            lss.remove(lss.size()-1);
            lss.add(set1);
        }
        else if (t == '*') {
            List<String> list1 = new ArrayList<String>(lss.get(lss.size()-2));
            List<String> list2 = new ArrayList<String>(lss.get(lss.size()-1));
            TreeSet<String> set = new TreeSet<String>();
            for (int j=0;j<list1.size();j++) {
                for (int k=0;k<list2.size();k++) {
                    set.add((String)(list1.get(j)+list2.get(k)));
                }
            }
            lss.remove(lss.size()-1);
            lss.remove(lss.size()-1);
            lss.add(set);
        }
    }

    public List<String> braceExpansionII(String expression) {
        char[] ec= expression.toCharArray();

        for (int i=0;i<ec.length;i++) {
            if (ec[i]=='{') {
                if (i>0 && (ec[i-1]=='}' || (ec[i-1]>='a' && ec[i-1]<='z'))) {
                    dq.addLast('*');
                }
                dq.addLast('{');
            }
            else if (ec[i]>='a' && ec[i]<='z') {
                TreeSet<String> ss = new TreeSet<>();
                if (i>0 && ec[i-1]=='}') {
                    dq.addLast('*');
                }
                int p = i+1;
                while (p<ec.length && (ec[p]>='a' && ec[p]<='z')) {
                    p++;
                }
                ss.add(expression.substring(i,p));
                i = p - 1;
                lss.add(ss);
            }
            else if (ec[i]==',') {
                while (!dq.isEmpty() && dq.peekLast()=='*') {
                    char t = dq.pollLast();
                    Option(t);
                }
                dq.addLast('+');
            }
            else if (ec[i]=='}') {
                while (!dq.isEmpty()) {
                    char t = dq.pollLast();
                    if (t == '{') {
                        break;
                    }
                    Option(t);
                }
            }
        }

        while (!dq.isEmpty()) {
            char t = dq.pollLast();
            if (t == '{') {
                break;
            }
            Option(t);
        }

        return new ArrayList<String>(lss.get(0));
    }
}

1124. 表现良好的最长时间段

中等题。

思路：找子串最大长度，表示满足一个子串，使得其左边和右边要么是边界、要么是不劳累，且其内部劳累大于不劳累。

class Solution {
    public int longestWPI(int[] hours) {
        // 最大长度，表示满足一个子串，使得其左边和右边要么是边界，要么是不劳累，且其内部劳累大于不劳累
        int n = hours.length;
        ArrayList<int[]> al = new ArrayList<int[]>();
        al.add(new int[]{-1,0,0});     //下标，劳累，不劳累
        int l = 0, nl = 0;

        for (int i=0;i<n;i++) {
            if (hours[i]>8) {
                l++;
            }
            else {
                nl++;
                al.add(new int[]{i,l,nl});
            }
        }

        al.add(new int[]{n,l,nl});

        int max = 0;

        for (int left=0; left<al.size(); left++) {
            // System.out.println(al.get(left)[2]);
            for (int right=left+1; right<al.size(); right++) {
                int t = al.get(right)[1]-al.get(left)[1] , nt = al.get(right)[2]-al.get(left)[2];
                if (al.get(right)[0]>=0 && al.get(right)[0]<n) {
                    if (hours[al.get(right)[0]]>8) {
                        t--;
                    }
                    else {
                        nt--;
                    }
                }
                
                if (t > nt) {
                    // System.out.print(left);
                    // System.out.print(" ");
                    // System.out.println(right);
                    max = Math.max(max,al.get(right)[0]-al.get(left)[0]-1);
                }
            }
        }
        return max;
    }
}

1125. 最小的必要团队⭐

考察： #背包问题

题解：题解

代码如下：

class Solution {
    public long all;

    public long[][] memo;
    public int[] skill;

    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        HashMap<String,Integer> hash = new HashMap<String,Integer>();
        int m = req_skills.length;
        for (int i=0;i<m;i++) {
            hash.put(req_skills[i],i);
        }

        int n = people.size();
        skill = new int[n];
        for (int i=0;i<n;i++) {
            for (int j=0;j<people.get(i).size();j++) {
                skill[i] = skill[i] | 1<<hash.get(people.get(i).get(j));
            }
        } 

        memo = new long[n][1<<m];
        for (int i=0;i<n;i++) {
            Arrays.fill(memo[i],-1);
        }

        all = (1L << n) - 1;     // 表示所有人员都参与

        long res = dfs(n-1, (1<<m)-1);     // n-1 表示最后一个人，(1<<m)-1表示最终状态

        // res是结果的人的集合，需要将每一位提取出来
        int[] ans = new int[Long.bitCount(res)];
        int j = 0;
        for (int i=0;i<n;i++) {
            if (((res >> i) & 1) == 1) {
                ans[j] = i;
                j++;
            }
        }
        return ans;
    }

    // dfs(i,j) 定义成从前 i 个人中选择一些人，他们的技能并集为j， 所选择的最少人的集合
    public long dfs(int i, int j) {
        if (j==0) {
            return 0;     //全装满了
        }
        if (i<0) {
            return all;     // 没办法装满背包，返回全集
        }
        if (memo[i][j] != -1) {    // 记忆化搜索
            return memo[i][j];
        }
        
        long res1 = dfs(i-1,j);    //如果不选当前people
        long res2 = (1L << i) | dfs(i-1, j & ~skill[i]);    // ~skill[i]表示取反，即i这个人拥有的能力为0，没有的为1

        if (Long.bitCount(res1) < Long.bitCount(res2)) {
            memo[i][j] = res1;
            return res1;
        }
        else {
            memo[i][j] = res2;
            return res2;
        }
    }
}

1137、第 N 个斐波那契数

简单哦~

1138. 字母板上的路径

思路：构建一个 hash 表，存储每个字母的位置。在移动时一定要注意‘z’的判断，如果 if (start[0]+1==5 && start[1]>=1) 成立，则不能向下移动。

具体代码如下：

class Solution {
    public String alphabetBoardPath(String target) {
        HashMap<Character,int[]> hash = new HashMap<Character,int[]>();
        for (int i=0;i<26;i++) {
            hash.put((char)('a'+i),new int[]{i/5,i%5});
        }

        StringBuilder sb = new StringBuilder();
        char[] tc = target.toCharArray();
        int[] start = new int[]{0,0};

        for (int i=0;i<tc.length;i++) {
            int[] end = hash.get(tc[i]);
            while (start[0]!=end[0] || start[1]!=end[1]) {
                while (start[0]>end[0]) {    //需要上移
                    start[0]--;
                    sb.append("U");
                }
                while (start[0]<end[0]) {    //需要下移
                    if (start[0]+1==5 && start[1]>=1) {
                        break;
                    }
                    else {
                        start[0]++;
                    }
                    sb.append("D");
                }
                while (start[1]>end[1]) {    //需要左移
                    start[1]--;
                    sb.append("L");
                }
                while (start[1]<end[1]) {    //需要右移
                    start[1]++;
                    sb.append("R");
                }
            }
            sb.append("!");
        }

        return  sb.toString();
    }
}

1139. 最大的以 1 为边界的正方形

中等题，思路比较简单。构造两个二维数据，分别记录以当前为止 (i, j) 的上方连续 1 和左方连续 1 的个数（都包括自己），然后取其中较小值，判断如果以这个值作为边的长度，另外两个顶点是否能满足条件，如果不满足则缩小边的长度，继续判断。

具体代码如下：

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

        int res = 0;

        int[][] u1 = new int[n][m];    //记录包括其上面的连续1的个数
        int[][] l1 = new int[n][m];    //记录包括其左边的连续1的个数

        //对第一列
        for (int i=0;i<n;i++) {
            l1[i][0] = grid[i][0];
            if (grid[i][0]==1) {
                if (i>0) {
                    u1[i][0] = u1[i-1][0] + 1;
                }
                else {
                    u1[i][0] = 1;
                }
                res = 1;
            }
        }

        //对第一行
        for (int i=0;i<m;i++) {
            u1[0][i] = grid[0][i];
            if (grid[0][i]==1) {
                if (i>0) {
                    l1[0][i] = l1[0][i-1] + 1;
                }
                else {
                    l1[0][i] = 1;
                }
                
                res = 1;
            }
        }

        for (int i=1;i<n;i++) {
            for (int j=1;j<m;j++) {
                if (grid[i][j]==1) {
                    u1[i][j] = u1[i-1][j] + 1;
                    l1[i][j] = l1[i][j-1] + 1;

                    int edge = Math.min(u1[i][j],l1[i][j]);
                    for (int e=edge;e>0;e--) {
                        if (u1[i][j-e+1]>=e && l1[i-e+1][j]>=e) {

                            res = Math.max(res,e);
                            break;
                        }
                    }
                }
            }
        }
        return res*res;
    }
}

1144. 递减元素使数组呈锯齿状

中等题，但是思路比较简单。只需要判断奇数下标比偶数下标的小和偶数下标比奇数下标小这两种情况下，需要的最小操作的次数。

小优化：当判断奇数下标比偶数下标的小的情况时，只需要以奇数位置为判断点，如果它比两边大就缩小，如果比两边小则继续判断下一个奇数下标。当判断偶数下标比奇数下标小的情况时，只需要判断偶数位置，如果比两边大则缩小，如果比两边小则继续判断下一个偶数下标。

详细代码如下：

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int n = nums.length;

        int res = 0;
        // 先判断奇数下标小，只要判断奇数位置元素即可
        for (int i=1;i<n;i=i+2) {
            int k = nums[i];
            if (i-1>=0 && k>=nums[i-1]) {
                res += k - nums[i-1] + 1;
                k = nums[i-1] - 1;
            }
            if (i+1<n && k>=nums[i+1]) {
                res += k - nums[i+1] + 1;
                k = nums[i+1] - 1;
            }
        }

        int total = 0;
        // 先判断偶数下标小，只要判断偶数位置元素即可
        for (int i=0;i<n;i=i+2) {
            int k = nums[i];
            if (i-1>=0 && k>=nums[i-1]) {
                total += k - nums[i-1] + 1;
                k = nums[i-1] - 1;
            }
            if (i+1<n && k>=nums[i+1]) {
                total += k - nums[i+1] + 1;
                k = nums[i+1] - 1;
            }
        }

        return Math.min(res,total);
    }
}

1145. 二叉树着色游戏

题解：没有思路？一张图秒懂！（Python/Java/C++/Go） - 二叉树着色游戏 - 力扣（LeetCode）

看完题解，可能还有点懵。简单说就是以 x 为中心，可以分为三部分，分别是其左子树、右子树、还有剩下的部分。要如果 y 在第一步先占领了 x 四周的某一个部分，那么这一部分的所有元素都是 y 所有了。如果这一部分的元素个数比其他部分的元素个数之和还多，那么 y 是稳赢！

所以正确的步骤应该是： 先利用 dfs 找到 x 的节点 node，再分别用 dfs 算出其左子树的元素个数、右子树的元素个数、其他部分的元素个数。选其中元素个数最多的部分作为 y 要占领的，如果这一部分的元素比其他部分的元素个数和都多，那么稳赢。

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode findn1(TreeNode root, int x) {
        if (root == null || root.val == x) {
            return root;
        }
        if (findn1(root.left,x)!=null) {
            return findn1(root.left,x);
        }
        else {
            return findn1(root.right,x);
        }
    }
    public int dfs(TreeNode root) {
        if (root==null) {
            return 0;
        }
        return dfs(root.left) + dfs(root.right) + 1;
    }
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        root = findn1(root,x);
        int ln = dfs(root.left); 
        int rn = dfs(root.right); 
        int n2 = Math.max(ln, Math.max(rn, n - ln - rn - 1));
        if (n2 > n - n2) {
            return true;
        }
        else {
            return false;
        }
    }
}

1147. 段式回文

困难题。因为找分的最多的 k 的数量，所以直接双指针+贪心即可。

代码如下：

class Solution {
    // aba    aba
    public int longestDecomposition(String text) {
        char[] tc = text.toCharArray();
        int len = tc.length;
        int start = 0, end = len - 1;
        int res = 0;
        int l = 1;    // 窗口大小
        while (start<=end) {
            int i = start;
            int j = end - l + 1;
            if (i>=j) {
                res++;
                break;
            }
            boolean isFind = true;
            for (;i<start+l;i++,j++) {
                if (tc[i]!=tc[j]) {
                    isFind = false;
                }
            }
            if (isFind) {
                res += 2;
                start = start + l;
                end = end - l;
                l = 1;
            }
            else {
                l++;
            }
        }
        return res;

    }
}

1163. 按字典序排在最后的子串⭐⭐

考察： #双指针

困难题，使用暴力会超时。很抽象的解法。题解：题解

思路： 定义两个指针 i，j。i 表示最终结果的起始位置，j 表示开始判断的起始位置，定义 k 表示判断的偏移。每次判断 sc[i+k] 和 sc[j+k] ： - 如果 sc[i+k]==sc[j+k]，则 k++，这表示 [i, i+k] 和 [j, j+k] 的元素完全一样，但因为 i 一直在 j 之前，所以以 i 开头的字符串一定比以 j 结尾的字符串要大。 - 如果 sc[i+k]<sc[j+k]，这表示 [i, i+k-1] 和 [j, j+k-1] 的元素完全一样，那么但是因为 j+k 位置的元素比 i+k 大，那么 i 就不能作为开头了，因为 j 作为开始位置的字符串一定是大于 i 作为开始位置的字符串的。那 i 直接等于 j 吗？ 这也不对，因为 i 只是表示以 i 开头进行判断，可能 i+1、i+2……开头会有更大的结果，但是我们可以发现在 [i, i+k-1] 开头都比不过 [j, j+k-1] 开头，但是 i+k 开头我们能判断出来吗？ 显然不能，所以我们将 i=i+k+1，j 如果大于新的 i 那就不变，如果 j 小于等于新的 i，那就 j=i+1，k 重置为 0。 - 如果 sc[i+k]>sc[j+k]，这表示 [i, i+k-1] 和 [j, j+k-1] 的元素完全一样，但是 i+k 的元素更大，那么表示在选择 [i, i+k-1] 为开头都已经是已经是已知的最大，但是以 i 结束的一定就是最大的吗，不一定，我们需要重新将 j 置为 j+k+1，k 重置为 0，再对应 i 重新判断。

思路很抽象，代码如下：

class Solution {
    public String lastSubstring(String s) {
        int n = s.length();
        char[] sc = s.toCharArray();
        int i = 0, j = 1, k = 0;
        while (j+k<n) {
            if (sc[i+k]==sc[j+k]) {
                k++;
            }
            else if (sc[i+k] < sc[j+k]) {    // 表示[i,i+k-1]和[j,j+k-1]之间的内容一模一样，这之间的内容谁当开头i都行，但是k不一样，导致i+k这个位置不能当当开头，就算当也要在j+k这个位置
                i = i+k+1;
                j = Math.max(i+1, j);
                k = 0;
            }
            else {     // 表示[i,i+k-1]和[j,j+k-1]之间的内容一模一样，这之间的内容谁当开头i都行。但是k不一样，i+k依然可以当开头，但是j+k已经不能了
                j = j+k+1;
                k = 0;
            }
        }
        return s.substring(i);

    }
}

1172. 餐盘栈

考察： #小根堆 #栈

困难题。典型的思维题。题解：题解。代码如下：

class DinnerPlates {

    private int capacity;

    private List<Deque<Integer>> stacks = new ArrayList<>();    // list的每一个元素是一个栈，这里保存所有的栈

    private PriorityQueue<Integer> idx = new PriorityQueue<>();    // 最小堆返回的永远都是最小的值，这里存储的是没有存满的栈的下标

    public DinnerPlates(int capacity) {
        this.capacity = capacity;
    }
    
    public void push(int val) {
        if (!idx.isEmpty() && idx.peek()>=stacks.size()) {    // idx中所有元素都是越界下标，直接清空
            idx.clear();
        }
        if (!idx.isEmpty()) {     // 有未满栈，且最小的下标没有越界，表示可以取出来用
            Deque<Integer> temp = stacks.get(idx.peek());     // 相当于指针
            temp.push(val);
            if (temp.size() == capacity) {
                idx.poll();
            }
        }
        else {     // 所有的栈都已经满了
            Deque<Integer> temp = new LinkedList<>();
            temp.push(val);
            stacks.add(temp);
            if (capacity > 1) {
                idx.add(stacks.size() - 1);
            }
        }
    }
    
    public int pop() {
        return popAtStack(stacks.size()-1);
    }
    
    public int popAtStack(int index) {
        // 非法操作
        if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) {
            return -1;
        }

        Deque<Integer> temp = stacks.get(index);    // 相当于一个指针
        
        if (temp.size() == capacity) {
            idx.add(index);
        }

        int val = temp.pop();

        while (!stacks.isEmpty() && stacks.get(stacks.size()-1).isEmpty()) {
            stacks.remove(stacks.size()-1);
        }

        return val;

    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */

1187. 使数组严格递增⭐

考察： #动态规划

困难题，思路很重要。

题解：题解

代码如下：

class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        int MAXN = 1000000007;
        arr2 = Arrays.stream(arr2).sorted().distinct().toArray();
        int n = arr1.length+2;

        // 设置左右哨兵-1和MAXN
        int[] arr = new int[n];
        arr[0] = -1;
        for (int i=0;i<n-2;i++) {
            arr[i+1] = arr1[i];
        }
        arr[n-1] = MAXN;

        int[] dp = new int[n];    // 记录在i不变的情况下，[0,i]升序的最小次数
        Arrays.fill(dp,MAXN);
        dp[0] = 0;   // 第一个元素是-1，在它不动的情况下，变化0次可以保证升序

        for (int i=1;i<n;i++) {
            int j = lower_bound(arr2, arr[i]);    // j是在arr2的下标，这是比arr[i]大于或等于的最小数的位置，j是不可以用的。替换i-1的值应该从j-1开始。但是j反映了[0,j-1]的个数为j个
            
            // 如果下标i不换，i-1换
            for (int k = 1; k<=Math.min(i-1, j); k++) {
                if (arr[i-k-1] < arr2[j-k]) {     // 这里打算替换arr[i-k]为arr2[j-k]，所以先要判断arr[i-k-1]是不是严格小于arr2[j-k]
                    dp[i] = Math.min(dp[i], dp[i-k-1]+k);     // 对比dp[i]和在下标i-k-1不动的情况下，之后k个元素都变了的最小次数。     
                }
            }

            // 如果下标i不换，i-1不换
            if (arr[i-1] < arr[i]) {
                dp[i] = Math.min(dp[i],dp[i-1]);
            }
            
        }
        int res = dp[n-1];
        if (res>=MAXN) {
            return -1;
        }
        return res;
    }

    public int lower_bound(int[] arr2, int k) {    // 找>=k的第一个数的下标
        int l = 0, r = arr2.length;
        while (l<r) {
            int m = (l+r)/2;
            if (arr2[m]<k) {
                l = m + 1;
            }
            else {
                r = m;
            }
        }
        return l;
    }
}

注意

1210. 穿过迷宫的最少移动次数

方法一、广度优先搜索

当遇到最少移动次数，首先想到的就是广度优先搜索，广度优先搜索使用的是队列。

思路：以蛇尾巴为考察点，蛇有两种状态，当蛇为横着时，蛇只会向右、向下平行、顺时针旋转；当蛇为竖着时，蛇只会向下、向右平行、逆时针旋转。每次考察的时候需要判断当前位置当前状态是否第一次访问、是否越界、是否有墙。

详细代码如下：

class Solution {
    public int minimumMoves(int[][] grid) {
        int n = grid.length;
        int[][][] dist = new int[n][n][2];    // 记录在此格子此姿势下的移动次数（只会向右边和下面，所以不会来回跑，不用记录最小次数）
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                Arrays.fill(dist[i][j],-1);     //相当于dis[i][j][0]和dis[i][j][1]都初始化为-1
            }
        }
        // 只考虑尾巴
        dist[0][0][0] = 0; 
        Deque<int[]> dq = new LinkedList<>();     //int[]记录的是三元组
        dq.offerLast(new int[]{0, 0, 0});

        while (!dq.isEmpty()) {
            int[] arr = dq.pollFirst();
            int x = arr[0], y = arr[1], status = arr[2];
            // 基于当前尾巴位置进行广度优先搜索

            // 如果当前是横着的
            if (status==0) {
                // 有三种情况，分别是平行向下，向右，以尾巴为中心顺时针转(要求另外的两个单元都是空的)
                // 1. 向右
                if (y+2 < n && grid[x][y+2] == 0 && dist[x][y+1][0] == -1) {    //如果已经走过，那一定比这次的次数要小
                    dist[x][y+1][0] = dist[x][y][0] + 1;
                    dq.offerLast(new int[]{x, y+1, 0});
                }
                // 2. 平行向下
                if (x+1 < n && grid[x+1][y] == 0 && grid[x+1][y+1] == 0 && dist[x+1][y][0] == -1) {
                    dist[x+1][y][0] = dist[x][y][0] + 1;
                    dq.offerLast(new int[]{x+1, y, 0});
                }
                // 3. 旋转
                if (x+1 < n && y+1 < n && grid[x+1][y] == 0 && grid[x+1][y+1]==0 && dist[x+1][y][1] == -1){
                    dist[x][y][1] = dist[x][y][0] + 1;
                    dq.offerLast(new int[]{x, y, 1});
                }
            }
            else {
                // 1. 向右
                if (y+1 < n && grid[x][y+1] == 0 && grid[x+1][y+1] == 0 && dist[x][y+1][1] == -1) {
                    dist[x][y+1][1] = dist[x][y][1] + 1;
                    dq.offerLast(new int[]{x, y + 1, 1});
                }
                // 2. 向下
                if (x+2 < n && grid[x+2][y] == 0 && dist[x+1][y][1] == -1) {
                    dist[x+1][y][1] = dist[x][y][1] + 1;
                    dq.offerLast(new int[]{x + 1, y, 1});
                }
                // 3. 旋转
                if (x+1 < n && y+1 < n && grid[x][y+1] == 0 && grid[x+1][y+1] == 0 && dist[x][y][0] == -1) {
                    dist[x][y][0] = dist[x][y][1] + 1;
                    dq.offerLast(new int[]{x, y, 0});
                }
            }
        }
        return dist[n - 1][n - 2][0];
    }
}

1233. 删除子文件夹

比较简单，字符串的匹配问题。

1234. 替换子串得到平衡字符串⭐

非常难且恶心的一道题。

思路和很多题一样，找中间的最小子串，实际上要找的是两边的满足条件的最大子串。定义一个 left=0，先遍历 right 从头到尾，当遇到某个 right 不满足外面每个字母<=l 这个条件时，继续右移 left，一直更新最小的 min。

class Solution {
    public int balancedString(String s) {
        char[] sc = s.toCharArray();
        int l = sc.length/4;
        HashMap<Character,Integer> hash = new HashMap<Character,Integer>();
        int[] remainder = new int[4];
        hash.put('Q',0);
        hash.put('W',1);
        hash.put('E',2);
        hash.put('R',3);
        for (int i=0;i<sc.length;i++) {
            remainder[hash.get(sc[i])]++;
        }

        if (remainder[0]==l && remainder[1]==l && remainder[2]==l && remainder[3]==l) {
            return 0;
        }

        int left = 0;
        int min = sc.length;
        
        //right和left算在里面
        for (int right=0;right<sc.length;right++) {
            remainder[hash.get(sc[right])]--;
            while (left <=right && remainder[0]<=l && remainder[1]<=l && remainder[2]<=l && remainder[3]<=l) {
                min = Math.min(min,right-left+1);
                remainder[hash.get(sc[left])]++;
                left++;
            }
        }
        return min;
    }
}

1237. 找出给定方程的正整数解

中等题，但是是阅读理解，唯一有用的是 Arrays.asList 的使用。代码如下：

/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */

class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int x=1;x<=z;x++) {
            for (int y=1;y<=z;y++) {
                if (customfunction.f(x,y)==z) {
                    res.add(Arrays.asList(x,y));
                }
            }
        }
        return  res;
        
    }
}

1238. 循环码排列⭐

方法一、格雷编码

详细见 89. 格雷编码，这里唯一的不同是定义了一个 start，其实不难想到先将整个二进制数组转化为格雷码数组，从 start 开始进行写入 res，再将前面部分补上即可。

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> res = new ArrayList<>();
        int[] gray = new int[1<<n];

        int j = 0;    //记录格雷码为start的位置

        // 存每个数的格雷码
        for (int i=0;i<(1<<n);i++) {
            gray[i] = i ^ (i>>1);
            if (gray[i]==start) {
                j = i;
            }
        }

        for (int i=j;i<j+(1<<n);i++) {
            int k = i%(1<<n);
            res.add(k ^ (k>>1));
        }
        return res;
    }
}

优化

但是这其实是可以优化的，标准的格雷码是从 0 开始，其实 start ⊕ 0 = start，所以直接将标准的格雷码⊕ start 即可。详细代码如下：

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> res = new ArrayList<>();
        for (int i=0;i<(1<<n);i++) {
            res.add(i ^ (i>>1) ^ start);
        }
        return res;
    }
}

1247. 交换字符使得字符串相同

中等题，但容易想的很复杂。其实思路很简单，对于 s1 和 s2 不同的组合，有如下的处理情况：

不难看出，只要有偶数个 xy 对或者偶数个 yx 对，都能通过一半的次数消去不同；对于一个 yx 对和一个 xy 对，需要 2 次处理。只有在处理完后还有 1 个 xy 对或者 yx 对时，表示无法完全消除。详细代码如下：

class Solution {
    public int minimumSwap(String s1, String s2) {
        char[] s1c = s1.toCharArray();
        char[] s2c = s2.toCharArray();
        int xy = 0, yx = 0;
        int res = 0;
        for (int i=0;i<s1c.length;i++) {
            if (s1c[i]!=s2c[i]) {
                if (s1c[i]=='x') {
                    xy ++;
                }
                else {
                    yx ++;
                }
            }
        }
        res += xy/2;
        xy = xy%2;

        res += yx/2;
        yx = yx%2;

        if (xy==0 && yx==0) {
            return res;
        }
        else if (xy==1 && yx==1) {
            return res+2;
        }
        else {
            return -1;
        }
    }
}

1255. 得分最高的单词集合

困难题，使用的是 DFS 遍历每种情况。题解

class Solution {
    int[] surplus = new int[26];
    int[] score;
    String[] words;
    int res = 0;

    public void dfs(int i,int total) {
        if (i<0) {
            res = Math.max(res,total);
            return;
        }

        // 不选words[i]
        dfs(i-1,total);

        // 选words[i]
        boolean haveAll = true;
        char[] wc = words[i].toCharArray();
        for (char c : wc) {
            surplus[c-'a']--;
            if (surplus[c-'a']<0) {
                haveAll = false;
            }
            total += score[c-'a'];
        }

        if (haveAll==true) {    //当前单词可以完全拼出
            dfs(i-1,total);
        }

        // 恢复现场
        for (char c : wc) {
            surplus[c-'a']++;
        }
    }

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        this.words = words;
        this.score = score;
        for (int i=0;i<letters.length;i++) {
            surplus[letters[i]-'a']++;
        }
        dfs(words.length-1,0);
        return res;
    }
}

1275、找出井字棋的获胜者

常规简单题。

注意

1
2
3

String[] s = new String[3];    //初始化为null
int[] i = new int[3];          //初始化为0
boolean b = new boolean[3];    //初始化为false

1326. 灌溉花园的最少水龙头数目⭐⭐

题解：题解

class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] right = new int[n+1];     //表示以下标为起点的最远能去的距离
        for (int i=0;i<=n;i++) {
            int l = Math.max(0,i-ranges[i]);
            int r = i+ranges[i];
            right[l] = Math.max(right[l],r);
        }

        int res = 0;
        int last = 0;
        int pre = 0;
        for (int i=0;i<n;i++) {     //i表示的是起点
            last = Math.max(last,right[i]);    //表示目前能一直到达的地方
            if (last<=i) {      //表示目前能到的地方比判断的起点还小
                return -1;
            }
            if (i==pre) {    //表示这一段结束了
                res++;
                pre = last;
            }
        }
        return res;
    }
}

1376. 通知所有员工所需的时间

考察： #图 #dfs #bfs

方法一、邻接表+dfs

中等题，按部就班 dfs 即可。代码如下：

class Solution {
    public List<List<Integer>> list;
    public int res = 0;
    public int[] informTime;
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        list = new ArrayList<>();
        this.informTime = informTime;
        for (int i=0;i<n;i++) {     // 构建邻接表
            list.add(new ArrayList<>()); 
        }
        for (int i=0;i<n;i++) {      // 遍历manager    
            if (manager[i]==-1) {
                continue;
            }
            list.get(manager[i]).add(i);
        }
        for (int i=0;i<n;i++) {
            if (manager[i]==-1) {
                dfs(i, 0);
            }
        }
        return res;
    }


    public void dfs(int i, int time) {    //表示当前节点是i，传给他的时候的时间已经是time
        res = Math.max(res, time);
        if (list.get(i).size()==0) {
            return;
        }
        for (int j=0; j<list.get(i).size(); j++) {
            dfs(list.get(i).get(j),time+informTime[i]);
        }
    }
}

1441、用栈操作构建数组

比较简单，注意ArrayList的构建：

1	ArrayList<String> al = new ArrayList<String>();

1487. 保证文件名唯一

利用 HashMap 记录，其 value 记录的值 v 表示[1, v]都是确定已经用过的了，下次可以直接从 v+1 进行查找。

代码如下：

class Solution {
    public String[] getFolderNames(String[] names) {
        int n = names.length;
        String[] sc = new String[n];
        HashMap<String,Integer> hash = new HashMap<String,Integer>();
        for (int i=0;i<n;i++) {
            String name = names[i];
            if (hash.containsKey(name)) {
                int v = hash.get(name);
                String temp = name + "(" + (v+1) + ")";
                while (hash.containsKey(temp)) {
                    v++;
                    hash.replace(name,v);
                    temp = name + "(" + (v+1) + ")";
                }
                hash.put(temp,0);
                sc[i] = temp;
            }
            else {
                hash.put(name,0);
                sc[i] = name;
            }
        }
        return sc;
    }
}

1567、乘积为正数的最长子数组长度⭐

本题是152、乘积最大子数组和的升级版。

方法一、常规思路

本思路其实很简单。

先遍历一遍找到所有的0，在0与0之间找我们的答案。

在每个0和0之间，如果负数的个数是0或者偶数，则这个范围长度就是这个范围内的max；如果不是偶数，用双指针对应范围内的首尾位置，找到第一个负数，返回除去这个负数的范围剩下的范围的长度，就是这个范围的max。具体可以看代码理解。

for (int i=0;i<z.size()-1;i++) {
    int left = z.get(i)+1;
    int right = z.get(i+1);
    if (f.get(i)%2==0) {
        max = Math.max(max,right-left);
    }
    else {
        int j=left,t=right-1;
        while (j<=t) {
            if (j==t) {     //一定是负数
                max = Math.max(max,j-left);
                break;
            }
            if (nums[j]<0) {
                max = Math.max(max,right-j-1);
                break;
            }
            if (nums[t]<0) {
                max = Math.max(max,t-left);
                break;
            }
            j++;
            t--;
        }
    }
}

方法二、动态规划⭐

题解

这个很厉害！

建立两个数组zs和fs：

1 2	int[] zs = new int[n]; //记录以当前下标i结尾的乘积为正数的长度 int[] fs = new int[n]; //记录以当前下标i结尾的乘积为负数的长度

处理第一个元素：

if (nums[0]>0) {
    zs[0] = 1;
}
else if (nums[0]<0){
    fs[0] = 1;
}
//如果是0，那么zs和fs都是0

int max = zs[0];

对i>=1后的所有元素进行分析：

对于nums[i]<0：

if (nums[i]>0) {
    //连续正数的个数+1
    zs[i] = zs[i-1] + 1;
    //当前数为正数
    if (fs[i-1]==0) {    //如果在此之前都没有能成为负数的乘积，再加上这个正数，负数长度仍然为0
        fs[i] = 0;
    }
    else {
        fs[i] = fs[i-1] + 1;
    }
}

对于nums[i]<0：

if (nums[i]<0) {
    if (fs[i-1]==0) {
        zs[i] = 0;
    }
    else {
        zs[i] = fs[i-1] + 1;
    }
    fs[i] = zs[i-1] + 1;
}

对于nums[i]==0：

if (nums[i]==0) {
    zs[i] = 0;
    fs[i] = 0;
}

动态规划优化

每次只使用了i-1的相关值，可以设置两个变量即可。

1574. 删除最短的子数组使剩余数组有序

考察： #滑动窗口

中等题，但是比较考验思路。首先找到左边非降序的子序列，left 为其结尾位置；再从右往左找右边部分的非降序子序列，right 为其开始位置。在 left 计算出来之后直接处理，如果 left 为结尾，那么表示全部元素非降序，那么直接返回 0。之后初始化窗口，也就是最大的窗口其实就是只要左边非降序部分的剩余部分或者只要右边非降序部分的剩余部分，取最小值，再依次从头移动 start，和 right 判断，如果 arr[start]<=arr[right]，那么更新窗口；否则继续右移 right 直到 right 到 n，那么意思就是只要左边非降序部分。注意窗口更新时都需要与自己取 min。

代码如下：

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int left, right;
        for (left=0;left<n-1;left++) {
            if (arr[left] > arr[left+1]) {
                break;
            }
        }
        if (left == n-1) {
            return 0;
        }
        for (right=n-1;right>0;right--) {
            if (arr[right] < arr[right-1]) {
                break;
            }
        }
        System.out.println(left);
        System.out.println(right);

        int start = 0;
        int res = Math.min(n-left-1, right);
        while (start <= left) {
            while (right < n && arr[start] > arr[right]) {
                right++;
            }
            res = Math.min(res, right-start-1);
            start++;
        }
        
        return res;

    }
}

1590. 使数组和能被 P 整除

方法一、前缀和 + 余数

思路：我们要找到一个子数组，使得整个数组减去它就能被 p 整数，那么可以发现：子数组的余数等于整个数组的余数，我们需要找到一个最短的满足这个要求的子数组。

这里涉及到几个小优化。我们设置前缀，是防止在后面求子数组和的时候要进行遍历求和，而前缀和直接用收尾的前缀和相减即可得到。但是为了优化代码和简化操作，这里实际上是前缀和的余数，一样的，他们对比的标准也是 nums 的余数。在下面的两层 for 循环内，我们不应该一个设置头一个设置尾进行循环，而是应该一个设置长度，一个设置头，这样找到一个最小的子数组就可以直接返回了。

详细代码如下：

class Solution {
    public int minSubarray(int[] nums, int p) {
        // 如果子数组的余数 == 整个数组的余数，则就是答案
        int n = nums.length;
        // 前缀和的余数
        int[] pre = new int[n];
        // 整个nums的余数
        int y = 0;
        for (int i=0;i<n;i++) {
            y = (y + nums[i] % p) % p;
            pre[i] = y;
        }
        // 如果整个nums的余数就是0，那么无需操作
        if (y == 0) {
            return  0;
        }
        for (int i=1;i<n;i++) {     //子数组的长度
            // 子数组的起点下标
            for (int start=0;start<=n-i;start++) {
                // 如果起点下标为0
                if (start==0) {
                    if (pre[i-1]==y) {
                        return i;
                    }
                }
                // 如果起点下标不是0
                else {
                    if ((pre[start+i-1] - pre[start-1] + p)%p == y) {
                        return i;
                    }
                }
            }
        }
        return -1;
    }
}

1599. 经营摩天轮的最大利润

中等题，读懂题目很重要！代码如下：

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        int surplus = 0;
        int ready = 0;
        int i = 1;
        int res = 0;
        int max = 0;

        for (i=1;i<=customers.length;i++) {
            surplus += customers[i-1];
            // 这一圈一定会亏损，如果需要转，在后面计算的时候会默认转，如果不转，这里的最大盈利就是当前的上一个情况的盈利值。
            if (surplus==0) {
                continue;
            }
            else if (surplus<4 && surplus>0) {
                ready += surplus;
                surplus = 0;
            }
            else {      // >=4个人
                ready += 4;
                surplus -= 4;
            }
            if (ready * boardingCost - i * runningCost > res) {
                res = ready * boardingCost - i * runningCost;
                max = i;
            }
        }
        
        i--;

        // 游客不再添加
        while (surplus > 0) {
            i++;
            if (surplus <= 4) {
                ready += surplus;
                if (ready * boardingCost - i * runningCost > res) {
                    res = ready * boardingCost - i * runningCost;
                    max = i;
                }
                break;
            }
            else {
                ready += 4;
                surplus -= 4;
                if (ready * boardingCost - i * runningCost > res) {
                    res = ready * boardingCost - i * runningCost;
                    max = i;
                }
            }
            
        }
        
        if (res<=0) {
            return -1;
        }
        else {
            return max;
        }

    }
}

1604. 警告一小时内使用相同员工卡大于等于三次的人

我们先用哈希表 hash 记录每个员工的所有打卡时间。注意这里需要将字符串的时间转为以分钟为单位的整形时间。

然后遍历哈希表，对于每个员工，我们先判断员工的打卡次数是否大于等于 3，如果不是，则跳过该员工。否则，我们将该员工的所有打卡时间按照时间先后排序，然后遍历排序后的打卡时间，判断下标距离为 2 的两个时间是否在同一小时内，如果是，则将该员工加入答案数组。

最后，将答案数组按照字典序排序，即可得到答案。

详细代码如下：

class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        HashMap<String,ArrayList<Integer>> hash = new HashMap<String,ArrayList<Integer>>();
        ArrayList<String> res = new ArrayList<String>();
        for (int i=0;i<keyName.length;i++) {
            int t = Integer.parseInt(keyTime[i].substring(0, 2)) * 60 + Integer.parseInt(keyTime[i].substring(3));     //将时间转为分钟
            if (!hash.containsKey(keyName[i])) {
                ArrayList<Integer> al = new ArrayList<Integer>();
                al.add(t);
                hash.put(keyName[i],al);
            }
            else {
                ArrayList<Integer> al = hash.get(keyName[i]);
                al.add(t);
                hash.replace(keyName[i],al);
            }
        }

        for (Map.Entry<String,ArrayList<Integer>> entry : hash.entrySet()) {
            String key = entry.getKey();
            ArrayList<Integer> value = entry.getValue();
            if (value.size()<=2) {
                continue;
            }
            else {
                Collections.sort(value);
                for (int i=0;i<value.size()-2;i++) {
                    if (value.get(i+2)-value.get(i)<=60) {
                        res.add(key);
                        break;
                    }
                }
            }
        }
        Collections.sort(res);
        return res;
    }
}

1605. 给定行和列的和求可行矩阵

贪心到底。每次 res[i][j] = Math.min(rowSum[i],colSum[j]) 并同时更新 rowSum[i] -= res[i][j] 和 colSum[j] -= res[i][j]，一定存在解。详细代码如下：

class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length;    // 行
        int n = colSum.length;    // 列
        int[][] res = new int[m][n];
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                res[i][j] = Math.min(rowSum[i],colSum[j]);
                rowSum[i] -= res[i][j];
                colSum[j] -= res[i][j];
            }
        }
        return res;
    }
}

1615. 最大网络秩

中等题，但是比较简单想到，利用邻接矩阵再小优化即可，代码如下：

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[][] map = new int[n][n+1];     //最后一列记录总数
        for (int[] road : roads) {
            map[road[0]][road[1]] = 1;
            map[road[0]][n]++;
            map[road[1]][road[0]] = 1;
            map[road[1]][n]++;
        }

        int max = 0;
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                if (map[i][j]==1) {
                    max = Math.max(max, map[i][n]+map[j][n]-1);
                }
                else {
                    max = Math.max(max, map[i][n]+map[j][n]);
                }
            }
        }

        // for (int i=0;i<n;i++) {
        //     for (int j=0;j<n+1;j++) {
        //         System.out.print(map[i][j]);
        //         System.out.print(" ");
        //     }
        //     System.out.println("");
        // }
        return max;
    }
}

1616. 分割两个字符串得到回文串⭐

考察： #回文串

中等题，但是想要在 O (n) 的时间复杂度里通过还是需要思考的。

我们可以分为两种情况，分别是 a 在 b 前面和 b 在 a 前面。现在讨论 a 在 b 前面的情况，我们可以直接进行判断 a 的头和 b 的尾是否相等，如果相等，则双指针继续往中间移动。如果直到两个指针遇到了，那就表示一定可以 true，如果在某一处两个指针不相等，那么开始判断 a 或者 b 这两个指针之间的元素是不是构成回文串，如果 a 或者 b 构成，那么也 true，如果不行则返回 false。讨论 b 在 a 前面的情况同理。

举个例子：
a = abcabaaaa
b = aaabdacba
按照上面的规则：
abc|abaaaa
aaabda|cba
我们需要判断 aba 或者 bda 是不是回文串，如本例，第一个 a 子串的 aba 是，那么最后可以划分：
abcaba|aaa
aaabda|cba
变成：abcabacba

代码如下：

class Solution {
    public boolean isPalindrome(String s, int i, int j) {
        char[] sc = s.toCharArray();
        while (i<=j) {
            if (sc[i]!=sc[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public boolean check (String a, String b) {
        int i = 0, j = a.length()-1;
        while (i<=j && a.charAt(i)==b.charAt(j)) {
            i++;
            j--;
        }
        return (isPalindrome(a,i,j) || isPalindrome(b,i,j));
    }

    public boolean checkPalindromeFormation(String a, String b) {
        return (check(a,b) || check(b,a));
    }
}

1625. 执行操作后字典序最小的字符串

考察： #哈希 #队列

中等题，利用 Hash 存储和 queue 队列进行判断。每次从队列中取出一个字符串，对它做两种操作，如果已经存在于 hash 中，则不管；如果没有在 hash 中，则存入 hash，并再放入 queue 中。结束条件为：队列为空。

感悟：本题说明了，bfs 是利用队列进行完成，优化可以搭配 hash 进行查重（hash 可以是 hashset、treeset、hashmap 等等，只要包含 contains () 即可）

代码如下：

class Solution {

    public String Add(String s, int a) {
        char[] sc = s.toCharArray();
        int n = s.length();
        for (int i=n-1;i>=0;i=i-2) {
            sc[i] = Integer.toString((sc[i] - '0' + a)%10).charAt(0) ;
        }
        
        return String.valueOf(sc);
    }

    public String Rotate(String s, int b) {
        int n = s.length();
        return s.substring(n-b) + s.substring(0,n-b);
    }

    public String findLexSmallestString(String s, int a, int b) {
        int n = s.length();
        String res = s;
        Deque<String> dq = new LinkedList<>();
        TreeSet<String> ts = new TreeSet<>();
        dq.addLast(s);
        ts.add(s);
        while (!dq.isEmpty()) {
            String t = dq.pollFirst();
            if (res.compareTo(t)>0) {     //res更大
                res = t;
            }
            String s1 = Add(t,a);
            if (!ts.contains(s1)) {
                ts.add(s1);
                dq.addLast(s1);
            }
            String s2 = Rotate(t,b);
            if (!ts.contains(s2)) {
                ts.add(s2);
                dq.addLast(s2);
            }
        }
        
        return res;
    }
}

1626. 无矛盾的最佳球队⭐

考察： #动态规划 #最长递增子序列

基础题：300. 最长递增子序列

中等题，典型的动态规划题。

按照分数进行从小到大排序，分数相等的按照年龄进行从小到大排序。只需要从左向右遍历构建 dp，dp 数组表示以当前数结尾的最大和。每遍历一个数时，再从当前数左边那个数从右往左遍历，因为越往前面表示分数越小，如果满足条件那年龄应该是相等或者更小，所以如果前面的年龄更大则直接 continue，直到把前面遍历完，找到最大和放入这个数的 dp 下。

代码如下：

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] sl = new int[n][2];
        for (int i=0;i<n;i++) {
            sl[i][0] = ages[i];
            sl[i][1] = scores[i];
        }
        Arrays.sort(sl, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[1]!=b[1]) {      // 分数不一样，则按照分数从小到大
                    return a[1]-b[1];
                }
                return a[0]-b[0];      // 分数一样，则按照年龄从小到大
            }
        });

        int[] dp = new int[n];
        dp[0] = sl[0][1];
        int max = dp[0];
        for (int i=1;i<n;i++) {
            int m = sl[i][1];
            for (int j=i-1;j>=0;j--) {
                if (sl[j][0]>sl[i][0]) {     //前面的表示分数小。如果前面的年龄更大
                    continue;
                }
                m = Math.max(m, sl[i][1] + dp[j]);
            }
            dp[i] = m; 
            max = Math.max(max,dp[i]);
        }
        
        return max;
    }
}

1630. 等差子数组

中等题，但是暴力模拟即可。

用到了数组的深拷贝：System.arraycopy(原数组, 原数组起点, 新数组, 新数组起点, 长度);

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        int n = nums.length, m = l.length;
        ArrayList<Boolean> res = new ArrayList<>();
        for (int i=0;i<m;i++) {
            int left = l[i], right = r[i];
            int[] child = new int[right-left+1];
            System.arraycopy(nums, left, child, 0, right-left+1);
            Arrays.sort(child);
            int dis = child[1]- child[0];
            boolean isTrue = true;
            for (int j=1;j<child.length;j++) {
                if (child[j]-child[j-1] != dis) {
                    isTrue = false;
                    break;
                }
            }
            res.add(isTrue);
        }
        return res;

    }
}

1637. 两点之间不包含任何点的最宽垂直区域

中等题，但是很简单。

1638. 统计只差一个字符的子串数目

方法一、暴力

直接遍历两个字符串的起点 i、j，再同时遍历相同长度，看看在这个长度内是否只有一个不同，如果成立，sum++。时间复杂度 \(O(n^3)\)。

方法二、极致优化

题解：题解，复杂度 \(O(nm)\)

class Solution {
    public int countSubstrings(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int sum = 0;
        int n = s.length(), m = t.length();
        for (int d = 1-m; d<n; d++) {    // d表示i比j的位置大多少（可以是负数），i表示sc的最后一个元素、j表示tc的最后一个元素
            int i = Math.max(0, d);     // i一定是>=0
            int k0 = i - 1, k1 = i - 1;
            for (; i < n && i - d < m; i++) {
                if (sc[i]!=tc[i-d]) {     
                    k0 = k1;
                    k1 = i;     //表示 (k0,k1] 是可以取s的起点
                }
                sum += k1 - k0;
            }
        }
        return sum;
    }
}

1640、能否连接形成数组

1641. 统计字典序元音字符串的数目

中等题，找规律即可。代码如下：

class Solution {
    public int countVowelStrings(int n) {
        int[] map = new int[5];   // u o i e a
        map[0] = 1;
        for (int i=1;i<5;i++) {
            map[i] = 1 + map[i-1];
        }
        if (n==1) {
            return map[4];
        }
        int k = 2;
        while (k<=n) {
            for (int i=1;i<5;i++) {
                map[i] += map[i-1];
            }
            k++;
        }
        return map[4];
    }
}

1652、拆炸弹

负数的求余：

被除数的绝对值与除数绝对值取余的值即为余数绝对值，余数符号与被除数一致。

1653. 使字符串平衡的最少删除次数⭐

方法一、分割

中等题，遍历分隔符。在分隔符的左边删掉 b，右边（及其自己）删掉 a。记录删除最少时的位置所删除的次数。题解

class Solution {
    public int minimumDeletions(String s) {
        char[] sc = s.toCharArray();
        int n = sc.length;
        
        int[][] nn = new int[2][n];
        int a = 0;
        for (int i=0;i<n;i++) {
            if (sc[i]=='a') {
                a++;
            }
        }
        for (int i=0;i<n;i++) {     // 带当前i下标的前面的b
            if (i==0) {
                if (sc[i]=='b') {
                    nn[0][i] = 1;
                    nn[1][i] = a;
                }
                else {
                    nn[0][i] = 0;
                    nn[1][i] = a;
                    a--;
                }
                continue;
            }
            if (sc[i]=='b') {
                nn[0][i] = nn[0][i-1] + 1;
                nn[1][i] = a;
            }
            else {
                nn[0][i] = nn[0][i-1];
                nn[1][i] = a;
                a--;
            }
        }

        int res = n;
        for (int i=0;i<=n;i++) {    //i和i之后的都是b，删a
            if (i==0) {
                res = Math.min(res,nn[1][i]);
            }
            else if (i==n) {
                res = Math.min(res,nn[0][i-1]);
            }
            else {
                res = Math.min(res,nn[0][i-1] + nn[1][i]);
            }
            
        }
        return res;
    }
}

方法二、动态规划

考虑 s 的最后一个字母：

如果它是‘b’，则无需删除，问题规模缩小，变成「使 s 的前 n−1 个字母平衡的最少删除次数」。
如果它是‘a’：
- 删除它，则答案为「使 s 的前 n−1 个字母平衡的最少删除次数」加上 1。
- 保留它，那么前面的所有‘b’ 都要删除；

class Solution {
    public int minimumDeletions(String s) {
        int bn = 0;
        int res = 0;
        for (char c : s.toCharArray()) {
            if (c == 'b') {
                bn++;
            }
            else {
                res = Math.min(res + 1, bn);
            }
        }
        return res;
    }
}

1658. 将 x 减到 0 的最小操作数⭐

本题较难，需要转换思路。

把问题转换成nums中移除一个最长的子数组，使得剩余元素的和为 x。换句话说，要从nums中找最长的子数组，其元素和等于 s−x，这里 s为 nums所有元素之和。最后答案为 nums 的长度减去最长子数组的长度。

题中想要找到两端最短和，转换思路就是找到 nums 的满足条件的最长子数组。

代码如下：

class Solution {
    public int minOperations(int[] nums, int x) {
        int snums = Arrays.stream(nums).sum() - x;    //找到最长的子数组，常读等于snums
        int n = nums.length;
        int left = 0;
        int sum = 0;
        int res = -1;
        if (snums<0) {
            return -1;
        }
        for (int right=0;right<n;right++) {
            sum += nums[right];
            while (sum > snums) {      //其实sum不可能减到负数的，应为while的限制条件会在减成0的时候及时打断
                sum -= nums[left];
                left++;
            }
            if (sum == snums) {
                res = Math.max(res, right-left+1);
            }
        }
        if (res==-1) {
            return -1;
        }      
        else {
            return n-res;
        } 
    }
}

1
2
3

求数组和：
```java
sum = Arrays.stream(nums).sum();

1663. 具有给定数值的最小字符串

比较简单的题目~

1664. 生成平衡数组的方案数

比较简单的一题，维护两个数组，动态区分正向和反向的偶数和和奇数和。

1669. 合并两个链表

比较简单。唯一要注意的是指针在没有定义时为 null，而不是 NULL。

1694、重新格式化电话号码

方法一、常规逻辑

先除去多余字符，再插入'-'

substring()使用方法：

1
2
3

s = s.substring(1,5);    //截取下标1~4

s = s.substring(5);   //截取下标为5~end

replace()使用方法

1	s = s.replace("-",""); //将全文的-变成无

方法二、StringBuilder方法

String内容是不可变的，StringBuilder内容是可变的

StringBuilder处理字符串性能比String好

StringBuilder的创建

1	StringBuilder sb = new StringBuilder();

StringBuilder的尾部插入

1	sb.append("wry");

StringBuilder的中间插入

1	sb.insert(0,'w'); //在下标为0之前插入字符w

StringBuilder的长度

1	int n = sb.length();

StringBuilder的删除

1	sb.delete(6, 14); //删除下标为[6,14)

StringBuilder转为String

1	String s = sb.toString();

String转为StringBuilder

1	StringBuilder sb = new StringBuilder(s);

1700、无法吃午餐的学生数量

方法一、队列

使用队列进行判断，容易想到。

方法二、优化

披萨和学生数量相同，所以不会出现披萨没了学生还有的情况。

所以除了会因为卡在第一个披萨的情况而结束，就只可能是成功的状态而结束。

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] nums = new int[2];    //记录学生的0和1的数量
        for (int i=0;i<students.length;i++) {
            nums[students[i]]++;
        }

        for (int i=0;i<sandwiches.length;i++) {
            nums[sandwiches[i]]--;
            if (nums[sandwiches[i]]==-1) {    //表示本来就只有0个学生要这种披萨，但是目前披萨的第一个就是这种，所以在这里会卡住
                return sandwiches.length - i;    //包含当前i
            }
        }

        //披萨和学生数量相同，所以不会出现披萨没了学生还有的情况。
        //所以除了会因为卡在第一个披萨的情况而结束，就只可能是成功的状态而结束
        return 0;
    }
}

1739、放置盒子🌟

题解：放置盒子

方法一、数学找规律

代码如下：

class Solution {
    public int minimumBoxes(int n) {
        int sum = 0;
        int res = 0;     //底面数量
        int c = 0;     //层数
        int cs = 0;    //每层的数量
        for (int i=1;i<=n;i++) {
            cs += i;
            sum += cs;
            if (sum == n) {
                res = i*(i+1)/2;
                return res;
            }
            else if (sum > n) {
                sum -= cs;
                c = i-1;
                res = c*(c+1)/2;
                break;
            }
        }
        for (int j=1;j<=c+1;j++) {
            sum += j;
            if (sum == n) {
                res += j;
                return res;
            }
            else if (sum > n) {
                res += j;
                return res;
            }
        }
        return res;
    }
}

方法 2、开平方和开立方优化

详细看题解，不太会写……

1732、找到最高海拔

Screenshot_20221119_004204_com.huawei.browser

简单题，没啥意思～

1750. 删除字符串两端相同字符后的最短长度

很简单的题目，意义不大。

1752、检查数组是否经排序和轮转得到

简单题，循环查数组，实现起来比较巧妙，判断是否有两个增区间，如果有则比较首位的大小；如果多于 2 个增区间，那就错；如果只有一个增区间，那就对。

1753. 移除石子的最大得分

比较简单的一题，一共就三个数，每次动态选取最大的两个减 1 即可。

1754、构造字典序最大的合并字符串⭐

本题考查对 String 的 compareTo 的灵活运用，需要熟知 compareTo 的核心。compareTo 可以比较两个字符串，字典序和长度都会影响结果。

本题不能按照字符单独比较，因为如果出现：

b a a b b a a a 按照字符比较，是 b a a b b a a a；但是正确的答案应该是 b b a a b a a a。

因此只能用 compareTo 进行比较。每次提取较大的那个字符串的第一个字符，再继续比较，这样既考虑了大小比较，又考虑了上述例子中的情况。

按照 compareTo 的情况：分别出现：b (1) b (2) a (1) a (1) b (1) a (2) a (2) a (2)

详细代码如下，代码不难，思想难：

class Solution {
    public String largestMerge(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        int i = 0, j = 0;
        StringBuilder sb = new StringBuilder();
        while (i<n1 && j<n2) {
            if (word1.substring(i).compareTo(word2.substring(j))>0) {
                sb.append(word1.charAt(i));
                i++;
            }
            else {
                sb.append(word2.charAt(j));
                j++;
            }
        }
        if (i<n1) {
            sb.append(word1.substring(i));
        }
        if (j<n2) {
            sb.append(word2.substring(j));
        }

        return sb.toString();
    }
}

1759、统计同构子字符串的数目

简单题，注意 long 的定义和相加。

res += (long)(i-start)*(i-start+1)/2%MOD;

详细代码如下：

class Solution {
    int MOD = 1000000007;
    public int countHomogenous(String s) {
        // zzzzz
        // 5
        // 4
        // 3
        // 2
        // 1
        char[] sc = s.toCharArray();
        int n = sc.length;
        int start = 0;
        long res = 0;
        for (int i=1;i<n;i++) {    //记录start
            if (sc[i]==sc[start]) {
                continue;
            }
            else {
                res +=  (long)(i-start)*(i-start+1)/2%MOD;
                start = i;
            }
        }
        res += (long)(n-start)*(n-start+1)/2%MOD;
        return (int)res;
    }
}

1760、袋子里最少数目的球⭐

二分法，思路较难。

题目想要求得最小的最大值，这很容易想到二分法。但是二分法要怎么用呢，这里就是二分遍历。每次找到一个数，如果它成立则往一边二分，否则往另一边二分。

观察题目发现，在只有“操作至多 maxOperations 次”这么一个条件的限制下，很难把握把袋子平均分成几份才是最好的。所以我们考虑人为增加一个条件，即“每个袋子至多有 y 个球”。

此时问题便转化成了“给定 maxOperations 次操作次数，能否可以使得单个袋子里球数目的最大值不超过 y”。

从 1 和 nums 数组的最大值之间二分。如果 y 可以实现，我们尝试继续压低 y，即将 right 更新为 y-1，然后继续二分；如果 y 不能实现，我们将 y 提高，即将此时 left 更新为 y+1，然后继续二分。

代码如下：

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        Arrays.sort(nums);
        int left = 1, right = nums[nums.length-1];
        while (left < right) {
            int r = (left + right)/2;
            int opt = 0;
            for (int num : nums) {
                opt += (num-1) / r;     //如果刚好满足r，那么就不用分袋子了
            }
            if (opt>maxOperations) {
                left = r+1;
            }
            else {
                right = r;
            }
        }
        return right;
    }
}

1764. 通过连接另一个数组的子数组得到一个数组⭐⭐

方法一、KMP⭐

经典 KMP，考察的就是 KMP 的计算和 next 数组的构建。

KMP 算法的实现步骤其实就是：text（长）和 pattern（短）数组进行匹配，当在 text[i] 和 pattern[j] 位置发生了第一次的不相同，但是可以清楚 pattern[0]~pattern[j-1] 的位置和 text[j] 往前 j 个元素都是相同的。KMP 要求 i 不动，但 j 要进行移动到 new_j，使得 pattern[0]~pattern[new_j] 与 text[i] 前 new_j 个元素完全相等。

现在如何从 j 找到这个 new_j 就是新的问题。所以需要构建一个 next 数组，假设 new_j=next[j] ，那么 0~new_j-1 间的 new_j 个元素与 j 之前的 new_j 个元素都完全相同。此时可以直接比较 text[i] 和 next[new_j]，这表示已经匹配成功 new_j 个元素了。

注意：next 数组的长度和 group 的长度一致。默认 next[0]=-1，每一个next[j] 是为了求出 next[j+1]。

代码如下：

class Solution {

    private int[] GetNext(int[] group) {
        int n = group.length;
        int[] next = new int[n];
        next[0] = -1;
        int j = 0, t = next[0];
        while (j<n-1) {
            if (t==-1 || group[t]==group[j]) {
                t++;
                j++;
                // System.out.println(j);
                next[j] = t;
            }
            else {
                t = next[t];
            }
        }
        return next;
    }

    private int KMP(int[] nums, int[] group, int start) {
        int[] next = GetNext(group);
        int n = nums.length, m = group.length;
        int j = 0;
        while (start<n && j<m) {
            if (j==-1 || nums[start]==group[j]) {
                start++;
                j++;
            }
            else {
                j = next[j];
            }
        }
        if (j==m) {
            return start;    //下一个数组的起始位置
        }
        else {
            return -1;
        }
    }

    public boolean canChoose(int[][] groups, int[] nums) {
        int start = 0;
        for (int[] group : groups) {
            start = KMP(nums, group, start);
            if (start == -1) {
                return false;
            }
        }
        return true;
    }
}

1781、所有子字符串美丽值之和

暴力解法。循环固定左端和右端，再遍历这一段，找到最大和最小出现的次数，加入 res，3 个嵌套 for。意义不大。

1784、检查二进制字符串字段

方法一、正常思路

方法二、一行代码

本题可以转化为只能出现一次10，也就是只能出现111111000000这种情况。

1785. 构成特定和需要添加的最少元素

虽然是中等题，但是很简单。只需要分类讨论：

根据规律，不难发现，其实只要将 dis 都转为正数，循环与 limit 比较即可。或者直接进行除法操作，注意存在什么都不用操作的可能。代码如下：

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long dis = 0;
        long res = 0;
        for (int n : nums) {
            dis += n;
        }
        dis = Math.abs(dis-goal);
        return (int)((dis + limit - 1) / limit);
    }
}

1790、仅执行一次字符串交换能否使两个字符串相等

思路简单，不多说了。

1792. 最大平均通过率⭐

中等题，但是不太好想，如果有思路就会很简单。

首先我考虑的时背包问题，但是一顿操作后并不能实现。根据题解，转换了思路，每次加一个学生，选择增量最大的确定永久增加，循环判断即可。

这里考察大根堆的构建。

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int c = classes.length;
        PriorityQueue<double[]> q = new PriorityQueue<double[]>((a,b) -> {
            double x = (a[0]+1)/(a[1]+1) - a[0]/a[1];
            double y = (b[0]+1)/(b[1]+1) - b[0]/b[1];
            return Double.compare(y, x);     //如果后面的增量比前面的增量大，那么返回正值，则调换顺序
        });
        for (int[] cl : classes) {
            q.offer(new double[]{(double)cl[0],(double)cl[1]});
        }
        for (int i=0;i<extraStudents;i++) {    
            double[] temp = q.poll();
            temp[0]++;
            temp[1]++;
            q.offer(temp);
        }
        double res = 0;
        while (!q.isEmpty()) {
            double[] temp = q.poll();
            res += temp[0]/temp[1];
        }
        return res/c;
    }
}

tips

double 元素比较大小，使用 Double.compare(x,y)，如果 x>y 则返回正数，如果 y>x 则返回负数。

1797. 设计一个验证系统

普通工程题，意义不大。

注意：hashmap 在 put 时如果有相同 key，value 会进行覆盖。

1798. 你能构造出连续值的最大数目⭐

方法一、动态规划+贪心算法

利用动态规划的思想。先使 coins 升序，我们假设 res 之前的数（连续的）都能凑出来，那么在考察 res 时，如果 coins[i] 能小于 res，那么 coins[i] 加上 res-coins[i] 就可以构造出来 res，其中 res-coins[i] 是一定能构造出来的；如果 coins[i]大于 res，那么没有办法通过加上什么数达到当前需要的 res。

具体代码如下：

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int res = 1;
        for (int c : coins) {
            if (c>res) {
                break;
            }
            else {
                res += c;
            }
        }
        return res;
    }
}

1799. N 次操作后的最大分数和⭐

动态规划+位运算压缩存储

难题!!!

class Solution {

    public int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x%y);
    }

    public int maxScore(int[] nums) {
        int l = nums.length;

        // 构造最大公约数矩阵
        int[][] gcdmap = new int[l][l];
        for (int i=0;i<l;i++) {
            for (int j=0;j<l;j++) {
                gcdmap[i][j] = gcd(nums[i],nums[j]);
            }
        }

        // 构造res向量，下标i表示位运算中已经包含的值的最大结果
        int len = 1 << l;     //一共l个数，则1后面l个0。len的十进制所表示的是多个元素的组合

        int[] res = new int[len];

		//表示res的下标从0（还没有一个元素进行判断），到二进制全是1（表示所有元素都判断完了）（res[len-1]就是我们要的最终结果）
        for (int k=0;k<len;k++) {      
            //对k中的任意一对数据拿出来，比较res[k]和没有这对数据时的res+这对数据的得分的最大值
            int cnt = Integer.bitCount(k);     //判断k的二进制由多少个1组成
            if (cnt%2==0) {     //偶数个1，表示成对的，那么可以进行判断
                for (int i=0;i<l;i++) {     //i表示第一个数是从nums[0]到nums[i-1]
                    if (((k>>i) & 1) == 1) {     //如果第i个数据是在这个k中的
                        for (int j=i+1;j<l;j++) {
                            if (((k>>j) & 1) ==1) {     //i和j两个数据都在k中，可以按照计划进行判断
                                res[k] = Math.max(res[k],res[k^(1<<i)^(1<<j)]+cnt/2*gcdmap[i][j]);
                            }
                        }
                    }   
                }
            }
        }

        return res[len-1];

    }
}

1800、最大升序子数组和

思路简单，只要判断当前值是否比上一个值大，如果大，那以当前值结尾的最大升序子数组和 = 以上一个值为结尾的最大升序子数组和 + 当前值的大小。否则值为本身。

1801、积压订单中的订单总数

方法一、HashMap 搜索+ArrayList 排序

思路比较简单，设置两个 hash 和两个 list，list 用来存储值，分别从小到大排序和从大到小排序，hash 可以根据 list 的值作为 key 查到对应的数量，再进行处理。涉及的 Java 基础语法比较多。

需要注意 (int)(res%MOD) 才是正确的返回，(int)res%MOD 不对。

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1000000007;

        HashMap<Integer,Integer> buy = new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> sell = new HashMap<Integer,Integer>();
        ArrayList<Integer> buylist = new ArrayList();    //从大到小
        ArrayList<Integer> selllist = new ArrayList();   //从小到大

        //buy大于sell才能抵消
        for (int[] or : orders) {

            if (or[2]==0) {    //表示buy采购，要找到小于等于它的最小的sell

                // 如果 or[0]>=selllist.get(0) && or[1]>0，可以进行判断
                // 如果只满足 or[0]>=selllist.get(0) 但不满足 or[1]>0，直接退出
                // 如果只满足 or[1]>0 但不满足 or[0]>=selllist.get(0)，直接退出

                while (selllist.size()>0) {
                    if (or[0]>=selllist.get(0) && or[1]>0) {
                        int key = selllist.get(0);
                        int value = sell.get(key);      //当前sell值得数量
                        if (or[1]>=value) {    //如果要加入的buy的值数量大于等于sell最小值的数量
                            or[1] -= value;
                            //将sell和selllist都删除对应的数据
                            sell.remove(key);
                            selllist.remove(0);      //可以进行接下来的判断 
                        }
                        else {
                            sell.replace(key,value-or[1]);   //更新sell散列表中的对应关系
                            or[1]=0;
                            break;
                        }
                    }
                    else {
                        break;
                    }
                }
                if (or[1]>0) {    //只有当or[1]>0时，表示现有的sell中没有比当前buy小的值了
                    buy.put(or[0],(buy.getOrDefault(or[0],0)+or[1])%MOD);     //如果原本就有这个值，那么取原来的值加上现在的值；如果原来没有，则设置初始值default为0再加上现在的值。
                    buylist.add(or[0]);
                    Collections.sort(buylist, new Comparator<Integer>() {    //升序排序
                        public int compare(Integer n1, Integer n2) {
                            return n2-n1;   //如果return>0则需要对调
                        }
                    }); 
                }
            } 
            else {        //表示sell采购，要找到大于等于它的最大的buy
                while (buylist.size()>0) {
                    if (or[0]<=buylist.get(0) && or[1]>0) {
                        int key = buylist.get(0);
                        int value = buy.get(key);      //当前sell值得数量
                        if (or[1]>=value) {   
                            or[1] -= value;
                            buy.remove(key);
                            buylist.remove(0); 
                        }
                        else {
                            buy.replace(key,value-or[1]);
                            or[1]=0;
                            break;
                        }
                    }
                    else {
                        break;
                    }
                }
                if (or[1]>0) { 
                    sell.put(or[0],(sell.getOrDefault(or[0],0)+or[1])%MOD);
                    selllist.add(or[0]);
                    Collections.sort(selllist);
                }
            }
            // System.out.println("=================buy====================");
            // System.out.print(buy.keySet());
            // System.out.println(buy.values());
            // System.out.println("=================sell====================");
            // System.out.print(sell.keySet());
            // System.out.println(sell.values());
            // System.out.println();
        }
        long res =0;
        for (int num : sell.values()) {
            res += (long)num;
        }
        for (int num : buy.values()) {
            res += (long)num;
        }
        return (int)(res%MOD);
    }
}

方法二、题解🐶

题解

1802. 有界数组中指定下标处的最大值

根据题目要求，其实只要从 index 左右递减，每次减少 1，如果还有多余的空位，全部设置为 1 即可。（getsum ()) 函数）

代码如下：

class Solution {
    public long getsum(long x, int len) {     //注意x必须是long，否则会在下面的乘法中越界
        if (x < len) {     //有多余的1
            return (long)((1+x)*x/2 + (len-x));
        }
        else {
            return (long)((x-len+1+x)*len/2);
        }
    }

    public int maxValue(int n, int index, int maxSum) {
        int llen = index + 1, rlen = n - index;       //这里的长度是包括当前mid的长度
        int left = 1, right = maxSum;     //right设置为maxsum，不能是n（nums.length）
        //找满足条件的最大的
        //需要在当前满足条件的前提下，不断右移，需要left存储最后一个判断成功的满足条件的
        while (left < right) {
            int mid = (left + right + 1)/2;
            if ((getsum(mid,llen)+getsum(mid,rlen)-mid)<=maxSum) {     //注意需要减去重复加上的mid值
                left = mid;    //left不断存储成功的最大的值
            }
            else {
                right = mid-1;
            }
        }
        return left;
    }
}

1806、还原排列的最少操作步数

中等题，通过列举多个情况找规律即可。

代码如下：

class Solution {
    public int reinitializePermutation(int n) {
        int res = 0;
        int loc = 1;
        do {
            if (loc*2>=1 && loc*2<n-1) {
                loc = loc * 2;
                res++;
            }
            else {
                loc = (loc * 2 - n) + 1;
                res++;
            }
        }while (loc!=1);
        return res;

    }
}

1807. 替换字符串中的括号内容

hash 的和 stringbuidler 的结合应用。比较简单~

1813、句子相似性 III⭐

简单但是需要考虑的比较多的题目。代码如下：

class Solution {
    public static boolean isCon(String s1,String s2) {    //判断s2是否包含在s1中且符合条件
        String[] str1 = s1.split(" ");
        String[] str2 = s2.split(" ");
        int n1 = str1.length;
        int n2 = str2.length;     //n1一定大于n2
        int i = 0;
        if (str1[i].equals(str2[i])) {     //说明最左边匹配成功
            for (i=0;i<n2;i++) {
                if (!str1[i].equals(str2[i])) {
                    break;
                }
            }
            if (i==n2) {
                return true;   //左匹配
            }
        }
        int j = n1-1;
        int t = n2-1;
        if (str1[j].equals(str2[t])) {        //说明最右边匹配成功
            for (j=n1-1,t=n2-1;t>=i;t--) {
                if (!str1[j].equals(str2[t])) {
                    return false;
                }
                j--;
            }
        }
        if (i==t+1) {
            return true;
        }             
        return false;          
    }

    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        int n1 = sentence1.length();
        int n2 = sentence2.length();
        if (n1<n2) {
            return isCon(sentence2,sentence1);
        }
        else if (n1>n2) {
            return isCon(sentence1,sentence2);
        }
        else {
            return sentence1.equals(sentence2);
        }
    }
}

1814. 统计一个数组中好对子的数目

比较难想也比较难操作的一题。核心思路：

nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) 与 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) 等价

此外，还需要注意在乘法时 long 的乘法，(long) 只能将紧跟着的变量或者括号强制转化为 long，如果后面跟的是括号，括号里的内容会先按照原来类型进行运算，再强转。

所以：res = (res + (long)((i-left)*(i-left-1)/2)%MOD); 可能会越界，但是 res = (res + (long)(i-left)*(i-left-1)/2)%MOD; 不会

代码如下：

class Solution {
    public int rev(int n) {
        int res = 0;
        while (n!=0) {
            res = res * 10 + n%10;
            n = n/10;
        }
        return res;
    }

    public int countNicePairs(int[] nums) {
        int MOD = 1000000007;
        int n = nums.length;
        for (int i=0;i<n;i++) {
            // System.out.println(rev(nums[i]));
            nums[i] = nums[i] - rev(nums[i]);
        }
        Arrays.sort(nums);
        int left = 0;
        long res = 0;
        for (int i=0;i<n;i++) {
            // System.out.println(nums[i]);
            if (nums[i]!=nums[left]) {
                if (i-left > 1) {   //不止一个数，能为数对
                    res = (res + (long)(i-left)*(i-left-1)/2)%MOD;     //下标为3 4 5 6 7，实际上相同是4个，也就是3 4 5 6，一共有3+2+1对，即(1+3)*3/2
                }
                left = i;
            }
        }
        if (left != n-1) {
            // System.out.println(n);
            res = (res + (long)(n-left)*(n-left-1)/2)%MOD;   //下标为6 7 (8)，实际上相同是2个，也就是6 7, 一共1对，即(1+(2-1))*(2-1)/2
        }
        return (int)(res%MOD);
    }
}

1817. 查找用户活跃分钟数

虽然是中等题，但是很简单，只要注意使用数组的自定义排序即可。

1819. 序列中不同最大公约数的数目⭐

困难题，原本思路是使用 list 和 hashmap 对 nums 的每对元素求最大公约数，但是超时。此方法不可行。注意：根据题目要求，每个单独的元素也算答案。

0 和任何数 x 的最大公约数都是 x

方法一、枚举

需要转换思路，枚举以 i 为因子的所有数，如果有 2 个或 2 个以上的数存在，判断这些数的最大公约数是不是 i，如果是，那么 res++。注意，每个单独元素也算答案。

详细代码如下：

class Solution {
    public int gys(int a,int b) {
        while (b!=0) {
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }

    public int countDifferentSubsequenceGCDs(int[] nums) {
        Arrays.sort(nums);
        int max = nums[nums.length-1];
        boolean[] ishas = new boolean[max+1];
        int res = 0;
        for (int n : nums) {
            ishas[n] = true;
        }
        for (int i=1;i<=max;i++) {     //公约数
            int g = 0;
            for (int j=i;j<=max;j=j+i) {
                if (ishas[j]) {
                    g = gys(j,g);      //
                }
            }
            if (g==i) {    //表示满足存在2个或2个以上的数，使得i作为最大公约数
                res++; 
            }
        }
        return res;
    }
}

方法二、枚举优化

在嵌套的 for 的判断中增加：g!=i，这表示如果出现 g==i 的情况，也就是出现 2 个或 2 个以上的数，使得 i 作为最大公约数，那么直接可以跳出循环，返回 i。

详细代码：

class Solution {
    public int gys(int a,int b) {
        while (b!=0) {
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }

    public int countDifferentSubsequenceGCDs(int[] nums) {
        Arrays.sort(nums);
        int max = nums[nums.length-1];
        boolean[] ishas = new boolean[max+1];
        int res = 0;
        for (int n : nums) {
            ishas[n] = true;
        }
        for (int i=1;i<=max;i++) {     //公约数
            int g = 0;
            for (int j=i;j<=max && g!=i;j=j+i) {
                if (ishas[j]) {
                    g = gys(j,g);      //
                }
            }
            if (g==i) {    //表示满足存在2个或2个以上的数，使得i作为最大公约数
                res++; 
            }
        }
        return res;
    }
}

方法三、最强优化

1819题解

1822、数组元素积的符号

简单模拟题……

1824. 最少侧跳次数⭐

方法一、动态规划（二维）

简而言之，在 i 点的 j 跑道上的最小侧翻次数来源于两个值，一个是 i-1 点的 j 跑道，另一个是 i 点的其他跑道。 这里需要注意，在求 i 点的其他跑道的值的时候，这些值也是来源于 i-1 点的相应的跑道，所以需要分为两步进行，先计算由 i-1 点的 j 跑道计算得到的，再计算由 i 点的其他跑道计算得到的。i 点的其他跑道实际上就是 i 点所有跑道的 dp 最小值。

详细代码：

class Solution {
    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length;
        int MAX = n+10;
        int[][] dp = new int[n][3];
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[0][2] = 1;
        for (int i=1;i<n;i++) {
            //从上一个点到这个点
            for (int j=0;j<3;j++) {
                if (obstacles[i]==j+1) {    //表示有石头
                    dp[i][j] = MAX;
                }
                else {
                    dp[i][j] = dp[i-1][j];
                }
            }
            int min_step = Math.min(dp[i][0],Math.min(dp[i][1],dp[i][2]));
            for (int j=0;j<3;j++) {
                if (obstacles[i]!=j+1) {    //表示没有石头
                    dp[i][j] = Math.min(dp[i][j],min_step+1);
                }
            }
        }
        return Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2]));
    }
}

方法二、动态规划优化（一维）

代码如下：

class Solution {
    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length;
        int MAX = n+10;
        int[] dp = {1,0,1};
        for (int i=1;i<n;i++) {
            //从上一个点到这个点
            for (int j=0;j<3;j++) {
                if (obstacles[i]==j+1) {    //表示有石头
                    dp[j] = MAX;
                }
                else {
                    dp[j] = dp[j];
                }
            }
            int min_step = Math.min(dp[0],Math.min(dp[1],dp[2]));
            for (int j=0;j<3;j++) {
                if (obstacles[i]!=j+1) {    //表示没有石头
                    dp[j] = Math.min(dp[j],min_step+1);
                }
            }
        }
        return Math.min(dp[0],Math.min(dp[1],dp[2]));
    }
}

1828. 统计一个圆中点的数目

方法一、暴力

意义不大的中等题。

方法二、压缩搜索

1828题解

1913、句子相似性III

对于题目只有三种情况：

A......

A
......A

A
A......B

AB

首先要确定谁是长的句子，谁是短的句子。

可以从第一个单词进行匹配，如果匹配上了，说明一定是1、3情况，如果遇到匹配不成功的，则从各自的最后一个单词进行匹配，如果最后两个指针遇上了，则说明成立。结束的条件是短的字符串的做指针和右指针能遇上（i = t + 1）。具体思路可以看代码，更容易懂。

1971. 寻找图中是否存在路径

典型并查集题目

```java
class Solution {

    public int find(int[] bc, int x) {
        if (bc[x]!=x) {     //如果自己不是根
            bc[x] = find(bc,bc[x]);     //将一条线上的所有的都变成直连根
        }
        return bc[x];    
    }

    public void union(int[] bc, int x, int y) {
        if (find(bc,x)==find(bc,y)) {
            return ;
        }
        else {
            bc[find(bc,x)] = find(bc,y);
        }
    }
    
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        int[] bc = new int[n];
        for (int i=0;i<n;i++) {
            bc[i] = i;     // 初始每个节点的根就是自己
        }
        for (int i=0;i<edges.length;i++) {
            union(bc,edges[i][0],edges[i][1]);
        }

        // for (int i=0;i<n;i++) {
        //     System.out.println(bc[i]);
        // }

        if (find(bc,source)==find(bc,destination)) {
            return true;
        }
        
        return false;
    }
}

2011. 执行操作后的变量值

简单题，没意思~

2016、增量元素之间的最大差值

本题思路很巧妙，目的是求一对升序的两个数，而且是差值最大的。

可以将左端点定为左边第一个数，开始遍历。

如果右边的某个值比左端点大，则记录他们之间的差值，并和已经保存的差值比较，保存更大的那个。

如果右边的某个值比左端点小，那么这个值就成为了新的左端点，然后再继续遍历。

比如 3...9...2...10

以3作为左端点的时候，当遇到9时，res = 6

再往后遍历遇到比左端点3更小的2，那么更小左端点为2，继续往后遍历，遇到更大的10，发现差值为8，比6大，则更新res = 8

2027. 转换字符串的最少操作次数

简单题，不多说。

2130、链表最大孪生和

方法一、常规遍历+数组

对链表遍历两次，第一次记录长度n；构建一个n/2长度的数据，第二次遍历的前一半直接放在数组中，后一半对数组从后往前分别加上，最后取得数组的最大值。

方法二、双端队列

遍历一次链表，将所有的数值都按顺序加入队列中。对队列进行操作，如果队列不为空!dq.isEmpyt()，那么每次pollFirst()和pollLast()，并相加，用max记录最大的和，最后输出。

2032. 至少在两个数组中出现的值

简单题，但涉及到动态数组和哈希表。

方法一、HashMap+位记录

class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); 
        ArrayList al = new ArrayList();
        for (int i=0;i<nums1.length;i++) {
            hash.put(nums1[i], 1);     //第1个有的在二进制第1位上至1
        }
        for (int i=0;i<nums2.length;i++) {
            hash.put(nums2[i], hash.getOrDefault(nums2[i],0) | 2);   //第2个有的在二进制第2位上至1
        }
        for (int i=0;i<nums3.length;i++) {
            hash.put(nums3[i], hash.getOrDefault(nums3[i],0) | 4);   //第3个有的在二进制第3位上至1
        }
        for (Map.Entry<Integer,Integer> entry : hash.entrySet()) {
            int v = entry.getValue();
            if ((v & (v-1)) != 0) {
                al.add(entry.getKey());
            }
        }
        return al;
    }
}

方法二、HashMap+排序+数量记录

class Solution {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); 
        ArrayList al = new ArrayList();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        Arrays.sort(nums3);
        for (int i=0;i<nums1.length;i++) {
            if (i>0 && nums1[i]==nums1[i-1]) {
                continue;
            }
            hash.put(nums1[i], hash.getOrDefault(nums1[i],0)+1);
        }
        for (int i=0;i<nums2.length;i++) {
            if (i>0 && nums2[i]==nums2[i-1]) {
                continue;
            }
            hash.put(nums2[i], hash.getOrDefault(nums2[i],0)+1);
        }
        for (int i=0;i<nums3.length;i++) {
            if (i>0 && nums3[i]==nums3[i-1]) {
                continue;
            }
            hash.put(nums3[i], hash.getOrDefault(nums3[i],0)+1);
        }
        for (Map.Entry<Integer,Integer> entry : hash.entrySet()) {
            if (entry.getValue()>=2) {
                al.add(entry.getKey());
            }
        }
        return al;
    }
}

2037. 使每位学生都有座位的最少移动次数

简单题，只要将 seat 和 student 两个数组排序，然后对应相减取绝对值，最后相加即可。

2042. 检查句子中的数字是否递增

简单题，大脑清晰且认真即可。

2180. 统计各位数字之和为偶数的整数个数

简单题，直接判断操作即可。

2185. 统计包含给定前缀的字符串

简单题，没啥意思~

2275、按位与结果大于零的最长组合

本题考到位运算，但是实际上思路很简单，就看能不能想到。

a&b什么情况下不为0？只有在某一位中全都是1的时候，他们一定是部位0的。

因此，我们可以拓展到本题。

首先建立一个数组，用来记录所有数再某一位中为1的个数。（1e7<2^25）

对每一个数进行遍历，如何找到这个数的每一位呢？

可以通过与00000001、00000010、00000100......进行与操作，如果结果不是0，那么就说明这一位为1。

这是一种思路，我们也可以对每个数每次与1与操作，然后右移一位，再与1与操作......（也就是题解的方法）

int num = candidates[i];
int j = 0;
//提取数字的每一位
while (num!=0) {
    //将 1 位存起来
    if ((num & 1)!=0) {
        times[j]++;
    } 
    num = num >> 1;   //每次num的二进制向右移动一位
    j++;
}

最后取1最多的那个值，即为次数。如果某一位的1有y个，那么说明在这n个数中一定会有y个数，他们'且'后这一位为1（即结果不为0）。

2283. 判断一个数的数字计数是否等于数位的值

简单题，利用 hash 表进行处理即可。但是要注意 int 转为 char 的相关操作。

1	(char)('0'+i)

代码如下：

class Solution {
    public boolean digitCount(String num) {
        char[] nc = num.toCharArray();
        int n = num.length();
        HashMap<Character,Integer> hash = new HashMap<Character,Integer>();
        for (int i=0;i<n;i++) {
            hash.put(nc[i], hash.getOrDefault(nc[i],0)+1);
        }
        // hash.forEach((key,value)-> {
        //     System.out.println(key);
        //     System.out.println(value);
        // });  
        for (int i=0;i<n;i++) {
            if (hash.getOrDefault((char)('0'+i),0)!=(nc[i]-'0')) {
                return false;
            }
        }
        return true;
    }
}

2287. 重排字符形成目标字符串

虽然是简单题，但是本题的解题过程不简单。需要清楚的是：题目中只是要求用过的字符不能再次用，并没有说每次匹配好的那段所有的其他字符都不能用。因此只需要构造两个 hashmap，一个是用来记录 target 的每个字符出现的次数，另一个是记录 s 中在 target 的字符出现的次数，然后对应字符的次数相除，取最小值即可。

代码如下：

class Solution {
    public int rearrangeCharacters(String s, String target) {
        char[] sc = s.toCharArray();
        char[] tc = target.toCharArray();
        
        HashMap<Character,Integer> hash1 = new HashMap<Character,Integer>();
        HashMap<Character,Integer> hash2 = new HashMap<Character,Integer>();

        for (char t : tc) {
            hash2.put(t,hash2.getOrDefault(t,0)+1);
        }
        for (char c : sc) {
            if (hash2.containsKey(c)) {
                hash1.put(c,hash1.getOrDefault(c,0)+1);
            }
        }
        if (hash1.size()!=hash2.size()) {
            return 0;
        }
        int sum = 100;
        for (Map.Entry<Character,Integer> entry : hash2.entrySet()) {  
            char key = entry.getKey();
            sum = Math.min(sum, hash1.get(key)/entry.getValue());
        }
        return sum;
    }
}

2293、极大极小游戏

简单题，方法很多。

方法一、list 操作

将 nums 转为 list，之后再操作。代码如下：

class Solution {
    public int minMaxGame(int[] nums) {
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        int size = list.size();
        while (size!=1) {      //多行的循环处理
            int t = 1;
            while (size!=0) {       //每一行的循环处理
                if (t%2==1) {
                    list.add(Math.min(list.get(0),list.get(1)));
                }
                else {
                    list.add(Math.max(list.get(0),list.get(1)));
                }
                t++;
                list.remove(0);
                list.remove(0);
                size = size-2;
            }
            size = list.size();
        }
        return list.get(0);

    }
}

方法二、数组原地操作

利用 /2 的特性，在原数组进行操作。代码如下：

class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length/2;
        while (n!=0) {
            for (int i=0;i<n;i++) {
                if (i%2==0) {
                    nums[i] = Math.min(nums[i*2],nums[i*2+1]);
                }
                else {
                    nums[i] = Math.max(nums[i*2],nums[i*2+1]);
                }
            }
            n = n/2;
        }
        return nums[0];
    }
}

2299. 强密码检验器 II

简单题。注意：判断一个字符是否包含在字符串内：

1	t.indexOf(pc[i])!=-1

2303. 计算应缴税款总额

简单题~遍历即可。

2309. 兼具大小写的最好英文字母

虽然是简单题，但是涉及很多 java 的基础知识。比如：小写转为大写需要 -32。详细代码：

class Solution {
    public String greatestLetter(String s) {
        char[] sc = s.toCharArray();
        Set<Character> set = new HashSet<Character>();
        char res = ' ';
        for (int i=0;i<sc.length;i++) { 
            set.add(sc[i]);
            if (sc[i]<='z' && sc[i]>='a') {    //小写
                if (set.contains((char)(sc[i]-32))) {    //存在它的大写
                    if (res==' ' || res<(char)(sc[i]-32)) {
                        res = (char)(sc[i]-32);    //对比的是大写
                    }
                }
            }
            else {     //大写
                if (set.contains((char)(sc[i]+32))) {    //存在它的小写
                    if (res==' ' || res<sc[i]) {
                        res = sc[i];  
                    }
                }
            }
        }
        if (res==' ') {
            return "";
        }
        return String.valueOf(res);

    }
}

2315. 统计星号

简单题。

2319. 判断矩阵是否是一个 X 矩阵

简单题。

2325. 解密消息

简单题。唯一需要注意的是普通的动态数组用 ArrayList，字符动态数组用 StringBuilder。

2331. 计算布尔二叉树的值

简单题，考察树的后序遍历，并存入栈中（使用双端队列）。

核心代码如下：

public void PostOrder(TreeNode root, Deque<Integer> dq) {
	if (root == null) {
		return;
	}
	PostOrder(root.left,dq);
	PostOrder(root.right,dq);
	if (root.val == 2 || root.val == 3) {
		int x = dq.pollLast();
		int y = dq.pollLast();
		if (root.val == 2) {    //or
			dq.addLast(x|y);
		}
		else {
			dq.addLast(x&y);
		}
	}
	else {
		dq.addLast(root.val);
	}
}

2335. 装满杯子需要的最短总时长

本题只要将最大的两个值同时-1，当只剩下最后一个温度的杯子没有装满时，再直接加上即可。

2341. 数组能形成多少数对

简单题，没有意义。

2347. 最好的扑克手牌

简单题，快排即可。

2351. 第一个出现两次的字母

简单题，利用位运算判断字符是否已经判断过。

2357. 使数组中所有元素都等于零

简单题。

2363. 合并相似的物品

简单题，但是涉及到很多知识点。

hash 的添加操作

1	hash.put(i[0],hash.getOrDefault(i[0],0)+i[1]);

hash 的遍历

for (Map.Entry<Integer,Integer> entry : hash.entrySet()) {
	list.add(entry.getKey());
	list.add(entry.getValue());
}

list 的自定义遍历（注意是 Collections，不是 Arrays）

Collections.sort(res,new Comparator<List<Integer>>() {
	public int compare(List<Integer> l1, List<Integer> l2) {
		return l1.get(0)-l2.get(0);
	}
});

2367. 算术三元组的数目

简单题。

2373. 矩阵中的局部最大值

简单题，意义不大。

2379. 得到 K 个黑块的最少涂色次数

简单题，滑动窗口基础题！

2383、赢得比赛需要的最少训练时长

本题思路比较简单：

首先要求训练后的experience值要比对手的experience之和多1；

因为是依次挑战（按顺序挑战），所以一个个计算，如果因为energy打不过当前，那就要额外训练一段时间，让他刚好能打过，依次类推，最后能算出energy的额外训练时间。

将两个训练时间相加即可。

2389. 和有限的最长子序列

简单题，先排序，然后计算前缀和即可。

2395. 和相等的子数组

简单题，求和即可。

2399. 检查相同字母间的距离

简单题。

2404. 出现最频繁的偶数元素

简单题，无脑 hash 存储即可。

2409. 统计共同度过的日子数

简单题，但是恶心人。只要找到两个人的出发日期的最大值和离开日期的最小值，它们之间的时间差就是我们要求得得。

2413. 最小偶倍数

简单题，一行结束，优雅。

2418. 按身高排序

考察： #数组排序

简单题， #模板题。但是注意：根据一个数组的结果排序另一个数组的，这是模板题。

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] idx = new Integer[n];
        for (int i=0;i<n;i++) {
            idx[i] = i;
        }

        Arrays.sort(idx, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return heights[b]-heights[a];
            }
        });

        String[] res = new String[n];
        for (int i=0;i<n;i++) {
            res[i] = names[idx[i]];
        }

        return res;
    }
}

2423. 删除字符使频率相同

简单模拟题。但是要考虑的东西特别多。

2427. 公因子的数目

简单题。

2469. 温度转换

简单题，没有意义。

2488. 统计中位数为 K 的子数组⭐

Tags： #前缀和 #后缀和 #哈希

困难题，思路很难！是前缀和的超级灵活考察，它不是简单的前缀相加再处理，而是用相对大小进行处理，最后记录大于 k 和小于 k 的个数之间的关系。

思路：

首先注意，由于 nums 长度为 n，且是 1~n 的不同整数组成，数组只能是一个 1 到 n 的排列。同时 k≤n，则 k 一定在数组中出现过。

那么可以在数组中先找到 k，考虑一个数组的中位数如果是 k，那么这个排序后的 k 就在中间或中间偏左。

因此可以将 k 及其右侧所有数字到 k 这个位置上的“前缀和”统计出来（这里“前缀和”并不是常规上的“前缀和”），k 位置上的 sum=0，大于 k 的位置是 sum+1，小于的是 sum-1，并都存入哈希表。哈希表的 key 就是 sum，value 就是 sum 出现的次数。不难发现 key=0 一定会出现 1 次，也就表示整个数组至少会出现一个只有 k 单独元素组成的符合条件的子数组。

接下来对 k 左侧进行相反处理，从 k 位置向左端点进行遍历，即求到 k 的“后缀和”。等于 k 就 sum=0，小于 k 是 sum+1，大于 k 是 sum-1。但是本次遍历不需要存入 hash，而是直接不断 hash. get (sum)+hash. get (sum+1) 求出结果了。

举个例子：

假设数组为[3, 2, 1, 5, 4, 7, 6]。

先处理右端：[0, 0, 0, 0, 0, 1, 2]。

再处理左端：[2, 1, 0, -1, 0 , 1, 2]。我们可以看出当左边遍历到 2 的时候 sum=1，意味着左边小于 k 的比大于 k 的多 1 个，如果要使得子数组成立，我需要再右边找到右边大于 k 的比小于 k 的多 1 个，或者右边找到大于 k 的比小于 k 的多 2 个（因为中位数靠左），所以本题下标为 1~5 可以为一个结果，1~6 也可以为一个结果。

代码如下：

class Solution {
    public int countSubarrays(int[] nums, int k) {
        int n = nums.length;

        // 1. 找k的位置
        int loc = 0;     //记录k的位置
        for (int i=0;i<n;i++) {
            if (nums[i]==k) {
                loc = i;
                break;
            }
        }

        // 2. 计算以k为起点的前缀和以k为终点的后缀
        HashMap<Integer, Integer> hash = new HashMap<Integer,Integer>();
        int res = 0;
        // 2.1 以k为起点，等于k的也就是起点设置为0，比k大的sum+1，比k小的sum-1，每次结果都存在hash中
        int sum = 0;
        for (int i=loc;i<n;i++) {
            if (nums[i]==k) {
                sum = 0;
            }
            else if (nums[i]>k) {
                sum++;
            }
            else {
                sum--;
            }
            hash.put(sum, hash.getOrDefault(sum,0)+1);
        }
        // 2.2 以k为终点，但是遍历的时候k仍然是起点，只是从右往左遍历，等于k的也就是最初时候sum=0，比k大的sum-1，比k小的sum+1，每次结果直接和hash中的进行对比。
        // 依赖的原则是：k左边的sum一定比k右边的sum相等或者大1，那么这段就是正确的。
        for (int i=loc;i>=0;i--) {
            if (nums[i]==k) {
                sum = 0;
            }
            else if (nums[i]<k) {
                sum++;
            }
            else {
                sum--;
            }
            res += hash.getOrDefault(sum,0);
            res += hash.getOrDefault(sum+1,0);
        }
        return res;
    }
}

面试题 01.02. 判定是否互为字符重排⭐

本题可以使用将字符串转为字符数组：

1	char[] sa1 = s1.toCharArray();

再对字符数组进行排序，一样可以使用Arrays.sort()：

1	Arrays.sort(sa1); //对sa1原地排序

判断两个字符数组是否相同，可以先将字符数组转为字符串：

1	String s = String.valueOf(sa1);

字符串的比较：

1	s1.equals(s2); //返回true或者false

剑指 Offer 47. 礼物的最大价值

经典动态规划~

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n+1];
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                dp[j+1] = Math.max(dp[j]+grid[i][j],dp[j+1]+grid[i][j]);
            }
        }
        return dp[n];
    }
}

面试题01.05.一次编辑

比较简单的一题，类似于1913题的思路.

面试题 01.08、零矩阵

方法一、两次遍历

对二维数组遍历两遍，第一遍是为了找到受影响的行和列，第二遍是针对这些行和列做处理。

List查找某个元素是否在其中，可以用：（List其他操作见15题）

1	list.contains(s); //查找s这个元素是否在list中

方法二、两个标记变量

这个思路就是将第一行第一列作为标签，如果matrix中i行j列为0，则将第一行的j列和第一列的i行置为0即可。但是为了保存第一行和第一列的信息，我需要先判断如果第一行中没有0，但是由于matrix[i][j]为0，所以第一行的第j列必然为0。所以在操作之前先判断第一行和第一列是否有0，如果有则在最后一步将其全置为0。接下来的操作是分析除去第一行和第一列的元素，如果为0，则其对应的第一行的元素和第一列的元素变为0。遍历完之后，根据第一行和第一列的情况对内部元素操作。最后按照上面刚说的那样对第一行和第一列处理。

面试题 01.09、字符串轮转

方法一、利用子串匹配

java中有内置的判断字符串是否在另一个字符串的函数：

1	s1.contains(s2); //如果s2包含在s1中，则返回true，否则返回false

只需要将其中的一个字符串连续两个相同的拼接上，如果可以循环成为它，则另一个字符串就一定包含在这个拼接的字符串中。

方法二、指针移动关系

如果s1向左循环移动i位得到s2，那么对于s2的下标为j的元素有这样的关系：s2[j] = s1[(i+j)%j]。其实很好理解，因为如果是s1向左移动i位，相当于s2相对s1向右移动i位，所以对于s2的i位，实际就是s1的0位，这样就能得到这样的关系。注意的是对于字符串，提取下标为i的字符需要用s1.charAt(i)。

面试题 05.02. 二进制数转字符串

常规中等题，考察 StringBuilder 和除法。

class Solution {
    public String printBin(double num) {
        if (num==1.0) {
            return "1.0";
        }
        StringBuilder sb = new StringBuilder();
        sb.append("0.");
        double cs = 0.5;
        while (num!=0) {
            if (sb.length() > 32) {
                return "ERROR";
            }
            if (num >= cs*2) {
                return "ERROR";
            }
            if (num >= cs) {
                num -= cs;
                cs = cs / 2;
                sb.append('1');
            }
            else {
                cs = cs / 2;
                sb.append('0');
            }
        }
        if (num==0) {
            return sb.toString();
        }
        return "ERROR";
    }
}

面试题 17.05. 字母与数字

方法一、前缀和+定长

先计算前缀和，因为要找最长子串，所以定长遍历，从最长的长度开始，遍历起点，再依次缩小长度，继续遍历起点。直到找到一个长度下满足条件的起点，这个起点和长度就是满足条件的最长且靠左的。

代码如下：

class Solution {
    public String[] findLongestSubarray(String[] array) {
        int n = array.length;

        // 前缀和
        int[] pren = new int[n];
        int[] prec = new int[n];
        
        for (int i=0;i<n;i++) {
            char c = array[i].charAt(0);
            if (i==0) {
                if ((c>='A' && c<='Z') || (c>='a' && c<='z')) {
                    prec[i] = 1;
                    pren[i] = 0;
                }
                else {
                    prec[i] = 0;
                    pren[i] = 1;
                }
            }
            else {
                if ((c>='A' && c<='Z') || (c>='a' && c<='z')) {
                    prec[i] = prec[i-1] + 1;
                    pren[i] = pren[i-1];
                }
                else {
                    prec[i] = prec[i-1];
                    pren[i] = pren[i-1] + 1;
                }
            }
        }

        boolean isFind = false;
        int left=0, right=0;

        for (int len = n; len > 0; len--) {
            for (int start=0;start<=n-len;start++) {
                if (start==0) {
                    if (prec[start+len-1] == pren[start+len-1]) {
                        left = start;
                        right = start+len-1;
                        isFind = true;
                        break;
                    }
                }
                else {
                    if (prec[start+len-1] - prec[start-1] == pren[start+len-1] - pren[start-1]) {
                        left = start;
                        right = start+len-1;
                        isFind = true;
                        break;
                    }
                }
            }
            if (isFind) {
                break;
            }
        }

        if (right==left) {
            return new String[0];
        }

        String[] res = new String[right-left+1];
        for (int i=0;i<right-left+1;i++) {
            res[i] = array[i+left];
        }
        return res;
    }
}

方法二、前缀和+哈希⭐

我们设遇到字母+1，遇到数字-1，所以满足条件的子串的和就是为 0。但是找到一个和为 0 的子串实际上操作和方法一一致，没有达到优化的效果，所以需要转换思路。

假设以下标为 i 结尾的前缀和为 k，以下标为 j 结尾的前缀和也为 k，那么可以知道 i~j 之间部分的和为 0，实际上是 [i+1, j] 区间的和为 0，这个区间长度为 j-i。

哈希表 hash 记录每个前缀和第一次出现的位置，max 记录最大子数组的长度，start 记录最大子数组时的起点位置。

关于数组的深拷贝，使用方法见：数组深拷贝

详细代码如下：

class Solution {
    public String[] findLongestSubarray(String[] array) {
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
        hash.put(0,-1);
        int sum = 0;
        int max = 0, start = 0;
        for (int i=0;i<array.length;i++) {
            char c = array[i].charAt(0);
            if ((c>='A' && c<='Z') || (c>='a' && c<='z')) {      // 字母+1
                sum++;
            }
            else {       // 数字-1
                sum--;
            }
            if (hash.containsKey(sum)) {
                if (i-hash.get(sum) > max) {       // 表示以hash.get(sum)为尾的前缀和 和 以i为尾的前缀和是相等的，所以他们中间部分就是满足条件的子串
                    max = i - hash.get(sum);
                    start = hash.get(sum)+1;
                }
            }
            else {
                hash.put(sum,i);
            }
        }

        if (max == 0) {
            return new String[0];
        }

        String[] res = new String[max];
        System.arraycopy(array,start,res,0,max);
        return res;

    }
}

面试题17.09、第k个数

方法一、硬算

使用方法三的手法进行优化

List本质上就是动态数组

创建：

1	List<Integer> list = new ArrayList<Integer>();

添加：

1	list.add(16);

查询：

1	list.get(0); // 通过下标查询

方法二、小根堆

小根堆

小根堆的创建：

1	PriorityQueue<Long> q = new PriorityQueue<>();

小根堆添加操作：

q.add(5);

小根堆判断是否为空：

1	q.isEmpty() //如果是空则返回true

小根堆弹出操作（弹出最小的数，并返回此数）：

1	long t = q.poll();

Set集合

Set 表示唯一对象的集合。集合中元素的排序是不相关的。

HashSet

HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

HashSet 允许有 null 值。

HashSet 是无序的，即不会记录插入的顺序。

HashSet 实现了 Set 接口。（这就是为什么这个解法可以使用Set<Long> set = new HashSet<>();）

Set对象的创建：

1	Set<Long> set = new HashSet<>();

1	Set<Character> set = new HashSet<>();

Set对象的添加操作：

1	set.add(6);

Set对象的判断是否存在操作：

1	set.contains(k) //判断k这个值在set中是否存在，存在则返回true

Set对象删除

1	set.remove("book");

方法三、多路归并（多指针）（方法一优化）

设置3个指针，分别是对于*3、*5、*7的，每次比较选择最小的加入到数组中。

注意

在使用两个数比大小时，尽量使用Math.min(a,b)。如果时三个数，使用Math.min(a,Math.min(b,c))。

面试题 17.19、消失的两个数字

方法一、硬算（不合规矩）

方法二、异或（官方）

负数的补码:

对于正数9：0000 1001

对于负数-9：先-1：0000 1000；再全部取反：1111 0111。

或者先变成：1000 1001；再除了符号位取反：1111 0110；再末位+1：1111 0111。

所以: 9 = 0000 1001

-9 = 1111 0111
          9 & -9 = 0000 0001（能生成二进制中为1的最小位） 
拓展: 10 = 0000 1010

-10 = 1111 0110
           10 & -10 = 0000 0010 
异或

Java中异或用^表示

1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 4 => 0 ^ 0 ^ 3 ^ 4 => 0 ^ 3 ^ 4（x = 3^4）=> 0 ^ x => x

即 a ^ a ^ b = b

Integer.MIN_VALUE = 1000 0000 0000 0000 0000 0000 0000 0000，-2 147 483 648

Integer.MAX_VALUE = 0111 1111 1111 1111 1111 1111 1111 1111， 2 147 483 647

逻辑：

这是考察异或和且的位运算算法题。我们想要找到n个数中没有出现的2个数，也就是再n个数中找出除了nums中存在的n-2个数的另外2个数。

如果先将这n个数和nums中n-2个数异或，也就是这2n-2（n-2 + n-2 + 2）个数异或，根据上面异或的相关知识，能得到结果x = x1 ^ x2（x为异或结果，x1、x2为我们想要求得的两个不在nums的数）。

得到x = x1 ^ x2，如何提取出x1和x2成为了最大的难题。我们发现x1和x2不可能相同，所以x1&x2! = 0，根据上面且的相关知识，对于x而言，它二进制最低位的1（假设是第k位）所代表的含义是x1的第k位和x2的第k位是不相同的（因为相同为0、不同为1），因此我们可以将nums分为两类，一类是第k位为0的，一类是第k位为1的。筛选出nums这两类很简单，只需要与x&-x（x&-x的结果是除了第k位为1，其他位都是0）进行且操作，如果结果是0，表示nums中的这个数的第k位是0；如果是1，表示nums中的这个数的第k位是1。这里需要进行防溢出操作，即判断x == Integer.MIN_VALUE，如果成立，说明-x已经越界，就直接将x与nums中每个数进行比较筛选。

经过上一步就已经将nums分为两部分了type1、type2，这时候只需要将n个数分为两部分，两部分分别是type1多一个x1、type2多一个x2。只需要再用一次异或，结果就分别是x1和x2了。

返回结果直接用new int[]{type1,type2}即可。

方法三、求和

本方法使用数学基础运算。先求出n个数之和，再求出nums中n-2个数之和，则这两个和之差就是x1+x2。我们可以通过x = x1+x2，算出x1和x2的中位数t，即x1一定小于t，x2一定大于t，求出1~t的和truenum，可以将nums遍历一遍，筛选每一个值小于等于t的num，再用truenum减去这个值，得到的结果就是x1。用x2 = x - x1得到结果。

LeetCode逐题笔记

https://wryit.fun/2022/11/15/LeetCode逐题笔记/

作者

火星架构师

发布于

2022-11-15

更新于

2023-05-03

许可协议

CC BY-NC-SA 4.0

LeetCode

1、两数之和

length的使用

2. 两数相加

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

4、寻找两个正序数组的中位数

5、最长回文子串

方法一、中心扩张法

注意

替换

方法二、动态规划

注意

11、盛最多水的容器

15、三数之和

20. 有效的括号

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

31、下一个排列

33、搜索旋转排序数组

方法一、暴力（不满足log(n)）

方法二、二分法（不完全满足log(n)）

方法三、二分法优化（满足log(n)）

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

方法一、二分+扩张

方法二、二分查找性质

35. 搜索插入位置

39、组合总和⭐

方法一、双端队列+DFS

相关知识

List<List>

Deque双端队列

方法二、剪枝叶

40、组合总和II

45、跳跃游戏II⭐

方法一、动态规划+数组

方法二、优化

46、全排列

拓展

49. 字母异位词分组

53、最大子数组和

55、跳跃游戏

方法一、动态规划+dp数组

方法二、优化——动态更新最大长度

56. 合并区间

68、文本左右对齐

方法一、枚举各种情况

70、爬楼梯

方法一、动态规划

简单优化

74. 搜索二维矩阵

78. 子集⭐⭐

方法一

方法二、更通用的回溯⭐（框架）

89. 格雷编码 ⭐

方法一、规律

方法二、格雷编码

90. 子集 II⭐

94. 二叉树的中序遍历

101. 对称二叉树😭

102. 二叉树的层序遍历

104. 二叉树的最大深度

118. 杨辉三角

121、买卖股票的最佳时机

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

128. 最长连续序列⭐

135、分发糖果

方法一、递归

方法二、左右遍历

136. 只出现一次的数字

方法一、HashSet

方法二、位运算👍

152、乘积最大子数组⭐

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

189. 轮转数组

方法一、开辟额外空间

方法二、原地翻转👍

198、打家劫舍（模板题）⭐⭐

优化前

注意：

优化后（理论上更优的）

208. 实现 Trie (前缀树)⭐

213、打家劫舍 II⭐

方法一、二维数组（纯暴力）