d1
leet1: 兩數(shù)之和
https://leetcode-cn.com/problems/two-sum
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
【hashmap存儲(chǔ)】
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 邊界值判斷
if not nums or target == None:
return []
has = {} # hash型map存值對(duì)應(yīng)的"索引"
for i, num in enumerate(nums):
if target - num in has:
return [has[target - num], i]
has[num] = i
return []
leet4: 兩個(gè)數(shù)組中的中位數(shù)
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2夺鲜。
請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)单起，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))炊甲。
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
【奇偶判斷】
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if not nums1 and not nums2:
return None
nums = []
nums.extend(nums1)
nums.extend(nums2)
nums.sort()
# 偶數(shù)個(gè)數(shù)情況欧芽，求均值新蟆；"http://"獲取整數(shù)索引
return nums[len(nums)//2] if len(nums) % 2 else (nums[len(nums)//2] + nums[len(nums)//2 - 1]) / 2
leet5: 最長(zhǎng)回文子串
給定一個(gè)字符串 s训柴，找到 s 中最長(zhǎng)的回文子串缸濒。你可以假設(shè) s 的最大長(zhǎng)度為 1000宝惰。
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案植榕。
【雙循環(huán)貪心】
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) <= 1:
return s
# 最大長(zhǎng)度開始判別，符合條件的字符串即最大回文子串
for length in range(len(s), 0, -1): # len(s)次尼夺，倒序
for i in range(0, len(s) - length + 1):
newS = s[i : i + length]
if newS == newS[::-1]: # '反轉(zhuǎn)'判別
return newS
d2
leet9: 回文數(shù)
判斷一個(gè)整數(shù)是否是回文數(shù)内贮。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)汞斧。
輸入: 121
輸出: true
【折半比較】
class Solution:
def isPalindrome(self, x: int) -> bool:
if x == None:
return False
if len(str(x)) <= 1:
return True
# 折半搜索
for i in range(len(str(x)) // 2):
if str(x)[i] != str(x)[-i - 1]:
return False
return True
leet409 最長(zhǎng)回文串
給定一個(gè)包含大寫字母和小寫字母的字符串夜郁，找到通過這些字母構(gòu)造成的最長(zhǎng)的回文串。
在構(gòu)造過程中粘勒，請(qǐng)注意區(qū)分大小寫竞端。比如 "Aa" 不能當(dāng)做一個(gè)回文字符串。
注意:
假設(shè)字符串的長(zhǎng)度不會(huì)超過 1010庙睡。
示例：
輸入:
"abccccdd"
輸出:
7
【集合更新與判空】(add remove, 放入可回文的字符事富，無重復(fù))
class Solution:
def longestPalindrome(self, s: str) -> int:
if len(s) < 2:
return len(s)
num = 0
set0 = set()
for i in s:
if i in set0: # 有兩個(gè)字符則能組成回文
set0.remove(i)
num += 2
else:
set0.add(i) # 更新可回文元素
# 只要還有沒有移除的set0元素，就更新元素個(gè)數(shù)+1
return num + 1 if len(set0)!=0 else num
leet10: 正則表達(dá)式匹配
給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p乘陪，請(qǐng)你來實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配统台。
'.' 匹配任意單個(gè)字符
'*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配，是要涵蓋 **整個(gè) **字符串 s的啡邑，而不是部分字符串贱勃。
說明:
-
s可能為空，且只包含從a-z的小寫字母。 -
p可能為空贵扰，且只包含從a-z的小寫字母仇穗，以及字符.和*。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個(gè)字符串戚绕。</pre>
【正則包與結(jié)果項(xiàng)】
import re
class Solution:
def isMatch(self, s:str, p:str)->bool:
if re.match(p, s):
return re.match(p, s).group() == s
return False
d3
leet26: 刪除排序數(shù)組的重復(fù)項(xiàng)
給定一個(gè)排序數(shù)組纹坐，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次舞丛，返回移除后數(shù)組的新長(zhǎng)度俊扳。
不要使用額外的數(shù)組空間走贪，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成枚赡。
示例:
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2膝宁。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
【新計(jì)數(shù)索引】
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
count = 0
# 修改數(shù)組欧聘，同時(shí)計(jì)數(shù)
for i in range(1, len(nums)): # 第0個(gè)一定不排除
if nums[i] != nums[count]:
count += 1
nums[count] = nums[i] # 僅需修改前若干個(gè)元素為關(guān)不重復(fù)元素即可片林，后面元素不改變
# 返回排序數(shù)組中不重復(fù)的元素個(gè)數(shù)
return count + 1
leet27: 移除元素
給定一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val 的元素怀骤，返回移除后數(shù)組的新長(zhǎng)度费封。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成蒋伦。
元素的順序可以改變弓摘。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2痕届。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素韧献。
【while val存在】
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if not nums:
return None
# while循環(huán)存有目標(biāo)的情況，不斷刪除
while val in nums:
nums.remove(val)
return len(nums)
leet28: strStr()
實(shí)現(xiàn) strStr() 函數(shù)：
給定一個(gè) haystack 字符串和一個(gè) needle 字符串研叫，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)锤窑。如果不存在，則返回 -1嚷炉。
示例:
輸入: haystack = "hello", needle = "ll"
輸出: 2
【str.index(p)】
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# 判斷needle的存在性渊啰，后檢測(cè)初始出現(xiàn)位置
return haystack.index(needle) if needle in haystack else -1
d4
leet50: pow(x, n)
【分支遞歸乘數(shù)】
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
elif n < 0:
return 1 / self.myPow(x, -n) # 調(diào)用自身
# 奇數(shù)情況
elif n % 2:
return x * self.myPow(x, n - 1)
# 減少為一般乘數(shù)
return self.myPow(x * x, n / 2)
leet303: 區(qū)域和檢索-數(shù)組不變情況【線段樹】
給定一個(gè)整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j (i ≤ j) 范圍內(nèi)元素的總和申屹，包含 i, j 兩點(diǎn)绘证。
給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數(shù)為 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
【緩存和】
class NumArray:
# 緩存機(jī)制便于快速查找區(qū)間和哗讥，不超時(shí)
def __init__(self, nums: List[int]):
self.nums = [0] + nums # 前加入0便于防止0越界：self.nums[j] - self.nums[i - 1]
# 從1開始求和, 更新self.nums
for i in range(1, len(self.nums)): # 更新的數(shù)組長(zhǎng)度不變
self.nums[i] = self.nums[i - 1] + self.nums[i]
def sumRange(self, i: int, j: int) -> int:
if not self.nums:
return 0
return self.nums[j + 1] - self.nums[i] # 索引向前+1
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
leet487：最大連續(xù)1的個(gè)數(shù)
給定一個(gè)二進(jìn)制數(shù)組嚷那，你可以最多將 1 個(gè) 0 翻轉(zhuǎn)為 1，找出其中最大連續(xù) 1 的個(gè)數(shù)杆煞。
輸入：[1,0,1,1,0]
輸出：4
解釋：翻轉(zhuǎn)第一個(gè) 0 可以得到最長(zhǎng)的連續(xù) 1魏宽。
當(dāng)翻轉(zhuǎn)以后腐泻，最大連續(xù) 1 的個(gè)數(shù)為 4。
【最近0的出現(xiàn)位置】
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
if nums == None:
return 0
maxNum, num = 0,0
lastZero = -1
# 遍歷更新0的最近出現(xiàn)位置湖员，與更新后的1計(jì)數(shù)num贫悄，與更改后的1個(gè)數(shù)maxNum
for i in range(len(nums)):
if nums[i] == 1:
num += 1
else:
maxNum = max(maxNum, num)
num = i - lastZero # 更新最近出現(xiàn)的0的位置
lastZero = i
return max(maxNum, num)
d5
leet507: 完美數(shù)
對(duì)于一個(gè) 正整數(shù)瑞驱，如果它和除了它自身以外的所有正因子之和相等娘摔，我們稱它為“完美數(shù)”
輸出: True
解釋: 28 = 1 + 2 + 4 + 7 + 14
【折平根比較】
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num == None or num == 1:
return False
i = 2
sum0 = 1 # 任何的數(shù)都有因數(shù)1
# 折平方根搜索
while i * i <= num:
if num % i == 0:
sum0 += num / i + i
i += 1
return sum0 == num
leet665： 非遞減數(shù)列
修改一個(gè)數(shù)，則變成非遞減數(shù)列唤反，輸出True
【嵌套條件分支】
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
if nums == None:
return False
count = 0
for i in range(len(nums)-1):
if nums[i] > nums[i + 1]: # 兩種情況只能出現(xiàn)一遍
# 大數(shù)(i位置)變小(i+1位置)
if i == 0 or nums[i + 1] > nums[i - 1]: # 4(i=0時(shí)) 2 1 or 2 4(i) 3
nums[i] = nums[i + 1]
# 小數(shù)(i+1位置)變大(i位置)
else: # 2 2(i) 1 3
nums[i + 1] = nums[i]
count += 1
return count <= 1
leet400: 第N個(gè)數(shù)字
123456789101112...求出第N個(gè)數(shù)字對(duì)應(yīng)的單字符數(shù)值
【while True中的數(shù)量級(jí)t和求解條件m】
class Solution:
def findNthDigit(self, n: int) -> int:
if n == None or n <= 0:
return None
# 9: t=1 m=9 9≤9:n=8 return '9'(1+8)[0]即0
# 19: t=1 m=9 n=10 i=2;t=10 m=180 n≤180 n=9 return '14'(10+9//2)[9%2]即4
i = 1
while True:
# 數(shù)量級(jí)遞增
t = 10 ** (i - 1)
# 求解終止條件凳寺，9 180
m = t * 9 * i
# m作為求解出口t條件
if n <= m:
n -= 1
return int(str(t + n // i)[n % i])
n -= m
i += 1
d6
leet219: 存在重復(fù)元素ii
列表中存在最大長(zhǎng)度為k的兩個(gè)相等的數(shù)，則返True
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k彤侍，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j肠缨，使得 nums [i] = nums [j]，并且 i 和 j 的差的絕對(duì)值最大為 k盏阶。如輸入: nums = [1,2,3,1], k = 3晒奕， 輸出: true
【集合表示滑動(dòng)窗口】
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
if not nums or k == None:
return False
set0 = set() # set存儲(chǔ)兩個(gè)規(guī)定距離的相等值
for i in range(len(nums)):
if nums[i] in set0: # 唯一的判別條件
return True
set0.add(nums[i]) # 添加元素【add】
# 只允許k長(zhǎng)度內(nèi)的元素存在集合內(nèi)，否則刪除最先進(jìn)入集合中的第i-k個(gè)元素名斟。
# 如:1 2 3(i處) 2 k=2
# 集合中元素?cái)?shù)超過k !
if len(set0) > k:
set0.remove(nums[i - k])
return False
leet面試題22: 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
返回鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)脑慧，如1->2->3->4->5, k = 2：
q先走2步，之后p/q一共走4步p指向4=>輸出4->5
【雙指針追蹤】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if not head or k <= 0:
return None
p = head
q = head
for _ in range(k):
q = q.next
# p最后倒數(shù)的位置與k循環(huán)的次數(shù)(q之前走過的長(zhǎng)度)相同
while q:
q = q.next
p = p.next
return p
leet1346: 整數(shù)及其兩倍數(shù)是否存在
兩個(gè)數(shù)不是同一個(gè)數(shù)砰盐，存在某數(shù)2倍數(shù)的一個(gè)數(shù)則返回True
【判雙零】
class Solution:
def checkIfExist(self, arr: List[int]) -> bool:
if not arr:
return False
if 0 in arr:
arr.remove(0)
if 0 in arr: # 兩個(gè)零存在才滿足條件
return True
for i in range(len(arr)):
if 2 * arr[i] in arr:
return True
return False
d7
leet415: 字符串相加
兩個(gè)數(shù)值型字符串闷袒，相加后返回結(jié)果字符串
【while中低位進(jìn)位】
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
if not num1:
return num2
elif not num2:
return num1
i, j = len(num1)-1, len(num2)-1
carry = 0 # 進(jìn)位數(shù)
res = ''
# 只要還有沒有相加完成的位， 9 + 99 = 108
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0 # 沒有位參加運(yùn)算則賦0
n2 = int(num2[j]) if j >= 0 else 0
tmp = n1 + n2 + carry
carry = tmp // 10 # 高位
res = str(tmp % 10) + res # 低位
i -= 1
j -= 1
# 最終含有進(jìn)位則添加結(jié)果項(xiàng)中的進(jìn)位
return '1' + res if carry else res
# -----or 直接簡(jiǎn)化的int()轉(zhuǎn)換--------
return str(int(num1) + int(num2))
leet1026: 節(jié)點(diǎn)與其祖先之間的最大差
求節(jié)點(diǎn)與其祖先之間的最大差岩梳，如：
輸入：[8,3,10,1,6,null,14,null,null,4,7,13]
輸出：7
解釋：
我們有大量的節(jié)點(diǎn)與其祖先的差值囊骤，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出
【左右遞歸dfs返回最大差】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
def dfs(node, ma = -999999, mi = 999999):
if not node:
return ma - mi
# 遞歸
l = dfs(node.left, max(ma, node.val), min(mi, node.val))#祖先與左孩子的最大差
r = dfs(node.right, max(ma, node.val), min(mi, node.val))
return max(l, r)
return dfs(root)
leet135：分發(fā)糖果
一排人領(lǐng)糖果, 相鄰的人rating高的獲得較多糖冀值，每人都有糖果也物。
老師想給孩子們分發(fā)糖果，有 N 個(gè)孩子站成了一條直線列疗，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)滑蚯，預(yù)先給他們?cè)u(píng)分。
你需要按照以下要求作彤，幫助老師給這些孩子分發(fā)糖果：
每個(gè)孩子至少分配到 1 個(gè)糖果膘魄。
相鄰的孩子中，評(píng)分高的孩子必須獲得更多的糖果竭讳。
那么這樣下來创葡，老師至少需要準(zhǔn)備多少顆糖果呢？如輸入: [1,0,2], 輸出: 5
解釋: 你可以分別給這三個(gè)孩子分發(fā) 2绢慢、1灿渴、2 顆糖果洛波。
【左右規(guī)則】
class Solution:
def candy(self, ratings: List[int]) -> int:
if not ratings:
return 0
left = [1 for _ in range(len(ratings))] # 每人一顆糖
right = left[:] # 復(fù)制一份left列表，【非引用】
# 左右規(guī)則均從(倒數(shù))第二個(gè)數(shù)開始與之前比較
# 左規(guī)則: 初始每個(gè)人都有糖骚露，從左向右遍歷1~len(ratings)-1索引的元素
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
left[i] = left[i - 1] + 1
# 右規(guī)則: 初始count為最右邊的元素值蹬挤，從右到左, 0~len(ratings)-2索引的元素
count = left[-1]
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
right[i] = right[i + 1] + 1
# 取左右規(guī)則中最大的糖果數(shù)累加
count += max(left[i], right[i])
return count
d8
leet面試02.02: 倒數(shù)第k個(gè)節(jié)點(diǎn)值
返回鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)值
【雙指針追蹤】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
if not head or k<=0:
return None
# 雙指針測(cè)量路徑長(zhǎng)
p = head
q = head
for _ in range(k):
q = q.next
while q:
q = q.next
p = p.next
return p.val
leet面試04.04/ 55: 平衡二叉樹
是否平衡二叉樹，即任意一個(gè)節(jié)點(diǎn)其兩顆子樹的高度差不超過一棘幸。
【遞歸返回是否平衡和樹高】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
# 返回當(dāng)前是否平衡樹與高度差
def check(node):
if not node:
return True, 0 # 空樹是平衡樹焰扳，高度差為0
lres, lheight = check(node.left)
rres, rheight = check(node.right)
# 分別返回是否當(dāng)前為平衡樹、當(dāng)前樹高(在子樹高度基礎(chǔ)上加一)
return lres and rres and abs(lheight - rheight) <= 1, max(lheight, rheight) + 1
# 返回結(jié)果中第一個(gè)值
return check(root)[0]
leet2/leet面試02.05: 鏈表求和
【三重while中低位進(jìn)位】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ''
carry = 0
# 鏈表的首位對(duì)應(yīng)數(shù)值的低位误续，即從鏈表收為開始計(jì)數(shù)吨悍、進(jìn)位
while l1 and l2:
n1 = l1.val
n2 = l2.val
tmp = n1 + n2 + carry
carry = tmp // 10
res = str(tmp % 10) + res
l1 = l1.next
l2 = l2.next
while l1:
n1 = l1.val
tmp = n1 + carry
carry = tmp // 10
res = str(tmp % 10) + res
l1 = l1.next
while l2:
n2 = l2.val
tmp = n2 + carry
carry = tmp // 10
res = str(tmp % 10) + res
l2 = l2.next
res = '1' + res if carry else res
# 反向輸出
head = ListNode(0)
p = head
for i in range(len(res)-1, -1, -1):
p.next = ListNode(res[i])
p = p.next
return head.next
d9
leet面試18: 刪除鏈表中節(jié)點(diǎn)
刪除鏈表中的節(jié)點(diǎn)
【制造偽頭結(jié)點(diǎn)】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head:
return None
# 情況一：刪除頭結(jié)點(diǎn)
if head.val == val:
return head.next
# 情況二：非頭結(jié)點(diǎn)
dummy = head # 制造偽頭結(jié)點(diǎn)
while head and head.next:
if head.next.val == val: # 與head.next.val比較
head.next = head.next.next
head = head.next # 逐次向后
return dummy
# --------------------or 類似【leet203的移除鏈表中所有元素，遞歸】------------
if not head:
return None
head.next = self.deleteNode(head.next, val)
return head.next if head.val == val else head
leet面試32: 從上到下之字形打印二叉樹
之字形層次遍歷二叉樹蹋嵌，如:
3
/ \
9 20
/ \
15 7
返回其層次遍歷結(jié)果：
[
[3],
[20,9],
[15,7]
]
【遞歸含層數(shù)的層次遍歷與折返判斷】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
# 層次遍歷
def output(node, level):
if not root:
return
list0 = [[]] # 二維數(shù)組
# 奇偶行賦值
if level % 2:
list0[level - 1].append(node.val) # 奇數(shù)行索引從0開始
else:
list0[level - 1].insert(0, node.val) # 偶數(shù)行索引為奇數(shù)育瓜，頭插法放入列表中
# 本行初始為空列表
if len(list0) == level:
list0.append([])
output(node.left, level + 1)
output(node.right, level + 1)
output(root, 1)
return list0[:-1] # 列表元素集中除去最后一個(gè)
leet724: 尋找數(shù)組的中心索引
如果一個(gè)數(shù)的左邊數(shù)組和與右邊數(shù)組和相等，則返回此中間數(shù)的索引栽烂。
【從左累加與總和比較】
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
if not nums:
return -1
lsum, sum0 = 0, 0
for i in range(len(nums)):
sum0 += nums[i]
# 左規(guī)則: 左邊累計(jì)和加上下一個(gè)元素的和等于總和躏仇，則下一個(gè)索引是所求
for i in range(len(nums)):
if sum0 == lsum * 2 + nums[i]:
return i
lsum += nums[i]
return -1
d10
leet面試27: 二叉樹的鏡像
輸出二叉樹的鏡像， 如：
輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
鏡像輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
【制造臨時(shí)節(jié)點(diǎn)的自身遞歸】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root:
return
# 遞歸自身
node0 = root.left # 創(chuàng)建臨時(shí)節(jié)點(diǎn)腺办，防止左節(jié)點(diǎn)被覆蓋
root.left = self.mirrorTree(root.right)
root.right = self.mirrorTree(node0) # 防止左節(jié)點(diǎn)被覆蓋
return root
leet107: 層次遍歷二叉樹
自底向上遍歷二叉樹焰手，如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的層次遍歷為：
[
[15,7],
[9,20],
[3]
]
【遞歸層次遍歷】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
list0 = [[]] # 新建二維數(shù)組
def output(node, level):
if not node:
return
# 賦值節(jié)點(diǎn)進(jìn)入二維數(shù)組
list0[level - 1].append(node.val)
# 當(dāng)前層已有賦值，則新增下一層的節(jié)點(diǎn)賦值空間
if len(list0) == level:
list0.append([])
output(node.left, level + 1)
output(node.right, level + 1)
output(root, 1)
# list0[:-1]后反轉(zhuǎn)列表
return list0[:-1][::-1]
leet662: 二叉樹的最大寬度
給定一個(gè)二叉樹菇晃，編寫一個(gè)函數(shù)來獲取這個(gè)樹的最大寬度册倒。樹的寬度是所有層中的最大寬度。
這個(gè)二叉樹與滿二叉樹（full binary tree）結(jié)構(gòu)相同磺送，但一些節(jié)點(diǎn)為空驻子。
每一層的寬度被定義為兩個(gè)端點(diǎn)（該層最左和最右的非空節(jié)點(diǎn)，兩端點(diǎn)間的null節(jié)點(diǎn)也計(jì)入長(zhǎng)度）之間的長(zhǎng)度估灿。如輸入:
1
/ \
3 2
/ \ \
5 3 9
輸出: 4
解釋: 最大值出現(xiàn)在樹的第 3 層崇呵，寬度為 4 (5,3,null,9)。
【含hashmap[depth]的dfs遞歸】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
hashmap = {} # hashmap初始, 外部變量記錄每層的寬度
def dfs(node, width, depth):
if not node:
# 沒有節(jié)點(diǎn)則寬度返回0
return 0
if depth not in hashmap:
hashmap[depth] = width # 深度depth對(duì)應(yīng)的寬度width
# 遞歸
l = dfs(node.left, 2 * width, depth +1)
# 即使沒有左節(jié)點(diǎn)馅袁，右分支還要加null的一個(gè)節(jié)點(diǎn)數(shù)
r = dfs(node.right, 2 * width + 1, depth + 1)
return max(l, r, width - hashmap[depth] + 1)
return dfs(root, 0, 0) # 初始深度與寬度從1開始
d11
leet29: 兩數(shù)相除
返回除法結(jié)果域慷，不越界[-2**31， 2**31-1]
【正負(fù)/零劃分】
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if divisor == 0:
return None
# 被除數(shù)為0
if dividend == 0:
return 0
# 同正同負(fù)
elif (dividend < 0 and divisor < 0) or (dividend > 0 and divisor > 0):
# 同為負(fù)數(shù)時(shí)汗销，最小負(fù)數(shù)//(-1)結(jié)果超越最大正數(shù)2**31-1
return (dividend // divisor) if (dividend // divisor) <= 2 ** 31 - 1 else 2 ** 31 - 1
# 一正一負(fù)
else:
return -(abs(dividend) // abs(divisor))
leet191: 位1的個(gè)數(shù)
一個(gè)數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
【帶奇偶判斷的逐右移位】
class Solution:
def hammingWeight(self, n: int) -> int:
if not n:
return 0
# 位依次右移通過n的奇偶性計(jì)數(shù)犹褒，奇數(shù)則加一
res = 0
while n:
res += (n % 2)
n >>= 1 # 右移1 or 【n //= 2】
return res
# --------or------
# n = n&(n-1)位運(yùn)算依次加一
res = 0
while n:
n &= n - 1
res += 1
return res
leet203: 移除鏈表元素
移除所有值為val的節(jié)點(diǎn)，返回鏈表弛针。如輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
【含有目標(biāo)比較的自身遞歸】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
if not head or val == None:
return None
# 自身遞歸, 下一個(gè)節(jié)點(diǎn)指代的鏈表移除目標(biāo)后的指向叠骑，是head.next
head.next = self.removeElements(head.next, val)
# head是目標(biāo)則返回head.next, 否則返回當(dāng)前head
return head.next if head.val == val else head
# --------or 不簡(jiǎn)潔方法--------------
# 存入列表，后逐次移除削茁，再建立鏈表
if not head or val == None:
return None
list0 = []
while head:
list0.append(head.val)
head = head.next
while val in list0:
list0.remove(val)
dummy = ListNode(0)
p = dummy
for i in list0:
p.next = ListNode(i)
p = p.next
return dummy.next
d12
leet69: x的平方根
實(shí)現(xiàn)int sqrt(int x)函數(shù)
【牛頓迭代】
class Solution:
def mySqrt(self, x: int) -> int:
# 牛頓迭代法
if x <= 1:
return x # 條件中非負(fù)整數(shù)x
res = x
while res > x / res:
res = (res + x / res) // 2
return int(res)
# -----------or 直接的庫(kù)函數(shù)------------
return int(math.sqrt(x))
leet617: 合并二叉樹
合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊宙枷，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值掉房，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)。如輸入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
輸出:
合并后的樹:
3
/ \
4 5
/ \ \
5 4 7
【兩次判空與全存在的各自相加】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
# 返回其中僅一個(gè)的有值節(jié)點(diǎn)
if not t1: return t2
if not t2: return t1
# 在兩者均存在情況下同一位置節(jié)點(diǎn)值相加
t1.val += t2.val
# 遞歸
t1.left = self.mergeTrees(t1.left, t2.left) # 合并左節(jié)點(diǎn)為新的t1節(jié)點(diǎn)
t1.right = self.mergeTrees(t1.right, t2.right) # 合并右節(jié)點(diǎn)為新的t1節(jié)點(diǎn)
# 返回新的節(jié)點(diǎn)
return t1
leet113: 路徑總和
求出根到葉子節(jié)點(diǎn)路徑總和為固定值的所有路徑集
給定一個(gè)二叉樹和一個(gè)目標(biāo)和慰丛，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑卓囚。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定如下二叉樹诅病，以及目標(biāo)和 sum = 22哪亿，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
【目標(biāo)遞減下葉子和當(dāng)前更新的路徑和與目標(biāo)值的比較】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res = []
def dfs(node, tmp, sum0):
if not node:
return
# 葉節(jié)點(diǎn)且是等于最后減下來的差值
if not node.left and not node.right and node.val == sum0:
tmp.append(node.val) # 放入當(dāng)前路徑中的葉子節(jié)點(diǎn)
res.append(tmp) # 存儲(chǔ)當(dāng)前完整的路徑
# 左右子樹依次遍歷，目標(biāo)長(zhǎng)度值逐次減去當(dāng)前值
dfs(node.left, tmp + [node.val], sum0 - node.val) # 節(jié)點(diǎn)逐次放入候選路徑集
dfs(node.right, tmp + [node.val], sum0 - node.val)
dfs(root, [], sum) # []: 當(dāng)前符合條件的一條路徑中的節(jié)點(diǎn)
return res
d13
leet1207: 獨(dú)一無二的出現(xiàn)次數(shù)
數(shù)組中是否有獨(dú)一無二的出現(xiàn)次數(shù)
【hashmap計(jì)數(shù)與值數(shù)組判重】
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
if not arr:
return True
count = {} # hashmap存儲(chǔ)每個(gè)值出現(xiàn)的個(gè)數(shù)
# 初始化每個(gè)數(shù)的長(zhǎng)度count睬隶，逐次加一
for i in arr: count[i] = 0
for i in arr: count[i] += 1
# hashmap中的值如果有重復(fù)則返回False, 若重則set后長(zhǎng)度減少
return len(set(count.values())) == len(count.values())
leet300: 最長(zhǎng)上升子序列
給定一個(gè)無序的整數(shù)數(shù)組锣夹，找到其中最長(zhǎng)上升子序列的長(zhǎng)度页徐。如輸入: [10,9,2,5,3,7,101,18]
輸出: 4 苏潜，解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4变勇。
【雙循環(huán)動(dòng)態(tài)規(guī)劃】
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
# 動(dòng)態(tài)規(guī)劃恤左，初始為長(zhǎng)度1的【len(nums)】長(zhǎng)序列
dp = [1] * len(nums)
for i in range(len(nums)): # (1, len(nums)):
for j in range(i):
# i與j相比較，逐次:【僅當(dāng)】組成長(zhǎng)為2的上升序列才更新dp[i]
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1) # 取當(dāng)前原始長(zhǎng)度值與更新后的長(zhǎng)度值中較大者
# 返回【最長(zhǎng)者】
return max(dp)
leet669: 修剪二叉搜索樹
【遞歸判斷】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
if not root:
return None
# 當(dāng)前節(jié)點(diǎn)值>R, 則修剪后的二叉數(shù)在當(dāng)前節(jié)點(diǎn)左側(cè), 即"返回"修剪左側(cè)后的二叉樹; 返回修剪右側(cè)后的二叉樹同理搀绣。
if root.val > R: return self.trimBST(root.left, L, R)
if root.val < L: return self.trimBST(root.right, L, R)
# 否則(root.val處于L飞袋，R中間), 分別修剪二叉樹左右分支
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
# 最終返回修改完成的二叉樹
return root
d14
leet121: 買賣股票的最佳時(shí)機(jī)
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格链患。
如果你最多只允許完成一筆交易（即買入和賣出一支股票）巧鸭，設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。
注意你不能在買入股票前賣出股票麻捻。如輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入纲仍，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 贸毕。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格郑叠。
【最低股價(jià)與最大利潤(rùn)同時(shí)更新】
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0 # 沒有則獲利0
min0 = 999999
maxp = -999999
# 逐次更新
for i in prices:
min0 = min(min0, i) # 最低股價(jià)
maxp = max(maxp, i - min0) # 最大利潤(rùn)
return maxp
leet面試42: 連續(xù)子數(shù)組的最大和
輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)明棍。數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組乡革。求所有子數(shù)組的和的最大值。
要求時(shí)間復(fù)雜度為O(n)摊腋。如輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6, 解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大沸版，為 6。
【max0 sum0初始索引0賦值兴蒸，與sum0>0判斷】
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
max0 = nums[0]
sum0 = nums[0]
# 從第二個(gè)數(shù)開始判斷累加
for i in range(1, len(nums)):
# 上次累計(jì)和小于0則sum0置當(dāng)前值
if sum0 < 0:
sum0 = nums[i]
else:
sum0 += nums[i] # 否則累加
max0 = max(max0, sum0) # 逐次更新連續(xù)子數(shù)組的最大和
return max0
leet279: 完全平方數(shù)
給定正整數(shù) n视粮，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少类咧。如輸入: n = 12
輸出: 3 馒铃，解釋: 12 = 4 + 4 + 4
【動(dòng)態(tài)規(guī)劃雙循環(huán)解背包問題】
class Solution:
def numSquares(self, n: int) -> int:
if n == None:
return 0
dp = [0] * (n + 1)
# 從1開始循環(huán)n遍
for i in range(1, n + 1):
dp[i] = i # 最壞情況每次加1
for j in range(1, int(math.sqrt(i)) + 1):
# 最少完全平方數(shù)的個(gè)數(shù)
dp[i] = min(dp[i], dp[i - j * j] + 1) # 動(dòng)態(tài)轉(zhuǎn)移方程
return dp[-1]
d15
leet204: 計(jì)數(shù)質(zhì)數(shù)
統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量蟹腾。如輸入: 10
輸出: 4，解釋: 小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7 区宇。
【篩去法】
class Solution:
def countPrimes(self, n: int) -> int:
if n == None or n <= 2:
return 0
count = 0
isPrime = [1] * n # 假設(shè)初始全部是素?cái)?shù)
for i in range(2, n):
if isPrime[i]:
count += 1
# 篩去i的倍數(shù)
j = 2 * i # 從2倍數(shù)開始
# 在是素?cái)?shù)的數(shù)的位置上置其為非素?cái)?shù)
while j < n:
isPrime[j] = 0 # I的倍數(shù)的值置非素?cái)?shù)
j += i
return count
leet264: 丑數(shù)ii
找出第 n 個(gè)丑數(shù)娃殖。
丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。如輸入: n = 10
輸出: 12议谷， 解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個(gè)丑數(shù)炉爆。
【三指針動(dòng)態(tài)規(guī)劃】
class Solution:
def nthUglyNumber(self, n: int) -> int:
if n == None:
return None
# 第0個(gè)丑數(shù)為1， 求出前n個(gè)丑數(shù)
# 0r: dp = [1 for _ in range(n)]
dp = [1] * n
i2 = 0
i3 = 0
i5 = 0
# 三指針在取最小的丑數(shù)為對(duì)應(yīng)索引上的數(shù)卧晓，逐次動(dòng)態(tài)更新, 遍歷n-1次即可
for i in range(1, n):
dp[i] = min(2 * dp[i2], 3 * dp[i3], 5 * dp[i5])
if 2 * dp[i2] == dp[i]:
i2 += 1
if 3 * dp[i3] == dp[i]:
i3 += 1
if 5 * dp[i5] == dp[i]:
i5 += 1
# 最后一個(gè)數(shù)字為第n個(gè)丑數(shù)
return dp[-1]
leet714: 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)
給定一個(gè)整數(shù)數(shù)組 prices芬首，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 ；非負(fù)整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用逼裆。
你可以無限次地完成交易郁稍，但是你每次交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購(gòu)買了一個(gè)股票胜宇，在賣出它之前你就不能再繼續(xù)購(gòu)買股票了耀怜。
返回獲得利潤(rùn)的最大值。如輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8桐愉，解釋: 能夠達(dá)到的最大利潤(rùn):
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤(rùn): ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
【買入賣出的動(dòng)態(tài)規(guī)劃】
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if not prices or fee < 0:
return None
cash = 0 # 不持股票時(shí)的最大利
hold = -prices[0] # 持有股票時(shí)的最大利
# 比較兩種操作的收益現(xiàn)金cash/hold
for i in range(1, len(prices)):
# 同一天賣出再買入(虧手續(xù)費(fèi))不比不進(jìn)行操作好
cash = max(cash, hold + prices[i] - fee) # 賣出時(shí)出手續(xù)費(fèi), cash在持有股票的利潤(rùn)的基礎(chǔ)上賣出
hold = max(hold, cash - prices[i]) # 買入
return cash
d16
leet122: 多次買賣股票的最大利
給定一個(gè)數(shù)組财破，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)从诲。你可以盡可能地完成更多的交易（多次買賣一支股票）左痢。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
如輸入: [7,1,5,3,6,4]
輸出: 7
解釋:
在第 2 天（股票價(jià)格 = 1）的時(shí)候買入系洛，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出,
這筆交易所能獲得利潤(rùn) = 5-1 = 4 俊性。
隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入碎罚，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出,
這筆交易所能獲得利潤(rùn) = 6-3 = 3 磅废。
【同leet714 多次買賣的動(dòng)態(tài)規(guī)劃】
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
cash = 0
hold = -prices[0] # 初始買入的第一支股票
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i]) # 賣出
hold = max(hold, cash - prices[i]) # 買入
return cash
leet100: 相同的樹
是否是相同的樹
【同空、不同空判斷后的自身遞歸】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# 同時(shí)存在則是True
if not p and not q: return True
# 有一個(gè)不存在則False
if not q or not q: return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
leet437: 路徑總和iii
不特定根節(jié)點(diǎn)和葉子節(jié)點(diǎn)荆烈，返回路徑總和為固定值的路徑數(shù)
【自身遞歸與dfs遞歸】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def dfs(node, sum0):
if not node:
return 0 # 無解
count = 0
if sum0 == node.val: count = 1
# 當(dāng)前節(jié)點(diǎn)是一個(gè)解, 遞歸求解左右兩邊拯勉，均從給定數(shù)值中減去當(dāng)前節(jié)點(diǎn)值
return count + dfs(node.left, sum0 - node.val) + dfs(node.right, sum0 - node.val)
if not root:
return 0
# 從自身左右邊、根節(jié)點(diǎn)開始憔购，尋找到符合條件的路徑則計(jì)數(shù)宫峦，最終返回總數(shù)
return self.pathSum(root.left, sum) + self.pathSum(root.right, sum) + dfs(root, sum)
d17
lee315線段樹
找出右邊的值小于當(dāng)前值的數(shù)的個(gè)數(shù)：
使用線段樹構(gòu)建左右子樹，并從右到左計(jì)算前面的數(shù)小于當(dāng)前值的數(shù)的個(gè)數(shù)玫鸟，最終返回依次進(jìn)入結(jié)果數(shù)組的list的倒置值导绷。
class Node:
def __init__(self, begin, end):
self.begin = begin
self.end = end
self.mid = (begin + end) // 2
self.left = None
self.right = None
self.count = 0
# 要是當(dāng)前值比最小值都小就返回0，否則比較最小值大則說明有一個(gè)比較當(dāng)前值小的值了屎飘。
# 線段樹遞歸自身的過程即是計(jì)算前方比當(dāng)前值小的數(shù)的個(gè)數(shù)
def add(self, num):
self.count += 1
if self.begin == self.end:
return 0
self.left = Node(self.begin, self.mid) if not self.left else self.left
self.right = Node(self.mid + 1, self.end) if not self.right else self.right
# 分情況提交左右子樹結(jié)果
if num <= self.mid:
return self.left.add(num)
else:
return self.left.count + self.right.add(num) # 左子樹結(jié)果+右遞歸結(jié)果
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums:
return []
# 使用自定義類初始化根節(jié)點(diǎn)
root = Node(min(nums), max(nums))
res = []
# 依次返回倒敘數(shù)組中前面的數(shù)比較當(dāng)前數(shù)小的值的個(gè)數(shù)
for i in range(len(nums)-1, -1, -1):
res.append(root.add(nums[i]))
# 返回倒過來的正確數(shù)組
return res[::-1]
leet1013: 劃分為和的三個(gè)部分：
【list復(fù)制法】
將遍歷到的前兩個(gè)和數(shù)都去掉妥曲，雙重遍歷T(n)= O(n)
class Solution:
def canThreePartsEqualSum(self, A: List[int]) -> bool:
if not A:
return False
for i in range(len(A)-2):
list0 = A[:]
sum0 = sum(A[:i+1])
for ii in range(0, i+1):
list0.remove(A[ii])
for k in range(i+1, len(A)-1):
list1 = list0[:]
sum1 = sum(A[i+1 : k+1])
for kk in range(i+1, k+1):
list1.remove(A[kk])
if sum1 == sum0 == sum(list1):
return True
return False
leet71：簡(jiǎn)化路徑
規(guī)范的路徑表示寫法轉(zhuǎn)換為最簡(jiǎn)路徑
【棧進(jìn)棧出贾费，判斷'' '.' '..'()】
class Solution:
def simplifyPath(self, path: str) -> str:
st = []
for i in path.split('/'):
if i not in ['','.','..']:
st.append(i)
elif i == '..' and st:
st.pop()
return '/' + '/'.join(st)
d18
leet792 匹配子序列的單詞數(shù)
【復(fù)制字符庫(kù)，逐次后移匹配庫(kù)起始點(diǎn)】
class Solution:
def numMatchingSubseq(self, S: str, words: List[str]) -> int:
if not S or not words:
return 0
resnum = 0
for i in words:
list0 = S[:] # 每次都要還原字符庫(kù)
point = 0# 匹配成功數(shù)
# 遍歷每個(gè)元素中的每個(gè)字母
for ii in i:
if ii in list0:
list0 = list0[list0.index(ii)+1 : ] # 在字符庫(kù)中則從命中索引往后(子"序列")檐盟，更新作剩余字符庫(kù)
point += 1
if point == len(i):
resnum += 1
return resnum
leet410 分割數(shù)組的最大值
按要求分一個(gè)數(shù)組為m份褂萧，求其中子數(shù)組的最大值中最小一個(gè)
【二分查找、設(shè)定子數(shù)組最大的和mid作劃分節(jié)點(diǎn)】
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
if not nums or not m:
return None
# 最小的最大值一定在l,r中徘徊葵萎，在終止條件l<r下將子數(shù)組最大和之mid調(diào)大調(diào)小
# mid由于是設(shè)定的最大值所以和數(shù)超過他就要另造茅廬(新增子區(qū)間)导犹，最終l、r收縮一起時(shí)返回最小值l==r
l, r = max(nums), sum(nums)
while l < r:
count = 1 # 每一次l羡忘、r的收縮都是一個(gè)方案谎痢，最初一個(gè)區(qū)間
subsum = 0 # 新子區(qū)間的和
mid = (l + r) // 2
for i in nums:
subsum += i
if subsum > mid:
subsum = i
count += 1
if count > m: # 劃分子區(qū)間太多了，要提高mid
l = mid + 1
else:
r = mid
return r
leet108 有序數(shù)組轉(zhuǎn)換為平衡二叉搜索樹
【二分思想卷雕，拆分?jǐn)?shù)組遞歸】(不用判斷平衡)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
# 二分處為root节猿，構(gòu)建平衡搜索樹; 其他遞歸求左右
root = TreeNode(nums[len(nums) // 2])
lnums = nums[ : len(nums) // 2]
rnums = nums[len(nums) // 2 + 1 : ]
root.left = self.sortedArrayToBST(lnums)
root.right = self.sortedArrayToBST(rnums)
return root
d19(52%)
leet 1208 盡可能使字符串相等
兩個(gè)字符串對(duì)應(yīng)位置移動(dòng)總次數(shù)在指定步數(shù)內(nèi)(ascii值的差)，求字符串的最大可變換長(zhǎng)
【滑窗記錄更新最初位置爽蝴、不斷更新當(dāng)前滑窗內(nèi)移動(dòng)步數(shù)最小值】
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
if not s or not t:
return 0
# 經(jīng)典滑動(dòng)窗口沐批，每一次一動(dòng)一個(gè)格子
l = 0 # 記錄好滑窗起始判斷的位置
cost = 0
maxlen = 0
for i in range(len(s)):
cost += abs(ord(s[i]) - ord(t[i]))
while cost > maxCost: # 該窗口不可用，代價(jià)減掉舊的初始點(diǎn)的代價(jià)
cost -= abs(ord(s[l]) - ord(t[l]))
l += 1 # 窗口起始位置遞增
maxlen = max(maxlen, i - l + 1) # 更新最大長(zhǎng)蝎亚，為當(dāng)前走到的滑窗內(nèi)的最大長(zhǎng)
return maxlen
leet374：猜數(shù)字大小
原本的數(shù)字比猜出的數(shù)字小則返回1，求最后的正確數(shù)字
【二分法壓縮區(qū)間】
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
if not n:
return None
l,r = 1, n
# 二分思想收縮區(qū)間
while l < r:
m = (l + r) // 2
if guess(m) == 1:
l = m + 1
elif guess(m) == -1:
r = m
else:
return m
return l # 總有對(duì)的時(shí)候
leet949 給定數(shù)字能組成的最大時(shí)間
如：1 2 3 4組成的最大數(shù)字為'23:41'
【判斷分鐘數(shù)先馆、三重遍歷后求index4】
class Solution:
def largestTimeFromDigits(self, A: List[int]) -> str:
if not A or min(A) >2 or len(A) != 4:
return ''
hour = 0
minu = 0
max0 = -1
for i in range(4):
for j in range(4):
if j != i:
for k in range(4):
if k != j and k != i:
l = 6 - i - j - k # 計(jì)算沒有用到的數(shù)索引index4
hour = A[i] * 10 + A[j]
minu = A[k] * 10 + A[l]
if hour < 24 and minu < 60:
max0 = max(max0, hour * 60 + minu) # 最大分鐘數(shù)更新
# 返回整數(shù)串发框；沒有滿足條件的結(jié)果返回''；不足的格式用0填充
return '%02d:%02d'% (max0//60,max0%60) if max0 >= 0 else ''
d20(51%)
leet997 找到小鎮(zhèn)的法官
法官不trust人任何人煤墙，任何人(除法官外)都trust法官
【圖遍歷每個(gè)人梅惯，出度為0入度N-者】
class Solution:
def findJudge(self, N: int, trust: List[List[int]]) -> int:
if not N: # 至少一個(gè)人
return -1
if not trust:
return N if N == 1 else -1
indegree = [0] * (N+1) # 因?yàn)槿说木幪?hào)從1開始
outdegree = [0] * (N+1)
for i in trust:
outdegree[i[0]] += 1
indegree[i[1]] += 1
for i in range(1, N+1): # 第0個(gè)值是空
# 其他N-1個(gè)人都相信他，自己不相信任何人(出度為0入度
if outdegree[i] == 0 and indegree[i] == N - 1:
return i
return -1
leet225 隊(duì)列進(jìn)出
模擬queue仿野；peak返回值不彈出
【list只pop(0)作移除元素或pop()】
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.queue.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if not self.empty():
val = self.queue.pop(0)
return val
def peek(self) -> int:
"""
Get the front element.
"""
if not self.empty():
return self.queue[0] # 與pop()均返回第一個(gè)元素即可
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return not self.queue
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
leet423 從英文中重建數(shù)字
【s.count計(jì)數(shù)铣减、獨(dú)特性】
class Solution:
def originalDigits(self, s: str) -> str:
if not s:
return ''
# list0 =['zero', 'one','two','three','four','five','six','seven','eight','nine']
# 默認(rèn)是被打亂的英文字母，所以只要知道特有字母對(duì)應(yīng)的數(shù)字格式即可脚作，如'w'只在2中出現(xiàn)
n0 = s.count('z')
n2 = s.count('w')
n6 = s.count('x')
n8 = s.count('g')
# 依次可以逐步確定對(duì)應(yīng)的數(shù)字個(gè)數(shù)葫哗，不能使用多次出現(xiàn)的字符如nine one的n
n3 = s.count('t') - n2 - n8
n7 = s.count('s') - n6
n5 = s.count('v') - n7
n4 = s.count('f') - n5
n9 = s.count('i') - n5 - n6 - n8
n1 = s.count('o') - n0 - n2 - n4
list0 = [n0, n1, n2, n3, n4, n5, n6, n7, n8, n9]
return ''.join( [str(i) * n for i,n in enumerate(list0)] ) # 從小到大
d21（100%）
leet7 整數(shù)反轉(zhuǎn)
如-321轉(zhuǎn)換為-123
【兩種情況判斷、str逆轉(zhuǎn)】
class Solution:
def reverse(self, x: int) -> int:
if x == None:
return None
newx = int(str(x)[::-1]) if x >=0 else int('-' + str(x)[1:][::-1])
return 0 if newx > 2**31 - 1 or newx < -2**31 else newx
leet165 比較版本號(hào)
如輸入: version1 = "7.5.2.4", version2 = "7.5.3"
輸出: -1球涛，即v1<v2
【遞進(jìn)字符串劣针、循環(huán)終止條件為有值比較、‘55’.split(‘.’)返回[] 】
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
if not version1 or not version2:
return None
while version1 or version2:
# 兩個(gè)都沒有點(diǎn)
if '.' not in version1 and '.' not in version2:
if int(version1) > int(version2):
return 1
elif int(version1) < int(version2):
return -1
else:
return 0
# return ('222'.split('.')[1:]) # true:[] 如果有一個(gè)不存在.也沒有關(guān)系
if int(version1.split('.')[0]) > int(version2.split('.')[0]):
return 1
elif int(version1.split('.')[0]) < int(version2.split('.')[0]):
return -1
else:
# 比較下層
version1 = '.'.join(str(int(i)) for i in version1.split('.')[1:] ) if '.' in version1 else '0' # 消除01這樣的版本表示為1
version2 = '.'.join(str(int(i)) for i in version2.split('.')[1:] ) if '.' in version2 else '0'
return None
leet515 找出二叉樹每行中的最大值
輸入:
1
/
3 2
/ \ \
5 3 9
輸出: [1, 3, 9]
【有層次號(hào)標(biāo)識(shí)的層次遍歷】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def largestValues(self, root: TreeNode) -> List[int]:
if not root:
return []
list0 = []
l = 0
def l_visit(node, l):
if node:
if len(list0)<l+1:
list0.append(node.val) # 當(dāng)前層數(shù)沒有最大值則放入當(dāng)前節(jié)點(diǎn)值
else:
list0[l] = max(list0[l], node.val)
# 左右節(jié)點(diǎn)依次層析次遍歷
l_visit(node.left,l+1)
l_visit(node.right,l+1)
l_visit(root,0)
return list0
d22 (67%)
leet141 環(huán)形鏈表
鏈表有環(huán)則返回True
【重置已遍歷的值】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head:
return False
while head: # 只要之前遍歷過的就是有環(huán)
if head.val =='findme':
return True
head.val = 'findme'
head = head.next
return False
leet142 環(huán)形鏈表II
鏈表有環(huán)則返回環(huán)的起始節(jié)點(diǎn)
【遍歷返回重置后的節(jié)點(diǎn)】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return None
while head: # 遍歷亿扁，如果有環(huán)則返回當(dāng)前節(jié)點(diǎn)
if head.val == 'visited':
return head
head.val = 'visited'
head = head.next
return None
leet491 遞增子序列
找到數(shù)組的所有遞增子序列捺典，len>2、不用連續(xù)
【保存當(dāng)前起始位置从祝、逐次選后面滿足條件元素的位置加入襟己，遞歸生成有效集】
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
set0 = set()
def gen(curloc, tmp):
# 元組長(zhǎng)大于2才能加入結(jié)果集合
if len(tmp) > 1 and tmp not in set0:
set0.add(tmp)
# 在當(dāng)前值集合tmp的條件下引谜，依次加入后面大于該tmp最大值的元素
for i in range(curloc + 1, len(nums)):
if tmp[-1] <= nums[i]:
gen(i, tmp + (nums[i],) ) # 更新tmp后滿足"不遞減"條件的起點(diǎn)位置
# 遍歷列表的每個(gè)位置，生成當(dāng)前位置為起點(diǎn)滿足條件的子集
for i, e in enumerate(nums):
gen(i, (e, )) # i放入元組中
return [list(i) for i in set0]
d23 (60%)
leet102 二叉樹層序遍歷
層序遍歷輸出各個(gè)層次的節(jié)點(diǎn)值擎浴，分別用list表示
【bfs遞歸煌张、層次值更新】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
list0 = []
def bfs(node, l):
if node:
if len(list0) < l+1:
list0.append([])
list0[l].append(node.val)
bfs(node.left, l+1)
bfs(node.right, l+1)
bfs(root, 0)
return list0
leet662 二叉樹最大寬度
【bfs(層次遍歷)非遞歸與dfs遞歸】
【bfs+隊(duì)列的非遞歸方式：左右節(jié)點(diǎn)標(biāo)識(shí)、依次遍歷隊(duì)列更新最大寬】
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
if not root:
return 0
# bfs非遞歸
queue = [(root, 0, 0)] # 元列表, 分別表示當(dāng)前節(jié)點(diǎn)退客、depth骏融、左右節(jié)點(diǎn)寬度位置loc(分別兩倍、兩倍+1個(gè)寬度)
curdepth = 0 # 當(dāng)前層次
start, loc = 0, 0
max0 = 0 # 最大寬度
# 逐漸變多的元組集(左萌狂、右)
for node, depth, loc in queue:
if node:
queue.append([node.left, depth+1, 2*loc]) # 逐增層次的同時(shí)档玻，將左右節(jié)點(diǎn)原先寬度位置更新:2*x和2x+1
queue.append([node.right, depth+1, 2*loc+1])
# 逐增當(dāng)前的深度值，并更新當(dāng)前深度茫藏、起始位置
if curdepth != depth:
curdepth = depth
start = loc
max0 = max(max0, loc - start + 1)
return max0
【dfs遞歸：默認(rèn)每層起始位置误趴、更新最大寬、hash0.setdefault()】
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
if not root:
return 0
self.max0 = 0 # 最大寬
start = {}
def dfs(node, depth=0, loc=0):
if node:
start.setdefault(depth, loc) # 就是當(dāng)前層depth的value不會(huì)再變了
# 更新現(xiàn)在的最大寬
self.max0 = max(self.max0, loc - start[depth] + 1)
# dfs务傲，每增加一層depth,左邊的就要翻倍凉当，右邊的就要翻倍加一；
# 即只要右邊有節(jié)點(diǎn)售葡，就是"2*loc+1 - 起始位置 + 1"的寬度看杭，如例中的9：其寬度為2*(2*0+1)+1 - 0 + 1 = 4
# 如果是例2的對(duì)稱例，start則與右子樹的loc相等
dfs(node.left, depth+1, 2*loc)
dfs(node.right, depth+1, 2*loc+1)
dfs(root)
return self.max0 # 閉包外用到挟伙，故self方式
leet453 最小移動(dòng)次數(shù)使數(shù)組元素相等
輸入:
[1,2,3]
輸出:
3, 解釋: 只需要3次移動(dòng)（注意每次移動(dòng)會(huì)增加兩個(gè)元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
【數(shù)學(xué)題楼雹，移動(dòng)后總和sum'(nums)與最小值的變化幅度m】
class Solution:
def minMoves(self, nums: List[int]) -> int:
# m次移動(dòng)后，sum(nums)+m(n-1) = len(nums)*mean尖阔，且min(nums) + m = mean即原本"最小值"m次加一最終變mean!
# sum(nums) + m * (len(nums)-1) = len(nums)* (min(nums)+m)
# 以上求m : m = sunsum(nums) - len(nums) * min(nums)
if not nums:
return 0
return sum(nums) - len(nums) * min(nums)
d24
leet22 括號(hào)生成
【初始'()'后循環(huán)n-1次贮缅、對(duì)所有上一次結(jié)果遍歷更新、找打所有空位進(jìn)行set0.update】
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if not n:
return []
res = set(['()'])
for _ in range(n-1): # n個(gè)括號(hào)
tmp = set()
for r in res: # 對(duì)之前結(jié)果所有都更新
# 每個(gè)結(jié)果string有l(wèi)en(string)個(gè)空位介却；update支持迭代
tmp.update( set(r[:j]+'()'+r[j:] for j in range(len(r))) ) #
res = tmp
return list(res)
leet13 羅馬數(shù)字轉(zhuǎn)整數(shù)
輸入: "LVIII"
輸出: 58, 解釋: L = 50, V= 5, III = 3.
【hash谴供、小值字符在大值之前】
class Solution:
def romanToInt(self, s: str) -> int:
if not s:
return 0
has = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1 }
res = 0
for i in range(len(s)):
# 當(dāng)前字符是最后一個(gè)，當(dāng)前字符對(duì)應(yīng)值<后一個(gè)
if i < len(s) - 1 and has[s[i]] < has[s[i+1]]: # 減法
res -= has[s[i]]
else:
res += has[s[i]] # 加法
return res
leet227 基本運(yùn)算器2
實(shí)現(xiàn)一個(gè)基本的計(jì)算器來計(jì)算一個(gè)簡(jiǎn)單的字符串表達(dá)式的值齿坷。
字符串表達(dá)式僅包含非負(fù)整數(shù)桂肌，+， - 胃夏，*轴或，/ 四種運(yùn)算符和空格 。 整數(shù)除法僅保留整數(shù)部分仰禀。
輸入: " 3+5 / 2 "
輸出: 5
【stack照雁、has_ops[op]對(duì)上個(gè)運(yùn)算符和之后數(shù)字運(yùn)算、轉(zhuǎn)為stack和的運(yùn)算】
import operator
class Solution:
def calculate(self, s: str) -> int:
if not s:
return None
stack = []
has_ops = {'+':lambda x: stack.append(x),
'-':lambda x: stack.append(-x),
'*':lambda x: stack.append(stack.pop()*x),
'/':lambda x: stack.append( int( operator.truediv(stack.pop(), x) ) ) } # 僅保留整數(shù)即可
op = '+'
num = 0
for i in s+'+':# 為了對(duì)于最后的操作符和數(shù)字進(jìn)行計(jì)算
if i.isdigit():
num = num*10 + int(i) # 整個(gè)數(shù)字
elif i !=' ': # 非空字符' '
# 上上次的操作符對(duì)應(yīng)上次數(shù)字，"*"饺蚊、"/"時(shí)與上上上次數(shù)字運(yùn)算后放入加運(yùn)算棧萍诱，加減法時(shí)獨(dú)自放入
has_ops[op](num)
op = i
num = 0
return sum(stack)
d25
leet373 查找和最小的k對(duì)數(shù)字
輸入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
輸出: [1,1],[1,1]，解釋: 返回序列中的前 2 對(duì)數(shù)：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
【sorted()中用帶有l(wèi)ambda的key】
class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
if not nums1 or not nums2 or not k:
return []
list0 = []
for i in nums1:
for j in nums2:
list0.append([i,j])
# 對(duì)數(shù)字對(duì)按和升序
list0 = sorted(list0, key = lambda x: x[0]+ x[1] ) # 和為升序條件
return list0[:k] # 返前k個(gè)
leet945 使數(shù)組唯一的最小增量
輸入：[3,2,1,2,1,7]
輸出：6污呼，解釋：經(jīng)過 6 次 move 操作裕坊，數(shù)組將變?yōu)?[3, 4, 1, 2, 5, 7]，可看出 5 次或 5 次以下的 move 操作是不能讓數(shù)組的每個(gè)值唯一的燕酷。
【記錄累積的步數(shù)籍凝、當(dāng)前可用值】
class Solution:
def minIncrementForUnique(self, A: List[int]) -> int:
if not A:
return 0
A.sort()
moves = 0
cur_avalible = 0
# 升序后逐次遍歷，記錄步數(shù)苗缩、可用值
for i in A:
moves += max(cur_avalible - i, 0) # 步數(shù)一定大于零饵蒂，第一個(gè)數(shù)moves=0
cur_avalible = max(cur_avalible,i) + 1 # 當(dāng)前可用值=當(dāng)前值與當(dāng)前可用值的較大值+1
return moves # sum(set0) - sum(A) # moves
# 如 1 1 2 2 3 7
# moves: 0 1 1+1 2+2 4+2 6+max(6-7,0)=6
# cur_avalible: 2 3 4 5 6
leet2 兩數(shù)相加
【當(dāng)前進(jìn)位、之前進(jìn)位+分配空間酱讶，頭建鏈表】
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return None
list0 = []
i = 0
while l1 or l2:
# 只有一個(gè)數(shù)存在退盯，有進(jìn)位則兩者相加，否則sum0=當(dāng)前值
if not l1:
sum0 = l2.val if len(list0)<i+1 else list0[i] + l2.val
elif not l2:
sum0 = l1.val if len(list0)<i+1 else list0[i] + l1.val
else: # 兩者均存在泻肯，之前有進(jìn)位則三者相加渊迁，否則兩數(shù)相加
sum0 = l1.val + l2.val if len(list0)<i+1 else list0[i] + l1.val + l2.val
# 當(dāng)前有進(jìn)位
if sum0 > 9:
if len(list0)<i+1: # 且之前有進(jìn)位則開辟空間后放入，否則直接放入進(jìn)位后值
list0.append(0)
list0[i] = sum0-10
list0.append(0)
list0[i+1] = 1
else: # 當(dāng)前無進(jìn)位
if len(list0)<i+1: # 之前無進(jìn)位則開辟空間后放入當(dāng)前值灶挟，否則直接放入當(dāng)前值
list0.append(sum0)
else:
list0[i] = sum0
# 只要后面優(yōu)有值琉朽，就往后推移
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
i += 1
# 頭建鏈表
head= ListNode(list0.pop(0))
p = head
while list0:
p.next = ListNode(list0.pop(0))
p = p.next
return head
d26
1/3
leet 912 排序數(shù)組
快速排序
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
if not nums:
return []
def quick(l, r):
if l > r:
return nums
i,j,pivot = l, r, l
while i < j:
while i < j and nums[j] > nums[pivot]:
j -= 1
while i < j and nums[i] <= nums[pivot]:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[j], nums[pivot] = nums[pivot], nums[j] # 與J交換
quick(l, j - 1) # 分治左排序
quick(j + 1, r) # 分治右排序
return nums
return quick(0, len(nums) - 1)
2/3
leet 1143 最長(zhǎng)公共子序列
【dp pre動(dòng)態(tài)規(guī)劃】
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
if not text1 or not text2:
return 0
# pre與dp動(dòng)態(tài)規(guī)劃
pre = [0 for _ in range(len(text2) + 1)]
dp = [0 for _ in range(len(text2) + 1)]
for i in range(len(text1)):
j = 0
for j in range(1, len(text2) + 1):
if text1[i] == text2[j-1]: # 之前最優(yōu)解+1的條件
dp[j] = pre[j-1] + 1
else:
dp[j] = max(pre[j], dp[j-1]) # 取最優(yōu)
pre[j-1] = dp[j-1] # 更新pre
pre[j] = dp[j] # 更新pre至len(text2))
return dp[-1]
