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