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

目录

1、强密码检验器 II

1）题目描述

如果一个密码满足以下所有条件，我们称它是一个 强 密码：
它有至少

8

个字符。
至少包含 一个小写英文 字母。
至少包含 一个大写英文 字母。
至少包含 一个数字 。
至少包含 一个特殊字符 。特殊字符为：

"!@#$%^&*()-+" 

中的一个。
它 不 包含 2 个连续相同的字符（比方说

"aab" 

不符合该条件，但是

"aba"

符合该条件）。
给你一个字符串

password

，如果它是一个 强 密码，返回

true

，否则返回

false 

。

2）原题链接

原题链接：LeetCode.6095：强密码检验器 II

3）思路解析

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

4）模板代码

classSolution{publicbooleanstrongPasswordCheckerII(String password){int n=password.length();if(n<8)returnfalse;boolean f1=false,f2=false,f3=false,f4=false;Set<Character> set=newHashSet<>();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))returnfalse;if(c>='a'&&c<='z') f1=true;elseif(c>='A'&&c<='Z') f2=true;elseif(c>='0'&&c<='9') f3=true;elseif(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：咒语和药水的成功对数

3）思路解析

•                                (                         1                         )                              (1)                  (1)对于一个咒语```x```，我们需要找到一个药水```y```，使得```xy>=success```。由于都是正整数且未乘法，我们可知，如果能量强度为```y```的药水满足，则大于```y```的药水也一定满足。
  

•                                (                         2                         )                              (2)                  (2)我们可以考虑对药水进行排序，然后进行二分，找到一个符合```xy>=success```的最小的一个```y```，则它右边所有的药水也都是满足的，左边所有的药水都不满足，具有二段性。
  

4）模板代码

classSolution{publicint[]successfulPairs(int[] spells,int[] potions,long success){int n=spells.length;int m=potions.length;int[] ans=newint[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;//注意可能爆intif((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：替换字符后匹配

3）思路解析

•                                (                         1                         )                              (1)                  (1)本题的范围不大，```1 <= sub.length <= s.length <= 5000```。因为数据不大，对于```s```的每个位置开始枚举，判断能否成功匹配```sub```。
  

•                                (                         2                         )                              (2)                  (2)用```Map```存储下对于每个字符可以替换成哪些字符，在匹配过程中，如果可以替换完成我们则继续匹配，否则直接枚举下一个位置。
  

4）模板代码

classSolution{Map<Character,Set<Character>> map=newHashMap<>();publicbooleanmatchReplacement(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)returntrue;}returnfalse;}voidadd(char a,char c){if(!map.containsKey(a)) map.put(a,newHashSet<>());
        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 的子数组数目

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）模板代码

classSolution{publiclongcountSubarrays(int[] nums,long k){int n=nums.length;long ans=0;long[] s=newlong[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;}booleancheck(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、周赛总结

  难度不高，注意细节。