此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更友善快捷的記憶和回憶算法重點(不用每次都重複看題解), 畢竟算法不是做了一遍就能完全記住的. 是以本文适合已經知道解題思路和方法, 想進一步加強了解和記憶的朋友, 并不适合第一次接觸此題的朋友(可以根據題号先去力扣看看官方題解, 然後再看本文内容).
關于本專欄所有題目的目錄連結, 刷算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點選此連結.
想進大廠, 刷算法是必不可少的, 歡迎和部落客一起打卡刷力扣算法, 部落客同步更新了算法視訊講解 和 其他文章/導圖講解, 更易于了解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.題目分析
- 2.哈希表的結構設計
- 3. java的Map類周遊
- 3.1 Map.Entry
- 3.2 Map.entrySet()
- 3.3 四種方法周遊Map
- 4.Python的 := 海象運算符
- 5.總結
- 5.1 Python求數組的度
- 5.2 滑動視窗的思想
- 源碼
- Python:
- java:
題目連結:https://leetcode-cn.com/problems/degree-of-an-array/solution/si-wei-dao-tu-zheng-li-jie-shao-entrylei-fkxe/
0.導圖整理
1.題目分析
這道題在題目的了解上還是有一定的難度的, 看到有些評論反應連題目都沒讀懂, 那先來解讀下題目.
數組的度的定義是指數組裡任一進制素出現頻數的最大值: 也就是數組中出現最多的那個數的個數.
你的任務是在nums中找到與nums擁有相同大小的度的最短連續子數組, 傳回其長度: 也就是要求我們找到一個子數組, 子數組中出現最多的那個數的個數 和 原數組是相同的, 并且要求這個子數組盡可能的短.
2.哈希表的結構設計
了解題目要求後, 這題的求解過程就分為兩部分: 先找到數組的度, 再找到滿足要求的最短連續子數組.
找數組的度很容易就能想到利用哈希表來解決, 隻需要利用哈希表來記錄每個數出現的次數, 然後周遊哈希表獲得最大的次數即可. 困難之處在于如何尋找最短連續子數組.
我們先來分析下最短連續子數組的要求: 記原數組中出現次數最多的數為 x, 那麼和原數組的度相同的最短連續子數組, 必然包含了原數組中的全部 x, 且兩端恰為 x 第一次出現和最後一次出現的位置, 這樣才能確定子數組的長度最短, 不會包含多餘的元素.
通過這樣的分析結果發現, 我們不僅要儲存每個數出現的次數, 還需要儲存每個數第一次出現和最後一次出現的位置, 是以就能設計出這樣的哈希表: 每一個數映射到一個長度為 3 的數組, 數組中的三個元素分别代表這個數出現的次數、這個數在原數組中第一次出現的位置 和 這個數在原數組中最後一次出現的位置.
這裡還涉及到一種特殊情況: 符合條件的 x 可能有多個, 即多個不同的數在原數組中出現次數相同. 這時我們隻需要比較哪個子數組的長度更短即可.
3. java的Map類周遊
在代碼實作中, 我們需要周遊哈希表中對應的所有的值, 來尋找數組的度 和 最短連續子數組長度. 這裡是利用Map.entrySet()來實作的, 可能很多朋友對此方法還是比較陌生的, 我們來介紹一下.
3.1 Map.Entry
在介紹方法之前, 我們首先介紹下Map.Entry這個類. 它是Map中的一個内部類, 表示一個映射項, 映射項包含Key和Value (我們常說的鍵值對, 每一個鍵值對也就是一個Entry類), Map.Entry裡面包含getKey()和getValue()方法. 用來擷取相應的 鍵和值.
3.2 Map.entrySet()
它是Map類的一個方法, 它的傳回值就是所有鍵值對組成的集合, Set裡面的類型是Map.Entry, 是以傳回值的類型就是Map.Entry類, 這樣我們通過調用Map.entrySet()這個方法獲得所有的鍵值對, 再通過Map.Entry類中的getValue()方法就可以獲得所有的值了. 之後就可以對這些值進行各種操作獲得結果了.
3.3 四種方法周遊Map
這裡總結的了四種方法周遊Map, 每種方式都有不同的用途, 感興趣的可以看一下.
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("1", "value1");
map.put("2", "value2");
map.put("3", "value3");
//第一種：普遍使用，二次取值
System.out.println("通過Map.keySet周遊key和value：");
for (String key : map.keySet()) {
System.out.println("key= "+ key + " and value= " + map.get(key));
}
//第二種
System.out.println("通過Map.entrySet使用iterator周遊key和value：");
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//第三種：推薦，尤其是容量大時
System.out.println("通過Map.entrySet周遊key和value");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//第四種
System.out.println("通過Map.values()周遊所有的value，但不能周遊key");
for (String v : map.values()) {
System.out.println("value= " + v);
}
}
4.Python的 := 海象運算符
随着Python 3.8的釋出, 指派表達式運算符（也稱為海象運算符）也釋出了, 它最大的特點就是能夠在表達式中進行指派, 不需要再單獨的進行指派了, 用起來還是很友善的.
我大概總結了它的幾種用法和優點如下:
- 運算符使值的指派可以傳遞到表達式中, 省去了一個指派中間變量的步驟, 這也是它設計的初衷.
my_list = [1,2,3]
count = len(my_list)
if count > 3:
print(f"Error, {count} is too many items")
# 當轉換為海象運算符時...
if (count := len(my_list)) > 3:
print(f"Error, {count} is too many items")
- 可以在while語句中合并表達式和修飾符, 指派在循環表達式之前
line = f.readLine()
while line:
print(line)
line = f.readLine()
# 轉換為海象運算符時
while line := f.readLine():
print(line)
- 替換無限while循環中最有用
while True:
p = input("Enter the password: ")
if p == "the password":
break
# 當轉換為海象運算符時
while (p := input("Enter the password: ")) != "the password":
continue
- 減少函數的調用次數
scores = [22,54,75,89]
valid_scores = [
longFunction(n)
for n in scores
if longFunction(n)
]
# 注意條件語句longFunction(n)了嗎？ 注意longFunction()被調用了兩次嗎？
scores = [22,54,75,89]
valid_scores = [
result for n in scores
result := longFunction(n)
]
# 在優化了的代碼中，longFunction()僅被調用一次，隐含的降低了調用次數
5.總結
5.1 Python求數組的度
這題因為哈希表的結構比較特殊, 用python求數組的度的時候也采用正常的字典的形式, 但如果隻是單獨的求數組的度, python有更加簡潔的方法, 直接利用counter類即可, 關于這個類, 我之前也詳細講解過, 可在此檢視.
5.2 滑動視窗的思想
當然這題也是可以使用滑動視窗的思想的, 它的思路如下: j向右的條件是目前視窗的度小于數組的度, i向右的條件是目前視窗的度等于數組的度, 但這個方法的缺點也是很明顯的: 每次都需要求子區間的度, 使用了max函數, 時間複雜度略高.
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
degree = max(Counter(nums).values()) # 數組的度
i = j = 0
dic = defaultdict(int)
res = len(nums)
while j < len(nums):
dic[nums[j]] += 1
maxCnt = max(dic.values())
while maxCnt >= degree:
res = min(res, j - i + 1)
dic[nums[i]] -= 1
i += 1
maxCnt = max(dic.values())
j += 1
return res
源碼
Python:
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
mp = dict() # 字典的值為長度為3的數組
for i, num in enumerate(nums):
if num in mp: # 重複出現的情況
mp[num][0] += 1 # 第一個數代表出現次數
mp[num][2] = i # 第三個數代表最後一次出現位置
else: # 第一次出現的情況
mp[num] = [1, i, i] # 第二個數代表第一次出現位置
maxNum = minLen = 0
for count, left, right in mp.values():
if maxNum < count: # 尋找數組的度 和 最短連續子數組長度
maxNum = count
minLen = right - left + 1
elif maxNum == count: # 若兩個元素的度相同,比較誰的長度更短
# 海象運算符:= 在表達式中為變量指派,簡化操作
if minLen > (span := right - left + 1):
minLen = span
return minLen
java:
class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, int[]> map = new HashMap<Integer, int[]>(); // 值為長度為3的數組
int n = nums.length;
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) { // 重複出現的情況
map.get(nums[i])[0]++; // 第一個數代表出現次數
map.get(nums[i])[2] = i; // 第三個數代表最後一次出現位置
} else { // 第一次出現的情況
map.put(nums[i], new int[]{1, i, i}); // 第二個數代表第一次出現位置
}
}
int maxNum = 0, minLen = 0;
// 通過map中的entrySet方法獲得所有鍵值對,它們的類型為Map.Entry内部類
for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
int[] arr = entry.getValue();
if (maxNum < arr[0]) { // 尋找數組的度 和 最短連續子數組長度
maxNum = arr[0];
minLen = arr[2] - arr[1] + 1;
} else if (maxNum == arr[0]) { // 若兩個元素的度相同,比較誰的長度更短
if (minLen > arr[2] - arr[1] + 1) {
minLen = arr[2] - arr[1] + 1;
}
}
}
return minLen;
}
}
我的更多精彩文章連結, 歡迎檢視
各種電腦/軟體/生活/音樂/動漫/電影技巧彙總(你肯定能夠找到你需要的使用技巧)
力扣算法刷題 根據思維導圖整理筆記快速記憶算法重點内容(歡迎和部落客一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目
最值得收藏的 計算機網絡 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和架構簡介
最值得收藏的 算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字圖像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和删除問題 包含詳細操作原理 情況對比
各種常見排序算法的時間/空間複雜度 是否穩定 算法選取的情況 改進 思維導圖整理
人工智能課件 算法分析課件 Python課件 數值分析課件 機器學習課件 圖像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和複習技巧你應該知道)
東南大學 軟體工程 906 資料結構 C++ 曆年真題 思維導圖整理
東南大學 軟體工程 複試3門科目曆年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
高等數學 中值定理 一張思維導圖解決中值定理所有題型
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm架構全部筆記
Spring springmvc Mybatis jsp
科技相關 小米手機
小米 紅米 曆代手機型号大全 釋出時間 釋出價格
常見手機品牌的各種系列劃分及其特點
曆代CPU和GPU的性能情況和常見字尾的含義 思維導圖整理