如果你已經對數據結構與算法略知一二,現在正在復習數據結構與算法的一些重點知識
-------------------------------------------------------------------------------------------------------------------------
點贊+收藏🌈,每天更新總結文章(多以圖文形式,方便記憶,均為網上搜集資料以及AI)?
-------------------------------------------------------------------------------------------------------------------------
時間:2025/5/23/ 19: 40分
-----------------------------------種一棵樹最好的機會是十年前,其次是現在
博主鏈接:黎明smaly-CSDN博客
快來參與討論💬,點贊👍、收藏?、分享📤,共創活力社區
一、LeetCode 283.移動零
方法一:
- 題目中,要求我們在原數組進行原地操作,所以先排除哈希這些
- 一般對于數組的題,要求原地進行的,首先考慮雙指針
- 這道題我們采用雙指針,我們定義一個左指針和一個右指針,這里的指針可以采用下標的方式進行,而不是真正意義上的指針變量
- 左右指針同時指向第一個元素
- 右指針先走,如果碰到0,繼續走++,如果碰到非0,也就是我們要的元素,則將他賦值給左指針對應的元素,左指針才走++
- 走到右指針走到結尾為止,這樣,我們就拿到了所有的非0元素,并且相對順序不變
- 只不過 后面的元素還不是0,最好我們需要把循環方式把剩下的元素賦值成0
代碼:
時間復雜度:? ? ? ? ? ? ? ? O(N) N是數組的長度
空間復雜度:
? ? ? ? ? ? ? ? O(1)
二、LeetCode 11.盛最多水的容器
方法一:
- 看到跟數組相關的,又是求某個階段最大/最小值問題的,我們可以考慮貪心算法
- 我們還是采用雙指針的方式,左,右指針,左指針指向開頭,右指針指向結尾
- 此時這兩個指針間,最大可容納水為 min(1,7)*8 = 1*8=8 (按示例圖來的)
- 然后我們將這個最大值記錄下來,此時就知道了一個局部解
- 移動指針,移動數字小的那個指針,只有數字小的移動,才能找到更大值,不然最大空間一直卡在了數字小的上面,因為有瓶頸
- 移動完繼續計算最大可容納水量 min(8, 7) * 7 = 1*7 = 7
- 此時又拿到了一個局部解,將其與上一次的進行判斷,大的存到我們定義的最大值變量里面,等下一次判斷繼續用
- 不斷這樣循環,如果兩個指針值相同,那么可以隨便移動一個
- 直到左右指針重合,此時最大值變量里面存的就是最大可容納水量
代碼:
時間復雜度:
? ? ? ? ? ? ? ? O(N) N是數組長度
空間復雜度:
? ? ? ? ? ? ? ? O(1)
三、LeetCode 15.三數之和
先仔細看題目,明白題意,再做題
方法一:
- 如果我們按照暴力枚舉的方式,需要O(N^3)次方時間復雜度,并且我們最后還有去重
- 我們尋找新的思路,簡化一些,我們發現題目無非是要求找出數組中三數之和=0的,
此時就能想到了有一道題叫兩數之和,也是數組的- 我們寫第一層循環,來找第一個數,其余的兩個數我們當作兩數之和這道題來做,
第一個數找到后,其余兩數之和就是 0-第一個數- 我們首先要對數組進行排序,排序是為了去重,也是為了更好的求兩數
- 寫第一層for循環,找到每個三元組的第一個數
第二層循環 設置左右雙指針,左指針指向第一個數右邊的數也就是i+1,右指針指向尾巴
?判斷左指針+右指針是否0-第一個數,如果等于,則找到了第一個三元組
如果!=0,且大于0-第一個數,則代表值大了,右指針向左移動,因為已經排序過了,右邊的值是最大值,所以它移動一位變小一點
然后繼續判斷,如果值小了就左指針向右移動一位變大些- 如此下去,就能找到所有的三元組,然后我們要處理去重的問題
我們在上面的基礎下加一些判斷條件即可,找到一個三元組后,左右指針分別移動到跟當前值相比的非重復值上,去重代碼:
時間復雜度:
? ? ? ? ? ? ? ? O(N^2)
空間復雜度:
? ? ? ? ? ? ? ? O(logN)?
總結:?
這三道題都是跟雙指針有關的
對于雙指針的使用要熟悉
加油,為了更好的明天!
種一棵樹最好的機會是十年前,其次是現在