LeetCode 第 367 场周赛

2903.找出满足差值条件的下标 I

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

abs(i - j) >= indexDifference 且
abs(nums[i] - nums[j]) >= valueDifference
返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

---

复杂度：O(N*N)
思路：遍历，找到满足条件的两个下标，直接返回。

class Solution {
    public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
        // int[] ans = ;
        int n = nums.length;
        for(int i=0; i<n; i++) {
            for(int j=i+indexDifference; j<n; j++) {
                if(Math.abs(nums[i]-nums[j])>=valueDifference) {
                    return new int[]{i, j};
                }
            }
        }
        
        return new int[]{-1, -1};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2904. 最短且字典序最小的美丽子字符串

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

例如，“abcd” 的字典序大于 “abcc” ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

---

复杂度：O(N)
思路：滑动窗口。窗口两个边界为left与right。
通过滑动窗口得到的子序列的1的数量小于K，则移动right。当子序列1的数量等于K时，更新答案，并移动left。

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        StringBuffer res = new StringBuffer("");
        // 滑动窗口
        /**
        不够，r移动
        够，l移动        
        */
        int n = s.length();
        int l = 0, r = 0;
        int cnt = 0;
        while(l<n) {
            if(s.charAt(l)=='1') {
                break;
            }
            l ++;
        }        
        for(r=l; r<n; r++) {
            char c = s.charAt(r);
            if(c == '1') {
                cnt ++;
            }          
            if(cnt == k) {
                // 满足条件
                String tmp = s.substring(l, r+1);
                //System.out.println(tmp);
                if(res.length()==0) {
                    res.append(tmp);
                } else if(res.length()>tmp.length()){
                    res.setLength(0);
                    res.append(tmp);
                    
                } else if(res.length()==tmp.length()) {
                    if(res.toString().compareTo(tmp)>0) {
                        res.setLength(0);
                        res.append(tmp);
                    }
                }
                cnt --;
                l ++;
                while(l<r) {
                    //System.out.println("what "+l);
                    if(s.charAt(l)=='1') {
                        break;
                    }
                    l ++;
                }                                
            }             
        }
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

2905. 找出满足差值条件的下标 II

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

abs(i - j) >= indexDifference 且
abs(nums[i] - nums[j]) >= valueDifference
返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

---

复杂度：O(N)
思路：因为abs(nums[i]-nums[j])>=v。可以理解为nums[i]>=nums[j]+v与nums[i]<=nums[j]-v。这两种情况，满足其一即可。即需要寻找后K个数据的最大值与最小值，若有满足条件的输出即可。

class Solution {
    public int[] findIndices(int[] nums, int index, int v) {
        int n = nums.length;
        if(n==0){
            return new int[]{-1, -1};
        }
        // 记录后k个最小值与索引
        int[] sm = new int[n];
        int[] smidx = new int[n];
        
        // 记录后k个最大值与索引
        int[] la = new int[n];
        int[] laidx = new int[n];
        
        // 更新
        for(int i=0; i<n; i++) {
            sm[i] = nums[i]-v;
            la[i] = nums[i]+v;
        }        
        
        smidx[n-1] = n-1;
        laidx[n-1] = n-1;
        int min = sm[n-1];
        int minidx = n-1;
        int maxidx = n-1;
        int max = la[n-1];
        for(int i=n-2; i>=0 ; i--) {
            if(sm[i]<=min) {
                 sm[i] = min;
                smidx[i] = minidx;                  
            }else {
                min = sm[i];
                minidx = i;
                smidx[i] = minidx;
            }            
            if(la[i]>=max){
                la[i] = max;
                laidx[i] = maxidx;
            } else {
                max = la[i];
                maxidx = i;
                laidx[i] = maxidx;
            }
        }        
        for(int i=0; i<n; i++) {
            int j = i + index;            
            if(j<n) {
               // System.out.println(nums[i]+" "+sm[j]+" "+la[j]);
                if(nums[i]<=sm[j]) {
                    return new int[]{i, smidx[j]};
                }
                if(nums[i]>=la[j]) {
                    return new int[]{i, laidx[j]};
                }
            }
        }
        return new int[]{-1, -1};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

2906. 构造乘积矩阵

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。
返回 grid 的乘积矩阵。

---

复杂度：O(N)
思路：前缀和与后缀和

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int MOD = 12345;
        int[][] res = new int[n][m];
        
        long suf = 1;
        for(int i=n-1; i>=0; i--) {
            for(int j=m-1; j>=0; j--) {
                res[i][j] = (int)suf;
                suf = suf*grid[i][j]%MOD;
            }
        }

        long prev = 1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                res[i][j] = (int)(prev*res[i][j]%MOD);
                prev = prev*grid[i][j]%MOD;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25