此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接. 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
目錄
0.導圖整理
1.維數太高, 分治處理
2.Java中map的merge和getOrDefault方法
3.Python中的Counter類
3.1 簡介
3.2 初始化
3.3 空的處理
3.4 洗掉元素
3.5 elements()方法
3.6 most_common([n])方法
3.7 subtract([iterable-or-mapping])方法
3.8 數學操作
3.9 注意點
4.總結
原始碼
題目鏈接: https://leetcode-cn.com/problems/4sum-ii/
0.導圖整理
1.維數太高, 分治處理
此題乍一看似乎和 四數之和 差不多, 但是本質上卻有著很大的區別, 首先無論是 三數之和 還是 四數之和, 它們都是在一個陣列上的操作, 本質上都是一維的, 同時它們都要求找到 不重復 的元組, 這就限制了我們不能簡單的使用哈希表進行去重操作, 最終只能將陣列排序后使用雙指標的方法.
但是本題是 四個獨立的陣列, 相當于是 四個維度, 想在四個維度上使用雙指標的方法顯然是不現實的. 同時此題只要求我們找到所有4個元素的和為0的元組個數即可, 并沒有要求是不重復的元組, 這樣就簡單了很多, 也是可以使用哈希表的方法的.
此題在使用哈希表的時候, 會遇到如下的三種情況:
1.HashMap存一個陣列,如A，然后計算三個陣列之和,如BCD，時間復雜度為：O(n)+O(n^3),得到O(n^3).
2.HashMap存三個陣列之和,如ABC，然后計算一個陣列,如D，時間復雜度為：O(n^3)+O(n),得到O(n^3).
3.HashMap存兩個陣列之和,如AB，然后計算兩個陣列之和,如CD，時間復雜度為：O(n^2)+O(n^2),得到O(n^2).
根據時間復雜度來看, 我們肯定選擇第三種情況.
確定了使用的方法(哈希表)以及分類的方法(兩兩分組), 接下來就是代碼的書寫了. 此題和 兩數之和 中使用的哈希表有著很大的區別, 在兩數之和中, 我們需要的是滿足條件的下標值, 所以在哈希表中的值存取的就是元組的下標值, 這點是很容易實作的. 但是在此題中我們需要的是所有滿足元素的個數, 所以哈希表中的值應存取出現的次數. 這相對于只存下標是有點難度的. 這就涉及到下文要講的幾個方法和類了.
2.Java中map的merge和getOrDefault方法
統計出現的次數, 在java中可以使用map類中的兩個方法進行實作.
一種是countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1), 這里比較重要的是getOrDefault(u + v, 0)方法, 它的含義是獲得鍵u + v對應的值, 也就是出現的次數, 如果當然哈希表中未出現, 則回傳默認值0. 通過后面的+1操作, 實作在現有次數上+1或者初始化次數為1, 然后將這個鍵值對放入到哈希表中.
另一種方法是countAB.merge(u+v, 1, (old,new_)->old+1), 這里使用了merge方法, 從名字就可以看出是 合并 的意思, 也就是將新出現的鍵值對和原來已有的鍵值對進行合并, 形成新的鍵值對. 中間的1表示如果原來沒有此鍵值對, 那么這個新鍵值對的值就是1(出現次數為1次). 最后的引數表示了新的值的相對于舊的值的變化情況, 這里就是+1的操作. 有一點要主要的是new_有個下劃線, 因為在java中new是創建物件的關鍵詞, 這里是為了區別開來. 這個函式的語法就是上文所示那樣, 具體的操作情況都可以根據實際來更改.
3.Python中的Counter類
在Python中哈希表是利用dict()字典來實作的, 但畢竟不是專為哈希表設計的類, 也沒有那么豐富的方法來使用. 但是Python中直接設計了能夠對哈希物件進行計數的類, 并且在功能上更加優秀, 下面我們重點介紹一下這個類.
3.1 簡介
1.一個 Counter 是一個 dict 的子類, 用于計數可哈希物件，它是一個集合, 元素像字典鍵(key)一樣存盤, 它們的計數存盤為值，計數可以是任何整數值, 包括0和負數.
2.通常字典方法都可用于 Counter 物件,除了有兩個方法作業方式與字典并不相同
fromkeys(iterable)這個類方法沒有在 Counter 中實作
update([iterable-or-mapping]是在原有的鍵值對上加上,而不是替換
sum(c.values()) # total of all counts
c.clear() # reset all counts
list(c) # list unique elements
set(c) # convert to a set
dict(c) # convert to a regular dictionary
c.items() # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs)) # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1] # n least common elements
+c # remove zero and negative counts3.2 初始化
元素從一個 iterable 被計數或從其他的 mapping (or counter)初始化
c = Counter() # a new, empty counter
c = Counter('gallahad') # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2}) # a new counter from a mapping
c = Counter(cats=4, dogs=8) # a new counter from keyword args3.3 空的處理
Counter物件有一個字典介面,如果參考的鍵沒有任何記錄,就回傳一個0,而不是彈出一個KeyError
c = Counter(['eggs', 'ham'])
c['bacon'] # count of a missing element is zero
03.4 洗掉元素
設定一個計數為0不會從計數器中移去一個元素，使用 del 來洗掉它
c['sausage'] = 0 # counter entry with a zero count
del c['sausage'] # del actually removes the entry3.5 elements()方法
回傳一個迭代器, 其中每個元素將重復出現計數值所指定次，元素會按首次出現的順序回傳，如果一個元素的計數值小于1, elements()將會忽略它
c = Counter(a=4, b=2, c=0, d=-2)
sorted(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']3.6 most_common([n])方法
回傳一個串列, 其中包含 n 個最常見的元素及出現次數, 按常見程度由高到低排序， 如果 n 被省略或為 None, most_common()將回傳計數器中的所有元素，計數值相等的元素按首次出現的順序排序
Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]3.7 subtract([iterable-or-mapping])方法
從 迭代物件 或 映射物件 減去元素，像dict.update()但是是減去, 而不是替換，輸入和輸出都可以是0或者負數
c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d)
c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})3.8 數學操作
提供了幾個數學操作, 可以結合 Counter 物件, 以生產multisets (計數器中大于0的元素)，
加和減, 結合計數器, 通過加上或者減去元素的相應計數，
交集和并集回傳相應計數的最小或最大值，
每種操作都可以接受帶符號的計數, 但是輸出會忽略掉結果為零或者小于零的計數
sum(c.values()) # total of all counts
c.clear() # reset all counts
list(c) # list unique elements
set(c) # convert to a set
dict(c) # convert to a regular dictionary
c.items() # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs)) # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1] # n least common elements
+c # remove zero and negative counts3.9 注意點
1.計數器主要是為了表達運行的正的計數而設計；但是, 小心不要預先排除負數或者其他型別
2.Counter 類是一個字典的子類,不限制鍵和值，值用于表示計數, 但你實際上可以存盤任何其他值
3.most_common()方法在值需要排序的時候用
4.原地操作比如 c[key] += 1, 值型別只需要支持加和減，所以分數,小數,和十進制都可以用, 負值也可以支持，這兩個方法update()和subtract()的輸入和輸出也一樣支持負數和0
5.Multiset多集合方法只為正值的使用情況設計，輸入可以是負數或者0, 但只輸出計數為正的值，沒有型別限制, 但值型別需要支持加, 減和比較操作
6.elements()方法要求正整數計數，忽略0和負數計數
4.總結
1.看到形如：A+B....+N=0的式子,要轉換為(A+...T)=-((T+1)...+N)再計算,這個T的分割點一般是一半,特殊情況下需要自行判斷，定T是解題的關鍵
2.dp一般不會超過二維, 這里都四維了, 維度太高, 需要分治
3.演算法中間使用了map的新方法merge和getOrDefault, 相比較于傳統的判斷寫法, 大大提高了效率
原始碼
Python:
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
# Counter類是dict()子類, 用于計數可哈希物件
# 它是一個集合,元素像字典鍵(key)一樣存盤,它們的計數存盤為值
countAB = collections.Counter(u + v for u in A for v in B)
ans = 0
for u in C:
for v in D:
if -u - v in countAB:
ans += countAB[-u - v]
return ansjava:
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
for (int u : A) {
for (int v : B) {
// 存盤u+v的結果,不存在賦值為1,存在在原來基礎上+1
// 另一種表達countAB.merge(u+v, 1, (old,new_)->old+1);
countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
}
}
int ans = 0;
for (int u : C) {
for (int v : D) {
if (countAB.containsKey(-u - v)) {
ans += countAB.get(-u - v);
}
}
}
return ans;
}
}感覺作者寫的不錯的, 別忘了點贊關注加收藏哦(一鍵三連)!你的支持會帶給我極大的動力, 寫出更多優秀文章!
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 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的性能情況和常見后綴的含義 思維導圖整理
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295158.html
標籤：java