每日Leetcode一題記錄

113602

決定了，沒事做就水記錄一下Leetcode的每日一題。
聲明，非專業，做這個僅是出于興趣，我的個人水平可能非常低。
感興趣的也可以共同討論學習。

113602

2023.6.2
統計范圍內的元音字符串數
給你一個下標從 0 開始的字符串數組 words 以及一個二維整數數組 queries 。

每個查詢 queries[i] = [li, ri] 會要求我們統計在 words 中下標在 li 到 ri 范圍內（包含 這兩個值）并且以元音開頭和結尾的字符串的數目。

返回一個整數數組，其中數組的第 i 個元素對應第 i 個查詢的答案。

注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

實例

輸入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
輸出：[2,3,0]
解釋：以元音開頭和結尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查詢 [0,2] 結果為 2（字符串 "aba" 和 "ece"）。
查詢 [1,4] 結果為 3（字符串 "ece"、"aa"、"e"）。
查詢 [1,1] 結果為 0 。
返回結果 [2,3,0] 。

個人感覺這題夠不上medium。

113602

2023.6.3
單字符重復子串的最大長度

如果字符串中的所有字符都相同，那么這個字符串是單字符重復的字符串。

給你一個字符串 text，你只能交換其中兩個字符一次或者什么都不做，然后得到一些單字符重復的子串。返回其中最長的子串的長度。

實例

輸入：text = "ababa"
輸出：3

滑動窗口加分類討論

206999

月亮伊布

7

剛去看了一眼，有專門的js題型卻沒有其他語言？我不扶器

113602

2023.6.4
不同的平均值數目

給你一個下標從 0 開始長度為 偶數 的整數數組 nums 。

只要 nums 不是 空數組，你就重復執行以下步驟：

找到 nums 中的最小值，并刪除它。
找到 nums 中的最大值，并刪除它。
計算刪除兩數的平均值。
兩數 a 和 b 的 平均值 為 (a + b) / 2 。

比方說，2 和 3 的平均值是 (2 + 3) / 2 = 2.5 。
返回上述過程能得到的 不同 平均值的數目。

注意 ，如果最小值或者最大值有重復元素，可以刪除任意一個。

實例

輸入：nums = [4,1,4,0,3,5]
輸出：2
解釋：
1. 刪除 0 和 5 ，平均值是 (0 + 5) / 2 = 2.5 ，現在 nums = [4,1,4,3] 。
2. 刪除 1 和 4 ，平均值是 (1 + 4) / 2 = 2.5 ，現在 nums = [4,3] 。
3. 刪除 3 和 4 ，平均值是 (3 + 4) / 2 = 3.5 。
2.5 ，2.5 和 3.5 之中總共有 2 個不同的數，我們返回 2 。

2 <= nums.length <= 100
nums.length 是偶數。
0 <= nums[i] <= 100

easy題，范圍較小，排序之后哈希即可。

113602

2023.6.5
對數組執行操作

給你一個下標從 0 開始的數組 nums ，數組大小為 n ，且由 非負 整數組成。

你需要對數組執行 n - 1 步操作，其中第 i 步操作（從 0 開始計數）要求對 nums 中第 i 個元素執行下述指令：

如果 nums[i] == nums[i + 1] ，則 nums[i] 的值變成原來的 2 倍，nums[i + 1] 的值變成 0 。否則，跳過這步操作。
在執行完 全部 操作后，將所有 0 移動 到數組的 末尾 。

例如，數組 [1,0,2,0,0,1] 將所有 0 移動到末尾后變為 [1,2,1,0,0,0] 。
返回結果數組。

注意 操作應當 依次有序 執行，而不是一次性全部執行。

實例

輸入：nums = [1,2,2,1,1,0]
輸出：[1,4,2,0,0,0]
解釋：執行以下操作：
- i = 0: nums[0] 和 nums[1] 不相等，跳過這步操作。
- i = 1: nums[1] 和 nums[2] 相等，nums[1] 的值變成原來的 2 倍，nums[2] 的值變成 0 。數組變成 [1,4,0,1,1,0] 。
- i = 2: nums[2] 和 nums[3] 不相等，所以跳過這步操作。
- i = 3: nums[3] 和 nums[4] 相等，nums[3] 的值變成原來的 2 倍，nums[4] 的值變成 0 。數組變成 [1,4,0,2,0,0] 。
- i = 4: nums[4] 和 nums[5] 相等，nums[4] 的值變成原來的 2 倍，nums[5] 的值變成 0 。數組變成 [1,4,0,2,0,0] 。
執行完所有操作后，將 0 全部移動到數組末尾，得到結果數組 [1,4,2,0,0,0] 。

簡單模擬，雙指針一個用來記錄當前執行的位置，一個記錄最靠前的0的位置，執行后將0與執行數交換。一次遍歷。

113602

2023.6.6
相等行列對

給你一個下標從 0 開始、大小為 n x n 的整數矩陣 grid ，返回滿足 Ri 行和 Cj 列相等的行列對 (Ri, Cj) 的數目。

如果行和列以相同的順序包含相同的元素（即相等的數組），則認為二者是相等的。

實例

輸入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
輸出：3
解釋：存在三對相等行列對：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行, 第 2 列)：[2,4,2,2]
- (第 3 行, 第 2 列)：[2,4,2,2]

按行遍歷哈希，按列遍歷累加，復雜度n^2

113602

2023.6.7
老鼠和奶酪

有兩只老鼠和 n 塊不同類型的奶酪，每塊奶酪都只能被其中一只老鼠吃掉。

下標為 i 處的奶酪被吃掉的得分為：

如果第一只老鼠吃掉，則得分為 reward1[i] 。
如果第二只老鼠吃掉，則得分為 reward2[i] 。
給你一個正整數數組 reward1 ，一個正整數數組 reward2 ，和一個非負整數 k 。

請你返回第一只老鼠恰好吃掉 k 塊奶酪的情況下，最大 得分為多少。
實例

輸入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
輸出：15
解釋：這個例子中，第一只老鼠吃掉第 2 和 3 塊奶酪（下標從 0 開始），第二只老鼠吃掉第 0 和 1 塊奶酪。
總得分為 4 + 4 + 3 + 4 = 15 。
15 是最高得分。

1 <= n == reward1.length == reward2.length <= 10^5
1 <= reward1[i], reward2[i] <= 1000
0 <= k <= n

貪心，只需要在所有reward中找出k個最大的1與2的差值即可。
值得一提的是，在范圍內取前k個最大/小只需要使用優先隊列，利用最小/大堆把最小/大pop出，保持堆的size在k即可。

113602

2023.6.8
鋪瓷磚

你是一位施工隊的工長，根據設計師的要求準備為一套設計風格獨特的房子進行室內裝修。

房子的客廳大小為 n x m，為保持極簡的風格，需要使用盡可能少的 正方形 瓷磚來鋪蓋地面。

假設正方形瓷磚的規格不限，邊長都是整數。

請你幫設計師計算一下，最少需要用到多少塊方形瓷磚？

實例

輸入：n = 2, m = 3
輸出：3
解釋：3 塊地磚就可以鋪滿臥室。
     2 塊 1x1 地磚
     1 塊 2x2 地磚

有論文證明特定情況下的轉移方程，但是不通用，如果要dp的話需要把特殊情況拉出來。
一般情況回溯法dfs即可。