近期Leetcode题解

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

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        """
        对于305295这个数而言
        我们假设从百位开始算，百位前面305计为a,百位后面95计为b，百位数等于n%100，100计为base
        当百位数大于1的时候
            百位数的前半段可以取值为0～305，一共有a+1个数，后半段可以取0～99，一共有base个数
            则百位上1能取到的个数是(a+1)*base个数
        对于305195这个数而言
        当百位数等于1的时候，分两种情况
            1.百位数的前半段可以取值为0～304，一共有a个数，后半段可以取0～99，一共有base个数。
            2.百位数的前半段可以取值为305，一共有1个数，后半段可以取0～95，一共有b+1个数。
            则百位上1能取到的个数是(a*base+1*(b+1))个数
        对于305095这个数而言
        当百位数小于1的时候
            百位数的前半段可以取值为0～304，一共有a个数，后半段可以取0～99，一共有base个数
            则百位上1能取到的个数是(a*base)个数
        之后while循环分三种情况统计每一位上1的个数即可
        """
        base = 1
        res = 0
        while base <= n:
            b = n % base
            a = n // base
            cur = a % 10
            a //= 10
            if cur > 1:
                res += (a + 1) * base
            elif cur == 1:
                res += (a * base + b + 1)
            else:
                res += a * base
            base *= 10
        return res

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

class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        """
        通过不断地插入值来寻找前面大于当前值的元素个数
        """
        res = 0 #统计计数
        sorted_nums = [] #准备一个待插入的列表
        for i in range(len(nums)):
            #找到nums中当前数在sorted_nums中要插入的下标
            k = bisect.bisect(sorted_nums, nums[i]) 
            #当前下标减去要插入的下标就是在大于当前数的个数
            res += i - k
            sorted_nums[k:k] = [nums[i]] #插入当前元素
            # bisect.insort(sorted_nums,nums[i]) #插入当前元素
        return res

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

#import numpy as np
class Solution(object):
    def dicesProbability(self, n):
        """
        :type n: int
        :rtype: List[float]
        """
        #卷积做法
        # conv1 = [1.0/6 for i in range(6)]
        # if n==1:
        #     return conv1
        # else:
        #     convN = self.dicesProbability(n-1)
        #     return np.convolve(convN,conv1)

        #动态规划
        dp = [1.0/6 for _ in range(6)] #骰子数为1时候的值
        for i in range(2,n+1):
            #tmp长度为n个骰子能取到的值的个数，全部初始化为0
            tmp = [0 for _ in range(i*5+1)]

            for j in range(len(dp)): #n-1个骰子取到的所有值
                for k in range(6): #加上第n个骰子取得的值
                    tmp[j+k] += dp[j]/6.0 #之前的值和当前的值叠加
            dp = tmp #得到最新的值赋值给dp
        return dp

剑指 Offer 12. 矩阵中的路径(medium)

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        def dfs(board,i,j,word,k):
            #判断下标是否越界
            if i<0 or i == len(board) or j < 0 or j == len(board[0]):
                return False
            #如果当前值和word当前值不相等，直接返回
            if board[i][j] != word[k]:
                return False
            #如果访问到了word最后一个值，返回True
            if k == len(word)-1:
                return True
            #先将当前值置空，防止后面重复访问
            board[i][j] = ''
            res = dfs(board, i-1, j, word, k+1) or dfs(board, i, j-1, word, k+1) \
            or dfs(board, i+1, j, word, k+1) or dfs(board, i, j+1, word, k+1)
            board[i][j] = word[k]
            return res
        for i in range(len(board)):
            for j in range(len(board[i])):
                if dfs(board,i,j,word,0):
                    return True
        return False

剑指 Offer 41. 数据流中的中位数(hard)

from heapq import *
class MedianFinder(object):

    # 菜鸡的数组排序做法
    # def __init__(self):
    #     """
    #     initialize your data structure here.
    #     """
    #     self.res=[]


    # def addNum(self, num):
    #     """
    #     :type num: int
    #     :rtype: None
    #     """
    #     self.res.append(num)


    # def findMedian(self):
    #     """
    #     :rtype: float
    #     """
    #     self.res=sorted(self.res)
    #     if len(self.res)%2:
    #         return self.res[len(self.res)/2]
    #     else:
    #         return (self.res[len(self.res)/2-1]+self.res[len(self.res)/2])/2.0

    #大佬的堆解法
    def __init__(self):
        #heapq默认小顶堆
        self.A = [] # 小顶堆，保存较大的一半
        #实现大顶堆进堆的时候取相反数
        self.B = [] # 大顶堆，保存较小的一半

    def addNum(self, num):
        # 如果不相等，说明A多了一个
        # 把当前数存到A，调整堆之后，返回A中的最小值给B
        if len(self.A) != len(self.B):
            heappush(self.B, -heappushpop(self.A, num))
        # 如果相等，就把当前数给B，调整堆之后，返回B中的最大值给A
        else:
            heappush(self.A, -heappushpop(self.B, -num))


    def findMedian(self):
        # 如果是奇数，直接返回A中的最小值
        # 如果是偶数，则返回两者堆顶的平均值
        # print(self.A)
        # print(self.B)
        return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0

            

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

剑指 Offer 13. 机器人的运动范围(medium)

class Solution(object):
    def movingCount(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """
        def dfs(i,j,k):
            if not 0<= i <m or not 0<= j <n or (i,j) in a or (i%10+i//10+j%10+j//10)>k: return 0
            #把这个点加入到访问集合中
            a.add((i,j))
            #因为从（0,0）开始，所以只要向下走或向右走就行
            dfs(i+1,j,k)
            dfs(i,j+1,k) 
        a = set()
        dfs(0,0,k)
        return len(a)

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

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 10:
            return n
        i = 0
        num = 0
        temp=0
        """
        如果n大于9的话，判断n应该在哪个区间
        因为1位数一共有9个
        2位数有90*2=180个
        3位数有900*3=2700个
        因此我们可以知道n位数有9*(10**(i-1)*i)个
        """
        while n>num:
            temp = num #temp保存上一个num的数
            addnum = 9*(10**i)*(i+1)
            num+=addnum
            i+=1
        res = n-temp #减去区间之前的那些数
        """
        此时得到的i如果是3，则说明从三位数开始
        可以得到区间在100-1000之间
        从而算得起始的数是10**(3-1)=100
        """
        start_num = 10**(i-1)
        """
        因为在这个区间每一个数都是i位，因此我们得到除数div
        对于三位数来讲，如果除数div=10，则可以得到数字是在100+10-1=109附近
        """
        div = res / i
        mod = res % i
        new_num = start_num + div - 1 #这个数字就是区间内加上除数之后的数字
        """
        进一步通过余数判断，如果余数为0，则说明当前得到的数字的最后一个数字就是结果
        如果余数不为0，则说明最终结果在下一个数字，从而根据余数得到最终结果
        """
        if mod == 0:
            return int(str(new_num)[-1])
        else:
            return int(str(new_num+1)[mod - i - 1])

        #第一种方法，超时了
        # s=0
        # for i in range(n+1):
        #     s+=len(str(i))
        #     if s>=n+1:
        #         return int(str(i)[n-temp])

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

class Solution(object):
    def verifyPostorder(self, postorder):
        """
        :type postorder: List[int]
        :rtype: bool
        """
        if len(postorder) == 1 or (not postorder):
            return True
        root = postorder[-1] #后序遍历最后一个值为根结点
        for i in range(len(postorder)): #找到根节点右子树的第一个值
            if postorder[i]>=root:
                break
        left = postorder[:i] #划分左子树
        right = postorder[i:len(postorder)-1] #划分右子树
        for i in left: #如果左子树中有小于根的，直接return 
            if i>root:
                return False
        for i in right: #如果右子树中有小于根的，直接return 
            if i<root:
                return False
        left = self.verifyPostorder(left) #递归判断左子树
        right = self.verifyPostorder(right) #递归判断右子树
        if left and right:
            return True
        return False

剑指 Offer 16. 数值的整数次方(medium)

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n==0:
            return 1
        if n < 0:
            return 1/x * self.myPow(1/x,-n-1) 
        if n%2:
            return x * self.myPow(x*x,n/2)
        if not n%2:
            return self.myPow(x*x,n/2)

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

class Solution(object):
    def strToInt(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = list(str.lstrip())  # 去掉开头多余的空格
        num = ['0', '1','2', '3', '4', '5', '6', '7', '8', '9']
        if len(str)==0:
            return 0
        if len(str)==1:
            if str[0] in num:
                return int(str[0])
            else:
                return 0
        res = 0
        i = 0
        while i < len(str):
            if str[i] != "-" and str[i] != "+" and str[i] not in num:
                return 0
            elif str[i] == '-' or str[i] == '+': #处理以‘-’和‘+’开头的
                temp=str[i] #保存‘+-’符号
                i += 1
                if str[i] not in num:
                    return 0
                else:
                    while i < len(str):
                        if str[i] in num:
                            res *= 10
                            res += int(str[i])
                            i += 1
                        else: #如果第i个字符不是数字直接退出
                            break
                    if temp == '-':
                        if res>pow(2,31):
                            return -pow(2,31)
                        return -res
                    else:
                        if res>pow(2,31)-1:
                            return pow(2,31)-1
                        return res
            elif str[i] in num: #处理以字母开头的
                while i < len(str):
                        if str[i] in num:
                            res *= 10
                            res += int(str[i])
                            i += 1
                        else:
                            break
                if res>pow(2,31)-1:
                    return pow(2,31)-1
                else:
                    return res

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

class Solution(object):
    def translateNum(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num < 10:
            return 1
        elif num%100<10 or num%100>25:
            return self.translateNum(num/10)
        else:
            return (self.translateNum(num/10)+self.translateNum(num/100))

剑指 Offer 14- II. 剪绳子 II(medium)

class Solution(object):
    def cuttingRope(self, n):
        """
        :type n: int
        :rtype: int
        """
        """
        尽可能分成长度为3的
        """
        if n<=3:
            return n-1
        res = 1
        while n>4:
            res*=3
            n-=3
        return (res*n)% 1000000007

剑指 Offer 66. 构建乘积数组(medium)

class Solution(object):
    def constructArr(self, a):
        """
        :type a: List[int]
        :rtype: List[int]
        """
        """
        从前向后累乘一次并保存结果，从后向前累乘一次并保存结果
        就[1,2,3,4,5]而言
        """
        if len(a)==0:
            return []
        res1 = [] 
        res2 = []
        result = []
        m = 1
        n = 1
        for i in a[:-1]: #从前向后乘只计算到倒数第二个数
            m*=i
            res1.append(m) #res1中保存[1,1*2,1*2*3,1*2*3*4]
        for i in a[::-1][:-1]: #从后向前乘只计算到第二个数
            n*=i
            res2.append(n) #res2中保存[5,5*4,5*4*3,5*4*3*2]
        res2 = res2[::-1] #反转后得[5*4*3*2,5*4*3,5*4,5]
        """
        此时res1 = [1,1*2,1*2*3,1*2*3*4]
            res2 = [5*4*3*2,5*4*3,5*4,5]
        我们可以得到当缺失第一个数时，值为res2[0]
        当缺失最后一个数时，值为res1[-1]
        从缺失第二个数到倒数第二个数
        我们可以得到值为res[i]*res[i-1]
        """
        for i in range(len(res2)+1):
            if i == 0:
                result.append(res2[0])
            elif i == len(res2):
                result.append(res1[-1])
            else:
                result.append(res2[i]*res1[i-1])
        return result

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

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_num=0 #记录当前股票最大差值
        if len(prices)==0:
            return 0
        min_num=prices[0] #将第一天的股票作为最小的值
        for i in range(1,len(prices)):
            min_num = min(min_num,prices[i-1]) #判断当天和当前最小值中的最小值
            if prices[i]-min_num>max_num: #如果当天的股票减去之前的股票最小值大于最大差值
                max_num = prices[i]-min_num #则替换最大差值
        return max_num

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

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution(object):
    head = None
    tail = None
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if root == None:
            return None
        self.pre(root) #中序遍历
        self.head.left = self.tail #头节点前驱指向尾节点
        self.tail.right = self.head #尾节点后驱指向头节点
        return self.head
    
    def pre(self,root):
        if root == None:
            return
        self.pre(root.left)
        if(self.head == None):
            self.head = self.tail = root
        else:
            self.tail.right = root
            root.left = self.tail
            self.tail = root
        self.pre(root.right)

剑指 Offer 31. 栈的压入、弹出序列(medium)

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        s = [] #初始化一个栈
        for i in popped:
            #得到每一个pop出去的数字在push数组中的下标
            #加一为了方便后续对s栈进行插入操作，即这里res-1才是真正的下标
            res = pushed.index(i)+1
            #如果当前pop出去的数在push数组的下标大于s栈的长度
            #则需要将下标数字之前的数字都写入s栈中
            if res > len(s):
                for k in range(len(s),res):
                    s.append(k)
                #这一步对pop出去的下标置为-1
                s[res-1] = -1
            #如果当前pop出去的数在push数组的下标小于s栈的长度
            #则我们只需要判断在s栈中对于res下标之后的数值是否为-1即可
            elif res < len(s):
                for j in range(res,len(s)):
                    #如果在res下标之后存在不为-1的下标，则直接返回false
                    if s[j] != -1:
                        return False 
                #如果res下标之后存在s栈中的都是-1
                #则对当前下标进行置为-1操作
                s[res-1] = -1
        #循环结束的话返回True
        return True

剑指 Offer 35. 复杂链表的复制(medium)

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head == None:
            return None
        d = {}
        node = head #保留头节点不改变
        while(node): #先用字典单独复制每一个节点信息
            d[node] = Node(node.val)
            node = node.next
        node = head #保留头节点不改变
        while(node): #链接每一个单节点
            d[node].next = d.get(node.next)
            d[node].random = d.get(node.random)
            node = node.next
        return d[head]

剑指 Offer 07. 重建二叉树(medium)

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

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:
            return None
        root = TreeNode(preorder[0]) #将前序遍历第一个值作为根节点
        index = inorder.index(preorder[0]) #找到根节点再中序遍历中的位置
        root.left = self.buildTree(preorder[1:1+index],inorder[:index]) #递归构建左子树
        root.right = self.buildTree(preorder[1+index:],inorder[index+1:]) #递归构建右子树
        return root

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

class Solution(object):
    def minNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        """
        思路分析
        依次比较nums中的数字，将尽可能组合起来小的数放在res数组的前面
        """
        #先准备一个空的数组，用来存数组
        res = []
        flag = 0
        for i in nums:
            #如果res为空，那么直接添加当前数
            if not res:
                res.append(i)
                continue
            #如果res不为空，则从nums的当前数与res中的每一个数组合起来进行比较
            for j in range(len(res)):
                flag = 0
                """
                分别将当前数字和res中的每一个数字组合进行比较
                例如nums当前数是30，res中的当前数是3
                我们会得到两个组合，分别是303和330
                将这两个数进行比较，发现303会小一些，所以我们将3放在30后面
                在res数组中表现为继续向后比较
                """
                s1 = str(res[j]) + str(i)
                s2 = str(i) + str(res[j])
                if int(s1) < int(s2):
                    continue #继续向后比较
                else:
                    #如果nums中的数放在res[j]之前会使得值更小一些
                    #那么我们就把nums中的当前数插入到res[j]之前这个位置
                    res[j:j] = [i]
                    #flag=1说明已经nums中的值已经插入到res中了，不需要再比较了
                    #直接退出res循环
                    flag = 1
                    break
            if flag:
                continue
            #如果flag=0说明res已经遍历结束
            #这个时候只需要将nums当前值插入到res后面即可
            else:
                res.append(i)

        s = ""
        for i in res:
            s += str(i)
        return s

剑指 Offer 37. 序列化二叉树(hard)

# 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 __init__(self):
        self.strTree=[]

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            self.strTree.append("null")
            return self.strTree
        curStr = str(root.val)
        self.strTree.append(curStr)
        self.serialize(root.left)
        self.serialize(root.right)
        return self.strTree
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if len(data) == 1 and data[0] == "null":
            return None
        Tval = data.pop(0)
        if Tval == "null":
            return None
        root = TreeNode(Tval)
        root.left = self.deserialize(data)
        root.right = self.deserialize(data)
        return root
        

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