方法一：遍历
1
2
3
4
5
6
7
| class Solution {
public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {
int ans = 0;
for (int x : hours) if (x >= target) ans++;
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\)。
- 空间复杂度：\(O(1)\)。
方法一：暴力优化
比赛时本来是想滑窗的，但是当时没想通。而枚举左右端点再遍历的暴力方法，时间复杂度为 \(O(n^{3})\) 会超时。结果想半天发现可以使用前缀和的思路，先枚举左端点，然后一边遍历一边枚举右端点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int countCompleteSubarrays(int[] nums) {
int n = nums.length;
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int cnt = set.size(), ans = 0;
for (int i = 0; i <= n - cnt; i++) {
set.clear();
for (int j = i; j < n; j++) {
set.add(nums[j]);
if (set.size() == cnt) {
ans += n - j;
break;
}
}
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n^{2})\)。
- 空间复杂度：\(O(n)\)。
方法二：滑动窗口
枚举右端点，并且让窗口是完全子数组的前提下，使左端点尽可能靠右，此时所有小于等于左端点的位置，都满足条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int countCompleteSubarrays(int[] nums) {
int n = nums.length;
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int cnt = set.size();
int lo = 0, hi = 0, ans = 0;
Map<Integer, Integer> map = new HashMap<>();
while (hi < n) {
map.merge(nums[hi++], 1, Integer::sum);
if (map.size() == cnt) {
while (map.get(nums[lo]) > 1) {
map.merge(nums[lo++], -1, Integer::sum);
}
ans += lo + 1;
}
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\)。
- 空间复杂度：\(O(n)\)。
方法一：枚举
枚举字符串 \(a,b,c\) 的全排列，然后从前往后合并，以消除公共字符。需要注意，如果字符串存在包含关系，则不需要进行合并操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public String minimumString(String a, String b, String c) {
List<String> list = new ArrayList<>();
list.add(merge(merge(a, b), c));
list.add(merge(merge(a, c), b));
list.add(merge(merge(b, a), c));
list.add(merge(merge(b, c), a));
list.add(merge(merge(c, a), b));
list.add(merge(merge(c, b), a));
list.sort((s1, s2) -> {
int m = s1.length(), n = s2.length();
if (m != n) return m - n;
return s1.compareTo(s2);
});
return list.get(0);
}
private String merge(String a, String b) {
if (a.contains(b)) return a;
int m = a.length(), n = b.length();
for (int i = Math.min(m, n); ; i--) {
if (a.substring(m - i).equals(b.substring(0, i))) {
return a + b.substring(i);
}
}
}
}
|
复杂度分析
- 时间复杂度：\(O(n^{2})\)，其中 \(n\) 为字符串 \(a,b,c\) 长度的最大值。
- 空间复杂度：\(O(n)\)。
方法一：数位DP
感觉有点像 DFS，枚举当前位的数字，多传递一个参数 isLimit 可以省去很多判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countSteppingNumbers(String low, String high) {
int m = low.length(), n = high.length();
int[][] dp = new int[n][10];
Arrays.fill(dp[0], 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < 10; j++) {
if (j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
if (j + 1 <= 9) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
}
}
return (f(dp, high, 0, -1, true) - f(dp, low, 0, -1, true) + valid(low) + MOD) % MOD;
}
private int f(int[][] dp, String s, int i, int pre, boolean isLimit) {
int n = s.length();
if (i == n) return pre != -1 ? 1 : 0;
if (pre != -1 && !isLimit) return dp[n - i][pre];
int cur = s.charAt(i) - '0', res = 0;
int hi = isLimit ? cur : 9;
for (int j = 0; j <= hi; j++) {
if (pre == -1 || Math.abs(j - pre) == 1) {
res = (res + f(dp, s, i + 1, (pre == -1 && j == 0) ? -1 : j, isLimit && j == hi)) % MOD;
}
}
return res;
}
private int valid(String s) {
int n = s.length();
for (int i = 1; i < n; i++) {
if (Math.abs(s.charAt(i) - s.charAt(i - 1)) != 1) {
return 0;
}
}
return 1;
}
}
|
复杂度分析
- 时间复杂度：\(O(nm^{2})\)，其中 \(n\) 为
high 的长度，\(m = 10\)。
- 空间复杂度：\(O(nm)\)。