本文對267場周賽題目做一個小結。周賽題目鏈接在此

No 1 買票需要的時間

有 n 個人前來排隊買票，其中第 0 人站在隊伍 最前方 ，第 (n - 1) 人站在隊伍 最后方 。

給你一個下標從 0 開始的整數(shù)數(shù)組 tickets ，數(shù)組長度為 n ，其中第 i 人想要購買的票數(shù)為 tickets[i] 。

每個人買票都需要用掉 恰好 1 秒 。一個人 一次只能買一張票 ，如果需要購買更多票，他必須走到 隊尾 重新排隊（瞬間 發(fā)生，不計時間）。如果一個人沒有剩下需要買的票，那他將會 離開 隊伍。

返回位于位置 k（下標從 0 開始）的人完成買票需要的時間（以秒為單位）。

示例 1：

輸入：tickets = [2,3,2], k = 2
輸出：6
解釋：

• 第一輪，隊伍中的每個人都買到一張票，隊伍變?yōu)?[1, 2, 1] 。
• 第二輪，隊伍中的每個都又都買到一張票，隊伍變?yōu)?[0, 1, 0] 。
  位置 2 的人成功買到 2 張票，用掉 3 + 3 = 6 秒。

解析

本題是例行簽到題，數(shù)據(jù)范圍不大，暴力實現(xiàn)就可以通過。
本題給定一個數(shù)組，表示有n個人每個人購買若干張票。一個人每次只能買一張，如果還需要購買就要重新排隊。每次購票耗時1s，求第k個人買完自己的票要多久。
本題按照要求直接做即可。建一個隊列，將編號0~n-1依次入隊，每次出隊一個編號，就把該編號的購票數(shù)減一，同時計數(shù)器加1，代表這個號的人買票一張，耗時1s。如果減一之后這個編號還有票需要購買，就再次入隊。直到編號為k的購票數(shù)減少至0，返回計數(shù)器的數(shù)值即可。

由于本題數(shù)據(jù)范圍很小，最多100人，每人購票最多100張，最多只需10000次操作，因此暴力不會超時。如果要更快，也可以從數(shù)值角度計算排在k之前和之后的人在k買好票時分別買了幾張票，再加起來即可（這樣可以從$O(N^2)$ 降到 $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 反轉(zhuǎn)偶數(shù)長度組的節(jié)點

給你一個鏈表的頭節(jié)點 head 。

鏈表中的節(jié)點 按順序 劃分成若干 非空 組，這些非空組的長度構成一個自然數(shù)序列（1, 2, 3, 4, …）。一個組的 長度 就是組中分配到的節(jié)點數(shù)目。換句話說：

節(jié)點 1 分配給第一組
節(jié)點 2 和 3 分配給第二組
節(jié)點 4、5 和 6 分配給第三組，以此類推
注意，最后一組的長度可能小于或者等于 1 + 倒數(shù)第二組的長度 。

反轉(zhuǎn) 每個 偶數(shù) 長度組中的節(jié)點，并返回修改后鏈表的頭節(jié)點 head 。

示例 1：

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

• 第一組長度為 1 ，奇數(shù)，沒有發(fā)生反轉(zhuǎn)。
• 第二組長度為 2 ，偶數(shù)，節(jié)點反轉(zhuǎn)。
• 第三組長度為 3 ，奇數(shù)，沒有發(fā)生反轉(zhuǎn)。
• 最后一組長度為 4 ，偶數(shù)，節(jié)點反轉(zhuǎn)。

解析

本題要求對鏈表按規(guī)則分組翻轉(zhuǎn)。分組規(guī)則是，按照1,2，3,4的自然數(shù)數(shù)列遞增，先選擇第一個節(jié)點為1組，然后接下來2個節(jié)點一組，在之后3個節(jié)點劃在一組，以此類推。最后一組很可能不夠，那就剩下有多少節(jié)點就分在一組。分好組后，每組的長度就是1,2，3,4…last。last表示最后一組，其長度不一定是倒數(shù)第二組加1.然后對其中長度為偶數(shù)的每一組都做翻轉(zhuǎn)，返回完成翻轉(zhuǎn)后的鏈表。

本題其實也沒什么技巧，就是按照題意去做分組，需要注意的地方是最后一組長度可能不夠計劃值，實際長度為偶數(shù)也需要做翻轉(zhuǎn)。

考慮到鏈表分組翻轉(zhuǎn)有很多細節(jié)要考慮，容易出錯。我這里將其轉(zhuǎn)化為數(shù)組，完成翻轉(zhuǎn)后再構造一個新鏈表（題目沒有說必須原地翻轉(zhuǎn)）

首先將鏈表元素依次提出放入數(shù)組。數(shù)組下標從0開始，每次根據(jù)是否越界和當前這一組的長度，確定下一組開始位置和本組的范圍與長度。如果長度是偶數(shù)，就通過swap操作交換元素實現(xiàn)局部的翻轉(zhuǎn)。反轉(zhuǎn)結束后，新建頭結點，用數(shù)組元素值依次構造節(jié)點加入鏈表。

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 使用 斜向換位密碼 ，經(jīng)由 行數(shù)固定 為 rows 的矩陣輔助，加密得到一個字符串 encodedText 。
originalText 先按從左上到右下的方式放置到矩陣中。

先填充藍色單元格，接著是紅色單元格，然后是黃色單元格，以此類推，直到到達 originalText 末尾。箭頭指示順序即為單元格填充順序。所有空單元格用 ’ ’ 進行填充。矩陣的列數(shù)需滿足：用 originalText 填充之后，最右側列 不為空 。

接著按行將字符附加到矩陣中，構造 encodedText 。
先把藍色單元格中的字符附加到 encodedText 中，接著是紅色單元格，最后是黃色單元格。箭頭指示單元格訪問順序。

例如，如果 originalText = “cipher” 且 rows = 3 ，那么我們可以按下述方法將其編碼：

藍色箭頭標識 originalText 是如何放入矩陣中的，紅色箭頭標識形成 encodedText 的順序。在上述例子中，encodedText = “ch ie pr” 。
給你編碼后的字符串 encodedText 和矩陣的行數(shù) rows ，返回源字符串 originalText 。

注意：originalText 不 含任何尾隨空格 ’ ’ 。生成的測試用例滿足 僅存在一個 可能的 originalText 。

示例 1：

輸入：encodedText = “ch ie pr”, rows = 3
輸出：“cipher”
解釋：此示例與問題描述中的例子相同。

解析

本題給了一種字符串加密方式，先構造一定行數(shù)的二維網(wǎng)格，將原字符串按照左上到右下的對角線方向逐個填充，首先從第一行第一列開始，向右下角（行數(shù)+1，列數(shù)+1）填充；然后從第一行第二列開始，以此類推。最后將二維表格逐行讀取拼接成字符串，作為加密后的字符串。現(xiàn)在本題給定加密后的字符串以及二維網(wǎng)格行數(shù)，讓我們解析原字符串。

實際上本題也沒有什么技巧可言，由于加密后的字符串包含了二維網(wǎng)格所有元素（未填充按空格記錄），所以我們根據(jù)其長度和行數(shù)，就可以得到這個網(wǎng)格的列數(shù)，進而按照逐行填充的順序，把加密字符串的每個字符填回二維網(wǎng)格中，再根據(jù)原有規(guī)則，從對角線方向讀取恢復原字符串。

另外本題說明原始字符串沒有結尾處的空格，回復之后要將末尾空格刪去。

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 處理含限制條件的好友請求

給你一個整數(shù) n ，表示網(wǎng)絡上的用戶數(shù)目。每個用戶按從 0 到 n - 1 進行編號。

給你一個下標從 0 開始的二維整數(shù)數(shù)組 restrictions ，其中 restrictions[i] = [xi, yi] 意味著用戶 xi 和用戶 yi 不能 成為 朋友 ，不管是 直接 還是通過其他用戶 間接 。

最初，用戶里沒有人是其他用戶的朋友。給你一個下標從 0 開始的二維整數(shù)數(shù)組 requests 表示好友請求的列表，其中 requests[j] = [uj, vj] 是用戶 uj 和用戶 vj 之間的一條好友請求。

如果 uj 和 vj 可以成為 朋友 ，那么好友請求將會 成功 。每個好友請求都會按列表中給出的順序進行處理（即，requests[j] 會在 requests[j + 1] 前）。一旦請求成功，那么對所有未來的好友請求而言， uj 和 vj 將會 成為直接朋友 。

返回一個 布爾數(shù)組 result ，其中元素遵循此規(guī)則：如果第 j 個好友請求 成功 ，那么 result[j] 就是 true ；否則，為 false 。
注意：如果 uj 和 vj 已經(jīng)是直接朋友，那么他們之間的請求將仍然 成功 。

示例 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個用戶，根據(jù)請求和約束確定他們之間的朋友關系，對于每個請求，如果請求的兩個用戶(v1,v2)建立朋友關系，就記為true，否則記為false，最后返回每個請求是否成功的數(shù)組。

這里我們需要判斷和建立直接-間接朋友關系，也就是朋友關系是可以傳遞的。因此很容易想到采用數(shù)據(jù)結構并查集，一旦a和b建立了朋友關系，那么a和b原來各自的朋友之間也就建立了間接朋友關系。

因此我們采用并查集處理朋友關系。但是本題還有一個要求，有些用戶被約束無法成為直接或間接的好友。因此，我們應當對于每一個請求，首先通過查詢判斷是否已經(jīng)是好友了，是的話直接記錄該請求結果為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;  }