记录 leetcode剑指offer第49题丑数 class Solution: def nthUglyNumber(self, n: int) -> int: dp = [0] * n dp[0], a, b, c = 1, 0, 0, 0 for i in range(1, n): dp[i] = min(dp[a] * 2, dp[b] * 3, dp[c] * 5) if dp[i] == dp[a] * 2: a += 1

动态规划原地修改数组/仅迭代一个值 优化空间复杂度 滑动窗口取最值 双指针+哈希表 记录 leetcode剑指offer第48题最长不含重复字符的子字

记录 leetcode剑指offer第46题把数字翻译成字符串 动态规划 class Solution: def translateNum(self, num: int) -> int: a = b = 1 y = num % 10 while num != 0: num //= 10 x = num % 10 a, b = (a + b

手写快排 leetcode剑指offer第45题把数组排成最小的数 class Solution: def minNumber(self, nums: List[int]) -> str: def quicksort(start, end): if start >= end: return if start + 1 == end: if int(strs[start] + strs[end]) > int(strs[end] + strs[start]): strs[start], strs[end] = strs[end], strs[start] return pivot =

找规律，稿纸上画一画 leetcode剑指offer第44题数字序列中某一位的数字 class Solution: def findNthDigit(self, n: int) -> int: count = 1 tmp = 9 while n > tmp * count: n -= tmp * count tmp = 9 * 10

dp[i]代表以元素nums[i]为结尾的连续子数组的最大和 定义状态，抽象子问题，肢解大问题。 记录 leetcode剑指offer第43题[1

添加元素并保持有序 二分查找 python 堆也是列表 中位数：大顶堆+小顶堆 leetcode剑指offer第41题数据流中的中位数 class MedianFinder: def __init__(self): """ initialize your data structure here. """ self.max =

超过一半的数 对拼消耗，不内战，缩小规模后的众数 python的堆是小根堆 取相反数 TOP K 快排(只看一边，找到k位置，不用全排好)与堆(小顶堆) class Solution:

层序遍历 广搜 记录 leetcode剑指offer第37题序列化二叉树 class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return "" queue = collections.deque() queue.append(root) ans = [str(root.val)] while queue: node = queue.pop() if node.left

纯递归与dfs dfs基本框架 if not s: return ans = [] def dfs(args): if xxx == xxx: ans.append(yyy) return pass dfs(args) return ans 记录 leetcode剑指offer第38题字符串的排列 字符交换 class Solution: def permutation(self, s: str)