月度归档： 2022年6月

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

示例 1：

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

示例 2：

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

提示：

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

连续区间和，必然会想到的内容前缀和数组

所以在这题目中，我们的思路是这样的

1. 要求区间和为K的子数组的话，那么就需要判断 在当前位置前面，是否存在前缀和为当前区间和减去K的情况存在
2. 可以在前缀和数组上遍历，当然我们有更好的选择，哈希表
3. 在求前缀和数组的过程中，用哈希表统计各个值的前缀和出现次数
4. 那么当前位置的前缀和 与这个位置之前的 前缀和能组成多少个符合 区间和为K的区间就可以等价🐟， 当前位置之前有多少个 当前位置区间和 减去 K的值的区间和的数量
5. 边界考虑：当什么都没有的时候有一个区间和为0的情况

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] preSum = new int[nums.length];
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        hashMap.put(0,1);
        int idx = -1;
        int count = 0;

        while (++idx < nums.length){
            preSum[idx] = nums[idx] + (idx>0?preSum[idx-1]:0);
            count += hashMap.getOrDefault(preSum[idx] - k,0);
            hashMap.put(preSum[idx], hashMap.getOrDefault(preSum[idx],0)+1);
        }
        return count;
    }
}

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

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

提示：

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

滑动窗口，带注释

一样的，就是统计窗口内待匹配字符出现次数

1. 统计原t字符串中各个字符的数量
2. 在字符串s中进行窗口移动操作
3. 如果还有需要匹配的字符数量，则往右扩展右边界增大窗口
4. 如果字符数量都匹配达成，则左边界往右可移动缩小窗口
5. 在窗口移动过程中取到最小的那个子串

代码

class Solution {
    public String minWindow(String s, String t) {
        int[] arr = new int[128];
        HashSet<Character> hashSet = new HashSet<>();
        for (int i = 0; i < t.length(); i++) {
            arr[t.charAt(i)]++;
            hashSet.add(t.charAt(i));
        }
        int count = hashSet.size();
        //count 表示待匹配字符个数
        int l = 0;
        int r = -1;
        int minL = 0;
        int minLen = Integer.MAX_VALUE;

        while (r < s.length()){
            if (count == 0){
                //移动左边，尝试缩减长度
                arr[s.charAt(l)]++;
                //左边界每往右移动一个字符 在在arr[]中这个字符个数加1
                if (hashSet.contains(s.charAt(l)) && arr[s.charAt(l)] == 1){
                    // 如果这个字符在hashSet中，且结果等于1，即表示是从匹配成了变为缺少匹配个数的状态，那么count++;
                    count++;
                }
                //移动左边
                l++;
            }else{
                //移动右边边
                r++;
                if (r == s.length()){
                    break;
                }
                arr[s.charAt(r)]--;
                //右边界每新增一个字符， 在arr[]中减去这个字符个数减1
                if (hashSet.contains(s.charAt(r)) && arr[s.charAt(r)] == 0){
                    //    如果这个字符在hashSet中，如果结果为0 了表示都匹配到了，则count--;
                    count--;
                }
            }
            if (count==0 && r - l < minLen){
                //记下最小子串
                minLen = r - l;
                minL = l;
            }
        }
        return minLen==Integer.MAX_VALUE?"":s.substring(minL,minL+minLen+1);
    }
}

给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
• void reset() 将矩阵中所有的值重置为 0

示例：

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

提示：

• 1 <= m, n <= 104
• 每次调用flip 时，矩阵中至少存在一个值为 0 的格子。
• 最多调用 1000 次 flip 和 reset 方法。

分析，实现，【掉坑】，改进

直接模拟，思路

1. 声明一个m * n的二维数组，随机翻转一个
2. 但是接下来的问题就是，如何随机保证横轴和纵轴的坐标的随机概率相等，所以我们可以换个思路，直接声明一个m * n长度的一维数组，在这个长度内随机，而每一个随机数都可以映射回原来的矩阵中，从而保证每一个格子的随机概率是相等的
3. 下一个问题，之前已经翻转到过的位置不能再随机到。
   • 那么我们就需要记录一下剩余多少位置可以随机，从而在这个范围内进行随机操作
   • 如果在这个范围内随机到的数字是之前原数组中已经翻转过的，那么就从这个位置开始一直往后找到未被翻转的过的那个位置
4. 最终将随机到的位置坐标重新映射回矩阵坐标中返回即可

代码

class Solution {

    int[] matrix;
    int m;
    int n;
    Random random;
    int total;

    public Solution(int m, int n) {
        random = new Random();
        this.m = m;
        this.n = n;
        reset();
    }
    
    public int[] flip() {
        int idx = random.nextInt(total);
        while (matrix[idx]==1){
            idx++;
        }
        total--;
        matrix[idx] = 1;
        return new int[]{idx/n,idx%n};
    }
    
    public void reset() {
        matrix = new int[m * n];
        total = matrix.length;
    }
}

提交，跑到第19个测试用例，报OOM了，看下入参是10000 * 10000，按照道理java中数组的最大长度根据具体数据类型和JVM配置实际情况应该是一个接近Integer.MAX_VALU - 8的值，最大就是这么多，此时OOM的话，必然应该是限制了内存大小了

那么我们不妨再换个思路，题面中给出了 最多调用 1000 次 flip 和 reset 方法，我们就可以不用记录整个数组的情况，而是换一种角度，只记录哪些位置被翻转过，使用一个HashSet来存储这些位置信息，那么修改后代码如下

代码

class Solution {

    int m;
    int n;
    Random random;
    int total;
    HashSet<Integer> hashSet;

    public Solution(int m, int n) {
        random = new Random();
        this.m = m;
        this.n = n;
        reset();
    }
    
    public int[] flip() {
        int idx = random.nextInt(total);
        while (hashSet.contains(idx)){
            idx++;
        }
        total--;
        hashSet.add(idx);
        return new int[]{idx/n,idx%n};
    }
    
    public void reset() {
        hashSet = new HashSet<>();
        total = m * n;
    }
}

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

双指针，串珠子

同剑指Offer25
这个问题之前给人家形象的比喻讲解过。

1. 你拿两串珠子，分别按照题意标上有序递增的数字
2. 另外你再拿一根线，把这两串珠子合并成一串，这时候你会怎么做呢？
   当然是两个原串头上挑小的串起来呀！哪个小串哪个，另外一串没有了就整个串上就完了

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

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

提示：

• 1 <= n <= 16

找规律想方法，找到对称关系

试着先从头开始写几行数据看下吧

   0
   0    1
  00   01   11   10
 000  001  011  010  110  111  101  100
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

1. 只有0的时候，不明显，继续往下看，只有第二行也一样
2. 第三行，我们先把数字都扩充到2位，之前的变成00, 01，那么剩下的只有11, 10 了此时只有 00 01 11 10这个顺序了，其他的组合情况暂不考虑
3. 第三行依旧扩充到3位000 001 011 010 ，下一个数字要和010只有一位不同的话只能选择110了，再下一位依旧只能111，这样 101 100
4. 开始总结规律，可以看到后半部分都是1xx这样的数据了，且如果户管最高位的话，和前面的内容是对称的，即，下标i和下标n - i对应，且下标i的值加1xx(二进制数)等于下标n - i 的值，那么我们基本就总结出规律了
5. 看第四行，原本前8位数字整体原封不动的保留，同时对应后面对称位置的值为当前位置的值加1000(二进制数)

稍微总结下

这个怎么来理解关系呢？我们来缕下 假设数组长度为 2n，（n不等于0，指实际位置从1开始，不是指从0开始的下标）

1. 从对称的最中间两位开始看，也就是第 n和n+1位，这两个数字后面部分是完全一样的，只有头部第一位一个是1 一个是0的区别，相差一位
2. 再看n-1 和n+2这两个对称位置，拿上面的第四行数据中间部分来说明
   0101 0100 1100 1101
   对应数字为0101和 1101, 因为0101和后面一位0100相差一位，所以同样对称部分的1100和1101如果忽略头部的1的话和这边其实是一致的也是相差一位，而又因为这两者头部都是加的1是相同的，所以这两者是必然相差一位的即n+1与n+2相差的一位是和n-1与n相差的一位是一样的
3. 再往后更多的对称部分和这一步也一样可以推断出是相差一位的

代码

class Solution {
    public List<Integer> grayCode(int n) {
        int i = 0;
        int[] list1 = new int[1];
        int[] list2 = new int[2];
        while (++i <=n){
            list2 = new int[1<<i];
            int lastIdx = list1.length * 2 - 1;
            int plus = 1 << (i-1);
            for (int idx = 0; idx < list1.length; idx++) {
                list2[idx] = list1[idx];
                list2[lastIdx - idx] =  list1[idx] | plus ;
            }
            list1 = list2;
        }
        List<Integer> r = new ArrayList<>();
        for (int i1 : list2) {
            r.add(i1);
        }
        return r;
    }
}

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

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

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

输入：s = ""
输出：0

栈模拟，java

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int idx = -1;
        int ans = 0;
        while (++idx < s.length()) {
            //表示上一个未被匹配的左括号'('
            if (s.charAt(idx) == '(') {
                stack.push(idx);
            } else {
                //这里是右括号‘)’
                stack.pop();
                if (!stack.isEmpty()) {
                    ans = Math.max(ans, idx - stack.peek());
                }else{
                    stack.push(idx);
                }
            }
        }
        return ans;
    }
}

1. 栈底元素是有效区间的起始位置
2. 之后栈内只插入左括号（的位置
3. 每遇到一个右括号，则从栈顶弹出一个元素
4. 如果弹出的是左括号，那么就能知道当前的有效区间的长度
5. 如果弹出的右括号，此时栈内为空，之前的有效区间不存在了，后面再能遇到的是新的有效区间，需要从当前位置重新开始表示，那么就把当前值插入到栈底部
6. 在每次得到有效区间的时候，依次比较取较大值