第335场周赛
题目一：递枕头
递枕头
标签
数学、模拟
思路
以n为4为例，
1
2
3
| step: 1 2 3 4 5 6
n： 2 3 4 3 2 1
每组数以 2 * (n - 1) 进行循环
|
然后使用time对2 * (n - 1)进行取余运算结果为y：
- 若结果y大于
n - 1：则对应的值应为n - (y - (n - 1))
- 若结果y小于
n - 1：则对应的值应为n - ((n - 1) - y)
- 最后合并一下即为：
n - Math.max(y - (n - 1))
题解
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int passThePillow(int n, int time) {
int res = 1;
int x = n x- 1;
int s = time / x;
int y = time % x;
if(s % 2 != 0) res = n - y;
else res = 1 + y;
return res;
}
}
|
1
2
3
4
5
6
7
| class Solution {
public int passThePillow(int n, int time) {
int x = 2 * (n - 1);
int y = time % x;
return n - Math.abs(y - (n - 1));
}
}
|
题目二：二叉树中的第 K 大层和
二叉树中的第 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
class Solution {
public long kthLargestLevelSum(TreeNode root, int k) {
long[] arr = new long[100010];
int npc = 0;
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
int count = 1;
long value = 0;
int sum = 0;
while(!que.isEmpty()) {
TreeNode top = que.remove();
value += top.val;
count --;
if(top.left != null) {
que.add(top.left);
sum ++;
}
if(top.right != null) {
que.add(top.right);
sum ++;
}
if(count == 0) {
arr[npc ++] = value;
count = sum;
sum = 0;
value = 0;
}
}
System.out.println(npc);
Arrays.sort(arr, 0, npc);
if(k > npc) return -1;
return arr[npc - k];
}
}
|
题目三：分割数组使乘积互质❗
分割数组使乘积互质
标签
质数
思路
题解
题目四：获得分数的方法数
获得分数的方法数
标签
动态规划、DP、多重背包问题
思路
状态表示：dp[i][j]表示前i个作业中恰好是j分的方法数。
状态方程：
- 不是使用第i个作业，则：
dp[i][j] = dp[i - 1][j]
- 使用第i个作业，需要遍历使用的次数 k，则有
dp[i][j] += dp[i - 1][j - k * type[i - 1][1]]。
注意：
- 前i个作业对应的最后一个作业的下标为
i - 1。
- 在遍历当前作业使用次数时，需要限制
k <= type[i - 1][0] && k * type[i - 1][1] <= j
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int waysToReachTarget(int target, int[][] types) {
int[][] dp = new int[55][1010];
int n = types.length;
for(int i = 0; i <= n; i ++) dp[i][0] = 1;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= target; j ++) {
int num = types[i - 1][0];
int score = types[i - 1][1];
for(int k = 0; k <= num && k * score <= j; k ++) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k * types[i - 1][1]]) % 1000000007;
}
}
}
return dp[n][target];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
const int MOD = 1000000007;
int waysToReachTarget(int target, vector<vector<int>>& types) {
int dp[55][1010]{0};
int n = types.size();
for(int i = 0; i <= n; i ++) dp[i][0] = 1;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= target; j ++) {
int count = types[i - 1][0];
int mark = types[i - 1][1];
for(int k = 0; k <= count && k * mark <= j; k ++) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k * mark]) % MOD;
}
}
}
return dp[n][target];
}
};
|
第336场周赛
题目一：统计范围内的元音字符串数
统计范围内的元音字符串数
标签
字符串
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int vowelStrings(String[] words, int left, int right) {
String str = "aeiou";
int res = 0;
for(int i = left; i <= right; i++) {
String s = words[i];
char front = s.charAt(0);
char tail = s.charAt(s.length() - 1);
if(str.contains(front + "") && str.contains(tail + "")) res ++;
}
return res;
}
}
|
题目二：重排数组以得到最大前缀分数
重排数组以得到最大前缀分数
标签
数组、前缀和
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxScore(int[] nums) {
Arrays.sort(nums);
for(int l = 0, r = nums.length - 1; l < r; l ++, r --) {
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
long sum = 0;
int res = 0;
for(int i = 0; i < nums.length; i ++) {
sum += nums[i];
if(sum > 0) res ++;
else break;
}
return res;
}
}
|
题目三：统计美丽子数组数目
统计美丽子数组数目
标签
数组、前缀和、哈希表
思路
求数组的前缀异或，当出现某个位置的前缀异或值在前面存在过，则是一次美丽子数组。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public long beautifulSubarrays(int[] nums) {
long res = 0;
int n = nums.length;
int[] sum = new int[n + 1];
sum[0] = 0;
for(int i = 0; i < n; i ++ ){
sum[i + 1] = sum[i] ^ nums[i];
}
Map<Integer, Integer> hsp = new HashMap<>();
for(int i = 0; i < n + 1; i ++) {
if(!hsp.containsKey(sum[i])) hsp.put(sum[i], 1);
else {
res += hsp.get(sum[i]);
hsp.put(sum[i], hsp.get(sum[i]) + 1);
}
}
return res;
}
}
|
题目四：完成所有任务的最少时间💡
完成所有任务的最少时间
标签
数组、排序、贪心
思路
核心思路是贪心。首先需要将所有的tasks[i]按照有边界从小到大进行排序，然后每次选取时刻的时候都从当前边界的右侧开始选取。
题解
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
| class Solution {
private boolean[] st;
public int findMinimumTime(int[][] tasks) {
st = new boolean[2010];
Arrays.sort(tasks, (a, b) -> {
if(a[1] == b[1]) return a[0] - b[0];
return a[1] - b[1];
});
for(int i = 0; i < tasks.length; i ++) {
int cnt = tasks[i][2] - (count(tasks[i][0], tasks[i][1]));
int end = tasks[i][1];
while(cnt > 0) {
while(st[end]) {
end --;
}
st[end] = true;
cnt --;
}
}
return count(0, 2009);
}
public int count(int start, int end) {
int res = 0;
for(int i = start; i <= end; i ++) {
if(st[i]) res ++;
}
return res;
}
}
|
第337场周赛
题目一：奇偶位数
奇偶位数
标签
位运算、数组
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] evenOddBit(int n) {
int[] res = new int[2];
int npc = 0;
int even = 0, odd = 0;
while(n != 0) {
int x = n & 1;
if(x == 1 && npc % 2 == 0) even ++;
else if(x == 1 && npc % 2 != 0) odd ++;
n = n >> 1;
npc ++;
}
res[0] = even;
res[1] = odd;
return res;
}
}
|
题目二：检查骑士巡视方案
检查骑士巡视方案
标签
广度优先搜索、数组、矩阵
题解
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
| class Solution {
public boolean checkValidGrid(int[][] grid) {
int x = 0, y = 0;
int n = grid.length;
boolean[][] st = new boolean[n][n];
st[0][0] = true;
int npc = 0;
int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1}, dy = {-2, -1, 1, 2, 2, 1, -1, -2};
while(npc < n * n - 1) {
boolean flag = false;
for(int i = 0; i < 8; i ++) {
int r = x + dx[i], c = y + dy[i];
if(r < 0 || r >= n || c < 0 || c >= n || st[r][c]) continue;
if(grid[r][c] == npc + 1){
x = r;
y = c;
flag = true;
break;
}
}
if(flag == true) {
npc ++;
} else {
return false;
}
}
return true;
}
}
|
题目三：美丽子集的数目❗
美丽子集的数目
标签
数组
题解
题目四：执行操作后的最大 MEX❗
执行操作后的最大 MEX
标签
数组
题解