6095. 强密码检验器 II
如果一个密码满足以下所有条件，我们称它是一个 强 密码：
- 它有至少 8 个字符。
- 至少包含 一个小写英文 字母。
- 至少包含 一个大写英文 字母。
- 至少包含 一个数字 。
- 至少包含 一个特殊字符 。特殊字符为：”!@#$%^&*()-+” 中的一个。
- 它 不 包含 2 个连续相同的字符（比方说 “aab” 不符合该条件，但是 “aba” 符合该条件）。
给你一个字符串 password ，如果它是一个 强 密码，返回 true，否则返回 false 。
示例 1：
输入：password = “IloveLe3tcode!” 输出：true 解释：密码满足所有的要求，所以我们返回 true 。
示例 2：
输入：password = “Me+You—IsMyDream” 输出：false 解释：密码不包含数字，且包含 2 个连续相同的字符。所以我们返回 false 。
示例 3：
输入：password = “1aB!” 输出：false 解释：密码不符合长度要求。所以我们返回 false 。
提示：
- 1 <= password.length <= 100
- password 包含字母，数字和 “!@#$%^&*()-+” 这些特殊字符。
思路：
模拟
class Solution {public boolean strongPasswordCheckerII(String s) {Set<Character> set = new HashSet<>();String t = "!@#$%^&*()-+";for (int i = 0; i < t.length(); i++) {set.add(t.charAt(i));}if (s.length() < 8)return false;boolean flag = false;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {flag = true;break;}}if (!flag) return false;flag = false;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {flag = true;break;}}if (!flag) return false;flag = false;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {flag = true;break;}}if (!flag) return false;flag = false;for (int i = 0; i < s.length(); i++) {if (set.contains(s.charAt(i))) {flag = true;break;}}if (!flag) return false;flag = true;for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == s.charAt(i - 1)) {flag = false;break;}}return flag;}}
6096. 咒语和药水的成功对数
给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
请你返回一个长度为 n 的整数数组 _pairs，其中 _pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
示例 1：
输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7 输出：[4,0,3] 解释： - 第 0 个咒语：5 [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。 - 第 1 个咒语：1 [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。 - 第 2 个咒语：3 [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。 所以返回 [4,0,3] 。
示例 2：
输入：spells = [3,1,2], potions = [8,5,8], success = 16 输出：[2,0,2] 解释： - 第 0 个咒语：3 [8,5,8] = [24,15,24] 。总共 2 个成功组合。 - 第 1 个咒语：1 [8,5,8] = [8,5,8] 。总共 0 个成功组合。 - 第 2 个咒语：2 [8,5,8] = [16,10,16] 。总共 2 个成功组合。 所以返回 [2,0,2] 。
提示：
- n == spells.length
- m == potions.length
- 1 <= n, m <= 105
- 1 <= spells[i], potions[i] <= 105
- 1 <= success <= 1010
思路：
二分，考虑每个咒语有多少个药水能与之匹配
class Solution {public int[] successfulPairs(int[] s, int[] p, long success) {Arrays.sort(p);int n = s.length, m = p.length;int[] res = new int[n];for (int i = 0; i < n; i++) {long x = s[i];int l = 0, r = m - 1;if (x * p[m - 1] < success) continue;while (l < r) {int mid = l + r >> 1;if (x * p[mid] < success)l = mid + 1;elser = mid;}res[i] = m - l;}return res;}}
6097. 替换字符后匹配
给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ，其中 mappings[i] = [oldi, newi] 表示你可以替换 sub 中任意数目的 oldi 个字符，替换成 newi 。sub 中每个字符 不能 被替换超过一次。
如果使用 mappings 替换 0 个或者若干个字符，可以将 sub 变成 s 的一个子字符串，请你返回 true，否则返回 false 。
一个 子字符串 是字符串中连续非空的字符序列。
示例 1：
输入：s = “fool3e7bar”, sub = “leet”, mappings = [[“e”,”3”],[“t”,”7”],[“t”,”8”]] 输出：true 解释：将 sub 中第一个 ‘e’ 用 ‘3’ 替换，将 ‘t’ 用 ‘7’ 替换。 现在 sub = “l3e7” ，它是 s 的子字符串，所以我们返回 true 。
示例 2：
输入：s = “fooleetbar”, sub = “f00l”, mappings = [[“o”,”0”]] 输出：false 解释：字符串 “f00l” 不是 s 的子串且没有可以进行的修改。 注意我们不能用 ‘o’ 替换 ‘0’ 。
示例 3：
输入：s = “Fool33tbaR”, sub = “leetd”, mappings = [[“e”,”3”],[“t”,”7”],[“t”,”8”],[“d”,”b”],[“p”,”b”]] 输出：true 解释：将 sub 里第一个和第二个 ‘e’ 用 ‘3’ 替换，用 ‘b’ 替换 sub 里的 ‘d’ 。 得到 sub = “l33tb” ，它是 s 的子字符串，所以我们返回 true 。
提示：
- 1 <= sub.length <= s.length <= 5000
- 0 <= mappings.length <= 1000
- mappings[i].length == 2
- oldi != newi
- s 和 sub 只包含大写和小写英文字母和数字。
- oldi 和 newi 是大写、小写字母或者是个数字。
思路：
预处理 + 暴力处理s的所有长度为sub.length()的子串，如果通过变化能与sub相同，说明存在，否则不存在
class Solution {public boolean matchReplacement(String s, String sub, char[][] mappings) {boolean[][] st = new boolean[300][300];for (char[] c : mappings) {char a = c[0], b = c[1];st[a][b] = true;}int n = s.length(), m = sub.length();char[] cs = s.toCharArray(), csub = sub.toCharArray();for (int i = m - 1; i < n; i++) {int p = i - m + 1, q = 0;boolean flag = true;while (q < m) {char a = cs[p], b = csub[q];p++;q++;if (a == b) continue;if (!st[b][a]) {flag = false;break;}}if (flag) return true;}return false;}}
6098. 统计得分小于 K 的子数组数目
一个数字的 分数 定义为数组之和 乘以 数组的长度。
- 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。
子数组 是数组中的一个连续元素序列。
示例 1：
输入：nums = [2,1,4,3,5], k = 10 输出：6 解释： 有 6 个子数组的分数小于 10 ： - [2] 分数为 2 1 = 2 。 - [1] 分数为 1 1 = 1 。 - [4] 分数为 4 1 = 4 。 - [3] 分数为 3 1 = 3 。 - [5] 分数为 5 1 = 5 。 - [2,1] 分数为 (2 + 1) 2 = 6 。 注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。
示例 2：
输入：nums = [1,1,1], k = 5 输出：5 解释： 除了 [1,1,1] 以外每个子数组分数都小于 5 。 [1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。 所以总共有 5 个子数组得分小于 5 。
提示：
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 105
- 1 <= k <= 1015
思路：
满足单调性
方法1：双指针
方法2：枚举 + 二分
class Solution {public long countSubarrays(int[] nums, long k) {long res = 0;int n = nums.length;long[] s = new long[n + 1];for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + nums[i - 1];}for (int i = 1, j = 1; i <= n; i++) {while (j <= i && (s[i] - s[j - 1]) * (i - j + 1) >= k)j++;res += i - j + 1;}return res;}}class Solution {public long countSubarrays(int[] nums, long k) {long res = 0;int n = nums.length;long s = 0;for (int i = 0, j = 0; i < n; i++) {s += nums[i];while (j <= i && s * (i - j + 1) >= k)s -= nums[j++];res += i - j + 1;}return res;}}
class Solution {public long countSubarrays(int[] nums, long k) {int n = nums.length;long[] s = new long[n + 1];for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + nums[i - 1];}long res = 0;for (int i = 1; i <= n; i++) {if (s[i] - s[i - 1] >= k) continue;int l = 1, r = i;while (l < r) {int mid = l + r >> 1;if ((s[i] - s[mid - 1]) * (i - mid + 1) < k)r = mid;elsel = mid + 1;}res += i - l + 1;}return res;}}
若有收获，就点个赞吧
0 人点赞
