LeetcodeWk158

写在前面

这次比较难度中等,就是最后一道题目想乱了很蓝廋

第 158 场周赛

题目

A. 分割平衡字符串

在一个「平衡字符串」中,’L’ 和 ‘R’ 字符的数量是相同的。

给出一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。

返回可以通过分割得到的平衡字符串的最大数量。

示例 1:

1
2
3
输入:s = "RLRRLLRLRL"
输出:4
解释:s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。

示例 2:

1
2
3
输入:s = "RLLLLRRRLR"
输出:3
解释:s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。

示例 3:

1
2
3
输入:s = "LLLLRRRR"
输出:1
解释:s 只能保持原样 "LLLLRRRR"

提示:

  • 1 <= s.length <= 1000
  • s[i] = 'L' 或 'R'

实际上我们需要找到有多少个前缀满足 ‘L’ 出现的次数等于’R’ 出现的次数

这样的前缀数便是答案,因为我们可以按前缀划分,这样是满足题意而且最多的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int balancedStringSplit(String s) {
int[] buk = new int[2];
int ans = 0;
for (char c : s.toCharArray()) {
if (c == 'L')
buk[0]++;
else
buk[1]++;
if (buk[1] == buk[0])
ans++;
}
return ans;
}
}

B. 可以攻击国王的皇后

在一个 8x8 的棋盘上,放置着若干「黑皇后」和一个「白国王」。

「黑皇后」在棋盘上的位置分布用整数坐标数组 queens 表示,「白国王」的坐标用数组 king 表示。

「黑皇后」的行棋规定是:横、直、斜都可以走,步数不受限制,但是,不能越子行棋。

请你返回可以直接攻击到「白国王」的所有「黑皇后」的坐标(任意顺序)。

示例 1:

img

1
2
3
4
5
6
7
8
9
输入:queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出:[[0,1],[1,0],[3,3]]
解释:
[0,1] 的皇后可以攻击到国王,因为他们在同一行上。
[1,0] 的皇后可以攻击到国王,因为他们在同一列上。
[3,3] 的皇后可以攻击到国王,因为他们在同一条对角线上。
[0,4] 的皇后无法攻击到国王,因为她被位于 [0,1] 的皇后挡住了。
[4,0] 的皇后无法攻击到国王,因为她被位于 [1,0] 的皇后挡住了。
[2,4] 的皇后无法攻击到国王,因为她和国王不在同一行/列/对角线上。

示例 2:

img

1
2
输入:queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
输出:[[2,2],[3,4],[4,4]]

示例 3:

img

1
2
输入:queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
输出:[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

提示:

  • 1 <= queens.length <= 63
  • queens[0].length == 2
  • 0 <= queens[i][j] < 8
  • king.length == 2
  • 0 <= king[0], king[1] < 8
  • 一个棋盘格上最多只能放置一枚棋子。

题意还是非常明确的,我们可以之间按皇后来从8个方向进行搜索,或我们可以反过来找,这实际上是等价的。

我们把king 当成是queen,这样我们就可以只通过king 来找一次即可,如果确定了某个方向能吃子,那么这个方向就应该停止搜索。

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
class Solution {
int[] dx = { 1, 1, 1, 0, 0, -1, -1, -1 };
int[] dy = { 0, 1, -1, 1, -1, 0, 1, -1 };
int len = 8;

public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
int mp[][] = new int[10][10];
int st[][] = new int[10][10];
int x = king[0];
int y = king[1];
for (int[] arr : queens) {
int a = arr[0];
int b = arr[1];
mp[a][b] = 1;
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
for (int j = 0; j < 8; j++) {
int nx = i * dx[j] + x;
int ny = i * dy[j] + y;
if (ny < 0 || ny >= 8 || nx < 0 || nx >= 8)
continue;

if (mp[nx][ny] == 1) {
dy[j] = 0;
dx[j] = 0;
List<Integer> cur = new ArrayList<>();
cur.add(nx);
cur.add(ny);
ans.add(cur);
}
}
}
return ans;

}
}

C. 掷骰子模拟

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i]i 从 1 开始编号)。

现在,给你一个整数数组 rollMax 和一个整数 n,请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同,就认为这两个序列是不同的。由于答案可能很大,所以请返回 10^9 + 7 之后的结果。

示例 1:

1
2
3
输入:n = 2, rollMax = [1,1,2,2,2,3]
输出:34
解释:我们掷 2 次骰子,如果没有约束的话,共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组,数字 1 和 2 最多连续出现一次,所以不会出现序列 (1,1) 和 (2,2)。因此,最终答案是 36-2 = 34。

示例 2:

1
2
输入:n = 2, rollMax = [1,1,1,1,1,1]
输出:30

示例 3:

1
2
输入:n = 3, rollMax = [1,1,1,2,2,3]
输出:181

提示:

  • 1 <= n <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15

一道很明显的递推的题目,实际上我们需要知道的是,以某个数字出现k次结尾的长度为n的序列有多少种,这样显然是不重漏的

我们考虑$f[n][t][k]$ 表示长度为n以t出现k次结束的序列的种类数

这样我们可以很容易的得到递推序列

然后我们就可以统计所有方案了

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
class Solution {
public int dieSimulator(int n, int[] rollMax) {
final long MOD = (long) (1e9 + 7);
long dp[][][] = new long[n + 1][7][20];
for (int i = 1; i <= 6; i++)
dp[1][i][1] = 1;
for (int i = 2; i <= n; i++) {
for (int t = 1; t <= 6; t++)
for (int j = 1; j <= 6; j++) {
for (int k = 1; k <= rollMax[j - 1]; k++) {
if (t == j) {
dp[i][t][k + 1] = (dp[i][t][k + 1] + dp[i - 1][j][k]) % MOD;
} else {
dp[i][t][1] = (dp[i][t][1] + dp[i - 1][j][k]) % MOD;
}
}
}
}
long ans = 0;
for (int i = 1; i <= 6; i++) {
for (int k = 1; k <= rollMax[i - 1]; k++) {
ans += dp[n][i][k];
ans %= MOD;
}
}
return (int) ans;
}
}

D. 最大相等频率

给出一个正整数数组 nums,请你帮忙从该数组中找出能满足下面要求的 最长 前缀,并返回其长度:

  • 从前缀中 删除一个 元素后,使得所剩下的每个数字的出现次数相同。

如果删除这个元素后没有剩余元素存在,仍可认为每个数字都具有相同的出现次数(也就是 0 次)。

示例 1:

1
2
3
输入:nums = [2,2,1,1,5,3,3,5]
输出:7
解释:对于长度为 7 的子数组 [2,2,1,1,5,3,3],如果我们从中删去 nums[4]=5,就可以得到 [2,2,1,1,3,3],里面每个数字都出现了两次。

示例 2:

1
2
输入:nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出:13

示例 3:

1
2
输入:nums = [1,1,1,2,2,2]
输出:5

示例 4:

1
2
输入:nums = [10,2,8,9,3,8,1,5,2,3,7,6]
输出:8

提示:

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

我们首先考虑什么时候能够满足题意

  • 如果只有一种长度的序列,而且长度为1 或只有一种序列

  • 如果有两种以上的序列,长的序列只有一种,而且删掉一个数的长度等于短的序列的长度,或长度为1的序列只有一种

实际上只有以上两种满足,因为删掉一个数,只会是一个序列的长度发生变化。

我们需要知道的是长度为t 的序列有几种 ,我们可以用hash 表来维护。

我们从后往前开始遍历,检查是否满足题意,如果不满足,我们就把最后的这个数删掉,这样就可以遍历所有的前缀。维护也很简单,因为变化是连续的(删掉一个数之后,这个数的长度会减1,换句话说,我们只需要知道当前这个数的序列的长度即可),我们通过减1加1便可维护。要注意的是,长度为0的序列应该直接被删除。

要知道某个数字出现的次数,我们可以用桶来维护。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public int maxEqualFreq(int[] nums) {
Map<Integer, Integer> M = new HashMap<>();
int n = nums.length;
int buk[] = new int[200000];
for (int i = 0; i < n; i++) {
int x = nums[i];
buk[x]++;
}
for (int i = 1; i <= 100000; i++) {
if (buk[i] == 0)
continue;
if (!M.containsKey(buk[i]))
M.put(buk[i], 1);
else
M.put(buk[i], M.get(buk[i]) + 1);
}
for (int i = n - 1; i >= 0; i--) {
if (M.size() == 1) {
for (Map.Entry<Integer, Integer> entry : M.entrySet()) {
if (entry.getValue() == 1 || entry.getKey() == 1)
return i + 1;
}
}
if (M.size() == 2) {
int k = 0;
int siz[] = new int[3];
int tim[] = new int[3];
for (Map.Entry<Integer, Integer> entry : M.entrySet()) {
siz[++k] = entry.getKey();
tim[k] = entry.getValue();
if (entry.getKey() == 1 && entry.getValue() == 1)
return i + 1;
}
if (siz[1] > siz[2]) {
if (siz[1] - siz[2] == 1 && tim[1] == 1)
return i + 1;
} else {
if (siz[2] - siz[1] == 1 && tim[2] == 1)
return i + 1;
}
}
int x = nums[i];
int t = buk[x];
buk[x]--;
if (M.get(t) == 1) {
M.remove(t);
} else {
M.put(t, M.get(t) - 1);
}
t--;
if (t == 0)
continue;
if (!M.containsKey(t))
M.put(t, 1);
else
M.put(t, M.get(t) + 1);
}
return 1;
}
}

总结

D 题因为没有写草稿,导致了很长时间的对着空气调试,就很难受