周赛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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(1)$

统计完全子数组的数目【LC2799】

给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

• 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

• 思路：滑动窗口

  • 对于每个$l$，找到其最左边合法的右端点$r$，以$l$为左端点的完全子数组个数为$n-r$
  • 随着左端点右移，合法右端点也右移，因此可以使用滑动窗口

• 实现

  • 求出nums中元素种类个数，并使用哈希表记录每个元素的个数$count$

  • 初始化$r$，找到左端点在0时，最左右端点位置，后续随着左端点右移，最左右端点一定在$r$的左边；移动右端点时，需要移除哈希表的元素

  • 滑动窗口，枚举$l$，如果哈希表中元素种类数目小于$count$，右移右指针至种类数目增加至$count$，然后计数

  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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(n)$

包含三个字符串的最短字符串【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
    • 否则，需要寻找最长公共前后缀（a的后缀==b的前缀），假设长度为len，那么构造字符串为$a+b[len,n2)$
    • 最长公共前后缀：暴力枚举长度，判断是否相等

• 实现

  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 aif (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;}
  }
  

  • 复杂度
    • 时间复杂度： O ( n 2 ) \mathcal{O}(n^2) O(n2)
    • 空间复杂度：$\mathcal{O}(n)$

统计范围内的步进数字数目【LC2801】

给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。

如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。

请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

**注意：**步进数字不能有前导 0 。

• 思路：数位dp

  定义 f s ( i , p r e , i s L i m i t , i s N u m ) f_s(i,pre,isLimit,isNum) fs​(i,pre,isLimit,isNum) 表示在$[1,s]$范围内，构造从左往右第 $i$ 位及其之后数位后的步进数字的个数，其余参数的含义为：

  • $i$表示当前构造至从左往右第$i$位

  • $pre$表示第$i-1$位的数值

  • $isLimit$ 表示当前是否受到了 $n$的约束。若为真，则第 $i$ 位填入的数字至多为 $s[i]$，否则可以枚举至 9。如果在受到约束的情况下填了 $s[i]$，那么后续填入的数字仍会受到 $n$的约束。

    • 取决于第$i-1$位填充是否受限，以及当前填充的数是否达到上限值

  • $isNum$ 不可以忽略，对于本题来说，当d为0时，前导零对答案有影响，isNum不可以省略

  那么 f h i g h ( 0 , − 1 , t r u e , f a l s e ) − f l o w ( 0 , − 1 , t r u e , f a l s e ) + f l a g f_{high}(0,-1,true,false)-f_{low}(0,-1,true,false) +flag fhigh​(0,−1,true,false)−flow​(0,−1,true,false)+flag 即为最终结果，如果$low$为步进数字，$flag$为1

• 实现：注意取模

  • 如果前一位不是数字，那么当前位可以不选数字也可以根据上下限选取数字
  • 否则，只能取$pre+1$或者$pre-1$，并且在$[0,9]$之内在可以取

  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;}
  }
  

  • 复杂度

    • 时间复杂度：$O(n)$$,n$为字符串的长度，时间复杂度 = 状态个数 * 单个状态的转移次数，状态个数就是 $dp$ 数组的长度，即 $O(n)$，而单个状态的转移次数前一位不是数字时为10次，否则为2次， O(10) = O(2)= O(1)，所以时间复杂度为 $O(n)$
    • 空间复杂度：$O(nC)$，即为动态规划中存储状态需要使用的空间。C=10为状态个数

• 灵神代码

  再写一个cal方法

  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++) // 枚举要填入的数字 dif (!isNum || Math.abs(d - pre) == 1) // 第一位数字随便填，其余必须相差 1res = (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）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！