本文對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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357039.html
標籤：其他