你好旅行者!欢迎来到cyt的练功房。本篇文章来记录一下力扣的第335场周赛，好久没打周赛了菜的一一一一一，就做出了两题，知道思路但就是写不出来嘤嘤嘤。

一、递枕头

n 个人站成一排，按从 1 到 n 编号。

最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。
给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号

输入：n = 4, time = 5

输出：2

解法：

找个规律就行，有规律长度是2*n-2，先取余就行。

class Solution {
public:
    int passThePillow(int n, int time) {
        time--;
        time %= (2*n-2);

        if(time + 2<=n)return time+2;
        else return n - (time-n +2);
    }
};

二、二叉树中的第 K 大层和

给你一棵二叉树的根节点 root 和一个正整数 k 。

树中的层和是指同一层上节点值的总和。

返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。

注意，如果两个节点与根节点的距离相同，则认为它们在同一层。

解法：

标准的bfs题目，wa四次，写出了经典的忘记循环size，标准的0分

输入：root = [5,8,9,2,1,3,7,4,6], k = 2

输出：13

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        queue<TreeNode*> q;
        q.push(root);
        vector<long long> res;
        while(!q.empty()){
            int si=q.size();
            long long sum=0;
            for(int i=0;i<si;i++){
                TreeNode *top=q.front();
                q.pop();
                if(top->left!=nullptr)q.push(top->left);
                if(top->right!=nullptr)q.push(top->right);
                sum+=top->val;
            }
            res.push_back(sum);
        }
        if(res.size()<k)return -1;
        sort(res.begin(),res.end(),greater<long long>());
        return res[k-1];
        
        
    }
};

三、分割数组使乘积互质

给你一个长度为 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 的最大公约数。

输入：nums = [4,7,8,15,3,5]

输出：2

解法：

这凭什么超时，这不是铁n方，差最后一个实例死活过不了逆天。

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        int right=0;
        int left=0;
        for(int i=left+1;i<nums.size();i++){
            if(gcd(nums[left],nums[i])!=1){
                    right=max(right,i);
            }
        }
        while(right<nums.size()&&left<right){
            for(int i=right+1;i<nums.size();i++){
                if(gcd(nums[left],nums[i])!=1){
                    right=i;
                }
            }
            if(right==nums.size()-1)return -1;
            left++;
        }
    if(right==nums.size()-1)return -1;
    return right;
    }
};

四、获得分数的方法数

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [ $count_i$ , $marks_i$ ] 表示第 i 种类型的题目有 $count_i$ 道，每道题目对应 $marks_i$ 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 10^9 +7 取余。

注意，同类型题目无法区分。

比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

输入：target = 6, types = [[6,1],[3,2],[2,3]]

输出：7

解法：

完全不会，背包问题直接忘干净，我是废物。