LeetCode 第 267 场周赛

本文对267场周赛题目做一个小结。周赛题目链接在此

No 1 买票需要的时间

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

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

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

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

示例 1：

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

• 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。
• 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。
  位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。

解析

本题是例行签到题，数据范围不大，暴力实现就可以通过。
本题给定一个数组，表示有n个人每个人购买若干张票。一个人每次只能买一张，如果还需要购买就要重新排队。每次购票耗时1s，求第k个人买完自己的票要多久。
本题按照要求直接做即可。建一个队列，将编号0~n-1依次入队，每次出队一个编号，就把该编号的购票数减一，同时计数器加1，代表这个号的人买票一张，耗时1s。如果减一之后这个编号还有票需要购买，就再次入队。直到编号为k的购票数减少至0，返回计数器的数值即可。

由于本题数据范围很小，最多100人，每人购票最多100张，最多只需10000次操作，因此暴力不会超时。如果要更快，也可以从数值角度计算排在k之前和之后的人在k买好票时分别买了几张票，再加起来即可（这样可以从

O

(

N

2

)

O(N^2)

O(N2) 降到

O

(

N

)

O(N)

O(N)

C++代码如下：

//No 1
  int timeRequiredToBuy(vector<int>& tickets, int k) {
    queue<int>q;
    int n = tickets.size(), ans = 0;
    for (int i = 0; i < n; ++i) {
      q.push(i);
    }
    while (tickets[k] > 0) {
      int c = q.front();
      q.pop();
      tickets[c]--;
      ++ans;
      if (tickets[c] > 0)q.push(c);
    }
    return ans;
  }

No 2 反转偶数长度组的节点

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

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

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

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

示例 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 ，偶数，节点反转。

解析

本题要求对链表按规则分组翻转。分组规则是，按照1,2，3,4的自然数数列递增，先选择第一个节点为1组，然后接下来2个节点一组，在之后3个节点划在一组，以此类推。最后一组很可能不够，那就剩下有多少节点就分在一组。分好组后，每组的长度就是1,2，3,4…last。last表示最后一组，其长度不一定是倒数第二组加1.然后对其中长度为偶数的每一组都做翻转，返回完成翻转后的链表。

本题其实也没什么技巧，就是按照题意去做分组，需要注意的地方是最后一组长度可能不够计划值，实际长度为偶数也需要做翻转。

考虑到链表分组翻转有很多细节要考虑，容易出错。我这里将其转化为数组，完成翻转后再构造一个新链表（题目没有说必须原地翻转）

首先将链表元素依次提出放入数组。数组下标从0开始，每次根据是否越界和当前这一组的长度，确定下一组开始位置和本组的范围与长度。如果长度是偶数，就通过swap操作交换元素实现局部的翻转。反转结束后，新建头结点，用数组元素值依次构造节点加入链表。

C++代码如下：

//No 2
  ListNode* reverseEvenLengthGroups(ListNode* head) {
    vector<int>l;
    ListNode* p = head;
    int n = 0;
    while (p) {
      l.push_back(p->val);
      p = p->next;
      ++n;
    }
    int i = 0,k=1;
    while (i < n) {
      int curL = 0;
      if (i + k <= n) curL = k;
      else curL = n - i;
      if (curL % 2 == 0) {
        for (int j = 0; j < curL / 2; ++j) {
          swap(l[i + j], l[i + j + curL / 2]);
        }
      }
      i = i + curL;
      ++k;
    }
    ListNode* helper = new ListNode(-1);
    p = helper;
    for (auto v : l) {
      p->next = new ListNode(v);
      p = p->next;
    }
    return helper->next;
  }

No 3 解码斜向换位密码

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

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

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

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

蓝色箭头标识 originalText 是如何放入矩阵中的，红色箭头标识形成 encodedText 的顺序。在上述例子中，encodedText = “ch ie pr” 。
给你编码后的字符串 encodedText 和矩阵的行数 rows ，返回源字符串 originalText 。

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

示例 1：

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

解析

本题给了一种字符串加密方式，先构造一定行数的二维网格，将原字符串按照左上到右下的对角线方向逐个填充，首先从第一行第一列开始，向右下角（行数+1，列数+1）填充；然后从第一行第二列开始，以此类推。最后将二维表格逐行读取拼接成字符串，作为加密后的字符串。现在本题给定加密后的字符串以及二维网格行数，让我们解析原字符串。

实际上本题也没有什么技巧可言，由于加密后的字符串包含了二维网格所有元素（未填充按空格记录），所以我们根据其长度和行数，就可以得到这个网格的列数，进而按照逐行填充的顺序，把加密字符串的每个字符填回二维网格中，再根据原有规则，从对角线方向读取恢复原字符串。

另外本题说明原始字符串没有结尾处的空格，回复之后要将末尾空格删去。

C++代码如下：

//No 3
  string decodeCiphertext(string encodedText, int rows) {
    int n = encodedText.size(),cols=n/rows;
    vector<vector<char>> board(rows, vector<char>(cols));
    for (int i = 0; i < n; ++i) {
      int r = i / cols, c = i % cols;
      board[r][c] = encodedText[i];
    }
    string ans;
    for (int i = 0; i < cols; ++i) {
      int sr = 0, sc = i;
      while (sr < rows && sc < cols) {
        ans.push_back(board[sr][sc]);
        ++sr;
        ++sc;
      }
    }
    while (ans.back() == ' ') ans.pop_back();
    return ans;
  }

No 4 处理含限制条件的好友请求

给你一个整数 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 已经是直接朋友，那么他们之间的请求将仍然 成功 。

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

解析

本题要求我们对于编号0~n-1的n个用户，根据请求和约束确定他们之间的朋友关系，对于每个请求，如果请求的两个用户(v1,v2)建立朋友关系，就记为true，否则记为false，最后返回每个请求是否成功的数组。

这里我们需要判断和建立直接-间接朋友关系，也就是朋友关系是可以传递的。因此很容易想到采用数据结构并查集，一旦a和b建立了朋友关系，那么a和b原来各自的朋友之间也就建立了间接朋友关系。

因此我们采用并查集处理朋友关系。但是本题还有一个要求，有些用户被约束无法成为直接或间接的好友。因此，我们应当对于每一个请求，首先通过查询判断是否已经是好友了，是的话直接记录该请求结果为true；如果不是，我们要先判断将二者加为好友会不会违反一些约束，如果违反了，就记录为false并且不把这个朋友关系真的添加进去，如果不违反，再进行添加，添加后请求结果为true。

这个思路也比较简单粗暴，复杂度比较极限，正好能过。由于并查集没有删除的操作（并集之后无法还原），我这里用了很直接的方式。如果一个请求的两个用户还不是好友，就先把原并查集拷贝一份副本，在副本对象中进行添加好友关系，判断是否与约束条件有冲突。如果没有冲突，再把修改后的副本赋值给原并查集，添加成功；否则就认为这个添加无法进行，原并查集对象不做修改，该请求为false。

C++代码如下：

class UnionFind {
  int n;
  vector<int> parent;
  vector<int> size;

public:
  UnionFind(int n_) {
    this->n = n_;
    parent = vector<int>(n);
    size = vector<int>(n, 1);
    for (int i = 0; i < n; ++i)
      parent[i] = i;
  }

  int find(int idx) {
    if (parent[idx] == idx)
      return idx;
    return find(parent[idx]);
  }

  void connect(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa != fb) {
      if (size[fa] > size[fb]) {
        parent[fb] = fa;
        size[fa] += size[fb];
      }
      else {
        parent[fa] = fb;
        size[fb] += size[fa];
      }
    }
  }
};
//No 4
  vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
    int nre = requests.size();
    vector<bool>ans(nre);
    UnionFind UF(n);
    for (int i = 0; i < nre; ++i) {
      int v1 = requests[i][0], v2 = requests[i][1];
      if (UF.find(v1) == UF.find(v2)) ans[i] = true;
      else {
        UnionFind UFtmp = UF;
        UFtmp.connect(v1, v2);
        bool can = true;
        for (auto r : restrictions) {
          if (UFtmp.find(r[0]) == UFtmp.find(r[1])) {
            can = false;
            break;
          }
        }
        ans[i] = can;
        if(can) UF.connect(v1, v2);
      }
    }
    return ans;
  }