【周赛复盘】LeetCode第80场双周赛

太过爱你忘了你带给我的痛 2023-10-01 22:07 19阅读 0赞

#### 目录 ####

*  1、强密码检验器 II
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  2、咒语和药水的成功对数
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  3、替换字符后匹配
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  4、统计得分小于 K 的子数组数目
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  5、周赛总结

## 1、强密码检验器 II ##

### 1）题目描述 ###

> 如果一个密码满足以下所有条件，我们称它是一个 强 密码：  
> 它有至少 `8` 个字符。  
> 至少包含 **一个小写英文** 字母。  
> 至少包含 **一个大写英文** 字母。  
> 至少包含 **一个数字** 。  
> 至少包含 **一个特殊字符** 。特殊字符为：`"!@#$%^&*()-+"`中的一个。  
> 它 **不** 包含 2 个连续相同的字符（比方说 `"aab"`不符合该条件，但是 `"aba"` 符合该条件）。  
> 给你一个字符串`password`，如果它是一个 **强** 密码，返回 `true`，否则返回 `false`。

### 2）原题链接 ###

> 原题链接：[LeetCode.6095：强密码检验器 II  
> ][LeetCode.6095_ II]

### 3）思路解析 ###

*   ( 1 ) (1) (1)比较简单的模拟题，对于每个要求用一个`boolean`变量表示，每符合一个将其变为`true`，最后判读是否全部都为`true`。

### 4）模板代码 ###

class Solution {
        
        public boolean strongPasswordCheckerII(String password) {
        
             int n=password.length();
            if (n<8) return false;
            boolean f1=false,f2=false,f3=false,f4=false;
            Set<Character> set=new HashSet<>();
            String s="!@#$%^&*()-+";
            for(int i=0;i<s.length();++i) set.add(s.charAt(i));
            for (int i = 0; i < n; i++) {
        
                char c=password.charAt(i);
                 if (i>0&&c==password.charAt(i-1)) return false;
                if (c>='a'&&c<='z') f1=true;
                else if (c>='A'&&c<='Z') f2=true;
                else if (c>='0'&&c<='9') f3=true;
                else if (set.contains(c)) f4=true;
            }
            return f1&&f2&&f3&&f4;
        }
    }

### 5）算法与时间复杂度 ###

算法：**模拟**  
  时间复杂度：遍历一次字符串，时间复杂度为 O ( n ) O(n) O(n)。

## 2、咒语和药水的成功对数 ##

### 1）题目描述 ###

> 给你两个正整数数组 `spells` 和 `potions` ，长度分别为 `n` 和`m`，其中 `spells[i]` 表示第 `i` 个咒语的能量强度，`potions[j]` 表示第`j` 瓶药水的能量强度。  
> 同时给你一个整数 `success` 。一个咒语和药水的能量强度 **相乘** 如果 **大于等于**`success` ，那么它们视为一对 成功 的组合。  
> 请你返回一个长度为 `n` 的整数数组 `pairs`，其中 `pairs[i]` 是能跟第 `i` 个咒语成功组合的 **药水** 数目。

### 2）原题链接 ###

> 原题链接：[LeetCode.6096：咒语和药水的成功对数  
> ][LeetCode.6096_]

### 3）思路解析 ###

*   ( 1 ) (1) (1)对于一个咒语`x`，我们需要找到一个药水`y`，使得`xy>=success`。由于都是正整数且未乘法，我们可知，如果能量强度为`y`的药水满足，则大于`y`的药水也一定满足。
 *   ( 2 ) (2) (2)我们可以考虑对药水进行排序，然后进行二分，找到一个符合`xy>=success`的最小的一个`y`，则它右边所有的药水也都是满足的，左边所有的药水都不满足，具有二段性。

### 4）模板代码 ###

class Solution {
        
     public int[] successfulPairs(int[] spells, int[] potions, long success) {
        
            int n=spells.length;
            int m=potions.length;
            int[] ans=new int[n];
            Arrays.sort(potions);
            for (int i = 0; i < n; i++) {
        
                int l=0;
                int r=m-1;
                while (l<r){
        
                    int mid=l+r>>1;
                    //注意可能爆int
                    if ((long)spells[i]*potions[mid]>=success) r=mid;
                    else l=mid+1;
                }
                //有可能无解，也就是一个药水都不符合，所以需要判断一下
                if ((long)spells[i]*potions[r]>=success) ans[i]=m-r;
                else ans[i]=0;
            }
            return ans;
        }
    }

### 5）算法与时间复杂度 ###

算法：**二分、排序**  
  时间复杂度：排序的世界复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，遍历加二分的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，整体的复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

## 3、替换字符后匹配 ##

### 1）题目描述 ###

> 给你两个字符串 `s` 和 `sub` 。同时给你一个二维字符数组 `mappings` ，其中 `mappings[i] = [oldi, newi]` 表示你可以替换 `sub` 中任意数目的 `oldi` 个字符，替换成 `newi` 。`sub` 中每个字符 **不能** 被替换超过一次。  
> 如果使用 `mappings` 替换 0 个或者若干个字符，可以将 `sub` 变成 `s` 的一个子字符串，请你返回 `true`，否则返回 `false` 。  
> 一个 **子字符串** 是字符串中连续非空的字符序列。

### 2）原题链接 ###

> 原题链接：[LeetCode.6097：替换字符后匹配  
> ][LeetCode.6097_]

### 3）思路解析 ###

*   ( 1 ) (1) (1)本题的范围不大，`1 <= sub.length <= s.length <= 5000`。因为数据不大，对于`s`的每个位置开始枚举，判断能否成功匹配`sub`。
 *   ( 2 ) (2) (2)用`Map`存储下对于每个字符可以替换成哪些字符，在匹配过程中，如果可以替换完成我们则继续匹配，否则直接枚举下一个位置。

### 4）模板代码 ###

class Solution {
        
         Map<Character,Set<Character>> map=new HashMap<>();
        public boolean matchReplacement(String s, String sub, char[][] mappings) {
        
            for (char[] c:mappings){
        
                add(c[0],c[1]);
            }
            int n=s.length();
            int m=sub.length();
            for (int i = 0; i+m-1<n; i++) {
        
                boolean f=true;
                for (int j = 0; j <m; j++) {
        
                    if (s.charAt(i+j)==sub.charAt(j)) continue;
                    else{
        
                        if (!map.containsKey(sub.charAt(j))){
        
                            f=false;
                            break;
                        }else{
        
                            Set<Character> set=map.get(sub.charAt(j));
                            if (!set.contains(s.charAt(i+j))){
        
                                f=false;
                                break;
                            }
                        }
                    }
                }
                if (f) return true;
            }
            return false;
        }
        void add(char a,char c){
        
            if (!map.containsKey(a)) map.put(a,new HashSet<>());
            map.get(a).add(c);
        }
    }

### 5）算法与时间复杂度 ###

算法：**哈希、模拟**  
  时间复杂度：对于`s`的每个位置开始模拟`sub`的长度，最差的时间复杂度为 O ( 5000 ∗ 5000 ) O(5000\*5000) O(5000∗5000),可以过。

## 4、统计得分小于 K 的子数组数目 ##

### 1）题目描述 ###

> 一个数字的 **分数** 定义为数组之和 **乘以** 数组的长度。  
> 比方说，`[1, 2, 3, 4, 5]` 的分数为 `(1 + 2 + 3 + 4 + 5) * 5 = 75`。  
> 给你一个正整数数组 `nums` 和一个整数 `k` ，请你返回 `nums` 中分数 **严格小于** k 的 **非空整数子数组数目。**  
> **子数组** 是数组中的一个连续元素序列。

### 2）原题链接 ###

> 原题链接：[LeetCode.6096：统计得分小于 K 的子数组数目  
> ][LeetCode.6096_ K _]

### 3）思路解析 ###

*   ( 1 ) (1) (1)对于题意不难发现，对于任意一个符合条件的数组，则它的子数组也一定符合也一定符合。因为子数组的长度和和一定都比数组更小，乘积也一定会更小。
 *   ( 2 ) (2) (2)对于每个位置  i i i 我们视为子数组的起始位置(左坐标)，我们可以在它的右边找到一个最大的 j j j,使得所有 \[ i , j \] \[i,j\] \[i,j\]范围内的坐标为右坐标形成的子数组都符合下式， \[ j + 1 , n \] \[j+1,n\] \[j\+1,n\]都不符合题意。  
     s u m \[ i , j \] ∗ ( j − i + 1 ) < = k sum\[i,j\]\*(j-i+1)<=k sum\[i,j\]∗(j−i\+1)<=k
 *   ( 3 ) (3) (3)很明显，枚举 j j j的位置具有二段性，我们可以使用二分。找到 j j j后，以每个 i i i为起始位置的符合题意的子数组的个数为 j − i + 1 j-i+1 j−i\+1，枚举每个位置累加答案即可。对于枚举子数组的和，我们使用前缀和数组来求。

### 4）模板代码 ###

class Solution {
        
        public long countSubarrays(int[] nums, long k) {
        
            int n=nums.length;
            long ans=0;
            long[] s=new long[n+1];
            for(int i=0;i<n;++i) s[i+1]=s[i]+nums[i];
            for (int i = 1; i <=n; i++) {
        
                int l=i;
                int r=n;
                while (l<r){
        
                    int mid=l+r+1>>1;
                    if (check(s,i,mid,k)) l=mid;
                    else r=mid-1;
                }
                if (check(s,i,r,k)){
        
                    int len=r-i+1;
                    ans+=len;
                }
            }
            return ans;
        }
        boolean check(long[] s,int i,int j,long k){
        
            long value=(s[j]-s[i-1])*(j-i+1);
            return value<k;
        }
    }

### 5）算法与时间复杂度 ###

算法：**枚举**、**前缀和**、**二分**  
  时间复杂度：枚举的时间复杂度为 O ( n ) O(n) O(n)，每个位置二分的时间复杂度为 O ( l o g n ) O(logn) O(logn)，整体的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

## 5、周赛总结 ##

难度不高，注意细节。

[LeetCode.6095_ II]: https://leetcode.cn/problems/strong-password-checker-ii/
[LeetCode.6096_]: https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/
[LeetCode.6097_]: https://leetcode.cn/problems/match-substring-after-replacement/
[LeetCode.6096_ K _]: https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/