目錄
- LeetCode Python實作演算法簡介
- 0001 兩數之和
- 0002 兩數相加
- 0003 無重復字符的最長子串
- 0004 尋找兩個有序陣列的中位數
- 0005 最長回文子串
- 0006 Z字型變換
- 0011 盛最多水的容器
- 0015 三數之和
- 0016 最接近的三數之和
- 0026 洗掉排序陣列中的重復項
- 0027 移除元素
- 0031 下一個排列
- 0033 搜索旋轉排序陣列
- 0034 在排序陣列中查找元素的第一個和最后一個位置
- 0035 搜索插入位置
- 0039 組合總和
- 0040 組合總和II
- 0041 缺失的第一個正數
LeetCode Python實作演算法簡介
邊刷邊記邊總結，歡迎討論與指導，持續更新
代碼倉庫
0001 兩數之和
-
初始化一個字典 numtarget（哈希表、散串列），用來存盤“若我需要 derta 湊成目標值，則應該尋找陣列第 i 項”，即 numtarget[derta] = i
-
從前至后遍歷陣列，計算目標值 target 與當前整數 num 的差值 derta
-
查找 numtarget ，若已有 derta 記錄則回傳 i ，否則把 derta 與當前元素位置插入 numtarget
0002 兩數相加
-
初始化一個鏈表 result ，只含有一個節點，賦值為零，用來存放計算和
-
對 l1 和 l2 從表頭開始逐節點相加，有四種情況：
-
不產生進位，且 l1 或 l2 有后繼節點，將無后繼節點鏈表表尾補零節點，繼續計算
-
不產生進位，且 l1 和 l2 均無后繼節點，計算后結束
-
產生進位，且 l1 或 l2 有后繼節點，將無后繼節點鏈表表尾補零節點，繼續計算，下一輪計算結果 +1
-
產生進位，且 l1 和 l2 均無后繼節點，在result鏈表表尾補節點，取值為 1
-
0003 無重復字符的最長子串
-
初始化兩個指標 a, b 指向第一個字符, 子串 substr, 表示指標 a， b 之間的子串，初始為空, 和最長子串長度 maxlen = 0
-
將指標 b 逐個后移
-
若 b 不在子串中，說明無重復字符，則將 b 加入 substr
-
若 b 在子串中，則找到 substr 中 "b" 的位置 i， 將 a 移動到 i+1 的位置，更新子串substr
-
-
指標 b 每后移一次，判斷一次當前子串長度 len(substr) 與 maxlen 的大小關系
0004 尋找兩個有序陣列的中位數
暫略
0005 最長回文子串
可以暴力列舉，可以使用中心擴展演算法，但使用 manacher 演算法可使時間復雜降低至 O(n)
-
定義回文半徑陣列 radius，最右回文邊界 r，最右回文邊界的對稱中心 c
-
遍歷陣列，有兩種情況：
-
移動位置 i 在最大回文邊界 r 的右邊，那么以 i 為中心，向兩邊擴展，更新回文半徑陣列 radius[i]，對稱中心 c = i
-
移動位置 i 在最大回文邊界 r 的左邊或者在邊界上，定義 i' 為與 i 關于 c 對稱的點，il' 是以 i' 為中心的最長回文陣列左邊界， cl 是以 c 為中心的最長回文陣列左邊界，此時有三種情況：
-
i'l < cl，則位置 i 處的最長對稱半徑為 r - i + 1
-
i'l > cl，則位置 i 處的最長對稱半徑為 radius[i'l]
-
i'l = cl，則向最大回文邊界 r 向右擴展，更新最大回文邊界和對稱中心
-
-
-
找到 radius 的最大值，推算子串
0006 Z字型變換
-
若指定行數小于等于 1，直接回傳原字串
-
將給定字串 s 逐個寫入， toword 指示方向，當行數為 0 或者 numRows - 1 時反向
-
按行拼接字串
0011 盛最多水的容器
利用雙指標
-
初始化兩個指標，分別指向陣列頭尾，計算當前兩個數字的盛水面積
-
調整數值較小的指標，當指標數字大于之前指標數字時，計算當前兩個數字的盛水面積，比較記錄更大值
-
按照 2 中規則遍歷所有數字，得到最大值
0015 三數之和
兩種解體思路
-
輪流做中，即遍歷陣列，然后簡化為兩數之和問題
-
雙指標，將陣列排序后，利用雙指標遍歷，剪枝
0016 最接近的三數之和
與0015題類似，將判斷標準改變為三數之和與目標值的差值最小
0026 洗掉排序陣列中的重復項
雙指標法
-
初始化兩個指標 i，j，起始位置都在陣列頭部
-
用 j 遍歷陣列，若 nums[j] = nums[i]，跳過，若不相等，則令 nums[i] = nums[j]
0027 移除元素
雙指標法
-
初始化兩個指標 i = -1，j = 0
-
用 j 遍歷陣列，若等于指定值則跳過，否則將值賦給指標 i
0031 下一個排列
-
從后往前，找到第一個滿足 nums[i] > nums[i-1] 的數字
-
在 nums[i:] 中，找到大于 nums[i-1] 的最小數字，交換兩數，此時 nums[i:] 為降序排列
-
原地置逆 nums[i:]，此時即找到下一個排列
-
若 1 中不存在滿足條件的數字，將整個陣列原地置逆
0033 搜索旋轉排序陣列
-
要求時間復雜度為O(logn)，想到二分查找，取中間的元素 nums[m]
-
若 nums[m] < nums[r]，則中間元素落在后半段，此時，若 nums[m] < target < nums[r]，則 target 在 nums[m] 右側，否則在左側
-
若 nums[m] > nums[r]，則中間元素落在前半段，此時，若 nums[l] < target < nums[m]，則 target 在 nums[m] 左側，否則在右側
0034 在排序陣列中查找元素的第一個和最后一個位置
-
第一個二分查找，找到陣列中是否存在 target ,有回傳位置 numposition ，無回傳 [-1, -1]
-
在 numposition 左右分別二分查找，尋找開始位置和結束位置
0035 搜索插入位置
-
二分查找，若找到 target ，則回傳位置，否則執行第二步
-
二分查找未果的最后一步時， 有 l = r = m，即左、右、中重合，因為陣列是有序的，若 nums[m] > target, 則應在 m 處插入，否則在 m + 1 處插入
0039 組合總和
-
將陣列按非遞減排序
-
假設某元素 num 已在組合中，那么組合中其它元素和為 target-num，則原問題分解為 n 個小問題，n 表示陣列長度
-
由于每個元素可重復使用，但組合不能重復，則根據排序后的陣列，下一步迭代從元素自身位置開始，即忽略掉小于自身的元素，這部分元素若構成組合，應已經包含在本層迭代小于自身的元素組合中
0040 組合總和II
與0039類似，進一步剪枝，區別有兩點：
-
每個元素不可重復，下一步迭代從下一個元素開始
-
陣列中可能有相同元素，因此同層元素相同時，剪枝
0041 缺失的第一個正數
使用常數級別的空間，意味著需要在對陣列本身進行操作
-
遍歷陣列，把 nums 中，數值為 i 的值放在 i-1 的位置，比如，若 num[i] 取值在 0~i 之間，那么將位置 i 處的元素 num[i] 與 位置在 num[i] 處的元素 nums[nums[i]]交換位置，直到位置 i 處的元素取值不在 0~i 之間
-
第二次遍歷陣列，若 nums[i] != i + 1，則缺失的第一個正數為 i + 1
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79593.html
標籤：其他
下一篇：字串匹配演算法 之BF、KMP