@author : zzhijiki

剑指offer 代码练习

面试题03. 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        temp=set()
        for num in nums:
            if num not in temp:
                temp.add(num)
            else:
                return num
        return False

面试题04. 二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

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

面试题05. 替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

# 略 这题不是给python玩家出的

面试题06. 从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if not listNode:return []
        ans=[]
        while listNode:
            ans.append(listNode.val)
            listNode=listNode.next
        return ans[::-1]

面试题07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

# 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:
        if len(inorder) == 0:
            return 
        root=TreeNode(preorder[0])
        mid=inorder.index(preorder[0])
        root.left=self.buildTree(preorder[1:mid+1],inorder[:mid])
        root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])
        return root

面试题09. 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

class CQueue:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def appendTail(self, value: int) -> None:
        self.stack1.append(value)
    def deleteHead(self) -> int:
        if self.stack2:
            return self.stack2.pop()
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop() if self.stack2 else -1

面试题10- I. 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

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

面试题10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

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

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        dp=[1]*(number+1)
        if number==1:return 1
        for i in range(2,number+1):
            for j in range(1,i):
                dp[i]+=dp[i-j]
        return dp[number]

其实就是

面试题11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

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

面试题12. 矩阵中的路径

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

初版代码：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:return False
        m=len(board)
        n=len(board[0])        
        dx=[1,-1,0,0]
        dy=[0,0,1,-1]
        self.visited=[[1]*n for _ in range(m)]

        def dfs(i,j,level):
            if i<0 or i>=m or j<0 or j>=n:return False
            if level>=len(word):return True
            for ix,iy in zip(dx,dy):
                x,y=i+ix,j+iy
                if x<0 or x>=m or y<0 or y>=n:continue
                if board[x][y]==word[level] and self.visited[x][y]:
                    self.visited[x][y]=0
                    flag=dfs(x,y,level+1)
                    if flag:
                        return True
                    self.visited[x][y]=1
            return False

        for i in range(m):
            for j in range(n):
                if board[i][j]==word[0]:
                    self.visited[i][j]=0
                    flag=dfs(i,j,1)
                    self.visited[i][j]=1
                    if flag:
                        return True
        return False

优化后代码：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:return False
        m=len(board)
        n=len(board[0])        
        dx=[1,-1,0,0]
        dy=[0,0,1,-1]
        self.visited=[[1]*n for _ in range(m)]

        def dfs(i,j,level):
            if i<0 or i>=m or j<0 or j>=n:return False
            if board[i][j]!=word[level]:return False
            if level==len(word)-1:return True
            self.visited[i][j]=0
            for ix,iy in zip(dx,dy):
                x,y=i+ix,j+iy
                if x<0 or x>=m or y<0 or y>=n:continue
                if self.visited[x][y] and dfs(x,y,level+1):return True
            self.visited[i][j]=1
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i,j,0):return True
        return False

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

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def check(i,j,k):
            ans=0
            while i:
                ans+= i%10
                i//=10
            while j:
                ans+= j %10
                j//=10
            return ans<=k

        self.ans=0
        self.visited=[[1]*n for _ in range(m)]
        dx=[1,-1,0,0]
        dy=[0,0,1,-1]

        def dfs(i,j):
            if i>=m or i<0 or j<0 or j>=n:return 
            if not self.visited[i][j]:return
            if check(i,j,k):
                self.ans+=1
            else:
                return
            self.visited[i][j]=0
            for ix,iy in zip(dx,dy):
                x,y=i+ix,j+iy
                dfs(x,y)
        dfs(0,0)
        return self.ans

面试题14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

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

面试题14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007）

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

面试题15. 二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans=0
        while n:
            n&=n-1
            ans+=1     
        return ans

面试题16. 数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

位运算快速幂：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n==0:return 1
        ans=1
        if n>0:
            while n:
                if n&1:ans*=x
                x*=x              
                n>>=1
            return ans
        if n<0:
            return 1/self.myPow(x,-n)

面试题17. 打印从1到最大的n位数

考察意义是什么。。。应该不是给python玩家出的。。

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

面试题18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        p=ListNode(-1)
        p.next=head
        if head.val==val:return head.next
        while head and head.next:
            if head.next.val==val:
                head.next=head.next.next
            head=head.next
        return p.next

面试题19. 正则表达式匹配

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab_ac_a”匹配，但是与”aa.a”和”ab*a”均不匹配

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n1= len(s)
        n2= len(p)
        ## dp[i][j]：表示s的前i个能被p的前j个匹配     
        # 边界条件
        s="@"+s
        p="@"+p
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        dp[0][0] =1
        # 处理边界 第一行
        for i in range(1, n2+1):
            if p[i] == '*':
                dp[0][i] = dp[0][i-2]
        # 处理非边界
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                if s[i] == p[j] or p[j] == '.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j] == '*':
                    if p[j-1] == s[i] or p[j-1] == '.':
                        dp[i][j] = max(dp[i][j-2] , dp[i][j-1], dp[i-1][j])
                    else:
                        dp[i][j] = dp[i][j-2] 
        return bool(dp[-1][-1])

面试题20. 表示数值的字符串

验证给定的字符串是否可以解释为十进制数字。

例如:

“0” => true
……

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

面试题21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分

普通算法：就已经双90%了

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        temp1=[]
        temp2=[]
        for value in nums:
            if value&1:
                temp1.append(value)
            else:
                temp2.append(value)
        return temp1+temp2

快慢指针：其实也就快了一点

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if len(nums)==0:return []
        p1,p2=0,0
        for value in nums:
            if nums[p2]&1:
                nums[p1],nums[p2]=nums[p2],nums[p1]
                p2+=1
                p1+=1
            else:
                p2+=1
        return nums

面试题22. 链表中倒数第k个节点

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

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

面试题24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:return None
        cur=None
        while head:
            temp=ListNode(head.val)
            temp.next=cur
            cur=temp
            head=head.next
        return cur

利用python的性质：

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

面试题25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

普通：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        p1,p2=l1,l2
        res=ans=ListNode(-1)
        while p1 or p2:
            if not p1:
                ans.next=p2
                return res.next
            if not p2:
                ans.next=p1
                return res.next
            if p1.val<=p2.val:
                ans.next=p1             
                p1=p1.next
                ans=ans.next      
            else:
                ans.next=p2
                p2=p2.next
                ans=ans.next   
        return res.next

递归：

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

面试题26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

# 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 check(A,B):
            de=[B]
            pe=[A]
            while de:
                new_q=[]
                new_p=[]
                for node1,node2 in zip(de,pe):
                    if node1.val!=node2.val:
                        return False
                    if node1.left:
                        if not node2.left:
                            return False
                        else:
                            new_q.append(node1.left)
                            new_p.append(node2.left)
                    if node1.right:
                        if not node2.right:
                            return False
                        else:
                            new_q.append(node1.right)
                            new_p.append(node2.right)
                de=new_q
                pe=new_p
            return True

        if not A or not B:return False
        if A.val==B.val and check(A,B):return True
        return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

上面是bfs，下面是dfs解法：

# 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 check(A,B):
            if not B:return True
            if not A:return False
            if A.val !=B.val :return False
            return check(A.left,B.left) and check(A.right,B.right)

        if not A or not B:return False
        if A.val==B.val and check(A,B):return True
        return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

面试题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:
        if not root:
            return
        root.left,root.right=root.right,root.left
        if root.left:
            self.mirrorTree(root.left)
        if root.right:
            self.mirrorTree(root.right)
        return root

上面是递归，下面用dfs的栈

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:return root
        stack=[root]
        while stack:
            node=stack.pop()
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            node.left,node.right=node.right,node.left
        return root

面试题28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

我的提交太长了，算法：先翻转再验证是否一样。我还有一个想法就是：中序遍历是回文。

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:return True
        def turn(root):
            if not root:return
            root.left,root.right=root.right,root.left
            if root.left:
                turn(root.left)
            if root.right:
                turn(root.right)
            return root
        def check(root1,root2):
            if not root1 and not root2:return True
            if root1 and root2:
                if root1.val==root2.val:
                    return check(root1.left,root2.left) and check(root1.right,root2.right)
                else:
                    return False
            else:
                return False
        if root.right and root.left:
            if root.right.val==root.left.val and check(turn(root.left),root.right):
                print(turn(root.left))
                print(root.right)
                return True
        if not root.right and not root.left:return True
        return False

递归的算法：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def mirror(root1,root2):
            if not root1 and not root2:return True
            if root1 and root2 and root1.val==root2.val:
                return mirror(root1.left,root2.right) and mirror(root1.right,root2.left)
            return False
        if not root:return True
        return mirror(root,root)

栈迭代法

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:return True
        stack1=[root]
        stack2=[root]
        while stack1 and stack2:
            node1=stack1.pop()
            node2=stack2.pop()
            if not node1 and not node2:
                continue
            if not node1 or not node2:
                return False
            if node1.val!=node2.val:
                return False
            else:
                stack1.extend([node1.left,node1.right])
                stack2.extend([node2.right,node2.left])
        return True

面试题29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:return []
        m=len(matrix)
        n=len(matrix[0])  
        i,j=0,-1
        dire=1
        ans=[]
        while m>0 and n>0:
            for x in range(n):
                j+=dire
                ans.append(matrix[i][j])
            for y in range(m-1):
                i+=dire
                ans.append(matrix[i][j])
            dire*=-1
            m-=1
            n-=1
        return ans

面试题30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

其实就是单调栈，这里没有不合法数据，所以就没有处理异常（空pop这种情况）

class MinStack:
    def __init__(self):
        self.de=[]
        self.pe=[]
    def push(self, x: int) -> None:
        self.de.append(x)
        if self.pe:
            if x<=self.pe[-1]:
                self.pe.append(x)
        else:
            self.pe.append(x)
    def pop(self) -> None:
        temp=self.de.pop()
        if temp==self.pe[-1]:
            self.pe.pop()
    def top(self) -> int:
        return self.de[-1]
    def min(self) -> int:
        return self.pe[-1]

面试题31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列

算法1: 暴力，弹出某数（2）时，向前看（4,3,5,1），比他小的数（1）一定在比他大的数（4,3,5）的前面，否则就是错误的。
#card=math&code=O%28N%5E2%29)

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        n=len(pushed)
        if n<3:return True
        popped=[pushed.index(x)+1 for x in popped]
        for index,value1 in enumerate(popped):
            if index<2:continue
            flag=1
            for i,value2 in enumerate(popped[:index]):
                if flag and value2>value1:
                    flag=0
                    continue
                if not flag and value2<value1:return False
        return True

算法2：模拟栈的推出 。
#card=math&code=O%28N%29)

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack=[]
        for value in popped[::-1]:
            stack.append(value)
            while stack and stack[-1]==pushed[-1]:
                pushed.pop()
                stack.pop()
        return False if pushed else True

面试题32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:return []
        de=deque([root])
        ans=[]
        while de :
            node=de.popleft()
            ans.append(node.val)
            if node.left:
                de.append(node.left)
            if node.right:
                de.append(node.right)
        return ans

面试题32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:return []
        de=deque([root])
        ans=[]
        while de:
            temp=[]
            new_q=[]
            for node in de:
                temp.append(node.val)
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right)
            ans.append(temp)
            de=new_q
        return ans

面试题32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:return []
        de=deque([root])
        ans=[]
        count=1         
        while de:
            new_q=[]
            temp=[]
            for node in de:
                temp.append(node.val)
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right)
            if count&1:
                ans.append(temp)
            else:
                ans.append(temp[::-1])
            de=new_q
            count+=1
        return ans

面试题33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if not postorder or len(postorder)==1:return True
        node=postorder[-1]
        flag=0
        position=0
        for index,value in enumerate(postorder):
            if value>node and not flag:
                flag=1
                position=index
                continue
            if flag and value<node:return False
        return self.verifyPostorder(postorder[:position]) and self.verifyPostorder(postorder[position:-1])

面试题34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

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

面试题35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

递归

class Solution:
    def __init__(self):
        self.visited={}
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return 
        if head in self.visited:
            return self.visited[head]
        node=Node(head.val,None,None)
        self.visited[head]=node
        node.next=self.copyRandomList(head.next)
        node.random=self.copyRandomList(head.random)
        return node

面试题37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

解题思路：

前序遍历，递归，因为前序遍历，生成序列的第一个值是root的值，方便重建
后续遍历和前序的方向相反，也可以重建树
只有，中序遍历的时候，不能重建树，因为无法确定总根的位置，每次的子树都找不到总根，因此需要前序和后序作为找根节点的辅助。

class Codec:
    def serialize(self, root):
        if not root:
            return [None]
        ans = [root.val] + self.serialize(root.left) + self.serialize(root.right)
        return ans
    def deserialize(self, data):
        if data is None:return None
        num = data.pop(0)
        if num is not None:
            root = TreeNode(num)
            root.left = self.deserialize(data)
            root.right = self.deserialize(data)
        else:
            return None   
        return root

面试题38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

class Solution:
    def permutation(self, s: str) -> List[str]:
        ans=[]
        ansset=set()
        s=list(s)
        def dfs(left,temp):
            n=len(left)   
            if n==0:
                if temp not in ansset:
                    ans.append(temp[:])
                    ansset.add(temp[:])
                    return
            for i in range(n):
                copy=left.pop(i)
                new_temp=temp+copy
                dfs(left,(new_temp)[:])
                left.insert(i,copy)
        dfs(s,"")
        return ans

全排列另附模板在其他文件

面试题39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import Counter
        a=Counter(nums)
        for key,value in a.items():
            if value>len(nums)//2:
                return key

面试题40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        import heapq
        ans=[]
        for value in arr:
            if len(ans)<k:
                heapq.heappush(ans,-value)
            else:
                heapq.heappushpop(ans,-value)
        return list(map(lambda x:-x ,ans))

面试题41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

class MedianFinder:
    import heapq
    def __init__(self):
        self.big=[]
        self.small=[]
    def addNum(self, num: int) -> None:
        if len(self.big)==len(self.small):
            heapq.heappush(self.small,-heapq.heappushpop(self.big,-num))
        else:
            heapq.heappush(self.big,-heapq.heappushpop(self.small,num))
    def findMedian(self) -> float:
        if len(self.big)==len(self.small):
            return (-self.big[0]+self.small[0])/2.0
        else:
            return self.small[0]

面试题42. 连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

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

面试题46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法

class Solution:
    def translateNum(self, num: int) -> int:
        temp="0"+str(num)
        n=len(str(temp))
        dp=[0 for _ in range(n)]
        dp[0],dp[1]=1,1
        for i in range(2,n):
            if int(str(temp)[i-1:i+1])<26  and str(temp)[i-1]!='0':
                dp[i]=dp[i-1]+dp[i-2]
            else:
                dp[i]=dp[i-1]
        return dp[-1]

面试题47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

第一反应是bfs，但是第1.1反应就是dp了

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

面试题48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start=0
        width=1
        n=len(s)
        if not s:return 0

        for i in range(1,n):
            if len(s[start:start+width+1])!=len(set(s[start:start+width+1])):
                start+=1
            else:
                width+=1
        return width

面试题49. 丑数

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

算法：三指针动态规划

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp=[1 for _ in range(n)]
        i2,i3,i5=0,0,0
        for i in range(1,n):
            min_val=min([ dp[i2]*2,dp[i3]*3,dp[i5]*5 ])
            dp[i]=min_val
            if dp[i2]*2==min_val:
                i2+=1
            if dp[i3]*3==min_val:
                i3+=1
            if dp[i5]*5==min_val:
                i5+=1
        return dp[-1]

面试题50. 第一个只出现一次的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

如果当前字符流没有存在出现一次的字符，返回“ ”。

class Solution:
    def firstUniqChar(self, s: str) -> str:
        from collections import Counter
        a=Counter(s)
        for value in s:
            if a[value]==1:
                return value
        return " "

面试题52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

算法：我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

太6了，理解： 两个链表长度分别为L1+C、L2+C， C为公共部分的长度，按照楼主的做法： 第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node1,node2=headA,headB

        while node1!=node2:
            node1= node1.next if node1 else headB
            node2= node2.next if node2 else headA

        return node1

node1 = node1.next if node1 else headB

而不是

node1 = node1.next if node1.next else headB

可以理解为两条链表最后都指向了同一个 null （None）节点，代替了不相交的特殊情况。 非常的巧妙。假设链表A长度是m，链表B是n，公共部分是b，那么走过m+n+b步之后一定会相遇，返回结果。 如果没有公共部分，b=0， 那么走过m+n都指向None，返回None

面试题53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

二分查找的练习：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:return 0

        l, r = 0, len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        if l== len(nums) or nums[l] != target:
            return 0
        lower = l

        l, r = 0, len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid
        upper = r
        return upper - lower

面试题53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        temp=-1
        for num in nums:
            if num!=temp+1:
                return temp+1
            temp=num
        return len(nums)

二分：找value>id 的下界(value=id 的上界，即value<=id 的上界)

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

面试题54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

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

面试题55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        self.level=0
        def dfs(root,level):
            if not root:
                self.level=max(self.level,level)
                return
            dfs(root.left,level+1)
            dfs(root.right,level+1)
        dfs(root,0)
        return self.level

面试题55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        self.flag=1
        def dfs(root):
            if not root:
                return 0
            left_level=dfs(root.left)
            right_level=dfs(root.right)
            if abs(left_level-right_level)>1:
                self.flag=0
            return max(left_level,right_level)+1
        dfs(root)
        return bool(self.flag)

面试题56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        all_xor = 0
        for num in nums:
            all_xor ^= num
        mask = 1
        while mask & all_xor == 0:  # 找到all_xor中的1某个位置，这里为右数第一个位置（哪个都可以）
            mask = mask << 1
        a = 0
        for num in nums:
            if mask & num != 0:  # 该位置为1才进行亦或
                a ^= num
        return [a, all_xor ^ a]

面试题56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one,two=0,0 # means 3N+1,3N+2 on each bit
        for num in nums:
            one = one^num & ~two #if two=0,then become 1,
                                 #if two=1,then become three, so one still 0
            two = two^num & ~one #if one=0,then become 0,else become 1 
        return one # means 3N+1

链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        fast=slow=pHead
        flag=0
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                flag=1
                break
        if flag:
            arr=set()
            while pHead:
                arr.add(pHead)
                pHead=pHead.next
                if pHead in arr:
                    return pHead
        else:
            return slow.next

删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or not pHead.next:return pHead
        dummy=ListNode(-1)
        dummy.next=pHead
        fast=dummy.next
        slow=dummy
        while fast:
            if fast.next and fast.next.val==fast.val:
                temp=fast.val
                while fast and fast.val==temp:
                    fast=fast.next
            else:
                slow.next=fast
                slow=fast
                fast=fast.next
        slow.next = fast
        return dummy.next

用计数可能理解起来会好点，但是毕竟开了新空间。

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        temp = []
        head = pHead
        while head:
            temp.append(head.val)
            head = head.next
        res = ListNode(None)
        head = res
        for i in temp:
            if temp.count(i) == 1:
                head.next = ListNode(i)
                head = head.next
        return res.next

面试题57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

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

面试题58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

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

面试题58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        l = len(s)
        res = ''
        for i in range(n, n + l):
            res += s[i % l]
        return res

面试题59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

暴力法：过了。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        start,end =0,k
        ans=[]
        n=len(nums)
        if n==0:return []
        for i in range(n-k+1):
            ans.append(max(nums[start+i:end+i]))
        return ans

双端队列 & 单调队列：存的是index

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

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

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

from collections import deque
class MaxQueue:
    def __init__(self):
        self.de=deque()
        self.pe=deque()

    def max_value(self) -> int:       
        return self.pe[0] if len(self.de) else -1

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

    def pop_front(self) -> int:
        if not self.de:return -1
        ans=self.de.popleft()
        if ans== self.pe[0]:
            self.pe.popleft()
        return ans

面试题60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

class Solution:
    def twoSum(self, n: int) -> List[float]:
        dp=[[0]*(6*n+1) for _ in range(n)]
        for i in range(1,7):
            dp[0][i]=1
        for i in range(1,n):
            for j in range(6*n+1):
                dp[i][j]=sum([dp[i-1][j-k] for k in range(1,7) if j-k>=0])
        for i in range(n):
            for j in range(6*n+1):
                dp[i][j]/= 6**n
        return dp[n-1][n:]

面试题61. 扑克牌中的顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

不用考虑，10JQKA

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        nums.sort()
        count=nums.count(0)
        if len(set(nums[count:]))!=5-count:return False
        for num in nums:
            if num==0:continue
            temp=num
            break
        for num in range(temp+1,temp+5):
            if num in nums:continue
            elif count:
                count-=1
            else:
                return False
        return True

面试题62. 圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

推导过程：

记
#card=math&code=f%28k%2Cp%29)

起始点的定义如列表

设已知
#card=math&code=f%28k-1%2C0%29)#card=math&code=f%28k%2C0%29)

要从
#card=math&code=f%28k-1%29)#card=math&code=f%28k%29)

如

要变成

则

刚好就是

所以：

%3Df(k%2Cn-m)#card=math&code=f%28k-1%2C0%29%3Df%28k%2Cn-m%29)

我们知道
#card=math&code=f%28k%2C0%29)#card=math&code=f%28k%2Cn-m%29)

%3D%5Bf(k%2Cn-m)%2Bn-m%5D%20%5Cmod%20%20n%20%3D%5Bf(k-1%2C0)-m%5D%20%5Cmod%20n#card=math&code=f%28k%2C0%29%3D%5Bf%28k%2Cn-m%29%2Bn-m%5D%20%5Cmod%20%20n%20%3D%5Bf%28k-1%2C0%29-m%5D%20%5Cmod%20n)

由
%3D0#card=math&code=f%281%2C0%29%3D0)

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

面试题63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:return 0
        ans=0
        temp=prices[0]
        for i in range(1,len(prices)):
            if prices[i]>temp:
                ans =max(ans, prices[i]-temp)
            else:
                temp =prices[i]
        return ans

面试题64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

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

面试题65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

无进制和 a^b 进制位 a&b <<1

第一步转换无符号整数，每次进制位也要转换

答案再映射回有符号整数 ~(a^0xFFFFFFFF)，界限是0x80000000

class Solution:
    def add(self, a: int, b: int) -> int:
        a &= 0xFFFFFFFF
        b &= 0xFFFFFFFF
        while b:
            ans = a^b
            carry = (a&b)<<1  & 0xFFFFFFFF
            a=ans
            b=carry
        return a if a < 0x80000000 else ~(a^0xFFFFFFFF)

这题建议使用C++

class Solution {
public:
    int getSum(int a, int b) {
        while( b != 0){
            int temp = a ^ b;
            b = ((unsigned int)(a & b) << 1);
            a = temp;
        }
        return a;
    }
};

或者java，可以把面试官秀傻了

class Solution {
    public int getSum(int a, int b) {
            while (b != 0) {
            int temp = a ^ b;
            int carry = (a & b) << 1;
            a = temp;
            b = carry;
        }
        return a;
    }
}

面试题66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        if not a:
            return []
        prefix = [1]*len(a)
        prefix[0]=1
        for i in range(1,len(a)):
            prefix[i] = prefix[i-1]*a[i-1]
        cur_suffix = 1
        for i in range(len(a)-1,-1,-1):
            prefix[i] = prefix[i] * cur_suffix
            cur_suffix *= a[i]
        return prefix

面试题67. 把字符串转换成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

class Solution:
    def strToInt(self, str: str) -> int:
        a=str.strip()
        if not a:return 0
        INT_MAX = 2**31-1
        INT_MIN = -2147483648
        self.temp=len(a)
        for index,value in enumerate(a):
            if index==0:
                if value=="-"or value=="+" or value.isdigit():
                    continue
                else:
                    return 0
            else:
                if value.isdigit():
                    continue
                else:
                    self.temp=index
                    break
        try :
            ans=int(a[:self.temp])
        except:
            return 0
        if ans >INT_MAX:return INT_MAX
        if ans<INT_MIN:return INT_MIN
        return ans

正则表达式：

class Solution:
    def myAtoi(self, str: str) -> int:
        ans = re.findall(r'^[+-]?[0-9]+[0-9]*',str.strip())
        if not ans:return 0
        ans=int(ans[0])
        if ans>2**31-1:return 2**31-1
        if ans<-2**31:return -2**31
        return ans

面试题68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

利用BST的性质：

迭代法：

class Solution:
    def lowestCommonAncestor(self, root, p: , q) :
        while root:
            if p.val>root.val and q.val>root.val:
                root=root.right
            elif p.val<root.val and q.val<root.val:
                root=root.left
            else:
                return root
        return root

递归：

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if p.val>root.val and q.val>root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        if p.val<root.val and q.val<root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        else:
            return root

面试题68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

找到两个路径，再求就行了

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        self.list1=[]
        self.list2=[]
        def dfs(root,node,listp,i):
            if not root:return 
            listp.append(root)
            if root.val!=node.val:
                dfs(root.left,node,listp,i)
                dfs(root.right,node,listp,i)
                listp.pop()
            else:
                if i:self.list2=listp[:]
                else:self.list1=listp[:]
                return
        dfs(root,p,[],0)
        dfs(root,q,[],1)
        ans=self.list1[0]
        for node1,node2 in zip(self.list1,self.list2):          
            if node1.val==node2.val:ans=node1
            else:return ans
        return ans