Q1：6917. 满足目标工作时长的员工数目（简单枚举模拟题）

https://leetcode.cn/problems/number-of-employees-who-met-the-target/
在这里插入图片描述

按题意枚举遍历一遍即可。

class Solution {public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {int ans = 0;for (int h: hours) {if (h >= target) ans++;}return ans;}
}

Q2：6900. 统计完全子数组的数目（双指针+滑动窗口）

https://leetcode.cn/problems/count-complete-subarrays-in-an-array/description/

在这里插入图片描述

数据范围比较小只有1000，使用 $O(n^2)$ 的方法估计也能过，但是这里我使用了 $O (n)$ 的双指针 + 滑动窗口。

使用双指针计算子数组数量的题目需要满足的性质，是以下两者之一：

当一个数组满足条件的情况下，增加一个元素必然仍满足条件。
当一个数组满足条件的情况下，去掉一个元素必然仍满足条件。

这里显然满足第一个性质。

枚举的是右端点，不断尝试将左端点向右移动。（在枚举的过程中，维护子数组中各个数字出现的频次，以及出现的不重复数字的个数，这里我是用哈希表来维护——哈希表的大小就是此时不重复数字的个数）。
对于每个右端点，当前左指针向左的所有位置都可以作为左端点，所以 ans += l + 1。

class Solution {public int countCompleteSubarrays(int[] nums) {// s.size()是整个数组种不同元素的数目Set<Integer> s = new HashSet<>();for (int num: nums) s.add(num);int n = nums.length, sum = s.size(), ans = 0;Map<Integer, Integer> m = new HashMap<>();      // 使用哈希表存储子数组中各个元素的数量for (int r = 0, l = 0; r < n; ++r) {m.merge(nums[r], 1, Integer::sum);while (m.get(nums[l]) > 1) {m.merge(nums[l], -1, Integer::sum);l++;}if (m.size() == sum) ans += l + 1;}return ans;}
}

Q3：6918. 包含三个字符串的最短字符串

https://leetcode.cn/problems/shortest-string-that-contains-three-strings/description/
在这里插入图片描述

这题感觉是挺怪的，但是数据范围比较小，字符串的长度只有 100 ，而且只有 3 个字符串。

只有 3 个字符串意味着只有 6 种拼接可能，分别是 abc，acb，bac，bca，cab，cba。（拼接的原则是找到最长的公共前后缀）
将这 6 个字符串放入列表中，按照长度 + 字典序排序即可。

class Solution {public String minimumString(String a, String b, String c) {List<String> ls = new ArrayList<>();// 6种拼接顺序的可能ls.add(op(a, b, c));ls.add(op(a, c, b));ls.add(op(b, a, c));ls.add(op(b, c, a));ls.add(op(c, a, b));ls.add(op(c, b, a));// 按照长度和字典序排序Collections.sort(ls, (x, y) -> {int l1 = x.length(), l2 = y.length();return l1 != l2? l1 - l2: x.compareTo(y);});                   return ls.get(0);}// 按顺序拼接3个字符串public String op(String a, String b, String c) {String ans = op2(op2(a, b), c);return ans;}// 按顺序拼接2个字符串public String op2(String a, String b) {// 不断尝试尽可能少的使用字符串b中的字符for (int i = 0; i <= b.length(); ++i) {String t = a + b.substring(b.length() - i, b.length());// 如果拼接后包括b，说明找到了既包括a又包括b的字符串，直接返回if (t.indexOf(b) != -1) return t;   }// 程序不会走到这，因为上面枚举到最后时t = a+b 一定既包括a又包括b。return "";  }
}

对于代码块：

for (int i = 0; i <= b.length(); ++i) {String t = a + b.substring(b.length() - i, b.length());// 如果拼接后包括b，说明找到了既包括a又包括b的字符串，直接返回if (t.indexOf(b) != -1) return t;   
}

如果不理解的话可以看个例子——拼接 "aaa" 和 "abc"

"aaa" 在前，"abc" 在后。所以就是不断尝试 “aaa”,“aaac”,“aaabc” 中是否包括字符串 "abc"。（也就是不断尝试将字符串 "abc" 末尾的字符添加在字符串 "aaa" 之后）（因为我们是从少到多添加的，所以找到就返回，那么返回的一定是这种排列下最短的那个）

Q4：6957. 统计范围内的步进数字数目（数位DP）

在这里插入图片描述

经典的数位DP题目，相关的链接可见：
【算法】数位DP
【算法基础：动态规划】5.4 数位统计DP（计数问题）（数位DP）

数位DP 这种题目建议记下模板，对于不同的题目按照题目修改模板就好了。

dp数组的定义：memo[1][3] 表示 i = 0 填 3，从 i = 1 往后随便填的方案数。

class Solution {char[] s;int[][] memo;final int mod = (int)1e9 + 7;public int countSteppingNumbers(String low, String high) {int ans = op(high) - op(low);if (check(low)) ans++;		// 因为low可能是个很大的数字，不方便-1，所以单独判断return (ans + mod) % mod;   // +mod防止计算出负数}public int op(String n) {s = n.toCharArray();int m = s.length;memo = new int[m][10];for (int i = 0; i < m; ++i) Arrays.fill(memo[i], -1);   // -1表示没有被计算过return f(0, true, false, -1);}public int f(int i, boolean isLimit, boolean isNum, int last) {if (i == s.length) return isNum? 1: 0;if (!isLimit && isNum && memo[i][last] != -1) return memo[i][last];int res = 0;if (!isNum) res = f(i + 1, false, false, -1) % mod;int up = isLimit? s[i] - '0': 9;for (int d = isNum? 0: 1; d <= up; ++d) {if (Math.abs(d - last) == 1 || last == -1) {res = (res + f(i + 1, isLimit && d == up, true, d)) % mod;}}if (!isLimit && isNum) memo[i][last] = res;return res;}// 检查数字s 是否为 步进数public boolean check(String s) {for (int i = 1; i < s.length(); ++i) {if (Math.abs(s.charAt(i) - s.charAt(i - 1)) != 1) return false;}return true;}
}

做题的过程中一直卡样例

在这里插入图片描述
原因是 return (ans + mod) % mod; 写成了 return ans % mod;
具体来说，memo 数组里都是取模之后的数字，所以 op(high) 是可能比 op(low) 小的。

补充：相似题目——P2657 [SCOI2009] windy 数

https://www.luogu.com.cn/problem/P2657

在这里插入图片描述

跟这次周赛的题目几乎一模一样。

import java.util.*;public class Main {static long[][] memo;static char[] s;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int a = scanner.nextInt(), b = scanner.nextInt();System.out.println(op(b) - op(a - 1));}static long op(int a) {s = Integer.toString(a).toCharArray();int m = s.length;memo = new long[m][10];for (int i = 0; i < m; ++i) Arrays.fill(memo[i], -1);return f(0, true, false, -1);}static long f(int i, boolean isLimit, boolean isNum, int pre) {if (i == s.length) return isNum? 1: 0;if (!isLimit && isNum && memo[i][pre] != -1) return memo[i][pre];long res = 0;if (!isNum) res = f(i + 1, false, false, -1);int up = isLimit? s[i] - '0': 9;for (int d = isNum? 0: 1; d <= up; ++d) {if (pre == -1 || Math.abs(d - pre) >= 2) {res += f(i + 1, isLimit && d == up, true, d);}}if (!isLimit && isNum) memo[i][pre] = res;return res;}
}