这里是 HOT 100刷题笔记，篇幅较长，因此分成两部分，按照题目序号排列。有几题没做后序会补上。
- 两数之和
比较好的办法就是利用map来存储每一个元素以及其对应的索引，但是这里要考虑到map是无法存储重复的key，因此我们在判断是否存在满足符合条件的，一个为原数组中的索引，另一个为Map中的索引这个一定要注意。
解法1：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
Map = {}
for i in range(len(nums)):
Map[nums[i]] = i
for i in range(len(nums)):
j = Map.get(target - nums[i])
if j and j != i:
return[i, j]
return []
解法2：（将两个for循环合并一下，可以让程序提前终止，让Map存储当前元素之前的信息）
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
Map = {}
for i in range(len(nums)):
j = Map.get(target - nums[i])
if j != None :
return[j, i]
Map[nums[i]] = i #这一步的顺序不能调换
return []
- 两数相加
这一题其实就是两个链表相加，这一需要考虑到两个链表的长度不一致和进位的情况，这一题还有一个小技巧，就是使用一个头节点，这样代码写起来更方便。
# 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:
s = 0
head = p = ListNode(0)
while(l1 or l2 or s):
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
p.next = ListNode(s%10)
p = p.next
s = s // 10
if l1:
l1 = l1.next
else:
l1 = None
if l2:
l2 = l2.next
else:
l2 = None
return head.next
- 最长无重复子串
经典的滑动窗口题目，模板题，详情参考：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = {}
left = 0
right = 0
length = len(s)
res = 0
while(right < length):
c = s[right]
if c not in window:
window[c] = 1
else:
window[c] += 1
right += 1
while(window[c] > 1):
d = s[left]
left += 1
window[d] -= 1
res = max(res, right-left)
return res
- 最长回文子串
这一题与647回文字串这一题一样，具体的我就不多说了。
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ''
length = len(s)
dp = [[0]*length for i in range(length)]
for i in range(length):
for j in range(length):
if i == j:
dp[i][j] = 1
maxlength = 1
res = s[0]
for i in range(length-1, -1, -1):
for j in range(i+1, length):
if s[j] == s[i]:
if j == i+1:
dp[i][j] = 1
else:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = 0
if dp[i][j] == 1:
if j - i + 1 > maxlength:
maxlength = j - i + 1
res = s[i:j+1]
return res
- 盛最多水的容器
简单的DP:
采用双指针进行搜索，将a[i]和a[j]中较小的坐标进行移动，因为将较大的往里进行移动，最终的结果一定会变小。
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
res = -99999999
while(i <= j):
res = max(res, min(height[i], height[j])*(j - i))
if height[i] < height[j]:
i += 1
else:
j -= 1
return res
- 三数之和
参考：https://blog.csdn.net/sd4567855/article/details/86777399 先排序再利用双指针来去重。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
length = len(nums)
if length < 3 or nums[0] > 0 or nums[-1] < 0 :
return res
for i in range(length-2):
if nums[i] > 0:
break
if i > 0 and nums[i-1] == nums[i]:
continue
j = i + 1
k = length - 1
while(j < k):
if nums[i] + nums[j] + nums[k] == 0:
res.append([nums[i], nums[j], nums[k]])
while(j < k and nums[j] == nums[j+1]):
j += 1
while(j < k and nums[k-1] == nums[k]):
k -= 1
j += 1
k -= 1
elif nums[i] + nums[j] + nums[k] > 0:
k -= 1
else:
j += 1
return res
- 电话号码的字母组合
简单的DFS即可。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
Dict = {'2':{'a', 'b', 'c'},
'3':{'d', 'e', 'f'}, '4':{'g', 'h', 'i'}, '5':{'j', 'k', 'l'},
'6':{'m', 'n', 'o'}, '7':{'p', 'q', 'r', 's'}, '8':{'t', 'u', 'v'},
'9':{'w', 'x', 'y', 'z'}}
length = len(digits)
res = []
def dfs(route, count):
if count == length:
res.append(route)
return
for c in Dict[digits[count]]:
dfs(route + c, count + 1)
dfs('', 0)
return res
- 删除链表的倒数第N个节点
快慢指针，基本操作，需要注意的是有一种情况是直接删除头节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
return None
temp = head
count = 0
while(temp):
count += 1
if count == n:
break
temp = temp.next
slow = head
fast = temp
pre = None
while(fast.next):
fast = fast.next
pre = slow
slow = slow.next
if not pre:
return head.next
pre.next = slow.next
return head
- 有效的括号
- 比较直接的方法就是利用python的正则表达式直接对这三种括号进行替换。
- 借助栈结构来完成括号的匹配操作。
解法1：
class Solution:
def isValid(self, s: str) -> bool:
while('()' in s or '{}' in s or '[]' in s):
s = s.replace('()', '')
s = s.replace('[]', '')
s = s.replace('{}', '')
return s == ''
解法2：
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c == '(' or c == '[' or c == '{':
stack.append(c)
else:
if not stack:
return False
if c == ')':
temp = stack.pop()
if temp != '(':
return False
elif c == ']':
temp = stack.pop()
if temp != '[':
return False
elif c == '}':
temp = stack.pop()
if temp != '{':
return False
return stack == []
- 合并两个有序链表
正常的链表遍历操作，注意在合并链表的时候，除了要保存头节点以外，还需要用一个指针来记录链表当前节点的位置。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
head1 = l1
head2 = l2
head3 = None
temp = None
if head1.val <= head2.val:
head3 = head1
temp = head3
head1 = head1.next
else:
head3 = head2
temp = head3
head2 = head2.next
while(head1 and head2):
if head1.val <= head2.val:
temp.next = head1
temp = head1
head1 = head1.next
else:
temp.next = head2
temp = head2
head2 = head2.next
while(head1):
temp.next = head1
temp = head1
head1 = head1.next
while(head2):
temp.next = head2
temp = head2
head2 = head2.next
return head3
- 括号生成
https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
这一题使用递归比较符合正常的想法，同样需要设计好递归函数的参数，这里使用route，left，right这三个参数，分别表示存储的路径，左括号还剩余的数量，右括号还剩余的数量，该递归函数没有返回值，使用全局变量来存储不同的路径。
当左右剩余的括号数量为0的时候，表明找到了满足题意的路径。
当剩余的左括号数量大于剩余的右括号数量的时候，程序终止，因为这样生成的路径一点不满足题意。
左右剩余的括号数量大于0的时候，才进行下一次扩展。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(route, left, right):
if left == 0 and right == 0:
res.append(route)
return
if left > right:
return
if left > 0:
dfs(route + '(', left - 1, right)
if right > 0:
dfs(route + ')', left, right - 1)
dfs('', n, n)
return res
- 合并K个排序链表
比较直观的做法，直接利用分治的方法，接下来的重点就是如何设计好递归函数的参数了。
递归函数的参数还是借用二分的写法，采用左右边界来确定链表的个数。
也可以通过建立一个堆来合并这k个链表。
解法1：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def merge(l1, l2):
p = ListNode()
temp = p
while(l1 and l2):
if l1.val < l2.val:
temp.next = l1
l1 = l1.next
else:
temp.next = l2
l2 = l2.next
temp = temp.next
if l1 :
temp.next = l1
else:
temp.next = l2
return p.next
def recursion(l, r):
if l == r:
return lists[l]
if l > r:
return
mid = (l + r) // 2
left = recursion(l, mid)
right = recursion(mid + 1, r)
return merge(left, right)
return recursion(0, len(lists) - 1)
解法2：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from heapq import heappush, heappop
class MyNode:
def __init__(self, node):
self.node = node
def __lt__(self, other):
if self.node.val <= other.node.val:
return True
else: return False
def get(self):
return self.node
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
for l in lists:
if l:
heappush(heap, MyNode(l))
p = head = ListNode(0)
while heap:
node = heappop(heap)
p.next = node.get()
p = p.next
if node.get().next:
heappush(heap, MyNode(node.get().next))
return head.next
- 下一个排列
求下一个排列有着比较标准的算法，这个在组合数学上都有专门讲过，C++中STL也专门封装了这个方法。算法分为三步：
- 从后往前搜，找到第一个跳变：要求后一个大于前一个，如果没有说明当前排列已经是最大的了。
- 通过前面的跳变查找将数组分成了前后两个部分，在后面部分的数组中找到第一个大于跳变的那个数，进行交换。
- 将后面部分的数组按照从小到达的顺序进行交换。
语言表述可能不是很清楚，参考：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums) - 1
i = length
while(i >= 1 and nums[i-1] >= nums[i]):
i -= 1
if i == 0:
nums.reverse()
return nums
j = length
while(j >= 0 and nums[j] <= nums[i-1]):
j -= 1
temp = nums[j]
nums[j] = nums[i-1]
nums[i-1] = temp
res = nums[i:]
for i in range(len(res)):
nums[length-i] = res[i]
return nums
- 最长有效括号
直观上来看需要用到栈这样的结构。需要记录啥时候入栈，啥时候会出栈。当栈为空的时候，当前元素为'('或者当前栈顶元素为')'入栈，否则出栈，入栈的是字符的索引，这样方便计算出括号的长度。
class Solution:
def longestValidParentheses(self, s: str) -> int:
if s == "":
return 0
stack = []
res = 0
for index, c in enumerate(s):
if not stack or c == '(' or s[stack[-1]] == ')': #注意细节
stack.append(index)
else:
stack.pop()
temp = stack[-1] if stack else -1 #注意细节
res = max(res, index - temp )
return res
- 搜索旋转排序数组
那这一题显然是要用二分查找，但是这一题却是局部有序，因此我们需要在原始的二分查找上面进行一些改动，一半来说二分查找的难点在于边界条件。首先需要判断元素是在左边部分还是右边部分，然后对于左边部分和右边部分需要各自判断其的左右部分。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[left]:
if nums[mid] > target and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
- 在排序数组中查找元素的第一个和最后一个位置
二分法查找左边界和右边界，二分法的细节太难写了，开区间还是闭区间，等于还是不等于都需要注意。这里还有一种写法来求左右边界，如果有那么就一直向左移动或者是向右移动，没有的话就返回-1。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def serachLeft(nums):
if not nums:
return -1
left = 0
right = len(nums) - 1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target: #要求找最左边，因此更新右边界
right = mid - 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
if left <= len(nums) - 1 and nums[left] == target: #注意
return left
else:
return -1
def searchRight(nums):
if not nums:
return -1
left = 0
right = len(nums) - 1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target: #要求找最右边，因此更新左边界
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
if right >= 0 and nums[right] == target: #注意
return right
else:
return -1
return [serachLeft(nums), searchRight(nums)]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def search_left(nums):
l = 0
r = len(nums)-1
while(l <= r):
mid = (l+r) // 2
if nums[mid] == target:
left = mid
right = mid
while(left>=1):
if nums[left] == nums[left-1]:
left = left - 1
else:
break
while(right <= len(nums)-2):
if nums[right] == nums[right+1]:
right = right + 1
else:
break
return [left, right]
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return [-1, -1]
return search_left(nums)
最后一种写法:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def left_search(nums):
l = 0
r = len(nums) - 1
while(l <= r):
mid = (l + r) // 2
if nums[mid] == target:
r = mid - 1
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
if l == len(nums) or nums[l] != target:
return -1
return l
def right_searh(nums):
l = 0
r = len(nums) - 1
while(l <= r):
mid = (l + r) // 2
if nums[mid] == target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
if r < 0 or nums[r] != target:
return -1
return r
l = left_search(nums)
r = right_searh(nums)
return [l, r]
- 组合总和
标准的DFS，需要设计好递归函数的参数。基本的遍历和剪枝都很简单，关键是如何去重，这个跟以前的DFS有区别，不能用标记来记录走过的路径，因为这里的数字可以重复选取。解法里给了一个索引来记录当前节点的顺序，在下一次的遍历中从这个节点开始，这样就保证了数字可以重复选取，也避免了路径的重复。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, sumNum, route):
if sumNum == 0:
res.append(route)
return
for index in range(i, len(candidates)):
if sumNum >= candidates[index]:
dfs(index, sumNum - candidates[index], route + [candidates[index]])
dfs(0, target, [])
return res
- 接雨水
这一题本质上是要求一个定值，第一眼看到这题我也没啥好的思路，看了题解才知道要用单调递减栈。需要使用栈是因为新的凹槽左边界一定是最新遇到的，而要使用递减栈是因为当低的遇到高的才会相应的凹槽。在具体实现上这一题有很多细节，首先我们入栈是元素的下标，因为后面我们需要使用下标来求宽度。当前栈不为空且当前元素大于栈顶则出栈。在计算凹槽能存储的雨水时，需要当前元素，前一个元素，后面一个元素来共同计算，当没有前一个元素的时候，直接跳出，计算凹槽的宽度没啥难度，但是计算凹槽的高度的时候需要注意：前后两个高度取较低的再减去中间这个最低的才能得到相对高度差。
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
stack = []
for i in range(len(height)):
while(stack and height[stack[-1]] < height[i]):
temp = stack.pop()#出栈
if not stack:#没有前一个元素直接跳出
break
left = stack[-1]
right = i
width = right - left -1
length = min(height[left], height[right]) - height[temp]
ans += width*length
stack.append(i)#下标入栈
return ans
- 全排列
标准的排列做法。这里需要注意一下python中传递列表这一类数据的时候
解法1：（错误）
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
route = [0]*length
flags = [0]*length
def dfs(count):
if count == length:
print(route)
res.append(route)
return
for i in range(length):
if flags[i] == 0:
flags[i] = 1
route[count] = nums[i]
dfs(count + 1)
flags[i] = 0
dfs(0)
return res
解法2：(对传递的列表进行复制)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
route = [0]*length
flags = [0]*length
def dfs(count):
if count == length:
print(route)
res.append(route[:])
return
for i in range(length):
if flags[i] == 0:
flags[i] = 1
route[count] = nums[i]
dfs(count + 1)
flags[i] = 0
dfs(0)
return res
解法3：（将存储路径的变量采用参数的形式来传递）
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
flags = [0]*length
def dfs(count, route):
if count == length:
res.append(route)
return
for i in range(length):
if flags[i] == 0:
flags[i] = 1
dfs(count + 1, route + [nums[i]])
flags[i] = 0
dfs(0, [])
return res
- 旋转图像
先将矩阵进行转置，再将每一行反转即可。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
for i in range(len(matrix)):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(len(matrix)):
matrix[i].reverse()
- 字母异位词分组
比较好的办法就是利用字典，但是我们需要区分好键值，这里使用排序函数来进行区分。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
Dict = {}
for s in strs:
key = ''.join(sorted(s))
if key not in Dict:
Dict[key] = []
Dict[key].append(s)
return list(Dict.values())
- 最大子序和
简答的DP。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0]*len(nums)
dp[0] = nums[0]
res = nums[0]
for i in range(1, len(nums)):
if dp[i-1] < 0:
dp[i] = nums[i]
else:
dp[i] = dp[i-1] + nums[i]
res = max(res, dp[i])
return res
- 跳跃游戏
这一题需要用动态规划，k表示到达第i步时，能够走的最远距离。如果k<i那么就返回False，每次对k进行更新 k = max(k, i+nums[i])
解法1：超时
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
flags = [0]*length
flags[0] = 1
for i in range(length-1):
if flags[i] == 1:
for j in range(i, min(i+nums[i]+1, length)):
flags[j] = 1
if flags[-1] == 1:
return True
if flags[-1] == 1:
return True
else:
return False
解法2：
k表示在在当前位置能够走到的最远距离。
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
k = 0
for i in range(length):
if i > k:
return False
k = max(k, i + nums[i])
return True
- 合并区间
这个题目从暴力上是没法解决的，暴力的复杂度是n!，只能通过排序的手段来降低时间复杂度。注意cmp_to_key这个关键字需要引入functools包。
按照贪心的策略来进行排序，优先按照左端从小到大进行排序，如果左端相同则将右端较大的放在前面，如果前一个区间的右端点小于后一个区间的左端点，那么这两个区间不会重合，否则两个重复，新区间的右端点为这两个区间有边界的较大值。
改正，这个题目只需要对左边界排序即可，其他的不用管。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
def compare(a, b):
if a[0] > b[0] or (a[0] == b[0] and a[1] < b[1]):
return 1
elif a[0] == b[0] and a[1] == b[1]:
return 0
else:
return -1
intervals.sort(key = cmp_to_key(compare))
res = [intervals[0]]
for left, right in intervals[1:]:
temp = res[-1]
if left > temp[1]: #注意是严格大于
res.append([left, right])
else:
res[-1][1] = max(right, temp[1])
return res
- 不同路径
第一眼看上去像是简单的迷宫搜索问题，可以直接尝试暴力搜索，结果超时，这里我给了两种写法，第一种使用了标记数组，后面发现是没有必要的，因为根据题意是绝对不会往回走的。回过头来仔细看一下，这个题其实就是组合数的定义，或者我们也可以使用标准的DP来解决：
需要注意初始化的问题，不然结果全为0。
解法1：超时
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
self.count = 0
flags = [[0]*m for i in range(n)]
def dfs(x, y):
if x == n-1 and y == m-1:
self.count += 1
if x <0 or x >n-1 or y < 0 or y > m-1:
return
for (delta_x, delta_y) in [(0, 1), (1, 0)]:
if x+delta_x < 0 or x+delta_x > n-1 or y+delta_y <0 or y+delta_y > m-1:
continue
if flags[x+delta_x][y+delta_y] == 0:
flags[x+delta_x][y+delta_y] = 1
dfs(x+delta_x, y+delta_y)
flags[x+delta_x][y+delta_y] = 0
flags[0][0] = 1
dfs(0, 0)
return self.count
解法2：超时
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
self.count = 0
def dfs(x, y):
if x == n-1 and y == m-1:
self.count += 1
if x <0 or x >n-1 or y < 0 or y > m-1:
return
dfs(x+1, y)
dfs(x, y+1)
dfs(0, 0)
return self.count
解法3：DP
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0]*(m + 2) for i in range(n+2)]
for i in range(1, n+1):
for j in range(1, m+1):
if i == 1 and j == 1:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n][m]
- 最小路径和
同样这一题是非常基础的DP，按照我之前的写法将数组外围扩充一下，但是这种写法不能填充0，应该填充一个很大的值。这个一定要注意。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
width = len(grid)
length = len(grid[0])
dp = [[0]*length for i in range(width)]
for i in range(0, width):
for j in range(0, length):
if i == 0 and j == 0:
dp[i][j] = grid[i][j]
elif i == 0 and j != 0:
dp[i][j] = dp[i][j-1] + grid[i][j]
elif i !=0 and j == 0:
dp[i][j] = dp[i-1][j] + grid[i][j]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
- 爬楼梯
斐波拉契数列，注意初始值。
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0]*n
dp[0] = 1
dp[1] = 2
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]
return dp[n-1]
- 编辑距离
这一题也是经典的DP，这一题与求两个序列的最长公共子序列这一题类似，同样是二阶DP。
假设现在有两个字符串a，b，dp[i][j]表示a[:i]和b[:j]这两个字串的最短编辑距离，那么我们可以得到相应的状态转移方程：
a[i]=b[j]的时候很好理解，当a[i]!=b[j]的时候，我们以a为例，我们可以将a[i]修改成和b[j]一样的，这个时候就转换成求dp[i-1][j-1]了，我们也可以直接将a[i]删除，但是删除a[i]之后，我们也无法去顶a[i-1]和b[j]是否相等，这个时候问题转换成求dp[i-1][j]，我们也可以在a[i]后面增加一个和b[j]一样的元素，这个时候a[i+1]和b[j]是一样的，然后问题就转换成dp[i][j-1]了。在具体实现的时候，我们需要添加一个空串，因为这样容易初始化，因此代码中会有相应的调整。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
length1 = len(word1) + 1
length2 = len(word2) + 1
#print(length1, length2)
dp = [[0]*length1 for i in range(length2)]
for i in range(length2):
dp[i][0] = i
for j in range(length1):
dp[0][j] = j
for i in range(1, length2):
for j in range(1, length1):
if word2[i-1] == word1[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
#print(i, j)
dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
return dp[-1][-1]
- 颜色分类
三色国旗问题。官方题解写的挺好的：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/ ，关于这个算法其实也比较好理解。p0表示左边界，p2表示右边界，cur表示遍历的当前元素，因为最终我们需要让整个数组变成递增的形式，当nums[cur] = 2的时候，就需要和nums[p2]进行交换，并且将p2左移，当nums[cur] = 0的时候，就需要和nums[p1]进行交换，并且cur和p1都要右移，当nums[cur] = 1的时候，只需要cur右移即可。
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
p0 = cur = 0
p2 = len(nums) - 1
while(cur <= p2):
if nums[cur] == 2:
nums[cur], nums[p2] = nums[p2], nums[cur]
p2 -= 1
elif nums[cur] == 0:
nums[cur], nums[p0] = nums[p0], nums[cur]
cur += 1
p0 += 1
else:
cur += 1
- 最小覆盖子串
同样是经典的滑动窗口题目。需要维护两个字典，和两个指针。但是这一题需要子串覆盖，因此窗口收缩的条件更为严格，不能简单的通过双指针之间的距离大于等于目标串的长度就来进行窗口收缩操作，这样会增加时间复杂度。
class Solution:
def minWindow(self, s: str, t: str) -> str:
window = {}
need = {}
left = 0
right = 0
valid = 0
maxlength = inf
temp = 0
for c in t:
if c not in need:
need[c] = 1
else:
need[c] += 1
while(right < len(s)):
c = s[right]
right += 1
if c not in window:
window[c] = 1
else:
window[c] += 1
if c in need:
if window[c] == need[c]:
valid += 1
while(valid == len(need)): #这个收缩条件更为严格
if right - left < maxlength:
maxlength = right - left
temp = left
c = s[left]
left += 1
if c in need:
if need[c] == window[c]:
valid -= 1
window[c] -= 1
if maxlength == inf:
return ''
else:
return s[temp:temp+maxlength]
- 子集
类似于生成全排列，用一个深度优先搜索最为直接。具体的实现的时候需要注意终止条件，这里不需要使用标记数组来防止重复遍历。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
res = []
def dfs(count, route):
if count == length:
res.append(route)
return
for i in range(2):
if i == 1:
dfs(count + 1, route + [nums[count]])
else:
dfs(count + 1, route)
dfs(0, [])
return res
- 单词搜索
同样是DFS，但是这个DFS搜索稍微有点复杂。递归函数参数有3个，分别表示横纵坐标和走过的步数，由于这个题需要从所有可能的路径中找出一条满足题意的路径，因此这一题需要采用for循环的写法：用flags标记数组来在防止同一条路径上重复遍历，并且还要保证不同的路径之间互不影响。在进行下一步递归的时候需要保证不越界、未走过、且保证当前遍历的元素与word中相同位置的元素相同这三个条件。最后需要注意的是，这一题需要剪枝，也就是当找到一条满足题意的路径的时候，需要立刻将程序终止，否则会超时。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
length = len(board)
width = len(board[0])
flags = [[0]*width for i in range(length)]
self.res = 0
def dfs(x, y, count):
if count == len(word):
self.res = 1
return
for delta_x, delta_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if self.res == 1:
return
if x + delta_x >= 0 and x + delta_x <= length -1 and y + delta_y >= 0 and y + delta_y <= width - 1 and flags[x + delta_x][y + delta_y] == 0 and board[x+delta_x][y+delta_y] == word[count]:
flags[x + delta_x][y + delta_y] = 1
dfs(x + delta_x, y + delta_y, count + 1)
flags[x + delta_x][y + delta_y] = 0
for i in range(length):
for j in range(width):
if board[i][j] == word[0]:
flags[i][j] = 1
dfs(i, j, 1)
flags[i][j] = 0
if self.res == 1:
return True
return False
- 柱状图中最大的矩形
这一题与接雨水这一题神似，不同的是，接雨水那一题需要碰到更高的才会形成相应的凹槽，而这一题是遇到更低的柱形之后，后面会有凹槽这样无法形成对应的矩形，只能计算前面的矩形了。因此这一题也需要使用到单调栈，单调不减的栈，这一同样需要把元素索引入栈，因为需要计算对应的宽度，在计算宽度的时候还需要考虑前面是否有柱形，还有一个技巧就是在最后加上一个高度为0的柱形，计算宽度需要注意下，右边界为当前元素的位置，左边界为出栈后的栈顶，没有的话就为空。参考：https://blog.csdn.net/Zolewit/article/details/88863970
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0) #注意这一步
stack = []
res = 0
for i in range(len(heights)):
while(stack and heights[i] < heights[stack[-1]]):
mid = stack.pop()
right = i #注意这一步
if not stack:
width = right
else:
left = stack[-1] #注意这一步
width = right - left - 1
res = max(res, width*heights[mid])
stack.append(i)
return res
- 二叉树的中序遍历
题目要求使用非递归的方式来完成。这就需要定义一个栈来模拟系统栈的压栈、弹栈过程。
在模拟中序遍历的时候，同样需要让左子树不断入栈，直到最左边即可。若当前节点为空，则出栈并获取栈顶元素的值，并将当前元素更新到其右子树的状态。整个循环终止的条件为当前节点为空且栈也为空。
详细情况请参考：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
cur = root
while(cur or stack):
while(cur):
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
- 不同的二叉搜索树
简单的DP，dp[i]表示i个节点的树能够构成二叉搜索的种类:
如果这一题是普通的二叉树的话，就需要再乘以n!。
class Solution:
def numTrees(self, n: int) -> int:
dp = [0]*(n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(0, i):
dp[i] += dp[j]*dp[i-1-j]
return dp[n]
- 验证二叉搜索树
简单的递归函数即可，同样需要设计好参数和返回值，递归函数其实比较简单，违反二叉树的性质就返回False，当树遍历到空节点的时候返回True，因为这个时候表示在遍历过程中没有出现任何违反二叉搜索树性质的情况，最后当所有的条件都满足的时候，返回True即可。但是有一点需要注意，就是右子树的每一个节点都要大于根节点，左子树的每一个节点都要小于根节点，因此单独地判断每一个根节点和其左右子节点的大小关系是不够的。这里第一种解法就是这种错误的解法。
解法1：错误的解法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
if root.left:
if root.left.val >= root.val:
return False
if root.right:
if root.right.val <= root.val:
return False
left = self.isValidBST(root.left)
right = self.isValidBST(root.right)
if not left or not right:
return False
else:
return True
解法2：在递归函数的参数里设置上下界，lower和upper，注意是开区间：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
minNum = -9999999999
maxNum = 9999999999
def dfs(root, minNum, maxNum):
if not root:
return True
if root.val <= minNum or root.val >= maxNum:
return False
left = dfs(root.left, minNum, root.val)
right = dfs(root.right, root.val, maxNum)
if not left or not right:
return False
else:
return True
return dfs(root, minNum, maxNum)
- 对称二叉树
- 有一种最笨的办法就是直接将这棵树进行交换然后再遍历，如果遍历的结果相同，那么说明这是一颗对称树，这里强调一下，应该使用先序遍历，使用中序遍历的话有些数据过不了。
- 建立一个合理的递归关系，直接对左右子树进行判断，不满足相应的条件就返回False，满足相应的条件就返回True，但是要注意的一点是根节点为空需要单独判读，不能放在递归函数里，递归函数里的参数为两个表示左右子树。
解法1：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def swap(root):
if not root:
return None
newRoot = TreeNode()
temp1 = root.left
temp2 = root.right
root.left = swap(temp2)
root.right = swap(temp1)
'''
newRoot.val = root.val
newRoot.left = swap(root.right)
newRoot.right = swap(root.left)
return newRoot
'''
return root
def dfs(root):
if not root:
return ['null']
else:
left = dfs(root.left)
right = dfs(root.right)
return [root.val] + left + right
res1 = dfs(root)
newNode = swap(root)
res2 = dfs(newNode)
if res1 == res2:
return True
else:
return False
解法2：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def judge(left, right):
if not left and not right:
return True
if not left:
return False
if not right:
return False
if left.val != right.val:
return False
return judge(left.left, right.right) and judge(left.right, right.left)
if not root:
return True
if judge(root.left, root.right):
return True
else:
return False
