LeetCode 每日一题 2021/8/30-2021/9/5

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

目录

• • • 8/30 528. Random Pick with Weight 按权重随机选择
    • 8/31 1109. Corporate Flight Bookings 航班预订统计
    • 9/1 165. Compare Version Numbers 比较版本号
    • 9/2 剑指 Offer 22. 链表中倒数第k个节点
    • 9/3 面试题 17.14. 最小K个数
    • 9/4 剑指 Offer 10- I. 斐波那契数列
    • 9/5

8/30 528. Random Pick with Weight 按权重随机选择

前缀和 二分查找对应位置

import random
class Solution(object):

    def __init__(self, w):
        """
        :type w: List[int]
        """
        self.n = len(w)
        self.l = [w[0]]
        for i in range(1,self.n):
            self.l.append(w[i]+self.l[i-1])


    def pickIndex(self):
        """
        :rtype: int
        """
        rd = random.randint(1,self.l[-1])
        l,r=0,self.n-1
        while l<=r:
            mid = (l+r)>>1
            if self.l[mid]>=rd:
                r = mid-1
            else:
                l = mid+1
        return l
  

           

8/31 1109. Corporate Flight Bookings 航班预订统计

差分数组 适合区域范围同增同减

diff[i] 记录res[i]-res[i-1]

当增加[x,y]内所有位置数值v时 res[x]+=v res[y+1]-=v

def corpFlightBookings(bookings, n):
    """
    :type bookings: List[List[int]]
    :type n: int
    :rtype: List[int]
    """
    diff=[0]*(n+1)
    
    for i,j,num in bookings:
        diff[i-1]+=num
        diff[j]-=num
        
    #还原差分数组
    res=[0]*(n)
    res[0]=diff[0]
    for i in range(1,n):
        res[i] = res[i-1]+diff[i]
    
    return res

           

9/1 165. Compare Version Numbers 比较版本号

根据.切分字符串 比较每一位大小 缺少的为0

def compareVersion(version1, version2):
    """
    :type version1: str
    :type version2: str
    :rtype: int
    """
    vl1 = version1.split(".")
    vl2 = version2.split(".")
    n = max(len(vl1),len(vl2))
    
    for i in range(n):
        v1,v2 = 0,0
        if i<len(vl1):
            v1 = int(vl1[i])
        if i<len(vl2):
            v2 = int(vl2[i])
        if v1<v2:
            return -1
        elif v1>v2:
            return 1
    return 0

           

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

双指针x,y x先移动k步

之后x,y同步往后移动

当x到达链表尾部时 y为倒数第k个节点

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def getKthFromEnd(head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """
    x = head
    y = head
    for _ in range(k):
        x = x.next       
    while x:
        x,y = x.next,y.next
    return y

           

9/3 面试题 17.14. 最小K个数

1.排序 取前k个数

2.大顶堆

先将k个数放入大顶堆 堆顶为k个数中最大的值

遍历后续 与堆顶值比较 如果小于堆顶值 将堆顶值换出

最后堆中剩余为最小的k个

python中heap为小顶堆 所以将数值取反

def smallestK(arr, k):
    """
    :type arr: List[int]
    :type k: int
    :rtype: List[int]
    """
    arr.sort()
    return arr[:k]

def smallestK2(arr, k):
    """
    :type arr: List[int]
    :type k: int
    :rtype: List[int]
    """
    ans = []
    if k==0:
        return ans
    import heapq
    hp = []
    for i in range(k):
        heapq.heappush(hp,-arr[i])
        
    for i in range(k,len(arr)):
        num = arr[i]
        hnum = hp[0]
        if -hnum>num:
            heapq.heapreplace(hp,-num)
    ans = [-x for x in hp]
    return ans
           

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

1.递归

dic用来存储已计算值

对于n 求出n-1,n-2

直至n<2 或者改情况已被考虑

2.迭代

从0开始 依次计算 直至n

def fib(n):
    """
    :type n: int
    :rtype: int
    """
    dic = {}
    if n<2:
        dic[n]=n
        return n
    else:
        if n-2 not in dic:
            dic[n-2] = fib(n-2)
        if n-1 not in dic:
            dic[n-1] = fib(n-1)
        
        return dic[n-1]+dic[n-2]
    
def fib2(n):
    """
    :type n: int
    :rtype: int
    """
    if n<2:
        return n
    pre,now=0,1
    for i in range(2,n+1):
        pre,now = now,pre+now
    return now
    

           

9/5