锐客网

  1. 首页 > 睿知 > it技术 > >

《力扣周赛题解》|【周赛复盘】LeetCode第80场双周赛

算法leetcode职场和发展学习蓝桥杯


目录

  • 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

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 set=new HashSet<>(); String s="!@#$%^&*()-+"; for(int i=0; i.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）题目描述
【《力扣周赛题解》|【周赛复盘】LeetCode第80场双周赛】给你两个正整数数组 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）模板代码
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>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：替换字符后匹配

3）思路解析
  • ( 1 ) (1) (1)本题的范围不大，1 <= sub.length <= s.length <= 5000。因为数据不大，对于s的每个位置开始枚举，判断能否成功匹配sub。
  • ( 2 ) (2) (2)用Map存储下对于每个字符可以替换成哪些字符，在匹配过程中，如果可以替换完成我们则继续匹配，否则直接枚举下一个位置。
4）模板代码
class Solution { Map> 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 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 的子数组数目

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>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=https://www.it610.com/article/(s[j]-s[i-1])*(j-i+1); return value

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第298场单周赛