6917. Number of Employees Who Met the Target
公司里共有 n 名员工，按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。
公司要求每位员工工作 至少 target 小时。
给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。
请你用整数表示并返回工作至少 target 小时的员工数。
测试样例：
输入：hours = [5,1,4,2,2], target = 6
输出：0
解释：
公司要求每位员工工作至少 6 小时。共有 0 位满足要求的员工。
解答：就遍历一下数组，查看有多少满足要求的数。
class Solution {
public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {
int res = 0;
for (int h : hours) {
if (h >= target) {
++res;
}
}
return res;
}
}6900. Count Complete Subarrays in an Array
给你一个由 正 整数组成的数组 nums 。
如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
- 子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。
测试样例：
输入：nums = [1,3,1,2,2]
输出：4
解释：
完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。
解答：其实可以用双指针来优化一下，但是数据范围太小了，我就用暴力运算了。
class Solution {
public int countCompleteSubarrays(int[] nums) {
int res = 0;
Set<Integer> distinct = new HashSet<>();
for (int n : nums) {
distinct.add(n);
}
for (int i = 0; i < nums.length; ++i) {
Set<Integer> tmp = new HashSet<>();
for (int j = i; j < nums.length; ++j) {
tmp.add(nums[j]);
if (tmp.size() == distinct.size()) {
res += (nums.length - j);
break;
}
}
}
return res;
}
}6918. Shortest String That Contains Three Strings
给你三个字符串 a ，b 和 c ， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。
如果有多个这样的字符串，请你返回 字典序最小 的一个。
请你返回满足题目要求的字符串。
注意：
- 两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母 靠前 ，那么字符串 a 比字符串 b 字典序小 。
- 子字符串 是一个字符串中一段连续的字符序列。
测试样例
输入：a = "abc", b = "bca", c = "aaa"
输出："aaabca"
解释：
字符串 "aaabca" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且"aaabca" 是字典序最小的一个。
解答：一共只有三个字符串，而且长度都小于100。可以利用枚举三个字符串的不同拼接顺序，并计算最优字符串。
class Solution {
public String minimumString(String a, String b, String c) {
String[] arr = {a, b, c};
String[] res = {null};
dfs(arr, new boolean[3], 0, "", res);
return res[0];
}
private void dfs(String[] arr, boolean[] isUsed, int offset, String path, String[] res) {
if (offset == 3) {
if (res[0] == null || res[0].length() > path.length()
|| (res[0].length() == path.length() && res[0].compareTo(path) > 0)) {
res[0] = path;
}
} else {
for (int i = 0; i < 3; ++i) {
if (!isUsed[i]) {
isUsed[i] = true;
dfs(arr, isUsed, offset + 1, buildNextPath(arr[i], path), res);
isUsed[i] = false;
}
}
}
}
private String buildNextPath(String cur, String path) {
if (path.contains(cur)) {
return path;
}
int st = path.length() - Math.min(cur.length(), path.length());
for (int i = st; i < path.length(); ++i) {
if (isMatch(cur, path, i)) {
return path.substring(0, i) + cur;
}
}
return path + cur;
}
private boolean isMatch(String cur, String path, int st) {
for (int i = st; i < path.length(); ++i) {
if (path.charAt(i) != cur.charAt(i - st)) {
return false;
}
}
return true;
}
}6957. Count Stepping Numbers in Range
给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。
如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。
由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。
注意：步进数字不能有前导 0 。
测试样例
输入：low = "1", high = "11"
输出：10
解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。
解答：这题其实能算是套路题了。就是需要仔细看一下转移的不同情况。
class Solution {
private static final int mod = 1_000_000_007;
public int countSteppingNumbers(String low, String high) {
int len = high.length();
int[][] dp = buildMaxDp(len);
return add(minus(getSingleNum(high, dp), getSingleNum(low, dp)), isCurValid(high) ? 1 : 0);
}
private int[][] buildMaxDp(int len) {
int[][] dp = new int[len][10];
for (int i = 0; i < len; ++i) {
for (int n = 0; n < 10; ++n) {
if (i == 0) {
dp[i][n] = 1;
} else {
if (n - 1 >= 0) {
dp[i][n] = add(dp[i][n], dp[i - 1][n - 1]);
}
if (n + 1 <= 9) {
dp[i][n] = add(dp[i][n], dp[i - 1][n + 1]);
}
}
}
}
return dp;
}
private int getSingleNum(String str, int[][] dp) {
int res = 0;
for (int i = 0; i < str.length() - 1; ++i) {
res = add(res, getPosSum(dp, i));
}
int remain = str.length() - 1, last = -1;
for (int i = 0; i < str.length(); ++i) {
int num = str.charAt(i) - '0';
if (i == 0) {
for (int j = 1; j < num; ++j) {
res = add(res, dp[remain][j]);
}
--remain;
last = num;
} else {
if (last + 1 <= 9) {
if (last - 1 >= 0 && last - 1 < num) {
res = add(res, dp[remain][last - 1]);
} else if (last - 1 >= 0 && last - 1 == num) {
last = num;
--remain;
continue;
} else if (last - 1 >= 0 && last - 1 > num) {
break;
}
if (last + 1 < num) {
res = add(res, dp[remain][last + 1]);
break;
} else if (last + 1 == num) {
last = num;
--remain;
} else {
break;
}
} else {
if (last - 1 < num) {
res = add(res, dp[remain][last - 1]);
break;
} else if (last - 1 == num) {
last = num;
--remain;
} else if (last - 1 > num) {
break;
}
}
}
}
return res;
}
private int getPosSum(int[][] dp, int n) {
int res = 0;
for (int i = 1; i <= 9; ++i) {
res = add(res, dp[n][i]);
}
return res;
}
private int add(int x, int y) {
return (x + y) % mod;
}
private int minus(int x, int y) {
return (x + mod - y) % mod;
}
private boolean isCurValid(String str) {
for (int i = 1; i < str.length(); ++i) {
if (Math.abs(str.charAt(i) - str.charAt(i - 1)) != 1) {
return false;
}
}
return true;
}
}第四题真的得认真再认真，WA麻了