周赛356
T2T3少写条件各WA一次，T4忘记取余WA一次，时间不够没有通过，可惜
满足目标工作时长的员工数目【LC2798】
公司里共有 n 名员工，按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。
公司要求每位员工工作 至少target 小时。
给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。
请你用整数表示并返回工作至少
target小时的员工数。
- 实现：模拟+计数
class Solution { public int numberOfEmployeesWhoMetTarget(int[] hours, int target) { int res = 0; for (int h : hours){ if (h >= target){ res++; } } return res; } }
统计完全子数组的数目【LC2799】
给你一个由 正 整数组成的数组
nums。如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
- 子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。
- 思路：滑动窗口
class Solution { public int countCompleteSubarrays(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums){ map.put(num, map.getOrDefault(num, 0) + 1); } int count = map.size(); int res = 0, n = nums.length; // 对于每个l，找到其最左边合法的r，以l为左端点的完全子数组个数为n - r // 对于nums[0, r]，r右边的一定合法 int r = n - 1; while (r > 0 && map.get(nums[r]) > 1){ map.put(nums[r], map.get(nums[r]) - 1); r--; } for (int l = 0; l < n; l++){ while (r + 1 < n && map.size() < count){ r++; map.put(nums[r], map.getOrDefault(nums[r], 0) + 1); } if (map.size() == count){ res += n - r; } // 移除nums[l] map.put(nums[l], map.get(nums[l]) - 1); if (map.get(nums[l]) == 0){ map.remove(nums[l]); } } return res; } }
包含三个字符串的最短字符串【LC2800】
给你三个字符串
a，b和c， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。如果有多个这样的字符串，请你返回 字典序最小 的一个。
请你返回满足题目要求的字符串。
注意：
- 两个长度相同的字符串
a和b，如果在第一个不相同的字符处，a的字母在字母表中比b的字母 靠前 ，那么字符串a比字符串b字典序小 。 - 子字符串 是一个字符串中一段连续的字符序列。
思路
- 先考虑包含两个字符串的最短字符串，此时有两种可能结果，在a的末尾添加最少字符使其包含b的字符串或者在b的末尾添加最少字符使其包含a的字符串；
扩展至包含两个字符串的最短字符串时，有6种情况，取长度 最短 的字符串返回，长度相同时，取字典序最小的字符串
- abc：先找到在a的末尾添加最少字符使其包含b的最短字符串，再在得到的字符串末尾添加最少字符使其包含c
- acb
- bac
- bca
- cab
- cba
- 如何找到在a的末尾添加最少字符使其包含b的字符串
- 如果a包含b那么即为a
class Solution { public String minimumString(String a, String b, String c) { String res = null; StringBuilder sb = new StringBuilder(); // 6种情况 String s1 = minimumString(minimumString(a, b), c); String s2 = minimumString(minimumString(a, c), b); String s3 = minimumString(minimumString(b, a), c); String s4 = minimumString(minimumString(b, c), a); String s5 = minimumString(minimumString(c, a), b); String s6 = minimumString(minimumString(c, b), a); return compare(compare(compare(s1, s2), compare(s3, s4)), compare(s5, s6)); } public String minimumString(String a, String b){ // a中包含b，return a if (a.indexOf(b) != -1){ return a; } // 否则找到最长公共前后缀：a后缀 b前缀 int n1 = a.length(), n2 = b.length(); int maxIndex = 0, maxLen = 0; for (int i = 0; i < n1; i++){ if (n1 - i > n2) continue; if (a.substring(i, n1).equals(b.substring(0, n1 - i))){ maxLen = n1 - i; break; } } return a + b.substring(maxLen, n2); } public String compare(String s1, String s2){ if (s1.length() == s2.length()){ if (s1.compareTo(s2) <= 0){ return s1; }else{ return s2; } }else if (s1.length() < s2.length()){ return s1; } return s2; } }
统计范围内的步进数字数目【LC2801】
给你两个正整数
low和high，都用字符串表示，请你统计闭区间[low, high]内的 步进数字 数目。
如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。
由于答案可能很大，请你将它对 109 + 7取余 后返回。
**注意：**步进数字不能有前导 0 。
class Solution { public static final int MOD = (int)(1e9 + 7); public int countSteppingNumbers(String low, String high) { int[][] dp1 = new int[low.length()][10]; int[][] dp2 = new int[high.length()][10]; int flag = 1; for (int i = 0; i < low.length() - 1; i++){ if (Math.abs(low.charAt(i) - low.charAt(i + 1)) != 1){ flag = 0; break; } } for (int i = 0; i < low.length(); i++){ Arrays.fill(dp1[i], -1); } for (int i = 0; i < high.length(); i++){ Arrays.fill(dp2[i], -1); } return (f(high, dp2, 0, -1, false, true) - f(low, dp1, 0, -1, false, true) + flag + MOD) % MOD; } // 小于等于s的数目 public int f(String s, int[][] dp, int i, int pre, boolean isNum, boolean isLimit){ if (i == s.length()) return 1; if (isNum && !isLimit && dp[i][pre] >= 0) return dp[i][pre]; int res = 0; int up = isLimit ? s.charAt(i) - '0' : 9; int down = isNum ? 0 : 1; if (!isNum){ res = (res + f(s, dp, i + 1, -1, false, false)) % MOD; for (int d = down; d <= up; d++){ res = (res + f(s,dp, i + 1, d, true, isLimit && d == s.charAt(i) - '0')) % MOD; } }else{ if (pre - 1 >= down && pre - 1 <= up){ res = (res + f(s,dp, i + 1, pre - 1, true, isLimit && pre - 1 == s.charAt(i) - '0')) % MOD; } if (pre + 1 >= down && pre + 1 <= up){ res = (res + f(s,dp, i + 1, pre + 1, true, isLimit && pre + 1 == s.charAt(i) - '0')) % MOD; } } if (isNum && !isLimit){ dp[i][pre] = res; } return res; } }
class Solution { private static final int MOD = (int) 1e9 + 7; public int countSteppingNumbers(String low, String high) { return (calc(high) - calc(low) + MOD + (valid(low) ? 1 : 0)) % MOD; // +MOD 防止算出负数 } private char s[]; private int memo[][]; private int calc(String s) { this.s = s.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, 0, true, false); } private int f(int i, int pre, boolean isLimit, boolean isNum) { if (i == s.length) return isNum ? 1 : 0; // isNum 为 true 表示得到了一个合法数字 if (!isLimit && isNum && memo[i][pre] != -1) return memo[i][pre]; int res = 0; if (!isNum) // 可以跳过当前数位 res = f(i + 1, pre, false, false); int up = isLimit ? s[i] - '0' : 9; // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦） for (int d = isNum ? 0 : 1; d <= up; d++) // 枚举要填入的数字 d if (!isNum || Math.abs(d - pre) == 1) // 第一位数字随便填，其余必须相差 1 res = (res + f(i + 1, d, isLimit && d == up, true)) % MOD; if (!isLimit && isNum) memo[i][pre] = res; return res; } private boolean valid(String s) { for (int i = 1; i < s.length(); i++) if (Math.abs((int) s.charAt(i) - (int) s.charAt(i - 1)) != 1) return false; return true; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/count-stepping-numbers-in-range/solutions/2364624/shu-wei-dp-tong-yong-mo-ban-by-endlessch-h8fj/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
