【力扣Hot 100】学习记录（Python版）_python版本力扣100

文章目录

• 二叉树
• • 104. 二叉树的最大深度【简单】
  • 94. 二叉树的中序遍历【简单】
  • 98. 验证二叉搜索树【中等】
  • 543. 二叉树的直径【简单】
• 字符串
• • 20. 有效的括号【简单】
  • 32. 最长有效括号【困难】
  • 647. 回文子串【中等】
• 搜索查找
• • 448. 找到所有数组中消失的数字【简单】
  • 136. 只出现一次的数字【简单】
  • 704. 二分查找【简单】
• 排列
• • 283. 移动零【简单】
• 组合
• • 49. 字母异位词分组【中等】
  • 78. 子集【中等】
• 链表
• • 206. 反转链表【简单】
  • 234. 回文链表【简单】
• 位运算
• • 461. 汉明距离【简单】
  • 338. 比特位计数【简单】
• 排序
• • 冒泡排序

参考博客：LeetCode热题100Python解【题型分类】

二叉树

104. 二叉树的最大深度【简单】

思路：递归、最终深度需要加1

class Solution(object): def maxDepth(self, root): \"\"\" :type root: Optional[TreeNode] :rtype: int \"\"\" if root is None: return 0 else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right) return max(left_height, right_height) + 1

94. 二叉树的中序遍历【简单】

思路：递归、列表可以用加法append

class Solution(object): def inorderTraversal(self, root): \"\"\" :type root: Optional[TreeNode] :rtype: List[int] \"\"\" if root is None: return [] else: # 中序 return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

同理，前序遍历和后序遍历如下：

# 前序return [root.val] + self.inorderTraversal(root.left) + self.inorderTraversal(root.right)# 后序return self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]

98. 验证二叉搜索树【中等】

思路：中序遍历、判断单增

class Solution(object): def isValidBST(self, root): \"\"\" :type root: Optional[TreeNode] :rtype: bool \"\"\" def solve(root): if root is None: return [] else: return helper(root.left) + [root.val] + helper(root.right) tree_values = solve(root) ans = True for i in range(len(tree_values) - 1): if tree_values[i] >= tree_values[i + 1]: ans = False return ans

543. 二叉树的直径【简单】

思路：DFS

class Solution(object): def diameterOfBinaryTree(self, root): \"\"\" :type root: Optional[TreeNode] :rtype: int \"\"\" self.ans = 1 # 最大node数（全局变量） def solve(node): if node is None: return 0 left_depth = solve(node.left) right_depth = solve(node.right) total_length = left_depth + right_depth self.ans = max(self.ans, total_length + 1) # 加上root的node数 return max(left_depth, right_depth) + 1 # node数  solve(root) return self.ans - 1 # 得到的node数减1得到路径长

字符串

20. 有效的括号【简单】

思路：遇到左符号直接入栈，右符号则开始匹配，匹配标准是stack需要非空，并且和最近的元素成对。注意最终stack必须被消耗为空才成功。注意：列表非空的判断语法是if not list，而不是if list is None

class Solution(object): def isValid(self, s): \"\"\" :type s: str :rtype: bool \"\"\" if len(s) % 2 == 1: return False else: # 预定义匹配对 pairs_dict = { \")\": \"(\", \"}\": \"{\", \"]\": \"[\", } stack = [] # 空栈 for c in s: if c in pairs_dict: # 是右符号 待匹配  if not stack or stack[-1] != pairs_dict[c]: return False  stack.pop() else: # 是左符号 入栈  stack.append(c) # 最终stack必须被消耗为空才行 if not stack: return True else: return False

32. 最长有效括号【困难】

思路：栈存储下标而非元素值，这样就可以在后面用下标减法来计算长度。注意需要在开头插入-1，方便后面栈空的时候有东西可以减。

class Solution(object): def longestValidParentheses(self, s): \"\"\" :type s: str :rtype: int \"\"\" stack = [] ans = 0 # 存储最大长度的答案 stack.append(-1) # 为了后面计算下标差值时，有足够的元素减 for i in range(len(s)): if s[i] == \"(\": stack.append(i) else: stack.pop() if stack: # 非空  ans = max(ans, i - stack[-1]) else:  stack.append(i) return ans

647. 回文子串【中等】

思路：中心扩展（分奇数和偶数长度的回文）

class Solution(object): def countSubstrings(self, s): \"\"\" :type s: str :rtype: int \"\"\" n = len(s) def solve(left, right): cnt = 0 # 中心扩展法 while 0 <= left < n and 0 <= right < n and s[left] == s[right]: cnt += 1 left -= 1 right += 1 return cnt ans = 0 for i in range(n): ans += solve(i, i) # 奇数长度回文 ans += solve(i, i+1) # 偶数长度回文 return ans

搜索查找

448. 找到所有数组中消失的数字【简单】

思路：不能用python的if i in list，因为其实底层也是循环，会超时。最简单的做法是用辅助的flag来记录哪些位置有元素

class Solution(object): def findDisappearedNumbers(self, nums): \"\"\" :type nums: List[int] :rtype: List[int] \"\"\" n = len(nums) ans = [] flag = [] for i in range(n): flag.append(0) for i in range(n): flag[nums[i] - 1] = 1 # 减1是因为nums属于[1, n] for i in range(n): if flag[i] == 0: ans.append(i + 1) # 加1是因为前面的减1移动了范围 return ans

136. 只出现一次的数字【简单】

思路：集合set去重，然后用两倍sum减原来sum得到那个单个数

class Solution(object): def singleNumber(self, nums): \"\"\" :type nums: List[int] :rtype: int \"\"\" nums_set = set(nums) # 去重 nums_set_sum = sum(nums_set) # 去重后集合的和 gap = nums_set_sum * 2 - sum(nums) # 去重后两倍元素的和 - 原来的和 return gap

704. 二分查找【简单】

思路：二分查找

class Solution(object): def search(self, nums, target): \"\"\" :type nums: List[int] :type target: int :rtype: int \"\"\" left = 0 right = len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] > target: right = mid - 1 elif nums[mid] < target: left = mid + 1  return -1

排列

283. 移动零【简单】

思路：双指针（都从左侧开始，才能保证元素的相对顺序），实现inplace排列

class Solution(object): def moveZeroes(self, nums): \"\"\" :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. \"\"\" left = 0 for right in range(len(nums)): if nums[right] != 0: nums[right], nums[left] = nums[left], nums[right] left += 1 return nums

❌ 如果用双指针（从两端开始），无法保证元素的相对顺序：

class Solution(object): def moveZeroes(self, nums): \"\"\" :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. \"\"\" right = len(nums) - 1 left = 0 while left < right: if nums[left] == 0: nums[right], nums[left] = nums[left], nums[right] right -= 1 left += 1 return nums

当然也可以先把所有非零数放到左边，最后右边填补0:

class Solution(object): def moveZeroes(self, nums): \"\"\" :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. \"\"\" idx_non_zero = 0 for i in range(len(nums)): if nums[i] != 0: nums[idx_non_zero] = nums[i] idx_non_zero += 1 for i in range(idx_non_zero, len(nums)): nums[i] = 0 return nums

组合

49. 字母异位词分组【中等】

思路：用字典的相同key映射多个字母异位词（用value列表存）

class Solution(object): def groupAnagrams(self, strs): \"\"\" :type strs: List[str] :rtype: List[List[str]] \"\"\" d = {} for s in strs: sorted_s = \'\'.join(sorted(s)) # 把字符串按字符排序 d[sorted_s] = d.get(sorted_s, []) + [s] # 返回d中key=sorted_s的value，如果value为空，返回[] # 字典存储：key=排序后的字符串，value=原始的字符串 # 将具有相同排序后的字符串放在同一个value列表中 return d.values()

78. 子集【中等】

思路：维护一个ans列表，遍历nums中所有元素，每个元素都将和ans列表中每一项进行组合，然后放进ans列表中（难点在于区分python中list的加法和append，很容易在[]嵌套结构上出错。加法是把两个列表中的元素合并起来，append是往列表中添加一整个元素）

class Solution(object): def subsets(self, nums): \"\"\" :type nums: List[int] :rtype: List[List[int]] \"\"\" ans = [[]] # 初始化包含空列表的答案 for num in nums: tmp = [] for i in ans: tmp.append([num] + i) ans += tmp return ans

链表

206. 反转链表【简单】

思路：用双指针，挨个位置反转箭头的方向

class Solution(object): def reverseList(self, head): \"\"\" :type head: Optional[ListNode] :rtype: Optional[ListNode] \"\"\" prev = None curr = head while curr: next = curr.next # 先把本来的curr.next拿到 curr.next = prev # curr的后面接prev，即链表方向反转 # prev和curr一起往后走 prev = curr curr = next return prev

234. 回文链表【简单】

思路：遍历链表，把值存储在列表中，判断列表是否是回文的

class Solution(object): def isPalindrome(self, head): \"\"\" :type head: Optional[ListNode] :rtype: bool \"\"\" l = [] while head: l.append(head.val) head = head.next ans = (l == l[::-1]) return ans

位运算

461. 汉明距离【简单】

思路：直接异或再计数，注意bin()的输出是string

class Solution(object): def hammingDistance(self, x, y): \"\"\" :type x: int :type y: int :rtype: int \"\"\" xor = bin(x ^ y) # 得到二进制异或结果 dist = list(xor[2:]).count(\'1\') # 统计1的数目 return dist

338. 比特位计数【简单】

思路：转二进制然后计数

class Solution(object): def countBits(self, n): \"\"\" :type n: int :rtype: List[int] \"\"\" ans = [] for i in range(n+1): bin_num = list(bin(i))[2:] ans.append(bin_num.count(\'1\')) return ans

排序

冒泡排序

class Solution(object): def sortArray(self, nums): \"\"\" :type nums: List[int] :rtype: List[int] \"\"\" # 冒泡排序 O(n^2) n = len(nums) for i in range(1, n): # n-1趟：每趟可以将一个大数放到最后 for j in range(0, n-i): # 无需再到最后了 if nums[j] > nums[j+1]:  nums[j], nums[j+1] = nums[j+1], nums[j] return nums