leetcode vp 第267场周赛

第 267 场周赛 - 力扣（LeetCode)

盲猜这场也是个手速场，前三题均是大模拟，最后一题也就一个裸的并查集板子

T1

class Solution {
public:
    int timeRequiredToBuy(vector<int>& ti, int k) {
        queue<int> qu;
        for(auto t: ti) qu.push(t);
        int now = k, left = ti[k];
        int sum = 0;
        while(left) {
            sum ++;
            if(now == 0) {
                qu.pop();
                left --;
                if(left) qu.push(left);
                now = qu.size() - 1;
            } else {
                int t = qu.front();
                qu.pop();
                now --;
                t -- ;
                if(t) qu.push(t); 
            }
        }
        return sum;
    }
};

T2

class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        vector<int> nums;
        for(auto p = head; p; p = p->next) {
            nums.push_back(p->val);
        }
        int k = 1, l = 0, r = 0;
        while(r < nums.size()) {
            //if(k == 4) cout << l << " " << r << endl;
            if((r - l + 1) % 2 == 0) reverse(nums.begin() + l, nums.begin() + r + 1);
            l = min(l + k, (int)nums.size() - 1), r = min(r + k + 1, (int)nums.size() - 1);
            if(l == nums.size() - 1) break;
            k ++;
        }
        auto dummy = new ListNode(-1), tail = dummy;
        for(int i = 0; i < nums.size(); i ++ ) {
            tail = tail->next = new ListNode(nums[i]);
        }
        return dummy -> next;
    }   
};

T3

class Solution {
public:
    string decodeCiphertext(string en, int rows) {
        int n = en.size();
        int col = n / rows;
        vector<vector<char>> str(rows, vector<char>(col));
        int x = 0, y = 0;
        for(int i = 0; i < n; i ++ ) {
            str[x][y] = en[i];
            y ++;
            if(y >= col) y = 0, x ++ ;
        }
        string ans = "";
        for(int k = 0; k < col; k ++ ) {
            for(int i = 0, j = k; i <= rows && j <= min(k + rows - 1, col - 1); i ++, j ++ ) {
                ans += str[i][j];
            }
        }
        while(ans.back() == ' ') ans.pop_back();
        return ans;
    }
};

T4

分析：

并查集，每次处理一对请求的时候先枚举所有限制，如果和限制冲突了就无法请求成功

class Solution {
public:
    vector<int> p;

    int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    vector<bool> friendRequests(int n, vector<vector<int>>& re, vector<vector<int>>& q) {
        p.resize(n + 1);
        for(int i = 0; i < n; i ++) p[i] = i;
        vector<bool> ans(q.size());
        int i = 0;
        for(auto& e: q) {
            int pa = find(e[0]), pb = find(e[1]);
            bool flag = true;
            for(auto &g: re) {
                int qa = find(g[0]), qb = find(g[1]);
                if(qa == pa && qb == pb || qa == pb && qb == pa || e[0] == g[0] && e[1] == g[1] || e[1] == g[0] && e[0] == g[1]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                p[pa] = pb;
                ans[i] = true;
            }
            i ++;
        }    

        return ans;

    }
};