LeetCode是一個(gè)刷算法題的網(wǎng)站，這里用的是python3，做一下刷題記錄
1. 兩數(shù)之和
題目
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target钥弯，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 的那 兩個(gè) 整數(shù)，并返回它們的數(shù)組下標(biāo)睛蛛。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案忆肾。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)场仲。
你可以按任意順序返回答案渠缕。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 馍忽，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
提示：
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只會(huì)存在一個(gè)有效答案
解法
直接窮舉即可：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
優(yōu)化算法
可以通過hashmap的方式將時(shí)間復(fù)雜度將至O(n)：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashmap = {}
for index, num in enumerate(nums):
another_num = target - num
if another_num in hashmap:
return [hashmap[another_num], index]
hashmap[num] = index
return None
2. 兩數(shù)相加
題目
給你兩個(gè) 非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)吵血。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的蹋辅，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。
請(qǐng)你將兩個(gè)數(shù)相加褒傅，并以相同形式返回一個(gè)表示和的鏈表。
你可以假設(shè)除了數(shù)字 0 之外支竹，這兩個(gè)數(shù)都不會(huì)以 0 開頭。
示例 1：
輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.
示例 2：
輸入：l1 = [0], l2 = [0]
輸出：[0]
示例 3：
輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]
提示：
每個(gè)鏈表中的節(jié)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
0 <= Node.val <= 9
題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零
解法
這里做題習(xí)慣性忽略注釋叹坦，于是吃了個(gè)大虧募书，最終解決如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
newList = ListNode()
newNode = newList
carry = 0
while(l1 or l2 or carry):
sumNum = (l1.val if l1 else 0)+(l2.val if l2 else 0)+carry
if sumNum > 9:
carry = 1
newNode.next = ListNode(sumNum-10)
else:
newNode.next = ListNode(sumNum)
carry = 0
newNode = newNode.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return newList.next
27. 移除元素
題目
給你一個(gè)數(shù)組 nums 和一個(gè)值 val鬼吵，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度涣脚。
不要使用額外的數(shù)組空間遣蚀，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組芭梯。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素累奈。
說明:
為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請(qǐng)注意旱幼，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的匀油。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的敌蚜。也就是說齐媒，不對(duì)實(shí)參作任何拷貝
int len = removeElement(nums, val);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長度, 它會(huì)打印出數(shù)組中 該長度范圍內(nèi) 的所有元素唬血。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個(gè)元素均為 2拷恨。你不需要考慮數(shù)組中超出新長度后面的元素。例如兜挨，函數(shù)返回的新長度為 2 拌汇，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會(huì)被視作正確答案与倡。
示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數(shù)應(yīng)該返回新的長度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。注意這五個(gè)元素可為任意順序净响。你不需要考慮數(shù)組中超出新長度后面的元素馋贤。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
解法
這個(gè)題目的意思也就是直接在原列表中進(jìn)行更改配乓，因此直接使用remove即可：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
while val in nums:
nums.remove(val)
return len(nums)
在評(píng)論區(qū)看到了一種快慢指針的方法（據(jù)說時(shí)間更優(yōu)，但python執(zhí)行結(jié)果倒是差不多）：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
index = 0
for i in range(0, len(nums)):
if val != nums[i]:
nums[index] = nums[i]
index += 1
return index
28. 實(shí)現(xiàn) strStr()
題目
實(shí)現(xiàn) strStr() 函數(shù)实昨。
給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。如果不存在蛔趴，則返回 -1 鱼蝉。
說明：
當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢洁奈？這是一個(gè)在面試中很好的問題。
對(duì)于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 轮蜕。這與 C 語言的 strstr() 以及 Java 的 indexOf() 定義相符肠虽。
示例 1：
輸入：haystack = "hello", needle = "ll"
輸出：2
示例 2：
輸入：haystack = "aaaaa", needle = "bba"
輸出：-1
示例 3：
輸入：haystack = "", needle = ""
輸出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 僅由小寫英文字符組成
解法
解法如下（執(zhí)行用時(shí)：36 ms, 在所有 Python3 提交中擊敗了89.52%的用戶內(nèi)存消耗：15.1 MB, 在所有 Python3 提交中擊敗了47.80%的用戶）：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle == '':
return 0
elif needle not in haystack:
return -1
else:
return len(haystack.split(needle)[0])
91. 解碼方法
題目
一條包含字母 A-Z 的消息通過以下映射進(jìn)行了 編碼 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解碼 已編碼的消息痊剖，所有數(shù)字必須基于上述映射的方法韩玩，反向映射回字母（可能有多種方法）。例如陆馁，"11106" 可以映射為：
"AAJF" 找颓，將消息分組為 (1 1 10 6)
"KJF" ，將消息分組為 (11 10 6)
注意叮贩，消息不能分組為 (1 11 06) 击狮，因?yàn)?"06" 不能映射為 "F" ，這是由于 "6" 和 "06" 在映射中并不等價(jià)益老。
給你一個(gè)只含數(shù)字的 非空 字符串 s 酷誓，請(qǐng)計(jì)算并返回 解碼 方法的 總數(shù) 娘扩。
題目數(shù)據(jù)保證答案肯定是一個(gè) 32 位 的整數(shù)。
示例 1：
輸入：s = "12"
輸出：2
解釋：它可以解碼為 "AB"（1 2）或者 "L"（12）辣之。
示例 2：
輸入：s = "226"
輸出：3
解釋：它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 灾部。
示例 3：
輸入：s = "0"
輸出：0
解釋：沒有字符映射到以 0 開頭的數(shù)字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 逃呼。
由于沒有字符推姻，因此沒有有效的方法對(duì)此進(jìn)行解碼，因?yàn)樗袛?shù)字都需要映射。
示例 4：
輸入：s = "06"
輸出：0
解釋："06" 不能映射到 "F" 臭墨，因?yàn)樽址星皩?dǎo) 0（"6" 和 "06" 在映射中并不等價(jià)）掺冠。
提示：
1 <= s.length <= 100
s 只包含數(shù)字憾股，并且可能包含前導(dǎo)零伐庭。
解法
自己沒做出來饺著，看了下別人的答案绝葡，照著寫了個(gè)：
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == '0' or '00' in s:
return 0
else:
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
if s[i] == '0':
dp[i] = 0
if s[i-1] == '1' or (s[i-1] == '2' and int(s[i]) < 7):
dp[i+1] = dp[i-1]
dp[i+1] += dp[i]
return dp[n]
179. 最大數(shù)
題目
給定一組非負(fù)整數(shù) nums幽七，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)最大的整數(shù)词顾。
注意：輸出結(jié)果可能非常大吓笙，所以你需要返回一個(gè)字符串而不是整數(shù)幌墓。
示例 1：
輸入：nums = [10,2]
輸出："210"
示例 2：
輸入：nums = [3,30,34,5,9]
輸出："9534330"
示例 3：
輸入：nums = [1]
輸出："1"
示例 4：
輸入：nums = [10]
輸出："10"
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 109
解法
直接將兩個(gè)數(shù)字拼接比大小即可欧募，最后去掉一下前導(dǎo)0：
class Solution:
def largestNumber(self, nums: List[int]) -> str:
for i in range(0, len(nums)):
nums[i] = str(nums[i])
temp = nums[0]
temp1 = ''
temp2 = ''
for i in range(0, len(nums)):
for j in range(1, len(nums)):
temp1 = nums[j-1] + nums[j]
temp2 = nums[j] + nums[j-1]
if temp1 > temp2:
temp = nums[j-1]
nums[j-1] = nums[j]
nums[j] = temp
str1 = ''
nums.reverse()
for i in range(0, len(nums)):
str1 += str(nums[i])
index = 0
for i in range(len(str1)):
if str1[i] == '0' and index < len(str1)-1:
index += 1
else:
break
return str1[index:]
208. 實(shí)現(xiàn) Trie (前綴樹)
題目
Trie（發(fā)音類似 "try"）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)摇庙，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵讽营。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景膜蠢，例如自動(dòng)補(bǔ)完和拼寫檢查。
請(qǐng)你實(shí)現(xiàn) Trie 類：
Trie() 初始化前綴樹對(duì)象。
void insert(String word) 向前綴樹中插入字符串 word 祭饭。
boolean search(String word) 如果字符串 word 在前綴樹中，返回 true（即，在檢索之前已經(jīng)插入）猪钮；否則品山，返回 false 。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix 烤低，返回 true 肘交；否則，返回 false 扑馁。
示例：
輸入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出
[null, null, true, false, true, null, true]
解釋
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 僅由小寫英文字母組成
insert涯呻、search 和 startsWith 調(diào)用次數(shù) 總計(jì) 不超過 3 * 104 次
解法
根據(jù)相應(yīng)的函數(shù)寫出對(duì)應(yīng)功能即可（內(nèi)存消耗極小，但運(yùn)行時(shí)間奇高腻要，執(zhí)行用時(shí): 2356 ms复罐，內(nèi)存消耗: 20.8 MB）：
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.datalist = []
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
self.datalist.append(word)
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
for i in range(0, len(self.datalist)):
if word == self.datalist[i]:
return True
return False
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
for i in range(0, len(self.datalist)):
if prefix in self.datalist[i] and prefix == self.datalist[i][0:len(prefix)]:
return True
return False
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
看了下題解，看到一個(gè)代碼更簡(jiǎn)更加省內(nèi)存（執(zhí)行用時(shí)：424 ms, 內(nèi)存消耗：20.6 MB）的寫法：
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.datalist = ','
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
self.datalist = self.datalist + word + ','
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
return ',' + word + ',' in self.datalist
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
return ',' + prefix in self.datalist
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
但是嚴(yán)格來說都不符合前綴樹的定義雄家，于是查了下更省時(shí)間的前綴樹的寫法（執(zhí)行用時(shí)：120 ms效诅，內(nèi)存消耗：27.7 MB）：
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for s in word:
if s in node.keys():
node = node[s]
else:
node[s] = {}
node = node[s]
node['is_word'] = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for s in word:
if s in node.keys():
node = node[s]
else:
return False
return True if 'is_word' in node.keys() else False
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for s in prefix:
if s in node.keys():
node = node[s]
else:
return False
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
403. 青蛙過河
題目
一只青蛙想要過河。 假定河流被等分為若干個(gè)單元格咳短，并且在每一個(gè)單元格內(nèi)都有可能放有一塊石子（也有可能沒有）填帽。 青蛙可以跳上石子蛛淋，但是不可以跳入水中咙好。
給你石子的位置列表 stones（用單元格序號(hào) 升序 表示）， 請(qǐng)判定青蛙能否成功過河（即能否在最后一步跳至最后一塊石子上）褐荷。
開始時(shí)勾效， 青蛙默認(rèn)已站在第一塊石子上，并可以假定它第一步只能跳躍一個(gè)單位（即只能從單元格 1 跳至單元格 2 ）叛甫。
如果青蛙上一步跳躍了 k 個(gè)單位层宫，那么它接下來的跳躍距離只能選擇為 k - 1、k 或 k + 1 個(gè)單位其监。 另請(qǐng)注意萌腿，青蛙只能向前方（終點(diǎn)的方向）跳躍。
示例 1：
輸入：stones = [0,1,3,5,6,8,12,17]
輸出：true
解釋：青蛙可以成功過河抖苦，按照如下方案跳躍：跳 1 個(gè)單位到第 2 塊石子, 然后跳 2 個(gè)單位到第 3 塊石子, 接著 跳 2 個(gè)單位到第 4 塊石子, 然后跳 3 個(gè)單位到第 6 塊石子, 跳 4 個(gè)單位到第 7 塊石子, 最后毁菱，跳 5 個(gè)單位到第 8 個(gè)石子（即最后一塊石子）。
示例 2：
輸入：stones = [0,1,2,3,4,8,9,11]
輸出：false
解釋：這是因?yàn)榈?5 和第 6 個(gè)石子之間的間距太大锌历，沒有可選的方案供青蛙跳躍過去贮庞。
提示：
2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
解法
這個(gè)題沒做出來，看了下別人的題解：
class Solution:
def canCross(self, stones: List[int]) -> bool:
# 假設(shè)每次都跳 k + 1 步
# 0 1 2 3 4 5 6 ： i
# 1 2 3 4 5 6 7 : step
# 那么第 i 個(gè)單位最遠(yuǎn)能夠條 i + 1 步
# 動(dòng)態(tài)規(guī)劃
# dp[i][k] 表示能否由前面的某一個(gè)石頭 j 通過跳 k 步到達(dá)當(dāng)前這個(gè)石頭 i 究西，這個(gè) j 的范圍是 [1, i - 1]
# 當(dāng)然窗慎，這個(gè) k 步是 i 石頭 和 j 石頭之間的距離
# 那么對(duì)于 j 石頭來說，跳到 j 石頭的上一個(gè)石頭的步數(shù)就必須是這個(gè) k - 1 || k || k + 1
# 由此可得狀態(tài)轉(zhuǎn)移方程：dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1]
stonesLen = len(stones)
if stones[1] != 1:
return False
dp = []
for i in range(stonesLen):
dp.append([])
for j in range(stonesLen+1):
dp[i].append(False)
# print(dp)
dp[0][0] = True
for i in range(stonesLen):
for j in range(i):
k = stones[i] - stones[j]
if k <= j + 1:
if dp[j][k-1] or dp[j][k] or dp[j][k+1]:
dp[i][k] = True
if i == (stonesLen-1) and dp[i][k]:
return True
return False
633. 平方數(shù)之和
題目
給定一個(gè)非負(fù)整數(shù) c ，你要判斷是否存在兩個(gè)整數(shù) a 和 b遮斥，使得 a2 + b2 = c 峦失。
示例 1：
輸入：c = 5
輸出：true
解釋：1 * 1 + 2 * 2 = 5
示例 2：
輸入：c = 3
輸出：false
示例 3：
輸入：c = 4
輸出：true
示例 4：
輸入：c = 2
輸出：true
示例 5：
輸入：c = 1
輸出：true
解法
直接遍歷，然后求差開根號(hào)看是不是一個(gè)整數(shù)即可术吗，對(duì)于0需要特別處理下宠进，為了效率，直接遍歷到根號(hào)c即可：
import math
class Solution:
def judgeSquareSum(self, c: int) -> bool:
if c == 0:
return True
for i in range(math.ceil(math.sqrt(c))):
difference = math.sqrt(c - i*i)
if int(difference) == difference:
return True
return False
優(yōu)化
看了下題解藐翎，用雙指針更快材蹬，其思想大概是先從i=0和j=根號(hào)c開始，不滿足的話前者依次加1吝镣，后者依次減1堤器，然后i和j不停趨近，如果i>j的話就說明找不到了：
import math
class Solution(object):
def judgeSquareSum(self, c):
"""
:type c: int
:rtype: bool
"""
j = int(math.sqrt(c))
i = 0
while i <= j:
total = i * i + j * j
if total > c:
j = j - 1
elif total < c:
i = i + 1
else:
return True
return False
783. 二叉搜索樹節(jié)點(diǎn)最小距離
題目
給你一個(gè)二叉搜索樹的根節(jié)點(diǎn) root 末贾，返回 樹中任意兩不同節(jié)點(diǎn)值之間的最小差值 闸溃。
注意：本題與 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同
示例 1：
輸入：root = [4,2,6,1,3]
輸出：1
示例 2：
輸入：root = [1,0,48,null,null,12,49]
輸出：1
提示：
樹中節(jié)點(diǎn)數(shù)目在范圍 [2, 100] 內(nèi)
0 <= Node.val <= 105
解法
這里遇到了一個(gè)問題，就是python的Null報(bào)錯(cuò)拱撵，說未定義：
NameError: name 'Null' is not defined
if cursor == Null:
Line 18 in minDiffInBST (Solution.py)
ret = Solution().minDiffInBST(param_1)
Line 45 in _driver (Solution.py)
_driver()
Line 56 in <module> (Solution.py)
通過搜索引擎辉川，發(fā)現(xiàn)這里應(yīng)該用None
然后遇到了第二個(gè)錯(cuò)誤：
UnboundLocalError: local variable 'pre' referenced before assignment
if pre != None and node != None and abs(pre.val - node.val) < smallestDis:
Line 16 in traversalTree (Solution.py)
traversalTree(node.left)
Line 15 in traversalTree (Solution.py)
traversalTree(node.left)
Line 15 in traversalTree (Solution.py)
traversalTree(root)
Line 21 in minDiffInBST (Solution.py)
ret = Solution().minDiffInBST(param_1)
Line 44 in _driver (Solution.py)
_driver()
Line 55 in <module> (Solution.py)
發(fā)現(xiàn)是python的變量作用域的問題，在python3里面可以用nonlocal關(guān)鍵字來解決
最終代碼如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDiffInBST(self, root: TreeNode) -> int:
pre = None
smallestDis = 10e5
def traversalTree(node):
nonlocal smallestDis
nonlocal pre
if node.left != None:
traversalTree(node.left)
if pre != None and node != None and abs(pre.val - node.val) < smallestDis:
smallestDis = abs(pre.val - node.val)
pre = node
if node.right != None:
traversalTree(node.right)
traversalTree(root)
return smallestDis
938. 二叉搜索樹的范圍和
題目
給定二叉搜索樹的根結(jié)點(diǎn) root拴测，返回值位于范圍 [low, high] 之間的所有結(jié)點(diǎn)的值的和乓旗。
示例 1：
輸入：root = [10,5,15,3,7,null,18], low = 7, high = 15
輸出：32
示例 2：
輸入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
輸出：23
提示：
樹中節(jié)點(diǎn)數(shù)目在范圍 [1, 2 * 104] 內(nèi)
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同
解法
直接遞歸遍歷二叉樹即可：
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
# cursor = root
allSum = 0
def traversalTree(cursor):
nonlocal allSum
if cursor.left:
traversalTree(cursor.left)
if cursor.val <= high and cursor.val >= low:
allSum += cursor.val
if cursor.right:
traversalTree(cursor.right)
traversalTree(root)
return allSum
1011. 在 D 天內(nèi)送達(dá)包裹的能力
題目
傳送帶上的包裹必須在 D 天內(nèi)從一個(gè)港口運(yùn)送到另一個(gè)港口。
傳送帶上的第 i 個(gè)包裹的重量為 weights[i]集索。每一天屿愚，我們都會(huì)按給出重量的順序往傳送帶上裝載包裹。我們裝載的重量不會(huì)超過船的最大運(yùn)載重量务荆。
返回能在 D 天內(nèi)將傳送帶上的所有包裹送達(dá)的船的最低運(yùn)載能力妆距。
示例 1：
輸入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
輸出：15
解釋：
船舶最低載重 15 就能夠在 5 天內(nèi)送達(dá)所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
請(qǐng)注意函匕，貨物必須按照給定的順序裝運(yùn)娱据，因此使用載重能力為 14 的船舶并將包裝分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允許的。
示例 2：
輸入：weights = [3,2,2,4,1,4], D = 3
輸出：6
解釋：
船舶最低載重 6 就能夠在 3 天內(nèi)送達(dá)所有包裹盅惜，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：
輸入：weights = [1,2,3,1,1], D = 4
輸出：3
解釋：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
提示：
1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500
解法
這里用二分法中剩，直接認(rèn)為最小裝載量是列表中的最大值，而最大裝載量是列表的總和酷窥，然后二分分別驗(yàn)證是否能夠裝載：
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
loadAbi = max(weights)
maxWeight = sum(weights)
if loadAbi == maxWeight:
return loadAbi
def checkLoad(theLoad):
temp = 0
count = 0
for i in range(len(weights)):
temp += weights[i]
if temp > theLoad:
temp = weights[i]
count += 1
if temp != 0:
count += 1
if count <= D:
return True
else:
return False
while loadAbi < maxWeight:
mid = (loadAbi + maxWeight) // 2
if checkLoad(mid):
maxWeight = mid
else:
loadAbi = mid + 1
return loadAbi
1720. 解碼異或后的數(shù)組
題目
未知 整數(shù)數(shù)組 arr 由 n 個(gè)非負(fù)整數(shù)組成咽安。
經(jīng)編碼后變?yōu)殚L度為 n - 1 的另一個(gè)整數(shù)數(shù)組 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 蓬推。例如妆棒，arr = [1,0,2,1] 經(jīng)編碼后得到 encoded = [1,2,3] 。
給你編碼后的數(shù)組 encoded 和原數(shù)組 arr 的第一個(gè)元素 first（arr[0]）。
請(qǐng)解碼返回原數(shù)組 arr 糕珊《郑可以證明答案存在并且是唯一的。
示例 1：
輸入：encoded = [1,2,3], first = 1
輸出：[1,0,2,1]
解釋：若 arr = [1,0,2,1] 红选，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
示例 2：
輸入：encoded = [6,2,7,3], first = 4
輸出：[4,2,0,7,4]
提示：
2 <= n <= 104
encoded.length == n - 1
0 <= encoded[i] <= 105
0 <= first <= 105
解法
由于異或具有自反性澜公，即a^b = c可得出a^c = b，因此直接循環(huán)異或即可：
class Solution:
def decode(self, encoded: List[int], first: int) -> List[int]:
originList = [first]
for n in encoded:
originList += [n ^ originList[-1]]
return originList
