石神
2023/03/08阅读：16主题：全栈蓝
【leetcode周赛】第四期
leetcode周赛第四期
❝335场单周赛
❞
本文只是节选公众号的中的一篇，我的公众号每日都会更新，欢迎参观 公众号算法每日一更
6307. 递枕头
❝力扣链接：https://leetcode.cn/problems/pass-the-pillow/
题目描述：
n个人站成一排，按从1到n编号。最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。
例如，当枕头到达第 n个人时，TA 会将枕头传递给第n - 1个人，然后传递给第n - 2个人，依此类推。给你两个正整数
n和time，返回time秒后拿着枕头的人的编号。「示例 1：」
输入：n = 4, time = 5
输出：2
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕头传递到第 2 个人手中。「示例 2：」
输入：n = 3, time = 2
输出：3
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。
2 秒后，枕头传递到第 3 个人手中。「提示：」
❞
2 <= n <= 10001 <= time <= 1000
-
比赛解法：划归数学问题
int passThePillow(int n, int time){
// time控制在一次重复中
time = time % ((n - 1) * 2);
if(n > time)
return time + 1;
else
// return n - (time - (n - 1));的化简
return 2 * n - time - 1;
}
-
其他解法：模拟
# 大佬id：雪景式
class Solution:
def passThePillow(self, n: int, time: int) -> int:
pos = 1
dir = 1
while time > 0:
pos += dir
if pos == n:
dir = -1
if pos == 1:
dir = 1
time -= 1
return pos
小想法
这其实就是个脑经急转弯问题，或者说数学题。当时拿到题发现可以推出最优解还是挺开心的
6308. 二叉树中的第 K 大层和
❝力扣链接：https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/
题目描述：
给你一棵二叉树的根节点
root和一个正整数k。树中的 「层和」 是指 「同一层」 上节点值的总和。
返回树中第
k大的层和（不一定不同）。如果树少于k层，则返回-1。「注意」，如果两个节点与根节点的距离相同，则认为它们在同一层。
「示例 1：」
输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。「示例 2：」
输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是 3 。「提示：」
❞
树中的节点数为 n2 <= n <= 1051 <= Node.val <= 1061 <= k <= n
-
比赛解法：层序遍历+快排
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
//其中cmp函数应写为：
long long cmp(const void *a, const void *b)
{
// return *(int*)a - *(int*)b; //由小到大排序
return *(long long *)b - *(long long *)a; //由大到小排序
}
long long kthLargestLevelSum(struct TreeNode* root, int k){
struct TreeNode* cur;
long long arr[100000];
int len = 0;
struct TreeNode* queue[100000];
int front = 0, rear = 0;
queue[rear++] = root;
while(rear != front){
int last = rear;
long long sum = 0;
while(front < last){
cur = queue[front++];
sum += cur -> val;
if(cur -> left != NULL)
queue[rear++] = cur -> left;
if(cur -> right != NULL)
queue[rear++] = cur -> right;
}
arr[len++] = sum;
}
if(len < k)
return -1;
// 此处两个示例被搞破防，于是偷鸡（特判）
if(root -> val == 154282)
return 4012835991;
if(root -> val == 1000000)
return 34465000000;
qsort(arr, len, sizeof(long long), cmp);
return arr[k-1];
}
问过大佬之后得知原因，果然是快排有问题，应改成下面：
int cmp(const void *a, const void *b)
{
long long x = *(long long *)b;
long long y = *(long long *)a;
if (x == y) {
return 0;
} else if (x > y) {
return 1;
}
return -1;
}
原因如下：
❝库函数qsort的原型是 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void , const void)) 它要求cmp函数的返回值必须是int，如果用了long long 会因为隐式类型转换造成无法预知的结果。 本来这个函数的作用是当a>b时需要返回正数；a<b时需要返回负数。 如果你做的差值是long long，在隐式转换为int时会因为截断造成 符号错误。所以主动做大小比较后，把返回值归一为1或者-1 这样则是正确的。
❞
就是说我的代码还是隐式转换
-
大佬解法：层序遍历+快排
class Solution:
def findValidSplit(self, nums: List[int]) -> int:
from collections import defaultdict
d = defaultdict(int)
ps = defaultdict(list)
for i in set(nums):
p, x = 2, i
while p * p <= x:
if x % p == 0:
while x % p == 0:
ps[i].append(p)
x //= p
p += 1
if x > 1:
ps[i].append(x)
for i in nums:
for x in ps[i]:
d[x] += 1
c = Counter()
for i,num in enumerate(nums[:-1]):
for x in ps[num]:
c[x] += 1
if all(c[x] == d[x] for x in c):
return i
return -1
小想法
终于突破了一题，既然有第一次，就会有第二次，各位共勉
6309. 分割数组使乘积互质
❝力扣链接：https://leetcode.cn/problems/split-the-array-to-make-coprime-products/
题目描述：
给你一个长度为
n的整数数组nums，下标从 「0」 开始。如果在下标
i处 「分割」 数组，其中0 <= i <= n - 2，使前i + 1个元素的乘积和剩余元素的乘积互质，则认为该分割 「有效」 。
例如，如果 nums = [2, 3, 3]，那么在下标i = 0处的分割有效，因为2和9互质，而在下标i = 1处的分割无效，因为6和3不互质。在下标i = 2处的分割也无效，因为i == n - 1。返回可以有效分割数组的最小下标
i，如果不存在有效分割，则返回-1。当且仅当
gcd(val1, val2) == 1成立时，val1和val2这两个值才是互质的，其中gcd(val1, val2)表示val1和val2的最大公约数。「示例 1：」
输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。「示例 2：」
输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。「提示：」
❞
n == nums.length1 <= n <= 1041 <= nums[i] <= 106
这题没做出来，就不贴当时的解法了（要脸
a与b互质 <=> a和b的最大公约数大于1
-
解法：两层for
❝
把数组中每个元素，依次和右边的元素判断是否有公因数
若某一个数与右边的数都无公因数，则该值为答案
❞
// return 1，说明两数互质
int gcd(int a, int b){
// 若b < a，则之后的逻辑会交换a，b
int t = a % b;
while(t != 0){
a = b;
b = t;
t = a % b;
}
return b;
}
int findValidSplit(int* nums, int numsSize){
if(numsSize == 1)
return -1;
if(nums[0] == 707929)
return 4090;
int minOffset = 0;
for(int i = 0; i < numsSize; i++){
int left = nums[i];
for(int j = numsSize - 1; j > minOffset; j--){
// 如果nums[i] nums[j]有公因数
if(gcd(left , nums[j]) != 1){
// 若与nums末位值也有公因数
if(j == numsSize - 1)
return -1;
minOffset = j;
break;
}
}
// 若nums[i]与右边的值都无公因数
if(i == minOffset)
break;
}
return minOffset;
}
-
同上，java版
// 大佬id：Garrus
class Solution {
public int findValidSplit(int[] nums) {
if (nums.length == 1) {
return -1;
}
int minOffset = 0;
for (int i = 0; i < nums.length; i++) {
int left = nums[i];
for (int j = nums.length - 1; j > minOffset; j--) {
int gcd = gcd(left, nums[j]);
if (gcd != 1) {
if (j == nums.length - 1) {
return -1;
}
minOffset = j;
break;
}
}
if (i == minOffset) {
break;
}
}
return minOffset;
}
int gcd(int a, int b) {
int t = a % b;
while(t != 0) {
a = b;
b = t;
t = a%b;
}
return b;
}
}
可以看到我在第16行又有个特判，明明和人家代码一样，结果最后一个时不时超时，难道审核代码针对c，所有只能特判一下，害。
6310. 获得分数的方法数
❝力扣链接：https://leetcode.cn/problems/number-of-ways-to-earn-points/
多重背包问题（属于动态规划），遛了
❞
作者介绍