Skip to main content

剑指 Offer

跨国巨头公司面试官押题宝典。

题目​

字符串​

名称级别状态备注
剑指 Offer 05. 替换空格简单已解答字符串
剑指 Offer 58 - II. 左旋转字符串简单已解答字符串、数学、双指针
剑指 Offer 20. 表示数值的字符串中等已解答字符串
剑指 Offer 67. 把字符串转换成整数中等已解答字符串

链表​

名称级别状态备注
剑指 Offer 06. 从尾到头打印链表简单已解答栈、递归、链表
剑指 Offer 24. 反转链表简单已解答递归、链表
剑指 Offer 35. 复杂链表的复制中等已解答哈希表、链表

双指针​

名称级别状态备注
剑指 Offer 18. 删除链表的节点简单已解答链表
剑指 Offer 22. 链表中倒数第k个节点简单已解答链表、双指针
剑指 Offer 25. 合并两个排序的链表简单已解答递归、链表
剑指 Offer 52. 两个链表的第一个公共节点简单已解答递归、链表
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面简单已解答数组、双指针、排序
剑指 Offer 57. 和为s的两个数字简单已解答数组、双指针、二分查找
剑指 Offer 58 - I. 翻转单词顺序简单已解答双指针、字符串

栈与队列​

名称级别状态备注
剑指 Offer 09. 用两个栈实现队列简单已解答栈、设计、队列
剑指 Offer 30. 包含min函数的栈简单已解答栈、设计
剑指 Offer 59 - I. 滑动窗口的最大值困难已解答队列、滑动窗口、单调队列
剑指 Offer 59 - II. 队列的最大值中等已解答设计、队列、单调队列

模拟​

名称级别状态备注
剑指 Offer 29. 顺时针打印矩阵简单已解答数组、矩阵、模拟
剑指 Offer 31. 栈的压入、弹出序列中等已解答栈、数组、模拟

查找算法​

名称级别状态备注
剑指 Offer 03. 数组中重复的数字简单已解答数组、哈希表、排序
剑指 Offer 53 - I. 在排序数组中查找数字 I简单已解答数组、二分查找
剑指 Offer 53 - II. 0～n-1中缺失的数字简单已解答位运算、数组、哈希表
剑指 Offer 04. 二维数组中的查找中等已解答数组、二分查找、分治
剑指 Offer 11. 旋转数组的最小数字简单已解答数组、二分查找
剑指 Offer 50. 第一个只出现一次的字符简单已解答队列、哈希表、字符串

搜索与回溯算法​

名称级别状态备注
剑指 Offer 32 - I. 从上到下打印二叉树中等已解答树、广度优先搜索、二叉树
剑指 Offer 32 - II. 从上到下打印二叉树 II简单已解答树、广度优先搜索、二叉树
剑指 Offer 32 - III. 从上到下打印二叉树 III中等已解答树、广度优先搜索、二叉树
剑指 Offer 26. 树的子结构中等已解答广度优先搜索、二叉树
剑指 Offer 27. 二叉树的镜像简单已解答树、深度优先搜索、二叉树
剑指 Offer 28. 对称的二叉树简单已解答树、深度优先搜索、广度优先搜索
剑指 Offer 12. 矩阵中的路径中等已解答数组、回溯、矩阵
剑指 Offer 13. 机器人的运动范围中等已解答深度优先搜索、广度优先搜索、动态规划
剑指 Offer 34. 二叉树中和为某一值的路径中等已解答树、深度优先搜索、回溯
剑指 Offer 36. 二叉搜索树与双向链表中等已解答栈、树、深度优先搜索
剑指 Offer 54. 二叉搜索树的第k大节点简单已解答树、深度优先搜索、二叉搜索树
剑指 Offer 55 - I. 二叉树的深度简单已解答树、深度优先搜索、广度优先搜索
剑指 Offer 55 - II. 平衡二叉树简单已解答树、深度优先搜索、二叉树
剑指 Offer 64. 求1+2+…+n中等已解答位运算、递归、脑筋急转弯
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先简单已解答树、深度优先搜索、二叉搜索树
剑指 Offer 68 - II. 二叉树的最近公共祖先简单已解答树、深度优先搜索、二树
剑指 Offer 37. 序列化二叉树困难已解答树、深度优先搜索、广度优先搜索
剑指 Offer 38. 字符串的排列中等已解答字符串、回溯

分治算法​

名称级别状态备注
剑指 Offer 07. 重建二叉树中等已解答树、数组、哈希表
剑指 Offer 16. 数值的整数次方中等已解答递归、数学
剑指 Offer 33. 二叉搜索树的后序遍历序列中等已解答栈、数、二叉搜素树
剑指 Offer 17. 打印从1到最大的n位数简单已解答数组、数学
剑指 Offer 51. 数组中的逆序对困难已解答树状数组、线段树、数组

排序​

名称级别状态备注
剑指 Offer 45. 把数组排成最小的数中等已解答贪心、字符串、排序
剑指 Offer 61. 扑克牌中的顺子简单已解答数组、排序
剑指 Offer 40. 最小的k个数简单已解答数组、分治、快速选择
剑指 Offer 41. 数据流中的中位数困难已解答设计、双指针、数据流

动态规划​

名称级别状态备注
剑指 Offer 10- I. 斐波那契数列简单已解答记忆化搜索、数学、动态规划
剑指 Offer 10- II. 青蛙跳台阶问题简单已解答记忆化搜索、数学、动态规划
剑指 Offer 63. 股票的最大利润中等已解答数组、动态规划
剑指 Offer 42. 连续子数组的最大和简单已解答数组、分治、动态规划
剑指 Offer 47. 礼物的最大价值中等已解答数组、动态规划、矩阵
剑指 Offer 46. 把数字翻译成字符串中等已解答字符串、动态规划
剑指 Offer 48. 最长不含重复字符的子字符串中等已解答哈希表、字符串、滑动窗口
剑指 Offer 19. 正则表达式匹配困难已解答递归、字符串、动态规划
剑指 Offer 49. 丑数中等已解答哈希表、数学、动态规划
剑指 Offer 60. n个骰子的点数中等已解答数学、动态规划、概率与统计

位运算​

名称级别状态备注
剑指 Offer 15. 二进制中1的个数简单已解答位运算
剑指 Offer 65. 不用加减乘除做加法简单已解答位运算、数学
剑指 Offer 56 - I. 数组中数字出现的次数中等已解答位运算、数组
剑指 Offer 56 - II. 数组中数字出现的次数 II中等已解答位运算、数组

数学​

名称级别状态备注
剑指 Offer 39. 数组中出现次数超过一半的数字简单已解答数组、哈希表、分治
剑指 Offer 66. 构建乘积数组中等已解答数组、前缀和
剑指 Offer 14- I. 剪绳子中等已解答数学、动态规划
剑指 Offer 14- II. 剪绳子 II中等已解答数学、动态规划
剑指 Offer 57 - II. 和为s的连续正数序列简单已解答数学、双指针、枚举
剑指 Offer 62. 圆圈中最后剩下的数字简单已解答递归、数学
剑指 Offer 43. 1～n 整数中 1 出现的次数困难已解答递归、数学、动态规划
剑指 Offer 44. 数字序列中某一位的数字中等已解答数学、二分查找

解题​

字符串​

剑指 Offer 05. 替换空格​

class Solution:
    def replaceSpace(self, s: str) -> str:
        if not s: return ""

        # 时间复杂度：O(N)
        # 空间复杂度：O(N)
        result = ""
        for i in s:
            if i == ' ':
                result += '%20'
            else:
                result += i
        return result

剑指 Offer 58 - II. 左旋转字符串​

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        if not s and k < 1: return ""
        # py 下标获取字符串是左闭，右开
        return s[n:len(s)] + s[0:n]

剑指 Offer 20. 表示数值的字符串​

class Solution:
    def isNumber(self, s: str) -> bool:
        try:
            float(s.strip())
        except:
            return False
        return True

剑指 Offer 67. 把字符串转换成整数​

class Solution:
    def strToInt(self, str: str) -> int:
        # 去除前导空格
        str = str.strip()
        if not str: return 0
        if len(str) == 0: return 0

        sign = 1
        if str[0] == '-':
            sign = -1
            str = str[1:]
        elif str[0] == '+':
            str = str[1:]
        
        # 转换字符串为整数
        res = 0
        for c in str:
            if not c.isdigit():
                break
            res = res * 10 + int(c)
            # 判断是否超过整数范围
            if res > 2**31 - 1:
                return 2**31 - 1 if sign == 1 else -2**31
        return sign * res

链表​

剑指 Offer 06. 从尾到头打印链表​

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        res = []
        curr = head
        while curr:
            res.append(curr.val)
            curr = curr.next
        return res[::-1]

剑指 Offer 24. 反转链表​

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head: return None

        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

剑指 Offer 35. 复杂链表的复制​

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        self.map = {}
        return self.copList(head)

    def copList(self, head):
        if not head: return None

        if head in self.map:
            return self.map.get(head)
        else:
            node = Node(head.val)
            self.map[head] = node
            node.next = self.copList(head.next)
            node.random = self.copList(head.random)
        return self.map.get(head)

双指针​

剑指 Offer 18. 删除链表的节点​

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head: return None
        if head.val == val: return head.next
        pre, cur = head, head.next
        while cur:
            if cur.val == val:
                pre.next = cur.next
                break
            else:
                pre, cur = cur, cur.next
        return head

剑指 Offer 22. 链表中倒数第k个节点​

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast = head
        low = head
        for _ in range(k):
            if not fast: return
            fast = fast.next
        while fast:
            fast,low = fast.next, low.next
        return low

剑指 Offer 25. 合并两个排序的链表​

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

剑指 Offer 52. 两个链表的第一个公共节点​

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1 = headA
        l2 = headB
        while l1 != l2:
            if l1 is None:
                l1 = headB
            else:
                l1 = l1.next
            if l2 is None:
                l2 = headA
            else:
                l2 = l2.next
        return l1

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面​

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if not nums: return nums
        return self.s2(nums)

    def s2(self, nums):
        n = len(nums)
        res,left,right = [0] * n,0,n-1
        for num in nums:
            if num % 2 == 1:
                res[left] = num
                left +=1
            else:
                res[right] = num
                right -= 1
        return res

    def s1(self, nums):
        res = []
        for i in nums:
            if i%2 == 1:
                res.append(i)
        for i in nums:
            if i%2 == 0:
                res.append(i)
        return res

剑指 Offer 57. 和为s的两个数字​

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if not nums: return []
        left,right = 0,len(nums)-1
        while left <= right:
            if nums[left] + nums[right] == target:
                return [nums[left],nums[right]]
            elif nums[left] + nums[right] > target:
                right -=1
            else:
                left +=1
        return []

剑指 Offer 58 - I. 翻转单词顺序​

class Solution:
    def reverseWords(self, s: str) -> str:
        if not s: return ""
        res = ""
        words = s.strip().split(" ")
        for i in range(len(words)-1, -1, -1):
            if len(words[i]) > 0:
                res += " " + words[i]
        return res.strip()

栈与队列​

剑指 Offer 09. 用两个栈实现队列​

class CQueue:

    def __init__(self):
        self.in_s = []
        self.out_s = []

    def appendTail(self, value: int) -> None:
        self.in_s.append(value)

    def deleteHead(self) -> int:
        if len(self.out_s) == 0:
            if len(self.in_s) == 0:
                return -1 
            else:
                while self.in_s:
                    self.out_s.append(self.in_s.pop())
        return self.out_s.pop()

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

剑指 Offer 30. 包含min函数的栈​

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.min_stack) == 0 or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        r = self.stack.pop()
        if r == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

剑指 Offer 59 - I. 滑动窗口的最大值​

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
    
        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1]  <= i-k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

    def s1(self, nums, k):
        start,end = 0,k
        res = []
        while end <= len(nums):
            v = self.maxWindow(nums, start, end)
            res.append(v)
            start += 1
            end += 1
        return res
    
    def maxWindow(self, nums, start, end):
        maximun = float("-inf")
        for i in range(start, end):
            if maximun < nums[i]:
                maximun = nums[i]
        return maximun

剑指 Offer 59 - II. 队列的最大值​

class MaxQueue:

    def __init__(self):
        self.q = deque()

    def max_value(self) -> int:
        return max(self.q) if self.q else -1

    def push_back(self, value: int) -> None:
        self.q.append(value)

    def pop_front(self) -> int:
        return self.q.popleft() if self.q else -1

# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()

模拟​

剑指 Offer 29. 顺时针打印矩阵​

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or  not matrix[0]: return list()

        rows, columns = len(matrix), len(matrix[0])
        order = list()
        left, right, top, bottom = 0, columns -1, 0, rows -1
        while left <= right and top <= bottom:
            for column in range(left, right + 1):
                order.append(matrix[top][column])
            for row in range(top + 1, bottom + 1):
                order.append(matrix[row][right])
            if left < right and top < bottom:
                for column in range(right-1, left, -1):
                    order.append(matrix[bottom][column])
                for row in range(bottom, top, -1):
                    order.append(matrix[row][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
        return order

剑指 Offer 31. 栈的压入、弹出序列​

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        st, j = [],0
        for x in pushed:
            st.append(x)
            while st and st[-1] == popped[j]:
                st.pop()
                j += 1
        return len(st) == 0

查找算法​

剑指 Offer 03. 数组中重复的数字​

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        if not nums: return -1
        numbers = [-1] * len(nums)
        for i in nums:
            if numbers[i] != -1 and numbers[i] == i:
                return i
            else:
                numbers[i] = i
        return -1

剑指 Offer 53 - I. 在排序数组中查找数字 I​

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return self.helper(nums, target) - self.helper(nums, target - 1)
    
    def helper(self, nums, target):
        i,j = 0, len(nums) - 1
        while i <= j:
            m = (i + j)//2
            if nums[m] <= target:
                i = m + 1
            else:
                j = m - 1
        return i

剑指 Offer 53 - II. 0～n-1中缺失的数字​

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right)//2
            if nums[mid] == mid:
                left = mid + 1
            else:
                right = mid - 1
        return left

剑指 Offer 04. 二维数组中的查找​

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0: return False
        for i in range(len(matrix)):
            nums = matrix[i]
            left,right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right)//2
                if nums[mid] == target:
                    return True
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

剑指 Offer 11. 旋转数组的最小数字​

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        # 只有一个元素，数组的最小值为 1；PS：限制条件
        if len(numbers) == 1: return 1
        for i in range(1, len(numbers)):
            # 旋转以后，子序列为升序，并且前一半序列比后一半都大，如果出现相减 < 0 说明 i 就是我们要找的最小元素
            if numbers[i] - numbers[i-1] < 0:
                return numbers[i]
        # 元素完全相同，比如：[-1,-1,-1] 或者 [1,1,1,1]
        return numbers[0]

剑指 Offer 50. 第一个只出现一次的字符​

class Solution:
    def firstUniqChar(self, s: str) -> str:
        if not s: return ' '
        dic = dict()
        for c in s:
            if c in dic:
                dic[c] = dic[c] + 1 
            else:
                dic[c] = 1
        for k,v in dic.items():
            if v == 1: return k
        return ' '
    
    def s1(self, s):
        if not s: return ' '
        kv = dict()
        for i in s:
            if i in kv:
                kv[i] = kv[i] + 1
            else:
                kv[i] = 1
        for i in s:
            if i in kv and kv[i] == 1:
                return i
        return ' '

搜索与回溯算法​

剑指 Offer 32 - I. 从上到下打印二叉树​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        # 前序遍历：根左右 -> BFS
        if not root: return []
        res = []
        queue = deque()
        queue.append(root)

        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res

剑指 Offer 32 - II. 从上到下打印二叉树 II​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        queue,res = deque(),[]
        queue.append(root)

        while queue:
            tmp = []
            for _ in range(len(queue)):
                v = queue.popleft()
                tmp.append(v.val)
                if v.left: queue.append(v.left)
                if v.right: queue.append(v.right)
            res.append(tmp)
        return res

剑指 Offer 32 - III. 从上到下打印二叉树 III​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        # bfs 按层打印，在反转数组
        res = []
        def bfs(root):
            queue = collections.deque()
            queue.append(root)
            
            state = True
            while queue:
                level = []
                for _ in range(len(queue)):
                    node = queue.popleft()
                    level.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                if state:
                    res.append(level)
                else:
                    res.append(level[::-1])
                state = False if state else True
        bfs(root)
        return res

剑指 Offer 26. 树的子结构​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: return True
            if not A or A.val != B.val: return False
            return recur(A.left, B.left) and recur(A.right, B.right)
        
        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

剑指 Offer 27. 二叉树的镜像​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        # return self.swap(root)
        return TreeNode(root.val, self.mirrorTree(root.right), self.mirrorTree(root.left)) if root else None
    
    def swap(self, node):
            if node:
                self.swap(node.left)
                self.swap(node.right)
                left = node.left
                node.left= node.right
                node.right = left
                return node
            else:
                return node

剑指 Offer 28. 对称的二叉树​

# 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:
        rnode = self.swap(root)
        return self.is_same_tree(root, rnode)
    
    def is_same_tree(self, A, B):
        # 值都为空，说明相等
        if A is None and B is None: return True
        # 任意一个为空
        if A is None or B is None: return False
        # 值不相等
        if A.val != B.val: return False
        return self.is_same_tree(A.left, B.left) and self.is_same_tree(A.right, B.right)

    def swap(self, root):
        return TreeNode(root.val, self.swap(root.right), self.swap(root.left)) if root else None

剑指 Offer 12. 矩阵中的路径​

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]: return False
        self.board = board
        self.word = word
        self.m,self.n = len(board), len(board[0])
        self.visited = [[False] * self.n for _ in range(self.m)]
        for i in range(self.m):
            for j in range(self.n):
                if self.backtrack(i,j,0):
                    return True
        
        return False
    
    def backtrack(self, i, j, index):
        # 单词已匹配
        if len(self.word) == index:
            return True
        
        # 越界、字符不匹配、被访问等情况
        if i < 0 or i >= self.m or j < 0 or j >= self.n \
            or self.board[i][j] != self.word[index] \
            or self.visited[i][j]:
            return False 
        
        self.visited[i][j] = True

        # 递归搜索相邻的字符：上下左右搜索
        if self.backtrack(i + 1, j, index + 1) \
           or self.backtrack(i - 1, j, index + 1) \
           or self.backtrack(i, j + 1, index + 1) \
           or self.backtrack(i, j - 1, index + 1):
           return True
        
        # 回溯，取消当前位置标记
        self.visited[i][j] = False

        return False

剑指 Offer 13. 机器人的运动范围​

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        if m <=0 or n <= 0 or k < 0: return 0
        visited = set()

        def getDigitSum(num):
            res = 0
            while num:
                res += num % 10
                num //= 10
            return res

        def dfs(i, j):
            # 越界、被访问、坐标之和是否等于K
            if i < 0 \
                or i >= m \
                or j < 0 \
                or j >= n \
                or (i, j) in visited \
                or getDigitSum(i) + getDigitSum(j) > k:
                return 0
            
            # 标记当前位置已访问
            visited.add((i,j))

            # 递归搜索相邻位置
            return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)

        return dfs(0, 0)

剑指 Offer 34. 二叉树中和为某一值的路径​

# 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 pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        result = []
        if not root:
            return result

        def dfs(node, path, path_cnt):
            # 结束条件，走到 node 叶子节点
            if not node: 
                return
            path.append(node.val)
            path_cnt += node.val
            # 递归结果
            if not node.left and not node.right and path_cnt == target:
                # path[:] 复制 path 内容，放入到 result 中
                result.append(path[:])
            dfs(node.left, path, path_cnt)
            dfs(node.right, path, path_cnt)
            path.pop()
        
        dfs(root,[],0)
        return result

剑指 Offer 36. 二叉搜索树与双向链表​

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return None
        result = []
        def dfs(root):
            if root:
                dfs(root.left)
                result.append(root)
                dfs(root.right)
        
        # 中序遍历得到有序列表
        dfs(root)
        
        # 整理中序遍历列表为双向链表
        n = len(result)
        for i in range(1, n-1):
            result[i].left = result[i-1]
            result[i].right = result[i+1]
        
        # 单独处理 head 和 tail 节点
        head = result[0]
        head.left = result[-1]
        head.right = result[1] if n > 1 else head
        if n > 1:
            tail = head.left
            # tail.left 倒数第二个node，right 是 head 节点
            tail.left = result[-2]
            tail.right = head
        return head

剑指 Offer 54. 二叉搜索树的第k大节点​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        s = []
        def dfs(root):
            if not root: return
            dfs(root.left)
            s.append(root.val)
            dfs(root.right)
        
        # dfs 中序遍历，二叉搜索树结果有序，k 大，则是 -k 数组值
        dfs(root)
        return s[-k]

剑指 Offer 55 - I. 二叉树的深度​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue,cnt = deque(),0
        queue.append(root)
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            cnt += 1
        return cnt

剑指 Offer 55 - II. 平衡二叉树​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def recur(root):
            if not root: return 0
            left = recur(root.left)
            if left == -1: return -1
            right = recur(root.right)
            if right == -1: return -1
            return max(left, right) + 1 if abs(left-right) <= 1 else -1
        
        return recur(root) != -1

剑指 Offer 64. 求1+2+…+n​

class Solution:
    def sumNums(self, n: int) -> int:
        if n <=0: return 0
        # 0 and num, 返回 0，非0返回num
        return n and (n + self.sumNums(n-1))

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.find2(root, p, q)

    def find2(self, root, p, q):
        # 二叉搜索树，特性：左边
        if p.val < root.val > q.val:
            return self.find2(root.left, p, q)
        # 二叉搜索树，特性：右边
        if p.val > root.val < q.val:
            return self.find2(root.right, p, q)
        return root

    def find1(self, root, p, q):
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

剑指 Offer 68 - II. 二叉树的最近公共祖先​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

剑指 Offer 37. 序列化二叉树​

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    # 前序遍历(根左右)，preOrder 进行序列化为字符串，字符串反序列化为二叉树
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "#"
        return str(root.val) + "," + self.serialize(root.left) + "," + self.serialize(root.right)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def helper(nodes):
            if not nodes: return None
            val = nodes.pop(0) # 弹出左边第一个元素
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = helper(nodes)
            node.right = helper(nodes)
            return node

        nodes = data.split(",")
        return helper(nodes)
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

剑指 Offer 38. 字符串的排列​

class Solution:
    def permutation(self, s: str) -> List[str]:
        res = []
        chars = list(s)

        def backtrack(start):
            if start == len(chars) - 1:
                res.append(''.join(chars))
                return
            
            visited = set()
            for i in range(start, len(chars)):
                if chars[i] in visited:
                    continue
                visited.add(chars[i])
                chars[start],chars[i] = chars[i],chars[start]
                backtrack(start + 1)
                # 复原字符数组
                chars[start],chars[i] = chars[i],chars[start]
        
        backtrack(0)
        return res

分治算法​

剑指 Offer 07. 重建二叉树​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 前序遍历：根左右
        # 中序遍历：左根右
        def buildTreeHelper(pre_start, pre_end, in_start, in_end):
            if pre_start > pre_end:
                return None
            
            root_val = preorder[pre_start]
            root = TreeNode(root_val)
            # 获取 root_val 在 inorder 中的位置
            in_index = inorder.index(root_val)
            # 左边有多少个元素： 中序遍历 root 左边元素左子树元素个数
            left_size = in_index - in_start
            root.left = buildTreeHelper(pre_start + 1, pre_start + left_size, in_start, in_index - 1)
            root.right = buildTreeHelper(pre_start + left_size + 1, pre_end, in_index + 1, in_end)

            return root

        return buildTreeHelper(0, len(preorder)-1, 0, len(inorder)-1)

剑指 Offer 16. 数值的整数次方​

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        elif n < 0:
            return 1 / self.myPow(x, -n)
        elif n % 2 == 0:
            return self.myPow(x * x, n // 2)
        else:
            return x * self.myPow(x * x, n // 2)

剑指 Offer 33. 二叉搜索树的后序遍历序列​

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        # 后序遍历：左右根
        # 中序遍历：左根右
        # 前序遍历：根左右
        if not postorder: 
            return True
        
        def helper(start, end):
            if start >= end:
                return True
            root_val = postorder[end]
            i = start

            # 二叉搜索树，左子树都小于 root_val
            while i < end and postorder[i] < root_val:
                i += 1

            # i 是右子树的第一个值
            j = i
            while j < end and postorder[j] > root_val:
                j += 1
            
            # 右子树能走到倒数第二个节点，才满足右子树都大于 root_val
            if j != end:
                return False
            
            # 左子树范围：start - (i-1)
            left_subtree = helper(start, i - 1)
            # 右子树范围：i - （end - 1），需排除 root 节点
            right_subtree = helper(i, end - 1)
            return left_subtree and right_subtree
        
        return helper(0, len(postorder) - 1)

剑指 Offer 17. 打印从1到最大的n位数​

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        res = []
        for i in range(1, pow(10, n)):
            res.append(i)
        return res

剑指 Offer 51. 数组中的逆序对​

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(l, r):
            # 终止条件
            if l >= r: return 0
            # 递归划分
            m = (l + r) // 2
            res = merge_sort(l, m) + merge_sort(m + 1, r)
            # 合并阶段
            i, j = l, m + 1
            tmp[l:r + 1] = nums[l:r + 1]
            for k in range(l, r + 1):
                if i == m + 1:
                    nums[k] = tmp[j]
                    j += 1
                elif j == r + 1 or tmp[i] <= tmp[j]:
                    nums[k] = tmp[i]
                    i += 1
                else:
                    nums[k] = tmp[j]
                    j += 1
                    res += m - i + 1 # 统计逆序对
            return res
        
        tmp = [0] * len(nums)
        return merge_sort(0, len(nums) - 1)
    
    # 超时
    def s1(self, nums): 
        cnt = 0
        for i in range(0, len(nums)-1):
            for j in range(i + 1, len(nums)):
                if nums[i] > nums[j]:
                    cnt += 1
        return cnt

排序​

剑指 Offer 45. 把数组排成最小的数​

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        # 将数字转换为字符串
        nums = [str(num) for num in nums]

        # 自定义比较函数 
        def compare(a, b):
            if a + b < b + a:
                return -1
            elif a + b > b + a:
                return 1
            else:
                return 0
        
        # 使用自定义比较函数排序
        nums.sort(key=cmp_to_key(compare))

        # 将排序后的字符串数组拼接起来
        return ''.join(nums)

剑指 Offer 61. 扑克牌中的顺子​

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        if not nums: return False
        joker = 0
        nums.sort()
        for i in range(4):
            if nums[i] == 0: joker += 1 # 统计大小王数量
            elif nums[i] == nums[i + 1]: return False # 重复数字，返回 False
        return nums[4] - nums[joker] < 5 # 最大牌 - 最小牌 < 5 则可构成顺子

剑指 Offer 40. 最小的k个数​

 def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k <= 0: return []
        arr.sort()
        return arr[0:k]

剑指 Offer 41. 数据流中的中位数​

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []

    def addNum(self, num: int) -> None:
        self.nums.append(num)

    def findMedian(self) -> float:
        self.nums.sort()
        if len(self.nums) % 2 == 1:
            return self.nums[len(self.nums)//2]
        else:
            mid = len(self.nums)//2
            return (self.nums[mid] + self.nums[mid-1])/2

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

动态规划​

剑指 Offer 10- I. 斐波那契数列​

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

剑指 Offer 10- II. 青蛙跳台阶问题​

class Solution:
    def numWays(self, n: int) -> int:
        if n == 0: return 1
        if n <= 3: return n
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]%1000000007

剑指 Offer 63. 股票的最大利润​

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # return self.s2(prices)
        # dp 求解
        if not prices: return 0

        # 结果
        res = 0

        # 值存储
        profit = [[0 for i in range(3)] for i in range(len(prices))]

        # 状态定义: 第一个下标，代表第 0 天，第二个下标，代表操作了多少次(包括买入和卖出)
        profit[0][0], profit[0][1], profit[0][2] = 0, -prices[0], 0

        # 状态方程
        for i in range(1, len(prices)):
            profit[i][0] = profit[i-1][0]
            profit[i][1] = max(profit[i-1][1], profit[i-1][0] - prices[i])
            profit[i][2] = profit[i-1][1] + prices[i]
            res = max(res, profit[i][0], profit[i][1], profit[i][2])
        return res
    
    def s2(self, prices):
        # for 循环，不断修正最小值，当前值 - 最小值 > 0 and > maximum，则替换掉 maximum 的值，循环结束，就得到最大利润
        if not prices: return 0
        minimum = prices[0]
        maximum = 0
        for i in prices:
            if i < minimum:
                minimum = i
            if i - minimum > 0 and i - minimum > maximum:
                maximum = i - minimum
        return maximum

    # 暴力法：timeout
    def s1(self, prices):
        if not prices: return 0
        maximum = 0
        for i in range(len(prices) - 1):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                if profit > 0 and profit > maximum:
                    maximum = profit
        return maximum

剑指 Offer 42. 连续子数组的最大和​

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 递归终止条件
        if len(nums) == 1:
            return nums[0]
        
        # 分解问题，将数组划分为两部分
        mid = len(nums) // 2
        left_nums = nums[:mid]
        right_nums = nums[mid:]
        
        # 递归求解左右两部分的最大子数组和
        left_max = self.maxSubArray(left_nums)
        right_max = self.maxSubArray(right_nums)
        
        # 计算跨越中点的最大子数组和
        cross_max = self.crossMaxSubArray(nums, mid)
        
        # 返回三者中的最大值作为最终结果
        return max(left_max, right_max, cross_max)
    
    def crossMaxSubArray(self, nums, mid):
        # 从中点向左扩展求取左半部分的最大子数组和
        left_sum = float('-inf')
        cur_sum = 0
        for i in range(mid-1, -1, -1):
            cur_sum += nums[i]
            left_sum = max(left_sum, cur_sum)
        
        # 从中点向右扩展求取右半部分的最大子数组和
        right_sum = float('-inf')
        cur_sum = 0
        for i in range(mid, len(nums)):
            cur_sum += nums[i]
            right_sum = max(right_sum, cur_sum)
            
        # 返回左右两部分的最大子数组和之和
        return left_sum + right_sum

    def _dp2(self, nums):
        if not nums: return 0

        dp = [0] * len(nums)
        dp[0] = nums[0]

        for i in range(1, len(nums)):
            # i-1 和大于0，说明有增益效果
            if dp[i-1] > 0:
                dp[i] = dp[i-1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)
    
    def _dp1(self, nums):
        if not nums: return 0

        # 结果存储
        dp = [0] * len(nums)
        # DP 状态初始化
        dp[0] = nums[0]

        for i in range(1, len(nums)):
            # DP 方程
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

剑指 Offer 47. 礼物的最大价值​

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid[0]: return 0
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        # 初始化第一行和第一列的最大值
        dp[0][0] = grid[0][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        for j in range(1, m):
            dp[j][0] = dp[j - 1][0] + grid[j][0]
        
        # DP 方程：递推计算每个格子的最大价值
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[m-1][n-1]

剑指 Offer 46. 把数字翻译成字符串​

class Solution:
    def translateNum(self, num: int) -> int:
        if num <= 9: return 1
        # 0 - 9：有一种翻译方法
        # 10-25: 有两种翻译方法
        num_str = str(num)
        n = len(num_str)

        # 创建一个长度为 n+1 的数组 dp，用于保存每个位置的翻译方案数
        dp = [0] * (n+1)

        # 初始化第一个位置的翻译方案数为 1
        dp[0] = 1

        # 递推计算每个位置的翻译数
        for i in range(1, n + 1):
            # 两位数字翻译 -> 1 个字母
            if i > 1 and '10' <= num_str[i-2:i] <= '25':
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        
        # 返回最后一个位置的翻译方案数
        return dp[n]

剑指 Offer 48. 最长不含重复字符的子字符串​

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希表记录字符和字符最近出现的位置
        char_dict = {} 
        left = 0 # 滑动窗口左边界
        max_length = 0 # 字符串最大长度

        for right in range(len(s)):
            if s[right] in char_dict and char_dict[s[right]] >= left:
                 # 当前字符重复了，更新左边界为重复字符的下一个位置
                left = char_dict[s[right]] + 1

            # 更新字符串在哈希表中的位置
            char_dict[s[right]] = right

            # 计算当前滑动窗口的长度
            current_length = right - left + 1

            # 更新最长子字符串的长度
            max_length = max(max_length, current_length)

        return max_length

剑指 Offer 19. 正则表达式匹配​

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        def matches(i: int, j: int) -> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]

        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] |= f[i][j - 2]
                    if matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

剑指 Offer 49. 丑数​

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1] # 存储丑数的数组
        p2,p3,p5 = 0,0,0  # 指向下一个丑数要乘以2、3、5的元素的索引

        for i in range(1, n):
            next_ugly2 = ugly[p2] * 2
            next_ugly3 = ugly[p3] * 3
            next_ugly5 = ugly[p5] * 5

            next_ugly = min(next_ugly2, next_ugly3, next_ugly5)
            ugly.append(next_ugly)

            # 移动指针
            if next_ugly == next_ugly2:
                p2 += 1
            if next_ugly == next_ugly3:
                p3 += 1
            if next_ugly == next_ugly5:
                p5 += 1
        return ugly[n-1]

剑指 Offer 60. n个骰子的点数​

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        dp = [1/6] * 6
        for i in range(2, n + 1):
            tmp = [0] * (5 * i + 1)
            for j in range(len(dp)):
                for k in range(6):
                    tmp[j + k] += dp[j]/6
            dp = tmp
        return dp

位运算​

剑指 Offer 15. 二进制中1的个数​

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n & 1
            n >>= 1
        return res
    
    def s1(self, n):
        rst = 0
        mask = 1
        for i in range(32):
            if n & mask:
                rst += 1
            mask = mask << 1
            print(mask)
        return rst

剑指 Offer 65. 不用加减乘除做加法​

class Solution:
    def add(self, a: int, b: int) -> int:
        if b == 0: return a
        return add(a ^ b, ((a & b) << 1))

剑指 Offer 56 - I. 数组中数字出现的次数​

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        nums_dict = {}
        for i in nums:
            if i in nums_dict:
                nums_dict[i] += 1
            else:
                nums_dict[i] = 1
        res = []
        for key,value in nums_dict.items():
            if value == 1:
                res.append(key)
        return res

剑指 Offer 56 - II. 数组中数字出现的次数 II​

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = [0] * 32
        res = 0 

        for num in nums:
            mask = 1
            for i in range(32):
                if num & mask:
                    count[i] += 1
                mask <<= 1
        
        for i in range(32):
            if count[i]%3 != 0:
                res |= (1 << i)

        return res

数学​

剑指 Offer 39. 数组中出现次数超过一半的数字​

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 排序
        nums.sort()
        return nums[len(nums)//2]

    # 哈希统计 
    def s1(sefl, nums):
        if not nums: return 0
        dic = {}

        res = 0
        for i in nums:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        for key,value in dic.items():
            if value > len(nums)//2:
                return key

剑指 Offer 66. 构建乘积数组​

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        # 结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积。一轮循环构建左边的乘积并保存在结果集中，
        # 二轮循环 构建右边乘积的过程，乘以左边的乘积，并将最终结果保存
        return self.s1(a)
    
    def s1(seflf, a):
        b, tmp = [1] * len(a), 1
        for i in range(1, len(a)):
            b[i] = b[i - 1] * a[i - 1] # 下三角
        for i in range(len(a) - 2, -1, -1):
            tmp *= a[i + 1]            # 上三角
            b[i] *= tmp                # 下三角 * 上三角
        return b

剑指 Offer 14- I. 剪绳子​

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(2, n+1):
            for j in range(i):
                dp[i] = max(dp[i], j* (i-j), j * dp[i-j])
        return dp[n]

剑指 Offer 14- II. 剪绳子 II​

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        
        # n >= 2
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], j * (i-j), j * dp[i-j])
                
        return dp[n]%1000000007

剑指 Offer 57 - II. 和为s的连续正数序列​

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i = 1 
        j = 1
        sum = 0
        res = []
        while i <= target//2:
            if sum < target:
                sum += j
                j += 1
            elif sum > target:
                sum -= i
                i += 1
            else:
                arr = list(range(i,j))
                res.append(arr)
                sum -= i
                i += 1
        return res

剑指 Offer 62. 圆圈中最后剩下的数字​

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        f = 0
        for i in range(2, n + 1):
             f = (m + f) % i
        return f

剑指 Offer 43. 1～n 整数中 1 出现的次数​

class Solution:
    def countDigitOne(self, n: int) -> int:
        digit, res = 1, 0
        high, cur, low = n // 10, n % 10, 0
        while high != 0 or cur != 0:
            if cur == 0: res += high * digit
            elif cur == 1: res += high * digit + low + 1
            else: res += (high + 1) * digit
            low += cur * digit
            cur = high % 10
            high //= 10
            digit *= 10
        return res

剑指 Offer 44. 数字序列中某一位的数字​

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit = 1  # 数位
        count = 9  # 数位范围内的数字个数
        start = 1  # 数位范围的起始数字

        # 确定目标数字所在的数位范围
        while n > count * digit:
            n -= count * digit
            digit += 1
            count *= 10
            start *= 10

        # 确定目标数字
        num = start + (n - 1) // digit

        # 确定目标数字中的具体数字
        return int(str(num)[(n - 1) % digit])