1 概述
概述
这是由 LeetCode 官方推出的的经典面试题目清单，我们将题目重新整理规划，从而为大家提供更好的练习体验和帮助大家找到理想的工作。 我们将题目分为以下三个部分：
初级算法 - 帮助入门
中级算法 - 巩固训练
高级算法 - 提升进阶
这一系列 LeetBook 将帮助您掌握算法及数据结构，并提高您的编程能力。
编程能力就像任何其他技能一样，也是一个可以通过 刻意练习 大大提高的。
大多数经典面试题目都有多种解决方案。 为了达到最佳的练习效果，我们强烈建议您至少将此清单里的题目练习两遍，如果可以的话，三遍会更好。
在第二遍练习时，你可能会发现一些新的技巧或新的方法。 到第三遍的时候，你会发现你的代码要比第一次提交时更加简洁。 如果你达到了这样的效果，那么恭喜你，你已经掌握了正确的练习方法！
记住：刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。 在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/x6vk7r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2 数组和字符串
2.1 三数之和
找出数组中和为0的三元组。
做法：转换成两数之和twoSum。固定第一个数a，问题就变成求和为-a的两数之和问题。然后可以用双指针解决。
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = [] for first in range(0,len(nums)): #跳过重复的数 if first > 0 and nums[first] == nums[first-1]: continue target = -nums[first] #变成求 和为-a的twoSum问题 third = len(nums)-1 for second in range(first+1,len(nums)): if second> first +1 and nums[second] == nums[second-1] : continue while second<third and nums[second] + nums[third] > target: third -= 1 if second == third: break if nums[second] + nums[third] == target: ans.append([nums[first],nums[second],nums[third]]) return ans
2.2 矩阵置零
容易想到用两个数组存储带0的行和列，然后将这些行和列置零。额外空间O(m+n)
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ row_0 = [] col_0 = [] for i in range(len(matrix)): for j in range(len(matrix[i])): if matrix[i][j] == 0: row_0.append(i) col_0.append(j) for i in row_0: for j in range(len(matrix[i])): matrix[i][j] = 0 for j in col_0: for i in range(len(matrix)): matrix[i][j] = 0
如果要常数级空间O(1)，用matrix的第一行和第一列来存储为0行和列。需要额外判断第一行，第一列是否存在0
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ row = False #第一行存在0 col = False #第一列存在0 for i in range(len(matrix)): for j in range(len(matrix[i])): if matrix[i][j] == 0: if i == 0 : row = True if j == 0 : col = True matrix[i][0] = 0 matrix[0][j] = 0 for i in range(1,len(matrix)): for j in range(1,len(matrix[0])): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if row: for j in range(0,len(matrix[0])): matrix[0][j] = 0 if col: for i in range(0,len(matrix)): matrix[i][0] = 0
2.3 字母异位词分组
字典dict()
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # 思路，遍历每个元素然后排序，若是异母同位词则排序后会相同，然后把相同的进行归为一类 res = [] dic = dict() for s in strs: l = [s] temp = list(s) temp.sort() dickey = ''.join(temp) if dickey in dic.keys(): dic[dickey].append(s) else: dic[dickey] = l for i in dic.values(): res.append(i) return res
2.4 无重复字符的最长子串
滑动窗口，每次窗口的左端 i 右移 一位；
关键点是：右端 r 保持，不需要回退。
例如s = "abcabcbb"，第一个循环结束时 i = 0,r = 2,最长无重复子串是abc
第二个循环时，i=1,r=2，r不需要回退，因为abc包含了bc。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: occ = set() maxLength,r = 0,0 for i in range(len(s)): if i != 0: occ.remove(s[i-1]) while r < len(s) and s[r] not in occ: occ.add(s[r]) r += 1 if r-i > maxLength : maxLength = r - i return maxLength
2.5 最长回文子串
容易 想到动态规划实现。最长回文子串
用dp[i][j] 表示从i到j的子串是否是回文子串
递推式:
dp[i][j] = s[i]== s[j] and dp[i+1][j-1]
终止条件：
i == j (length = 0), dp[i][j] = True
i+1 == j (length = 1), dp[i][j] = s[i] == s[j]
注意初始化顺序，需要按长度length顺序初始化。而不是按起始位置i。因为dp[i][j]会依赖dp[i+1][j-1]的结果。
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False for _ in range(n)] for _ in range(n)] ans = "" for length in range(n): for i in range(n-length): j = i + length if length == 0: dp[i][j] = True elif length == 1: dp[i][j] = s[i]==s[j] else: dp[i][j] = s[i]== s[j] and dp[i+1][j-1] if dp[i][j] and length+1 > len(ans): ans = s[i:i+length+1] return ans
2.6 递增的三元子序列
@Cany
我们只需要在从头到尾的遍历过程中，记录第一最小值small和第二最小值mid，然后当出现一个比第二最小值大的数，就能说明存在递增三元组的！
因为 mid的存在，永远说明前面有一个比自己小的数。所以不用担心small的下标到mid的后面。
例如2315，最后small = 1 ,mid = 3 large = 5 ，这三个下标不满足i<j<k,但mid前面一定有过比它小的数（2），所以是存在递增三元子序列的。
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: small,mid = 2**31-1,2**31-1 for num in nums: if num <= small: small = num elif num <= mid: mid = num else: return True return False
3 链表
3.1 两数相加
# 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: head,tail = None,None carry = 0 while l1 != None or l2 != None : n1 = l1.val if l1 != None else 0 n2 = l2.val if l2 != None else 0 sum_t = n1 + n2 + carry if head == None: head = ListNode(sum_t % 10) tail = head else: tail.next = ListNode(sum_t % 10) tail = tail.next carry = sum_t // 10 if l1 != None: l1 = l1.next if l2 != None: l2 = l2.next if carry > 0 : tail.next = ListNode(carry) return head
3.2 奇偶链表
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def oddEvenList(self, head: ListNode) -> ListNode: isOdd = True OddHead,EvenHead = ListNode(),ListNode() OddCur,EvenCur = OddHead,EvenHead while head != None : if isOdd: OddCur.next = head OddCur = OddCur.next else: EvenCur.next = head EvenCur = EvenCur.next head = head.next isOdd = not isOdd OddCur.next = EvenHead.next EvenCur.next = None #注意这里将EvenCur.next设置为None，不然就循环了 return OddHead.next
3.3 相交链表
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: lenA = 0 lenB = 0 curA,curB = headA,headB while curA != None: lenA += 1 curA = curA.next while curB != None: lenB += 1 curB = curB.next diff = lenA - lenB if diff > 0: while diff > 0: headA = headA.next diff -= 1 if diff < 0: while diff < 0: headB = headB.next diff += 1 while headA != None and headB != None: if headA == headB: return headA headA = headA.next headB = headB.next return None
4 树和图
4.1 二叉树的中序遍历
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] self.inOrder(root, res) return res def inOrder(self, root,res): if root == None: return self.inOrder(root.left,res) res.append(root.val) self.inOrder(root.right,res)
4.2 二叉树的锯齿形层次遍历
层次遍历+反转奇数层
1. # Def
4.3 从前序与中序遍历序列构造二叉树
递归。可以分成根，左，右三个子问题。
root = TreeNode(preorder[0])
#root_index = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:root_index+1],inorder[:root_index])
root.right = self.buildTree(preorder[root_index+1:],inorder[root_index+1:])
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if len(preorder)>0: #还有节点没有生成 root = TreeNode(preorder[0]) #找根节点位置 root_index = inorder.index(preorder[0]) #根据特性递归生成左右二叉树 root.left = self.buildTree(preorder[1:root_index+1],inorder[:root_index]) root.right = self.buildTree(preorder[root_index+1:],inorder[root_index+1:]) else: root=None return root
4.4 填充每个节点的下一个右侧节点指针
层序遍历，，每层的最右边的没有next节点
""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': if root == None: return root #层序遍历 queue = [root] while queue: length = len(queue) pre = queue.pop(0) if pre.left: queue.append(pre.left) queue.append(pre.right) for i in range(length-1): t = queue.pop(0) if t.left: queue.append(t.left) queue.append(t.right) pre.next = t pre = t return root
4.5 二叉搜索树中第K小的元素
二叉搜索数满足 左<根<右，所以中序遍历得到的就是升序的数组。
# 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 __init__(self): self.count = 0 self.res = 0 def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.count = k #inorder self.inorder(root) return self.res def inorder(self, root): if root == None: return self.inorder(root.left) self.count -=1 if self.count == 0: self.res = root.val self.inorder(root.right)
4.6 岛屿数量
深度优先。因为连着的陆地只算一个岛屿，所以发现一个陆地后，岛屿数量+1，并将连着的陆地('1')变为水('0')
class Solution: def numIslands(self, grid: List[List[str]]) -> int: count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': count +=1 self.dfs(i,j,grid) return count def dfs(self, i, j, grid): if i>=0 and i< len(grid) and j>=0 and j<len(grid[0]) and grid[i][j] == '1': grid[i][j] = '0' self.dfs(i+1,j,grid) self.dfs(i-1,j,grid) self.dfs(i,j-1,grid) self.dfs(i,j+1,grid)
5 回溯算法
回溯框架
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
5.1 电话号码的字母组合
class Solution: def letterCombinations(self, digits: str) -> List[str]: phoneMap = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz", } res = [] if len(digits) == 0 : return res self.backtrack(res, phoneMap, digits, 0, []) return res #深度优先 def backtrack(self, res, phoneMap, digits,index, st): if index == len(digits): res.append("".join(st)) else: digit = digits[index] letters = phoneMap.get(digit) for letter in letters: st.append(letter) self.backtrack(res, phoneMap, digits, index+1, st) st.pop(index)
5.2 括号生成
有限制条件的回溯，因为数据量小，也可以先无限制条件生成括号，在判断是否合法。
class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] self.backtrack(n,0,0,[],res) return res def backtrack(self,n,left,right,tmp,res): if right == n: res.append(''.join(tmp)) return if left< n: tmp.append('(') self.backtrack(n,left+1,right,tmp,res) tmp.pop() if right<left: tmp.append(')') self.backtrack(n,left,right+1,tmp,res) tmp.pop()
5.3 全排列
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] self.backtrack(nums,[],res,len(nums)) return res def backtrack(self,choices,tmp, res,n): if len(tmp) == n: res.append(tmp.copy()) return for i in range(len(choices)): tmp.append(choices[i]) choices.pop(i) # self.backtrack(choices,tmp,res,n) choices.insert(i,tmp.pop())
5.4 子集
除了回溯也可以用 位运算&做
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] self.backtrack(nums,0,[],res) return res def backtrack(self,nums,start,tmp, res): res.append(tmp.copy()) for i in range(start,len(nums)): tmp.append(nums[i]) self.backtrack(nums,i+1,tmp,res) tmp.pop()
5.5 单词搜索
对每个棋子使用dfs。
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: for i in range(len(board)): for j in range(len(board[0])): if self.dfs(board,word,i,j,0): return True return False def dfs(self, board, word, i,j,index): if i >= len(board) or i < 0 or j >= len(board[0]) or j < 0 or board[i][j] != word[index]: return False if index == len(word)-1: return True tmp = board[i][j] board[i][j] = '.' res = self.dfs(board,word,i+1,j,index+1) or self.dfs(board,word,i-1,j,index+1) or\ self.dfs(board,word,i,j+1,index+1) or self.dfs(board,word,i,j-1,index+1) board[i][j] = tmp return res
6 排序和搜索
6.1 颜色分类
由于只有3种元素，可以直接统计频率，然后重写nums。
class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ a = [0,0,0] for i in nums: a[i] += 1 index = 0 for i in range(len(a)): for j in range(a[i]): nums[index] = i index +=1
6.2 前k个高频元素
使用字典存频率，然后排序（sort很简单，也可以最小堆heapq）。
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: mmap = dict() for num in nums: mmap[num] = mmap[num]+1 if num in mmap else 1 sort = sorted(zip(mmap.values(),mmap.keys())) sort.reverse() res = [] for i in range(k): res.append(sort[i][1]) return res
6.3 数组中的第K个最大元素
最大堆/直接排序
import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: #res = heapq.nlargest(k,nums) #return res[-1] return sorted(nums)[-k]
6.4 寻找峰值
虽然不是有序数组，但问题的形式可以用二分法。
class Solution: def findPeakElement(self, nums: List[int]) -> int: length = len(nums) if length == 1: return 0 if nums[0]>nums[1]: return 0 if nums[length-1]>nums[length-2]: return length-1 #二分查找 left = 0 right = length-1 mid = (left+right)//2 while left<right: mid = (left+right)//2 if nums[mid]>nums[mid-1] and nums[mid]>nums[mid+1]: return mid elif nums[mid]<nums[mid-1]: right = mid elif nums[mid]<nums[mid+1]: left = mid return mid
6.5 在排序数组中查找元素的第一个和最后一个位置
遍历
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: length = len(nums) if length == 0: return [-1,-1] first = -1 for i in range(length): if nums[i] == target: first = i break last = -1 for i in range(length-1,first-1,-1): if nums[i] == target: last = i break return first,last
二分
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: length = len(nums) if length == 0: return [-1,-1] # first first = -1 left = 0 right = length-1 while left <= right: mid = (left+right)//2 if nums[mid] == target: first = mid right = mid-1 elif nums[mid] > target : right = mid-1 elif nums[mid]< target: left = mid+1 #last last = -1 left = first right = length-1 mid = (left+right)//2 while left <= right: mid = (left+right)//2 if nums[mid] == target: left = mid+1 last = mid elif nums[mid]< target: left = mid+1 elif nums[mid] > target : right = mid-1 return first,last
二分，但是简化了一下
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: length = len(nums) if length == 0 : return [-1,-1] first = -1 left,right = 0,length-1 while left <= right: mid = (left+right)//2 if nums[mid] >= target: right = mid-1 elif nums[mid]< target: left = mid+1 first = left if first not in range(length) or nums[first]!= target: return[-1,-1] #last last = -1 left, right = first, length-1 while left <= right: mid = (left+right)//2 if nums[mid] <= target: left = mid+1 elif nums[mid] > target : right = mid-1 last = right return first,last
6.6 合并区间
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: length = len(intervals) if length <= 1: return intervals intervals.sort() tmp = intervals[0] res = [] for num in intervals: if num[0] <= tmp[1] : tmp =[min(tmp[0],num[0]), max(tmp[1],num[1])] else: res.append(tmp) tmp = num print("res",res) if len(res)==0 or res[-1][1] < intervals[-1][0]: res.append(tmp) return res
6.7 搜索旋转排序数组
class Solution: def search(self, nums: List[int], target: int) -> int: # step1 找旋转点 res = -1 length = len(nums) if length == 0: return -1 if length == 1: return -1 if nums[0] != target else 0 left, right = 0, length - 1 zz = length - 1 mid = (left + right) // 2 while mid != left: mid = (left + right) // 2 if nums[mid] > nums[left]: left = mid else : right = mid zz = right print("zz", zz) # step2 二分查找 if target >= nums[0]: left, right = 0, zz - 1 else: left, right = zz, length - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: res = mid break elif nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 return res
6.8 搜索二维矩阵 II
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: row = len(matrix) col = len(matrix[0]) low_row = 0 high_row = row-1 while low_row < row and matrix[low_row][-1] < target : low_row += 1 while high_row > 0 and matrix[high_row][0] > target : high_row -= 1 for i in range(low_row, high_row+1): if self.b_search(matrix[i],target): return True return False def b_search(self, nums, target): left = 0 right = len(nums)-1 while left <= right : mid = (left+right)//2 if nums[mid] == target: return True elif nums[mid] < target: left = mid +1 elif nums[mid] > target: right = mid-1 return False
7 动态规划
7.1 跳跃游戏
class Solution: def canJump(self, nums: List[int]) -> bool: length = len(nums) if length == 1: return True #dp[i]：i位置能走的最远距离 dp = [0 for _ in range(length )] for i in range(len(nums)): dp[i] = max(dp[i-1]-1,nums[i]) if i+dp[i] >= length-1: return True if dp[i] == 0: return False
7.2 不同路径
class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1 for _ in range(n)] for _ in range(m)] for row in range(1,m): for col in range(1,n): dp[row][col] = dp[row-1][col] + dp[row][col-1] return dp[m-1][n-1]
7.3 零钱兑换
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1
7.4 最长上升子序列
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 length = len(nums) dp = [1 for i in range(len(nums))] for i in range(length): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[j]+1, dp[i]) return max(dp)
8 设计问题
8.1 二叉树的序列化与反序列化
前序遍历
class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ res = [] def preorder(root): if not root: res.append('#') return res.append(str(root.val)) preorder(root.left) preorder(root.right) preorder(root) return ','.join(res) return res def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ arr = data.split(',') arr.reverse() def preorder(arr): if not arr: return if arr[-1] == '#': arr.pop() return root = TreeNode(int(arr.pop())) root.left = preorder(arr) root.right = preorder(arr) return root return preorder(arr)
8.2 常数时间插入、删除和获取随机元素
使用字典记录元素
import random class RandomizedSet: def __init__(self): self.arr = [] self.length = 0 self.mdict = {} def insert(self, val: int) -> bool: if val not in self.mdict: self.arr.append(val) self.mdict[val] = self.length self.length += 1 return True else: return False def remove(self, val: int) -> bool: if val in self.mdict: index = self.mdict[val] del self.mdict[val] self.arr[index] = self.arr[-1] self.mdict[self.arr[-1]] = index self.arr.pop(-1) self.length -= 1 return True else: return False def getRandom(self) -> int: return random.choice(self.arr) # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()
9 数学
9.1 快乐数
class Solution: def isHappy(self, n: int) -> bool: def getn2(n): sum_n2 = 0 while n: sum_n2 +=(n %10)**2 n //=10 return sum_n2 d = {} while n != 1 : if n in d: return False else: d[n] = True n = getn2(n) return True
9.2 阶乘后的零
阶乘中结果中的0是 2*5产生的，所以问题转化成求有多少个5。
class Solution: def trailingZeroes(self, n: int) -> int: res = 0 while n>= 5: n //=5 res += n return res
9.3 Excel表列序号
class Solution: def titleToNumber(self, columnTitle: str) -> int: res = 0 for col in columnTitle: res *= 26 res += ord(col) - ord('A')+1 #ord获取字符ascii值 print(col) return res
9.4 Pow(x, n)
class Solution: def myPow(self, x: float, n: int) -> float: return x**n
9.5 x 的平方根
二分查找
class Solution: def mySqrt(self, x: int) -> int: left = 0 right = x //2 if x >= 4 else x mid = (left+right)//2 while left <= right: if mid*mid <= x and (mid+1)*(mid+1) >x: return mid elif mid*mid > x: right = mid-1 elif (mid+1)*(mid+1) <= x: left = mid+1 mid = (left+right)//2 return mid
9.6 两数相除
class Solution: def divide(self, dividend: int, divisor: int) -> int: if dividend == 0: return 0 if dividend == -2**31 and divisor == -1: #-inf return 2**31-1 negative = (dividend ^ divisor) < 0 #符号位（最高位）不同，异或结果<0 t = abs(dividend) d = abs(divisor) result = 0 #转换成减法，利用移位的高效率 for i in range(31,-1,-1): if (t>>i) >= d: result += 1<<i t -= d<<i return result if not negative else - result
9.7 分数到小数
class Solution: def fractionToDecimal(self, numerator: int, denominator: int) -> str: if numerator % denominator == 0: return str(numerator//denominator) s= [] if numerator^denominator < 0: s.append('-') #整数 numerator = abs(numerator) denominator = abs(denominator) intPart = numerator//denominator s.append(str(intPart)) s.append('.') #小数 indexMap = {} remainder = numerator % denominator while remainder and remainder not in indexMap: indexMap[remainder] = len(s) remainder *= 10 s.append(str(remainder//denominator)) remainder %= denominator if remainder: insertIndex = indexMap[remainder] s.insert(insertIndex,'(') s.append(')') return ''.join(s)
10 其它
10.1 两整数之和
class Solution: def getSum(self, a: int, b: int) -> int: #return sum([a,b]) #位运算 a^b 实现无进位加法，在用a&b，并<< 获得进位 if not b: return a return add(a^b,(a&b)<<1)
10.2 逆波兰表达式求值
栈
class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] res = 0 for i in tokens: if i == '+' : a = stack.pop() b = stack.pop() stack.append(b+a) elif i == '-' : a = stack.pop() b = stack.pop() stack.append(b-a) elif i == '*' : a = stack.pop() b = stack.pop() stack.append(b*a) elif i == '/': a = stack.pop() b = stack.pop() stack.append(int(b/a)) else : stack.append(int(i)) return int(stack[-1])
10.3 多数元素
collection.Counter()
class Solution: def majorityElement(self, nums: List[int]) -> int: length = len(nums) freq = collections.Counter(nums) for k,v in freq.items(): if v > length//2: return k
10.4 任务调度器
分析见官方题解。
class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: freq = collections.Counter(tasks) maxExc = max(freq.values()) maxCount = sum(1 for v in freq.values() if v == maxExc) return max((n+1)*(maxExc-1)+maxCount, len(tasks))
