LeetCode第267场周赛

LeetCode第267场周赛题解

比赛地址：https://leetcode-cn.com/contest/weekly-contest-267/

一、买票需要的时间

题意

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

提示：

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

示例

示例1：

输入：tickets = [2,3,2], k = 2
输出：6
解释：

• 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。

• 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。

  位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。

示例2：

输入：tickets = [5,1,1,1], k = 0
输出：8
解释：

• 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。
• 接下来的 4 轮，只有位置 0 的人在买票。
  位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。

题解

数据量小，直接暴力即可。

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int n=tickets.size();
        int ans=0;
        for(int i=0;i<n;i++){
            if(i==k){
                tickets[k]--;ans++;
                if(tickets[k]==0) break;
            }else{
                if(tickets[i]>0) tickets[i]--,ans++;
            }
            if(i==n-1) i=-1;
        }
        return ans;
    }
};

二、反转偶数长度组的节点

题意

给你一个链表的头节点 head 。

链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, …）。一个组的 长度 就是组中分配到的节点数目。换句话说：

节点 1 分配给第一组
节点 2 和 3 分配给第二组
节点 4、5 和 6 分配给第三组，以此类推
注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。

反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。

提示

• 链表中节点数目范围是 [1, 105]
• 0 <= Node.val <= 105

示例

示例1：

输入：head = [5,2,6,3,9,1,7,3,8,4]
输出：[5,6,2,3,9,1,4,8,3,7]
解释：

• 第一组长度为 1 ，奇数，没有发生反转。
• 第二组长度为 2 ，偶数，节点反转。
• 第三组长度为 3 ，奇数，没有发生反转。
• 最后一组长度为 4 ，偶数，节点反转。

示例2：

输入：head = [1,1,0,6]
输出：[1,0,1,6]
解释：

• 第一组长度为 1 ，没有发生反转。
• 第二组长度为 2 ，节点反转。
• 最后一组长度为 1 ，没有发生反转。

示例3：

输入：head = [2,1]
输出：[2,1]
解释：

• 第一组长度为 1 ，没有发生反转。
• 最后一组长度为 1 ，没有发生反转。

题解

当然可以直接用链表翻转，但是这里偷了点懒，首先将链表存入数组，然后对数组进行处理。

**坑点：**

例如链表$head=[2,1,3,4,2]$，应该输出为$[2,3,1,2,4]$，这里并不是偶数个子链表翻转，而是子链表长度为偶数个就翻转，所以对末尾的数据需要特判处理

于是代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        vector<int> ve;
        ListNode* p=head;
        while(p!=nullptr){
            ve.push_back(p->val);
            p=p->next;
        }
        int len=1,i=0;
        int n=ve.size();
        ListNode* ans=new ListNode();
        p=ans;
        while(i+len<n){
            if(len&1){
                for(int j=0;j<len;j++){
                    p->next=new ListNode(ve[i++]);
                    p=p->next;
                }
            }else{
                for(int j=i+len-1;j>=i;j--){
                    p->next=new ListNode(ve[j]);
                    p=p->next;
                }
                i=i+len;
            }
            ++len;
        }
        //最后一组元素是偶数个还是奇数个
        if((n-i)&1){
            while(i<n){
                p->next=new ListNode(ve[i++]);
                p=p->next;
            }
        }else{
            for(int j=n-1;j>=i;j--){
                p->next=new ListNode(ve[j]);
                p=p->next;
            }
        }
        return ans->next;
    }
};

三、解码斜向换位密码

题意

字符串 originalText 使用 斜向换位密码 ，经由 行数固定 为 rows 的矩阵辅助，加密得到一个字符串 encodedText 。originalText 先按从左上到右下的方式放置到矩阵中。

先填充蓝色单元格，接着是红色单元格，然后是黄色单元格，以此类推，直到到达 originalText 末尾。箭头指示顺序即为单元格填充顺序。所有空单元格用 ' ' 进行填充。矩阵的列数需满足：用 originalText 填充之后，最右侧列 不为空 。

接着按行将字符附加到矩阵中，构造 encodedText 。

先把蓝色单元格中的字符附加到 encodedText 中，接着是红色单元格，最后是黄色单元格。箭头指示单元格访问顺序。

例如，如果 originalText = "cipher" 且 rows = 3 ，那么我们可以按下述方法将其编码：

蓝色箭头标识 originalText 是如何放入矩阵中的，红色箭头标识形成 encodedText 的顺序。在上述例子中，encodedText = "ch ie pr" 。

给你编码后的字符串 encodedText 和矩阵的行数 rows ，返回源字符串 originalText 。

注意：originalText 不 含任何尾随空格 ' ' 。生成的测试用例满足 仅存在一个 可能的 originalText 。

提示

• 0 <= encodedText.length <= 106
• encodedText 仅由小写英文字母和 ' ' 组成
• encodedText 是对某个 不含 尾随空格的 originalText 的一个有效编码
• 1 <= rows <= 1000
• 生成的测试用例满足 仅存在一个 可能的 originalText

示例

示例1：

输入：encodedText = “ch ie pr”, rows = 3
输出：”cipher”
解释：此示例与问题描述中的例子相同。

示例2：

输入：encodedText = “iveo eed l te olc”, rows = 4
输出：”i love leetcode”
解释：上图标识用于编码 originalText 的矩阵。
蓝色箭头展示如何从 encodedText 找到 originalText 。

示例3：

输入：encodedText = “ b ac”, rows = 2
输出：” abc”
解释：originalText 不能含尾随空格，但它可能会有一个或者多个前置空格。

题解

直接按照题意模拟即可，将给定的encodedText放入矩阵中，斜向读取originalText即可。由于会末尾会产生多余的空格，所以最后需要处理一下。具体代码如下：

class Solution {
public:
    string decodeCiphertext(string encodedText, int rows) {
        int n=encodedText.length();
        int cols=n/rows;
        string ans="";
        for(int i=0;i<cols;i++){
            for(int j=0;j<rows;j++){
                int p=j*(cols+1)+i;
                if(p>=n) continue;
                ans+=encodedText[p];
            }
        }
        string res=ans;
        for(int i=ans.length()-1;i>=0;i--){
            if(ans[i]!=' ') break;
            res.pop_back();
        }
        return res;
    }
};

四、处理含限制条件的好友请求

题意

给你一个整数 n ，表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。

给你一个下标从 0 开始的二维整数数组 restrictions ，其中 restrictions[i] = [xi, yi] 意味着用户 xi 和用户 yi 不能 成为 朋友 ，不管是 直接 还是通过其他用户 间接 。

最初，用户里没有人是其他用户的朋友。给你一个下标从 0 开始的二维整数数组 requests 表示好友请求的列表，其中 requests[j] = [uj, vj] 是用户 uj 和用户 vj 之间的一条好友请求。

如果 uj 和 vj 可以成为 朋友 ，那么好友请求将会 成功 。每个好友请求都会按列表中给出的顺序进行处理（即，requests[j] 会在 requests[j + 1] 前）。一旦请求成功，那么对所有未来的好友请求而言， uj 和 vj 将会 成为直接朋友 。

返回一个 布尔数组 result ，其中元素遵循此规则：如果第 j 个好友请求 成功 ，那么 result[j] 就是 true ；否则，为 false 。

注意：如果 uj 和 vj 已经是直接朋友，那么他们之间的请求将仍然 成功 。

提示

• 2 <= n <= 1000
• 0 <= restrictions.length <= 1000
• restrictions[i].length == 2
• 0 <= xi, yi <= n - 1
• xi != yi
• 1 <= requests.length <= 1000
• requests[j].length == 2
• 0 <= uj, vj <= n - 1
• uj != vj

示例

示例1：

输入：n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
输出：[true,false]
解释：
请求 0 ：用户 0 和 用户 2 可以成为朋友，所以他们成为直接朋友。
请求 1 ：用户 2 和 用户 1 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (1—2—0) 。

示例2：

输入：n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
输出：[true,false]
解释：
请求 0 ：用户 1 和 用户 2 可以成为朋友，所以他们成为直接朋友。
请求 1 ：用户 0 和 用户 2 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0—2—1) 。

示例3：

输入：n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
输出：[true,false,true,false]
解释：
请求 0 ：用户 0 和 用户 4 可以成为朋友，所以他们成为直接朋友。
请求 1 ：用户 1 和 用户 2 不能成为朋友，因为他们之间存在限制。
请求 2 ：用户 3 和 用户 1 可以成为朋友，所以他们成为直接朋友。
请求 3 ：用户 3 和 用户 4 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0—4—3—1) 。

题解

由题意可知，显然是一个并查集的题目。

由于数据量不大，可以这么处理：我们将能够直接或间接成为朋友的放入同一个集合。然后遍历requests数组，

• 如果本来就能直接或间接成为朋友，则直接为true
• 如果在原来集合中不能判断两者能否直接或间接成为朋友，则遍历restrictions数组。若存在相关限制，则为false；否则为true，同时将两者放入同一集合。

具体代码如下：

class Solution {
public:
    int par[1010];
    int get_par(int a){
        if(a!=par[a]) par[a]=get_par(par[a]);
        return par[a];
    }
    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
        vector<bool> ans;
        for(int i=0;i<n;i++) par[i]=i;
        for(int i=0;i<requests.size();i++){
            int par_u=get_par(requests[i][0]);int par_v=get_par(requests[i][1]);
            if(par_u==par_v){
                ans.push_back(1);continue;
            }else{
                bool flag=1;
                for(int j=0;j<restrictions.size();j++){
                    int u=restrictions[j][0];int v=restrictions[j][1];
                    if((get_par(u)==par_u&&get_par(v)==par_v) || (get_par(v)==par_u&&get_par(u)==par_v)){
                        flag=0;break;
                    }
                }
                ans.push_back(flag);
                if(flag) par[par_u]=par_v;
            }
        }
        return ans;
    }
};

总结：

最后一题真的不是很难，应该看下题目的…

• 本文作者：lb
• 本文链接：http://bbstudy.net/weekly-contest-267/
• 版权声明：本博客所有文章除特别声明外，均默认采用 许可协议。