标签：return Offer int 第二 offer root self def

前15

题目	22.10.22	时间2	时间3	时间4
剑指 Offer 03. 数组中重复的数字	ac
剑指 Offer 04. 二维数组中的查找	ac
剑指 Offer 05. 替换空格	ac	x	x	x
剑指 Offer 06. 从尾到头打印链表	ac
剑指 Offer 07. 重建二叉树	ac、ac、？
剑指 Offer 09. 用两个栈实现队列	ac
剑指 Offer 10- I. 斐波那契数列	ac、？
剑指 Offer 10- II. 青蛙跳台阶问题	ac
剑指 Offer 11. 旋转数组的最小数字	ac
剑指 Offer 12. 矩阵中的路径	ac
剑指 Offer 14- I. 剪绳子	~
剑指 Offer 14- II. 剪绳子 II	ac
剑指 Offer 15. 二进制中1的个数	ac
剑指 Offer 16. 数值的整数次方	~

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

由于数字在0 - n-1，把数组当成hash，为了保证可以记录两次，减去n之后为负数的必定已经做过一次了

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            v = nums[i]
            if nums[i] < 0:
                v += n
            if nums[v] < 0:
                return v
            nums[v] -= n
        return -1

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

写matrix[0]是需要注意matrix是否存在的

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if not matrix:
            return False
        m = len(matrix[0])
        i = n - 1
        j = 0
        while 0 <= i < n and 0 <= j < m:
            if target == matrix[i][j]:
                return True
            elif target < matrix[i][j]:
                i -= 1
            else:
                j += 1
            # print(i, j,matrix[i][j])
        return False

剑指 Offer 05. 替换空格

语法

class Solution:
    def replaceSpace(self, s: str) -> str:
        s = s.replace(' ','%20')
        return s

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

使用额外数组

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

递归

先放转换后的，再放当前结点

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

剑指 Offer 07. 重建二叉树

朴素思想：根据根左右，左右根找到根节点后建树，由于每次需要index，花费n2的时间

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 根左右
        # 左根右
        if not preorder and not inorder:
            return
        # print(preorder, inorder)
        rootval = preorder[0]
        rootIdx = inorder.index(rootval)
        leftLength = rootIdx
        rightLength = len(inorder) - rootIdx - 1
        root = TreeNode(rootval)
        root.left = self.buildTree(preorder[1: 1 + leftLength], inorder[:leftLength])
        root.right = self.buildTree(preorder[1 + leftLength:], inorder[rootIdx + 1:rootIdx + 1 + rightLength])
        return root

优化：使用hash记录一下中序遍历结点值对应的位置

在这种情况下需要考虑递归过程中中序遍历序列是不断变化的，所以使用一个偏移量res记录在原始中序遍历序列上的实际位置

# 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:
        # 根左右
        # 左根右
        hash = {}
        for i, v in enumerate(inorder):
            hash[v] = i

        def dfs(preorder,inorder,res):
            if not preorder and not inorder:
                return
            # print(preorder,inorder,res)
            rootval = preorder[0]
            rootIdx = hash[rootval] - res
            # print(rootIdx)
            leftLength = rootIdx
            rightLength = len(inorder) - rootIdx - 1
            root = TreeNode(rootval)
            root.left = dfs(preorder[1: 1 + leftLength], inorder[:leftLength], res)
            root.right = dfs(preorder[1 + leftLength:], inorder[rootIdx + 1:rootIdx + 1 + rightLength], res + rootIdx + 1 )
            
            return root
        return dfs(preorder,inorder, 0)

迭代：？

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

数据全部存在helper里面

如果当加入新元素，就将helper的数据还原到stk中，在加入新元素后还原helper

class CQueue:

    def __init__(self):
        self.stk = []
        self.helper = []


    def appendTail(self, value: int) -> None:
        while self.helper:
            self.stk.append(self.helper.pop())
        self.stk.append(value)
        while self.stk:
            self.helper.append(self.stk.pop())

    def deleteHead(self) -> int:
        if not self.helper:
            return -1
        return self.helper.pop()

在添加时操作需要多次调换，比较慢
所以在删除时进行调换。
同样的stk只负责接受数据，helper负责输出。
这时由于保证了helper的输出的数据永远比stk中的数据老，所以只需要在helper为空的时候将stk的数据转移到helper中去

class CQueue:

    def __init__(self):
        self.stk = []
        self.helper = []

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

    def deleteHead(self) -> int:
        if self.helper:
            return self.helper.pop()
        if not self.stk and not self.helper:
            return -1
        while self.stk:
            self.helper.append(self.stk.pop())
        return self.helper.pop()

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

dp，终止为n，所以要for循环到n+1

class Solution:
    def fib(self, n: int) -> int:
        MOD = 1000000007
        if n == 0:
            return 0
        if n == 1:
            return 1
        f = [0] * (101)
        f[1] = 1
        for i in range(2, n + 1):
            f[i] = (f[i - 1] + f[i - 2]) % MOD
        # print(f)
        return f[n]

矩阵快速幂

？

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

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

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

二分，先去掉尾部和头部相同的部分。然后保证了和头部相同的一定在头部，这时后尾部还大于头部的话证明没有旋转，头部最小

二分的话如果mid大于头部的话，那么一定在区间的右侧，将left左移

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        k = 0
        n = len(numbers)
        while n - 1 - k >= 0 and numbers[n - 1 - k] == numbers[0]:
            k += 1
        tmp = numbers[0]
        numbers = numbers[:n - k]
        if not numbers:
            return tmp
        if numbers[-1] > numbers[0]:
            return numbers[0]
        l, r = 0, len(numbers) - 1
        while l < r:
            mid = l + r >> 1
            if numbers[mid] >= numbers[0]:
                l = mid + 1
            else:
                r = mid
        return numbers[l]

剑指 Offer 12. 矩阵中的路径

使用一个visited记录已经遍历的点

注意visited的删除不能使用pop，使用remove来删除

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(board)
        m = len(board[0])
        visited = set([])
        def dfs(x, y, cur):
            # print(sorted(list(visited)))
            if cur >= len(word):
                return True
            if not(0 <= x < n and 0 <= y < m):
                return False
            if board[x][y] != word[cur]:
                return False
            if (x, y) in visited:
                return False
            visited.add((x, y))
            res = dfs(x + 1, y, cur + 1) or  dfs(x, y + 1, cur + 1) or  dfs(x - 1, y, cur + 1) or  dfs(x, y - 1, cur + 1)
            visited.remove((x, y))
            return res

        for i in range(n):
            for j in range(m):
                visited = set([])
                if dfs(i, j, 0):
                    return True
        return False

剑指 Offer 14- I. 剪绳子

数学题：

如果能够整除3，直接就是结果

如果除以3余1，分两个2

如果除以3余2，分一个2

#  N > 0, N = n1 + n2 + ... + nk 为最大的分法
# 1. 假设ni >= 5 因为总有 3 *(ni - 3) >= ni，所以ni必不可能大于5
# 2. 假设ni = 4 4 = 2 * 2 乘积不会发生变化
# 3. 所以乘积只会包含2和3
# 下面证明最多只会有两个2
# 假设有3个2
# 2 + 2 + 2 < 3 * 3
# 所以不会存在3个以上的2

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3:
            return 1 * (n - 1)
        res = 1
        if n % 3 == 1:
            res *= 4
            n -= 4
        if n % 3 == 2:
            res *= 2
            n -= 2
        while n:
            res *= 3
            n -= 3
        return res

剑指 Offer 14- II. 剪绳子 II

就是加上了个MOD

class Solution:
    def cuttingRope(self, n: int) -> int:
        MOD = 1000000007
        if n <= 3:
            return n - 1
        res = 1
        if n % 3 == 1:
            res *= 4
            n -= 4
        elif n % 3 == 2:
            res *= 2
            n -= 2
        while n:
            res *= 3
            res %= MOD
            n -= 3
        return res % MOD

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

lowbit找到的是最后一个1对应的数值

所以lowbit之后使用原数减去lowbit之后，原数后面都是0

class Solution:

    def hammingWeight(self, n: int) -> int:
        def lowbit(x):
            return x & -x
        res = 0
        while n:
            n -= lowbit(n)
            res += 1
        return res

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

快速幂

如需求数据 a 的幂次，此处 a 可以为数也可以为矩阵，常规做法需要对a进行不断的乘积即 a * a * a * ... 此处的时间复杂度将为 O(n)

以求 3^10 的结果为例：

[优化步骤1：]

易知：

3^10=3*3*3*3*3*3*3*3*3*3

    =9^5 = 9^4*9

    =81^2*9

    =6561*9

基于以上原理，我们在计算一个数的多次幂时，可以先判断其幂次的奇偶性，然后：

如果幂次为偶直接 base(底数) 作平方，power(幂次) 除以2
如果幂次为奇则底数平方，幂次整除于2然后再多乘一次底数

[优化步骤2：]

对于以上涉及到 [判断奇偶性] 和 [除以2] 这样的操作。使用系统的位运算比普通运算的效率是高的，因此可以进一步优化：

把 power % 2 == 1 变为 (power & 1) == 1
把 power = power / 2 变为 power = power >> 1

只有power为偶数时才能将base变大

class Solution:
    def myPow(self, base: float, power: int) -> float:
        # 转换负数
        if power < 0:
            base = 1 / base
            power = -power
        res = 1
        while power > 0:
            # if power % 2 == 1:
            if power & 1 == 1:
                # 不能直接作用于底数上
                res *= base
            # power //= 2
            power >>= 1
            base *= base
        return res

中间靠前15个

题目	时间 22-10-22
剑指 Offer 17. 打印从1到最大的n位数	ac
剑指 Offer 18. 删除链表的节点	ac~
剑指 Offer 19. 正则表达式匹配	？
剑指 Offer 20. 表示数值的字符串	？
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面	ac~
剑指 Offer 22. 链表中倒数第k个节点	ac
剑指 Offer 24. 反转链表	ac_，
剑指 Offer 25. 合并两个排序的链表	ac，~
剑指 Offer 26. 树的子结构	~
剑指 Offer 27. 二叉树的镜像	ac
剑指 Offer 28. 对称的二叉树	ac
剑指 Offer 29. 顺时针打印矩阵	ac
剑指 Offer 30. 包含min函数的栈	ac
剑指 Offer 31. 栈的压入、弹出序列	ac~

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

找到上限即可

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        ans = [x for x in range(1, 10 ** n)]
        return ans

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

创建一个虚拟结点，这样不需要判断是不是需要删除head

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode()
        dummy.next = head
        cur = dummy
        while cur.next and cur.next.val != val:
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

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

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

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

相当于快排，需要注意的是与快排不同的是，可能存在找不到的情况，所以while中需要有判断

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if not nums:
            return nums
        left, right = -1, len(nums)
        while left < right:
            while 1:
                left += 1
                if left >= len(nums):
                    break
                if nums[left] % 2 != 1:
                    break
            while 1:
                right -= 1
                if right < 0:
                    break
                if nums[right] % 2 != 0:
                    break
            if left < len(nums) and right >= 0 and left < right:
                nums[left], nums[right] = nums[right], nums[left]
        return nums

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

快指针先走几步

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast = head
        slow = head
        while k:
            k -= 1
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

剑指 Offer 24. 反转链表

创建一个None结点，头结点指向指向这个结点，然后头结点变成新的需要被指向的结点

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

递归需要注意两个问题
一是退出递归的条件，单个结点或是没有结点都可以退出
二是如何递归。知道先反转head的后面，这时head.next的这根线还是连着的我们先需要迁出一条head.next到head的线，再断掉head到head.next的线

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        tmp = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return tmp

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        tmp = dummy
        while l1 and l2:
            if l1.val < l2.val:
                dummy.next = l1
                dummy = l1
                l1 = l1.next
            else:
                dummy.next = l2
                dummy = l2
                l2 = l2.next
        if l1:
            dummy.next = l1
        if l2:
            dummy.next = l2
        return tmp.next

递归：
当l1的值较小的时候，只需要将l1的next指针指向l1.next和l2的合并集合并且返回l1

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

剑指 Offer 26. 树的子结构

dfs是判断b是否是a的一部分

但是题目指定空树不是任意一个树的子结构，所以在外面需要修改not B为False

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

剑指 Offer 27. 二叉树的镜像

递归两种写法

第一种是在当前交换两个结点后，再进行下面结点的变换

第二种是先考虑变换完的结果，再改变当前结点的指向

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        root.left, root.right = root.right, root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        return root

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root   
        left = self.mirrorTree(root.left)
        right = self.mirrorTree(root.right)
        root.left, root.right = right, left
        return root

剑指 Offer 28. 对称的二叉树

左右两个结点分别判断

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def dfs(a,b):
            if not a and not b:
                return True
            if not a or not b:
                return False
            if a.val != b.val:
                return False
            return dfs(a.left,b.right) and dfs(a.right,b.left)
        if not root:
            return True
        if not root.left and not root.right:
            return True
        if not root.left or not root.right:
            return False
        return dfs(root.left,root.right)

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

注意访问完的元素需要标记一下

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        n = len(matrix)
        if not matrix:
            return []
        m = len(matrix[0])
        ans = []
        x, y = 0, 0
        idx = 0 
        for i in range(m * n):
            tx = x + dx[idx]
            ty = y + dy[idx]
            if not(0 <= tx < n and 0 <= ty < m and matrix[tx][ty] != 'x'):
                idx = (idx + 1) % 4
                tx = x + dx[idx]
                ty = y + dy[idx]
            ans.append(matrix[x][y])
            matrix[x][y] = 'x'
            x = tx
            y = ty
        return ans

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

一个辅助栈存目前的最小值，个数与stk的个数相同，同进同出

class MinStack:

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


    def push(self, x: int) -> None:
        self.stk.append(x)
        if self.help and self.help[-1] > x:
            self.help.append(x)
        else:
            if not self.help:
                self.help.append(x)
            else:
                self.help.append(self.help[-1])

    def pop(self) -> None:
        self.stk.pop()
        self.help.pop()

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

    def min(self) -> int:
        return self.help[-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 31. 栈的压入、弹出序列

用栈模拟，如果不符合就压栈，如果符合，idx+=1并且判断栈顶元素能否继续匹配

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        n = len(pushed)
        stk = []
        idx = 0
        for i in range(n):
            if pushed[i] != popped[idx]:
                stk.append(pushed[i])
            else:
                idx += 1
                while stk and stk[-1] == popped[idx]:
                    idx += 1
                    stk.pop()
        return len(stk) == 0

中间15个

题目	时间22-10-23
剑指 Offer 32 - I. 从上到下打印二叉树	ac	x	x	x
剑指 Offer 32 - II. 从上到下打印二叉树 II	ac	x	x	x
剑指 Offer 32 - III. 从上到下打印二叉树 III	ac	x	x	x
剑指 Offer 33. 二叉搜索树的后序遍历序列	~
剑指 Offer 34. 二叉树中和为某一值的路径	ac
剑指 Offer 35. 复杂链表的复制	~
剑指 Offer 36. 二叉搜索树与双向链表	~、？
剑指 Offer 37. 序列化二叉树	~
剑指 Offer 38. 字符串的排列	~
剑指 Offer 39. 数组中出现次数超过一半的数字	ac
剑指 Offer 40. 最小的k个数	ac~
剑指 Offer 41. 数据流中的中位数	ac~
剑指 Offer 42. 连续子数组的最大和	ac~
剑指 Offer 43. 1～n 整数中 1 出现的次数	~

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

bfs

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        q = [root]
        ans = []
        while q:
            tmp = q[:]
            q.clear()
            level = []
            while tmp:
                a = tmp.pop(0)
                level.append(a.val)
                if a.left:
                    q.append(a.left)
                if a.right:
                    q.append(a.right)
            ans.extend(level)
        return ans

dfs

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        ans = [[]]
        def dfs(u, level):
            if not u:
                return
            if level >= len(ans):
                ans.append([])
            ans[level].append(u.val)
            dfs(u.left, level + 1)
            dfs(u.right, level + 1)
        dfs(root, 0)
        res = []
        for x in ans:
            res.extend(x)
        return res

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

就是上一题

bfs

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = [root]
        ans = []
        while q:
            tmp = q[:]
            q.clear()
            level = []
            while tmp:
                a = tmp.pop(0)
                level.append(a.val)
                if a.left:
                    q.append(a.left)
                if a.right:
                    q.append(a.right)
            ans.append(level)
        return ans

dfs

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        ans = [[]]
        def dfs(u, level):
            if not u:
                return
            if level >= len(ans):
                ans.append([])
            ans[level].append(u.val)
            dfs(u.left, level + 1)
            dfs(u.right, level + 1)
        dfs(root, 0)
        return ans

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

相同的题，加了个判断

bfs

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = [root]
        ans = []
        idx = 0
        while q:
            tmp = q[:]
            q.clear()
            level = []
            while tmp:
                a = tmp.pop(0)
                level.append(a.val)
                if a.left:
                    q.append(a.left)
                if a.right:
                    q.append(a.right)
            if idx % 2 == 0:
                ans.append(level)
            else:
                ans.append(level[::-1])
            idx += 1
        return ans

dfs

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        ans = [[]]
        def dfs(u, level):
            if not u:
                return
            if level >= len(ans):
                ans.append([])
            ans[level].append(u.val)
            dfs(u.left, level + 1)
            dfs(u.right, level + 1)
        dfs(root, 0)
        for i,_ in enumerate(ans):
            if i % 2 == 1:
                ans[i] = ans[i][::-1]
        return ans

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

左右根

由于为二叉搜索树，所以左边必须要小于根结点，右边必须大于根节点。

使用l和r来帮助判定后序的左右分界，不需要传入数组

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def dfs(l ,r):
            if l >= r:
                return True
            root = postorder[r]
            k = l
            while k < r and postorder[k] < root:
                k += 1
            for i in range(k, r):
                if postorder[i] < root:
                    return False
            return dfs(l, k - 1) and dfs(k, r - 1)
        return dfs(0, len(postorder) - 1)

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

dfs

将res可以放在递归的外面

由于在判断到是子节点的时候sum值还没有加上当前val，要先加上去

class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        ans = []
        res = []
        def dfs(u):
            if not u:
                return
            if not u.left and not u.right:
                if sum(res) + u.val == target:
                    res.append(u.val)
                    ans.append(res[:])
                    res.pop()
                return
            res.append(u.val)
            dfs(u.left)
            dfs(u.right)
            res.pop()
        dfs(root)
        return ans

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

遵循规则：

先复制所有的点，再复制所有的边

不创建hash表，使用每个结点后面创建一个小弟

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        p = head
        # 创建一个小弟
        while p:
            q = Node(p.val)
            q.next = p.next
            p.next = q
            p = p.next.next
        p = head
        # 复制random指针
        while p:
            if p.random:
                p.next.random = p.random.next
            p = p.next.next
        # 拆分两个链表
        dummy = Node(-1)
        cur = dummy
        p = head
        while p:
            q = p.next
            # 插入
            cur.next = q
            cur = cur.next
            # 断链
            p.next = q.next
            p = p.next
        return dummy.next

复制图

133. 克隆图

创建一个hash，存放新老结点

要访问完所有的结点，使用dfs即可

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        hash = {}
        # 复制结点
        
        def dfs(node):
            hash[node] = Node(node.val)
            for nxt in node.neighbors:
                if nxt not in hash:
                    dfs(nxt)
        
        dfs(node)
        # 复制边
        for st in hash:
            ed = hash[st]
            for nxt in st.neighbors:
                ed.neighbors.append(hash[nxt])
        return hash[node]

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

找到每个点的左右两边，拼在一起后，返回左右两侧端点

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return root
        def dfs(u):
            if not u.left and not u.right:
                return [u, u]
            if u.left and u.right:
                lside = dfs(u.left)
                rside = dfs(u.right)
                lside[1].right = u
                u.left = lside[1]
                rside[0].left = u
                u.right = rside[0]
                return [lside[0], rside[1]]
            if not u.right:
                lside = dfs(u.left)
                lside[1].right = u
                u.left = lside[1]
                return [lside[0], u]
            if not u.left:
                rside = dfs(u.right)
                rside[0].left = u
                u.right = rside[0]
                return [u, rside[1]]
        [a, b] = dfs(root)
        a.left = b
        b.right = a
        return a

https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5?f=discussion

剑指 Offer 37. 序列化二叉树

使用前序遍历

序列话的话使用一个全局path记录下访问的路径情况

反序列化的化使用一个下标p记录访问到哪个位置，注意可能为负数或者数值大于10，要找到下一个，的位置再给当前结点赋值

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        path = ''
        def dfs_s(u):
            nonlocal path
            if not u:
                path += '#,'
                return
            path += str(u.val) + ','
            dfs_s(u.left)
            dfs_s(u.right)
        dfs_s(root)
        return path
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        p = 0
        def dfs_d():
            nonlocal p
            if data[p] == '#':
                p += 2
                return None
            k = p
            while data[p] != ',':
                p += 1
            root = TreeNode(int(data[k: p]))
            p += 1
            root.left = dfs_d()
            root.right = dfs_d()
            return root
        return dfs_d()
            
        

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

剑指 Offer 38. 字符串的排列

先把位置给出来--path 肥肠关键

为了避免选到重复的元素组合，我们规定如果两个元素相同，只允许后面的元素填在前面元素的后面，不允许在前面。当然这需要先sort一下。

class Solution:
    def permutation(self, s: str) -> List[str]:
        ans = []
        s = ''.join(sorted(list(s)))
        path = ['' for _ in range(len(s))] 

        def dfs(u,start,state):
            if u == len(s):
                ans.append(''.join(path))
                return
            # 去重判断
            if u == 0 or s[u] != s[u-1]:
                start = 0
            for i in range(start, len(s)):
                if not (state >> i & 1):
                    path[i] = s[u]
                    dfs(u + 1, i + 1, state + (1 << i))
            # print(path)

        dfs(0, 0, 0)
        return ans

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

摩尔投票，消减就完事了

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 摩尔投票
        n = len(nums)
        cnt = 1
        x = nums[0]
        for i in range(1, len(nums)):
            v = nums[i]
            if not cnt:
                x = v
                cnt = 1
            else:
                if x == v:
                    cnt += 1
                else:
                    cnt -= 1
        return x

剑指 Offer 40. 最小的k个数

创建一个堆，python默认为小顶堆，需要使用负数来创建成大顶堆，经过几次更新之后，将大的都pop出去了，所以剩余的为最小的k个

from heapq import *
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        q = []
        n = len(arr)
        for i in range(n):
            if len(q) < k:
                heappush(q, -arr[i])
            else:
                heappush(q, -arr[i])
                heappop(q)
        ans = []
        while q:
            ans.append(-heappop(q))
        return ans

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

创建一个大小相冲的堆。

下面为贫民区，下面为富人区。

来数字默认进入贫民区，如果此时发现这时他的大小比富人区的最小值要大，他晋级为富人区，富人区较拉的贬为贫民。 --- 竞争

为了保证均衡，当贫民区和富人区的人数差值达到2时，我们就需要向富人区补充新鲜血液。 --- 均衡

from heapq import *
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        # 小顶堆
        self.top = []
        # 大顶堆
        self.down = []

    def addNum(self, num: int) -> None:
        heappush(self.down, -num)
        # 逆序
        if self.top and self.top[0] < -self.down[0]:
            heappush(self.top, -heappop(self.down)) 
            heappush(self.down, -heappop(self.top))
        # 堆的大小相差为2
        if len(self.down) - len(self.top) >= 2:
            heappush(self.top, -heappop(self.down))

    def findMedian(self) -> float:
        if len(self.top) == len(self.down):
            return (self.top[0] + -self.down[0]) / 2
        return -self.down[0]



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

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

存在负数，不单调，不能用双指针

这里的f[i]是以i结尾的最大和，我们这里必须需要包含i，显然当f[i-1]为负数的时候，我们可以舍弃掉他

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * n
        for i in range(n):
            if i > 0 and f[i - 1] < 0:
                f[i] = nums[i]
            else:
                f[i] = f[i - 1] + nums[i]
        return max(f)

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

数位dp

i：当前第几位

cnt：当前有几个1

isLimited：当前位是否被前面的限制

这里只需要考虑1出现的次数，不需要考虑前导零，所以hasNum参数不需要

同样，由于不需要考虑避免重复，mask参数也不需要

class Solution:
    def countDigitOne(self, n: int) -> int:
        s = str(n)
        @cache
        def dfs(i, cnt, isLimited):
            if len(s) == i:
                return cnt
            up = 9
            if isLimited:
                up = int(s[i])
            res = 0
            for k in range(up + 1):
                res += dfs(i + 1, cnt + 1 if k == 1 else cnt, isLimited and k == up)
            return res
        return dfs(0, 0, True)

中间靠后15个

题目	时间22-10-25
剑指 Offer 44. 数字序列中某一位的数字	~
剑指 Offer 45. 把数组排成最小的数	~
剑指 Offer 46. 把数字翻译成字符串	ac，ac~
剑指 Offer 47. 礼物的最大价值	ac~
剑指 Offer 48. 最长不含重复字符的子字符串	ac
剑指 Offer 49. 丑数	ac
剑指 Offer 50. 第一个只出现一次的字符	ac
64. 字符流中第一个只出现一次的字符	~
剑指 Offer 51. 数组中的逆序对	ac~
剑指 Offer 52. 两个链表的第一个公共节点	ac~
剑指 Offer 53 - I. 在排序数组中查找数字 I	ac
剑指 Offer 53 - II. 0～n-1中缺失的数字	ac~
剑指 Offer 54. 二叉搜索树的第k大节点	ac~
剑指 Offer 55 - I. 二叉树的深度	ac	x	x	x

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

class Solution:
    def findNthDigit(self, n: int) -> int:
        # k 长度
        # t 当前长度数字的总个数
        # s k长度下的首个数字
        # => k * t 就是k长度下的数位个数
        k, t ,s = 1, 9, 1
        # 找到n数位属于哪个长度段的数字
        while n > k * t:
            n -= k * t
            k += 1
            t *= 10
            s *= 10
        # 找到n数位在k长度段的具体哪个数字
        # n / k 上取整 就是 n + k - 1 / k 下取整
        s += (n + k - 1) // k - 1
        # 找到数字是s,还需要知道是s的哪一位
        # 如果正好整除,是最后一位k
        n = n % k if n % k != 0 else k
        return int(str(s)[n - 1])

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

定义一个新的比较方式

使用cmp_to_key

它有两个传入参数x,y 当x>y时返回1 等于时返回0，否则返回-1

它在list中的工作机制就是将列表中的元素去两两比较，当cmp返回是正数时交换两元素

例如：

10， 2

102 与210，我们优先选择102

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        if not nums:
            return ''
        nums = [str(x) for x in nums]
        from functools import cmp_to_key
        nums = sorted(nums, key = cmp_to_key(lambda x,y: int(x + y) - int(y + x)))
        return ''.join(nums)

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

开始没想到可以转换成青蛙跳台阶

使用两个状态记录翻译不翻译，

不翻译的话前面必须翻译过

翻译的话要么是和前面相接<=25，就可以从不翻译状态转移过来

当然一直可以从翻译状态转移到翻译状态

返回的话返回最后一位也翻译的状态。

需要注意如果前面一位是0，是不能构成状态转移的

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        f = [[0, 0] for _ in range(len(s))]
        # f[i][0] 当前位不翻译
        # f[i][1] 当前位翻译 
        f[0][0] = 1
        f[0][1] = 1
        for i in range(1, len(s)):
            f[i][0] = f[i - 1][1]
            if s[i - 1] != '0' and int(s[i - 1] + s[i]) <= 25:
                f[i][1] = f[i - 1][0]
            f[i][1] += f[i - 1][1]
        # print(f)
        return f[len(s) - 1][1]

如果转换成青蛙跳台阶问题

f代表到目前位置的方案数

如果不能和上个数拼成一个数，只能继承上个数的方案数

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        n = len(s)
        f = [0] * n
        if num <= 9:
            return 1
        f[0] = 1
        if 0 <= int(s[0] + s[1]) <= 25:
            f[1] = 2
        else:
            f[1] = 1
        for i in range(2, n):
            if s[i-1] != '0' and 0 <= int(s[i-1] + s[i]) <= 25:
                f[i] = f[i-2] + f[i-1]
            else:
                f[i] = f[i-1]
            # print(f)
        return f[n-1]

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

初始化的时候需要将两边都初始化到

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        f = [[0 for _ in range(n)] for _ in range(m)]
        f[0][0] = grid[0][0]
        for i in range(1, m):
            f[i][0] = f[i - 1][0] + grid[i][0]
        for j in range(1, n):
            f[0][j] = f[0][j - 1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = max(f[i][j], max(f[i-1][j],f[i][j-1]) + grid[i][j])
        return f[m-1][n-1]

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

双指针，while里面是hash的i

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i, j = 0, 0
        hash = defaultdict(int)
        ans = 0
        while i < len(s):
            hash[s[i]] += 1
            while j <= i and hash[s[i]] >= 2:
                hash[s[j]] -= 1
                j += 1
            ans = max(i - j + 1, ans)
            i += 1
        return ans

剑指 Offer 49. 丑数

i，j，k是数组的下标，通过与下标的数字相乘得迭代得到下个数字

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [1] * n
        i, j, k = 0, 0, 0
        idx = 1
        while idx < n:
            a = res[i] * 2
            b = res[j] * 3
            c = res[k] * 5
            t = min(a, b, c)
            if a == t:
                i += 1
            if b == t:
                j += 1
            if c == t:
                k += 1
            res[idx] = t
            idx += 1
        return res[-1]

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

class Solution:
    def firstUniqChar(self, s: str) -> str:
        hash = Counter(s)
        for v in s:
            if hash[v] == 1:
                return v
        return ' '

64. 字符流中第一个只出现一次的字符

使用一个队列存放字符，如果当前字符加入后出现问题，--》隐疾

如果第一个字符雀氏出现问题，就一直pop，直到没有问题

from collections import Counter
class Solution:  
    def __init__(self):
        self.hash = Counter()
        self.q = []
    def insert(self, c):
        """
        :type char: str
        :rtype: void
        """
        self.hash[c] += 1
        if self.hash[c] > 1:
            while self.q and self.hash[self.q[0]] > 1 :
                self.q.pop(0)
        else:
            self.q.append(c)
        # print(self.hash, self.q)
        
        
    def firstAppearingOnce(self):
        """
        :rtype: str
        """
        if not self.q:
            return '#'
        return self.q[0]

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

arr不能缺少，返回值为个数

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge(l, r, arr):
            if l >= r:
                return 0
            mid = l + r >> 1
            cnt = merge(l, mid, arr) + merge(mid + 1, r, arr)
            res = []
            i, j = l, mid + 1
            while i <= mid and j <= r:
                if nums[i] > nums[j]:
                    cnt += (mid - i + 1)
                    res.append(nums[j])
                    j += 1
                else:
                    res.append(nums[i])
                    i += 1
            while i <= mid:
                res.append(nums[i])
                i += 1
            while j <= mid:
                res.append(nums[j])
                j += 1
            for i in range(len(res)):
                arr[i + l] = res[i]
            return cnt
        return merge(0, len(nums) - 1, nums)

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

就是当出现None时，就改变头部端点

该相交的人总会相交

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a = headA
        b = headB
        while a != b:
            if not a:
                a = headB
            else:
                a = a.next
            if not b:
                b = headA
            else:
                b = b.next
        return a

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

左右画图

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

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

可能会出现前面都是对的，缺了最后一个n，需要特判一下

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + r >> 1
            if nums[mid] != mid:
                r = mid
            else:
                l = mid + 1
        if l == nums[l]:
            return l + 1
        return l

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

k的更新在根节点是变动

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        ans = 0
        def dfs(u):
            nonlocal k
            nonlocal ans
            if not u:
                return
            dfs(u.right)
            k -= 1
            if k == 0:
                ans = u.val
            dfs(u.left)
        dfs(root)       
        return ans

剑指 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:
        def dfs(u):
            if not u:
                return 0
            return max(dfs(u.left),dfs(u.right)) + 1
        return dfs(root)

最后19个

题目	时间22-10-25
剑指 Offer 55 - II. 平衡二叉树	ac~
剑指 Offer 56 - I. 数组中数字出现的次数	~
剑指 Offer 56 - II. 数组中数字出现的次数 II	?
剑指 Offer 57 - II. 和为s的连续正数序列	~
剑指 Offer 58 - I. 翻转单词顺序	ac
剑指 Offer 58 - II. 左旋转字符串	ac~
剑指 Offer 59 - I. 滑动窗口的最大值	ac
剑指 Offer 60. n个骰子的点数	~
剑指 Offer 61. 扑克牌中的顺子	ac~
剑指 Offer 62. 圆圈中最后剩下的数字	~
剑指 Offer 63. 股票的最大利润	ac
剑指 Offer 64. 求1+2+…+n	ac	x	x	x
剑指 Offer 66. 构建乘积数组	ac
剑指 Offer 67. 把字符串转换成整数	？
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先	ac~
剑指 Offer 68 - II. 二叉树的最近公共祖先	~
面试题13. 机器人的运动范围	ac~
面试题59 - II. 队列的最大值	ac

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

需要注意的是left，right 都为-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 isBalanced(self, root: TreeNode) -> bool:
        def dfs(u):
            if not u:
                return 0
            l = dfs(u.left)
            r = dfs(u.right)
            if abs(l - r) > 1 or l == -1 or r == -1:
                return -1
            return max(l,r) + 1
        if dfs(root) == -1:
            return False
        return True

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

找到两个数的异或，怎么区分两个数

考虑最后异或出来的数的性质，将原集合分为两部分

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        s = 0
        for v in nums:
            s ^= v
        # x ^ y = s != 0
        # x, y 至少存在一位不同
        # s的第k位为1
        # 不妨设x的第k位为1
        # 将nums分成两大类
        # 左边是第k位为1的所有数，右边是第k位为0的所有数
        # x在左边 y在右边
        k = 0
        while s >> k & 1 == 0:
            k += 1
        x = 0
        for v in nums:
            if v >> k & 1 == 1:
                x ^= v
        return [x, s ^ x]

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

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

左右双指针

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l, r = 0 ,len(nums) - 1
        while 1:
            s = nums[l] + nums[r]
            if s == target:
                break
            elif s > target:
                r -= 1
            else:
                l += 1
        return [nums[l], nums[r]]

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

j移动的快，如果能找到，j的位置应该正好是找到target时i所对应的位置

将j + 1写在前面，避免乱序的情况

i缓慢移动，即使出现

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        i, j = 1, 1
        s = 1
        while i <= target:
            while s < target:
                j += 1
                s += j
            if s == target and j - i + 1 > 1:
                res.append(list(range(i,j + 1)))
            s -= i
            i += 1
        return res

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

如果为cpp，考虑先反转整个字符串，再反转每个字符

class Solution:
    def reverseWords(self, s: str) -> str:
        # s = s.strip()
        s = s.split()[::-1]
        return ' '.join(s)

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

先反转整个串

再反转除了后k个元素的所有串

再翻转后k个元素

class Solution:
    def reverseLeftWords(self, s: str, k: int) -> str:
        t = s[::-1]        
        p = t[:len(t) - k][::-1]
        q = t[len(t) - k:][::-1]
        # abcdefg
        # gfedcba cdefg ab
        # cdefgab
        return p + q

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

单调队列

先写窗口未形成前的，再写窗口形成之后的

使用deque加速，普通的list太慢了

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque([])
        for i in range(k):
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
        ans = [nums[q[0]]]
        for i in range(k, len(nums)):
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
            while q and i - q[0] >= k:
                q.popleft() 
            ans.append(nums[q[0]])
        return ans

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

首先明确目标：求概率不是很好求，我们选择求出现的次数

接着创建fij，指第i次出现结果j的情况个数

需要保证j大于等于0，所以for循环写成min

接着f数组不是全部都有意义，只有实际存在的即n以后的才有意义

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        f = [[0 for _ in range(6 * n + 1)] for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, 6 * n + 1):
                for k in range(1, min(j + 1, 7)):
                        f[i][j] += f[i - 1][j - k]
        res = f[n][n:]
        s = sum(res)
        res = [x / s for x in res]
        return res

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

首先明确如果最大的和最小的差值如果小于等于4，证明我们可以弥补

然后找到第一个0结束的位置，再判断是否存在相同的值，再判断差值

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        k = 0
        nums.sort()
        while not nums[k]:
            k += 1
        for i in range(k + 1, len(nums)):
            if nums[i] == nums[i-1]:
                return False
        return nums[-1] - nums[k] <= 4

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

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        # 约瑟夫环问题
        # 总结出相邻两项的关系
        # f[n,m] 表示一共n个人，第m个人被干掉
        # f[n,m] -> f[n - 1,m] 
        # 但是此时新问题的编号与老问题不一致，我们需要把新问题的解决编号映射到老问题上去
        # 寻找一个关系
        # 旧 m m+1 m+2
        # 新 0 1 2      (新 + m) % n = 旧
        if n == 1:
            return 0
        return (self.lastRemaining(n - 1,m) + m) % n

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

动态规划第一位为买入第二位为卖出

只能卖出一次，所以只能买入向卖出转移

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n = len(prices)
        f = [[0, 0]] * (n)
        f[0][0] = -prices[0]
        for i in range(1, n):
            f[i][0] = max(f[i - 1][0], -prices[i])
            f[i][1] = max(f[i - 1][0] + prices[i], f[i - 1][1])
        # print(f)
        return f[n - 1][1]

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

class Solution:
    def sumNums(self, n: int) -> int:
        return sum(range(1, n + 1))

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

在实际中可以并行的来计算

先算出所有数字的不进位结果，再算出进位

没有进位的时候证明结束了

func add(a int, b int) int {
    for b!=0{
        // xor 是不进位加法
        sum := a ^ b
        // 进位 当两位都是1时
        carry := (a & b) << 1
        a = sum
        b = carry
    }
    return a
}

写成递归就清楚了，最后两者还要加上，所以就调用这add方法

func add(a int, b int) int {
    if b == 0{
        return a
    }
    return add(a ^ b, (a & b) << 1)
}

剑指 Offer 66. 构建乘积数组

假如数组[a,b,c,d,e]
第一次循环我们得到的值是:当前下标前面的所有元素的乘积 res = [1, a, ab, abc, abcd]
第二次循环我们得到的是:res 反向遍历，然后错位乘积，得到的是当前下标后面的所有元素的乘积。res = [bcde, acde, abde, abce, abcd]

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        n = len(a)
        pre = [1] * n
        aft = [1] * n 
        for i in range(1, n):
            pre[i] = pre[i - 1] * a[i - 1]
        for i in range(0, n - 1)[::-1]:
            aft[i] = aft[i + 1] * a[i + 1]
        res = [1] * n
        for i in range(n):
            res[i] = pre[i] * aft[i]
        return res

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

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

是二叉搜索树，判断利用与根节点的大小关系

出口判定

root为p或q就可以直接返回

没root也直接返回

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

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

相对于上面的LCA，不能通过左右大小剪枝

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

面试题13. 机器人的运动范围

经典宽搜问题

class Solution:
    def getSum(self, x, y):
        s = 0 
        x = list(str(x))
        for v in x:
            s += int(v)
        y = list(str(y))
        for v in y:
            s += int(v)
        return s
    def movingCount(self, m: int, n: int, k: int) -> int:
        q = deque()
        q.append([0, 0])
        st = [[False for _ in range(n)] for _ in range(m)]
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        res = 0
        while q:
            # print(q)
            x, y = q.popleft()
            if x >= 0 and x < m and y >= 0 and y < n and not st[x][y] and self.getSum(x, y) <= k:
                res += 1
                st[x][y] = True
                for i in range(4):
                    tx = x + dx[i]
                    ty = y + dy[i]
                    q.append([tx, ty])
        return res

面试题59 - II. 队列的最大值

创建一个单调队列辅助存最大值

class MaxQueue:

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

    def max_value(self) -> int:
        if not self.helper:
            return -1
        return self.helper[0]

    def push_back(self, value: int) -> None:
        self.q.append(value)
        while self.helper and self.helper[-1] < value:
            self.helper.pop()
        self.helper.append(value)

    def pop_front(self) -> int:
        if not self.q:
            return -1
        t = self.q.popleft()
        if self.helper[0] == t:
            self.helper.popleft()
        return t


# 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()

标签：return,Offer,int,第二,offer,root,self,def
From： https://www.cnblogs.com/ydssx7/p/16829965.html

剑指offer(第二版）

前15

中间靠前15个

中间15个

中间靠后15个

最后19个

相关文章

赞助商

阅读排行