LeetCode是一个刷算法题的网站，这里用的是python3，做一下刷题记录
1. 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 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
只会存在一个有效答案
解法
直接穷举即可：
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]
优化算法
可以通过hashmap的方式将时间复杂度将至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. 两数相加
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 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]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
解法
这里做题习惯性忽略注释，于是吃了个大亏，最终解决如下：
# 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. 移除元素
题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
解法
这个题目的意思也就是直接在原列表中进行更改，因此直接使用remove即可：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
while val in nums:
nums.remove(val)
return len(nums)
在评论区看到了一种快慢指针的方法（据说时间更优，但python执行结果倒是差不多）：
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. 实现 strStr()
题目
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 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 仅由小写英文字符组成
解法
解法如下（执行用时：36 ms, 在所有 Python3 提交中击败了89.52%的用户内存消耗：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 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 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 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
提示：
1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。
解法
自己没做出来，看了下别人的答案，照着写了个：
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. 最大数
题目
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 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
解法
直接将两个数字拼接比大小即可，最后去掉一下前导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. 实现 Trie (前缀树)
题目
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 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 调用次数 总计 不超过 3 * 104 次
解法
根据相应的函数写出对应功能即可（内存消耗极小，但运行时间奇高，执行用时: 2356 ms，内存消耗: 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)
看了下题解，看到一个代码更简更加省内存（执行用时：424 ms, 内存消耗：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)
但是严格来说都不符合前缀树的定义，于是查了下更省时间的前缀树的写法（执行用时：120 ms，内存消耗：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. 青蛙过河
题目
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
示例 2：
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
提示：
2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
解法
这个题没做出来，看了下别人的题解：
class Solution:
def canCross(self, stones: List[int]) -> bool:
# 假设每次都跳 k + 1 步
# 0 1 2 3 4 5 6 ： i
# 1 2 3 4 5 6 7 : step
# 那么第 i 个单位最远能够条 i + 1 步
# 动态规划
# dp[i][k] 表示能否由前面的某一个石头 j 通过跳 k 步到达当前这个石头 i ，这个 j 的范围是 [1, i - 1]
# 当然，这个 k 步是 i 石头 和 j 石头之间的距离
# 那么对于 j 石头来说，跳到 j 石头的上一个石头的步数就必须是这个 k - 1 || k || k + 1
# 由此可得状态转移方程：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. 平方数之和
题目
给定一个非负整数 c ，你要判断是否存在两个整数 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
解法
直接遍历，然后求差开根号看是不是一个整数即可，对于0需要特别处理下，为了效率，直接遍历到根号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
优化
看了下题解，用双指针更快，其思想大概是先从i=0和j=根号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. 二叉搜索树节点最小距离
题目
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
注意：本题与 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
提示：
树中节点数目在范围 [2, 100] 内
0 <= Node.val <= 105
解法
这里遇到了一个问题，就是python的Null报错，说未定义：
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)
通过搜索引擎，发现这里应该用None
然后遇到了第二个错误：
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)
发现是python的变量作用域的问题，在python3里面可以用nonlocal关键字来解决
最终代码如下：
# 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. 二叉搜索树的范围和
题目
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
示例 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
提示：
树中节点数目在范围 [1, 2 * 104] 内
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 天内送达包裹的能力
题目
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 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
解法
这里用二分法，直接认为最小装载量是列表中的最大值，而最大装载量是列表的总和，然后二分分别验证是否能够装载：
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. 解码异或后的数组
题目
未知 整数数组 arr 由 n 个非负整数组成。
经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
请解码返回原数组 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，因此直接循环异或即可：
class Solution:
def decode(self, encoded: List[int], first: int) -> List[int]:
originList = [first]
for n in encoded:
originList += [n ^ originList[-1]]
return originList
