2023‐03‐05 第 335 场周赛

• 这次周赛其实挺简单的 我感觉能做但是实际效果却不是很理想

递枕头

• 第一题没有一次 A 掉
• 失误了 本来想整波花活 结果整出事了
• 罚时一次

class Solution {
public:
    int passThePillow(int n, int time) {
        /*int idx_1 = time / n;
        
        int idx_2 = time % n;
        
        int res = 0;
        
        if (idx_1 % 2 == 0) {
            res = 1 + idx_2;
        } else {
            res = n - idx_2 - 1;
        }
        
        return res;*/
        
        int res = 1, f = false;
        
        while (time) {
            if (res == n) f = true;
            
            if (res == 1) f = false;
            
            if (f) res --, time --;
            
            else res ++, time --;
         }
        
        return res;
    }
};

二叉树中的第K大层数和

• 第二题花费了太多的时间
• 题型是见过的
• 陷入了怎么判断树的节点具体是哪一层的瓶颈
• 最后也没有 A 掉...

/**
 * 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) {
        vector<long> st(1e5 + 10, 0);
        
        int res = 0, idx = 0;
    
        queue<TreeNode*> qu;
        
        qu.push(root);
        
        idx = 0;
        
        st[idx] = (qu.front() -> val), idx ++;
        
        while (!qu.empty()) {
            
            if (qu.front() -> left != nullptr) qu.push(qu.front() -> left), st[idx] = (qu.front() -> left -> val), idx ++;
            
            else idx ++;
            
            
            if (qu.front() -> right != nullptr) qu.push(qu.front() -> right), st[idx] = (qu.front() -> right ->val), idx ++;
            else idx ++;
            
            
            qu.pop();
            
        }
        
        //for (int i = 0; i < 6; i ++) cout << st[i] << endl;
        
        vector<long> ans;
        
        ans.push_back(st[0]);
        
        int l = 0 * 2 + 1, r = 0 * 2 + 2;
        
        res = st[0];
        
        while (res != 0) {
            res = 0;
            
            int tem_l = l, tem_r = r;
            
            while (l <= r) {
                res += st[l];
                
                l ++;
            }
            
            ans.push_back(res);
            
            l = tem_l * 2 + 1;
            r = tem_r * 2 + 2;
        }
        
        
        sort(ans.begin(), ans.end());
        
        int c = ans.size() - 1;
        
        while (k --) {
            res = ans[c];
            
            c --;
        }
        
        return res;
    }
};

正确思路

• 使用 BFS 来解决这样的问题
• 双数组
• 这样的题应该是第二次遇到了 下次不会再出错了

/**
 * 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) {
        vector<TreeNode*> q;

        vector<long long> sum;

        q.push_back(root);

        // q.clear();

        //cout << q.size() << endl;

        while (q.size() > 0) {
            vector<TreeNode*> tem;

            long long s = 0;

            tem = q, q.clear();

            for (auto node : tem) {
                s += node -> val;

                if (node -> left) q.push_back(node -> left);

                if (node -> right) q.push_back(node -> right);
            }

            sum.push_back(s);
        }

        sort(sum.begin(), sum.end());

        int n = sum.size();

        return n < k ? -1 : sum[n - k];
    }
};

分割数组使乘积互质

• 这题看第一眼感觉不难
• 但是第二题花的时间有点多 没时间做优化
• 最后是数字溢出了 应该还是大数的问题

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        int n = nums.size() - 2;
        
        int l = 0, r = 0;
        
        int res = -1;
        
        long long s = 1;
        
        for (int i = 0; i < nums.size(); i ++) s *= nums[i];
        
        while (l <= n) {
            long long tem_1 = 1, tem_2 = 1;
            
            for (int i = 0; i <= l; i ++) tem_1 *= nums[i];
            
            tem_2 = s / tem_1;
            
            cout << tem_1 << ' ' << tem_2 << endl;
            
            if (gcd(tem_1, tem_2) == 1) {
                res = l; 
                break;
            }
            
            //cout << gcd(tem_1, tem_2) << endl;
            
            l ++;
        }
        
        return res;
    }
};

正确思路

• 合并区间的问题
• 哪些地方可以分割 -> 逆向思维 -> 哪些地方不能分割
• 对每个质因子 都处理它在 nums 中最左边的下标和最右边的下标 left right 那么答案就不能在 [left, right) -> 最小的答案可能就在 right 这里
• 答案是第一组区间的右端点的最大值
• 分两步走 -> 1.分解质因子 2.如何计算区间合并区间

class Solution {
public:
    int findValidSplit(vector<int> &nums) {
        unordered_map<int, int> left; // left[p] 表示质数 p 首次出现的下标
        int n = nums.size(), right[n]; // right[i] 表示左端点为 i 的区间的右端点的最大值
        memset(right, 0, sizeof(right));
        auto f = [&](int p, int i) {
            auto it = left.find(p);
            if (it == left.end())
                left[p] = i; // 第一次遇到质数 p
            else
                right[it->second] = i; // 记录左端点 l 对应的右端点的最大值
        };

        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            for (int d = 2; d * d <= x; ++d) { // 分解质因数
                if (x % d == 0) {
                    f(d, i);
                    for (x /= d; x % d == 0; x /= d);
                }
            }
            if (x > 1) f(x, i);
        }

        for (int l = 0, max_r = 0; l < n; ++l) {
            if (l > max_r) // 最远可以遇到 max_r
                return max_r; // 也可以写 l-1
            max_r = max(max_r, right[l]);
        }
        return -1;
    }
};