每日Leetcode一題記錄

113602

2023.6.9
修改圖中的邊權

給你一個 n 個節點的 無向帶權連通 圖，節點編號為 0 到 n - 1 ，再給你一個整數數組 edges ，其中 edges[i] = [ai, bi, wi] 表示節點 ai 和 bi 之間有一條邊權為 wi 的邊。

部分邊的邊權為 -1（wi = -1），其他邊的邊權都為 正 數（wi > 0）。

你需要將所有邊權為 -1 的邊都修改為范圍 [1, 2 * 109] 中的 正整數 ，使得從節點 source 到節點 destination 的 最短距離 為整數 target 。如果有 多種 修改方案可以使 source 和 destination 之間的最短距離等于 target ，你可以返回任意一種方案。

如果存在使 source 到 destination 最短距離為 target 的方案，請你按任意順序返回包含所有邊的數組（包括未修改邊權的邊）。如果不存在這樣的方案，請你返回一個 空數組 。

注意：你不能修改一開始邊權為正數的邊。

實例

輸入：n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
輸出：[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
解釋：上圖展示了一個滿足題意的修改方案，從 0 到 1 的最短距離為 5 。

有點難，晚上再說

113602

2023.6.10
比較字符串最小字母出現頻次

定義一個函數 f(s)，統計 s  中（按字典序比較）最小字母的出現頻次 ，其中 s 是一個非空字符串。

例如，若 s = "dcce"，那么 f(s) = 2，因為字典序最小字母是 "c"，它出現了 2 次。

現在，給你兩個字符串數組待查表 queries 和詞匯表 words 。對于每次查詢 queries[i] ，需統計 words 中滿足 f(queries[i]) < f(W) 的 詞的數目 ，W 表示詞匯表 words 中的每個詞。

請你返回一個整數數組 answer 作為答案，其中每個 answer[i] 是第 i 次查詢的結果。

實例

輸入：queries = ["cbd"], words = ["zaaaz"]
輸出：[1]
解釋：查詢 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。

1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j]、words[i][j] 都由小寫英文字母組成

f函數遍歷一遍即可，由于word的長度較小，可以直接用后綴和

113602

2023.6.11
從鏈表中刪去總和值為零的連續節點

給你一個鏈表的頭節點 head，請你編寫代碼，反復刪去鏈表中由 總和 值為 0 的連續節點組成的序列，直到不存在這樣的序列為止。

刪除完畢后，請你返回最終結果鏈表的頭節點。



你可以返回任何滿足題目要求的答案。

（注意，下面示例中的所有序列，都是對 ListNode 對象序列化的表示。）

實例

輸入：head = [1,2,-3,3,1]
輸出：[3,1]
提示：答案 [1,2,1] 也是正確的。

這題比較巧妙，去掉和為零的子串可以通過前綴和，兩個前綴和相同的節點之間的節點和為0。
注意需要兩次遍歷，第一次前綴和作哈希表，鍵為前綴和，值為最后更新的節點，第二次遍歷記錄前綴和，如果哈希表內有重，則直接接到該節點。

113602

2023.6.12
樹節點的第 K 個祖先

給你一棵樹，樹上有 n 個節點，按從 0 到 n-1 編號。樹以父節點數組的形式給出，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。

樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點。

實現 TreeAncestor 類：

TreeAncestor（int n， int[] parent） 對樹和父數組中的節點數初始化對象。
getKthAncestor(int node, int k) 返回節點 node 的第 k 個祖先節點。如果不存在這樣的祖先節點，返回 -1 。


實例

輸入：
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

輸出：
[null,1,0,-1]

解釋：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // 返回 1 ，它是 3 的父節點
treeAncestor.getKthAncestor(5, 2);  // 返回 0 ，它是 5 的祖父節點
treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因為不存在滿足要求的祖先節點

1 <= k <= n <= 5 * 104
parent[0] == -1 表示編號為 0 的節點是根節點。
對于所有的 0 < i < n ，0 <= parent[i] < n 總成立
0 <= node < n
至多查詢 5 * 10^4 次

113602

2023.6.13
數組中不等三元組的數目

給你一個下標從 0 開始的正整數數組 nums 。請你找出并統計滿足下述條件的三元組 (i, j, k) 的數目：

0 <= i < j < k < nums.length
nums[i]、nums[j] 和 nums[k] 兩兩不同 。
換句話說：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。
返回滿足上述條件三元組的數目。

實例

輸入：nums = [4,4,2,4,3]
輸出：3
解釋：下面列出的三元組均滿足題目條件：
- (0, 2, 4) 因為 4 != 2 != 3
- (1, 2, 4) 因為 4 != 2 != 3
- (2, 3, 4) 因為 2 != 4 != 3
共計 3 個三元組，返回 3 。
注意 (2, 0, 4) 不是有效的三元組，因為 2 > 0 。

比較簡單。從小到大排，之前的i個元素，中間相同的j個元素，之后的k個元素，有i*j*k種組合。
排序可以直接排也可以利用哈希表。

113602

2023.6.14
二進制字符串前綴一致的次數

給你一個長度為 n 、下標從 1 開始的二進制字符串，所有位最開始都是 0 。我們會按步翻轉該二進制字符串的所有位（即，將 0 變為 1）。

給你一個下標從 1 開始的整數數組 flips ，其中 flips[i] 表示對應下標 i 的位將會在第 i 步翻轉。

二進制字符串 前綴一致 需滿足：在第 i 步之后，在 閉 區間 [1, i] 內的所有位都是 1 ，而其他位都是 0 。

返回二進制字符串在翻轉過程中 前綴一致 的次數。

實例

輸入：flips = [3,2,4,1,5]
輸出：2
解釋：二進制字符串最開始是 "00000" 。
執行第 1 步：字符串變為 "00100" ，不屬于前綴一致的情況。
執行第 2 步：字符串變為 "01100" ，不屬于前綴一致的情況。
執行第 3 步：字符串變為 "01110" ，不屬于前綴一致的情況。
執行第 4 步：字符串變為 "11110" ，屬于前綴一致的情況。
執行第 5 步：字符串變為 "11111" ，屬于前綴一致的情況。
在翻轉過程中，前綴一致的次數為 2 ，所以返回 2 。

只要記錄最大的翻轉位置，如果和翻轉次數相同，則一定是前綴一致

113602

出事了。
電腦顯示器爆了。
暫時停更，看jd什么時候送到新顯示器并且我把它裝上。