LeetCode 每日一题 2024/3/4-2024/3/10

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

3/4 232. 用栈实现队列

两个栈实现
一个为入栈 一个为出栈

class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.A,self.B=[],[]
        

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.A.append(x)
        

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        pk = self.peek()
        self.B.pop()
        return pk
        

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.B:
            return self.B[-1]
        if not self.A:
            return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B[-1]
        

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not self.A and not self.B

3/5 1976. 到达目的地的方案数

m[x][y]代表x,y之间的路径时间 如果没有直接路径则为无穷
dis[x]代表从0到x的路径长度
dijkstra 每次更新与邻居的最短路径 选最短的走
f[x]记录0到x点最短路径的条数

def countPaths(n, roads):
    """
    :type n: int
    :type roads: List[List[int]]
    :rtype: int
    """
    MOD = 10**9+7
    m= [[float("inf")*n] for _ in range(n)]
    for x,y,v in roads:
        m[x][y] = v
        m[y][x] = v
        
    dis=[float("inf")]*n
    dis[0]=0
    f=[0]*n
    f[0]=1
    done = [False]*n
    while True:
        x = -1
        for i,ok in enumerate(done):
            if not ok and (x<0 or dis[i]<dis[x]):
                x=i
        if x==n-1:
            return f[-1]
        done[x]=True
        dx=dis[x]
        for y,d in enumerate(m[x]):
            new = dx+d
            if new<dis[y]:
                dis[y]=new
                f[y]=f[x]
            elif new==dis[y]:
                f[y]=(f[y]+f[x])%MOD
            
        

3/6 2917. 找出数组中的 K-or 值

最多32位 枚举每一位情况

def findKOr(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    maxv = max(nums)
    ans = 0
    for i in range(32):
        if 1<<i>maxv:
            break
        cur = 0
        for num in nums:
            if num&(1<<i)>0:
                cur+=1
            if cur==k:
                ans +=(1<<i)
                break
    return ans

3/7 2575. 找出字符串的可整除数组

一次添加 增加一位 原数*10+新添加那一位的值

def divisibilityArray(word, m):
    """
    :type word: str
    :type m: int
    :rtype: List[int]
    """
    n = len(word)
    ans = [0]*n
    cur = 0
    for i,w in enumerate(word):
        cur = cur*10+int(w)
        if cur%m==0:
            ans[i]=1
        cur %=m
    return ans

3/8 2834. 找出美丽数组的最小和

为了不存在两个数相加=target 并且和尽量小
可以选1,2…target/2
从小到大选择 如果不够n个则继续添加target,target+1…

def minimumPossibleSum(n, target):
    """
    :type n: int
    :type target: int
    :rtype: int
    """
    MOD=10**9+7
    if target//2>=n:
        return (n*(n+1)/2)%MOD
    else:
        t = target//2
        ans = ((t*(t+1)/2)%MOD+(2*target+n-t-1)*(n-t)/2)%MOD
        return ans

3/9 2386. 找出数组的第 K 大和

最大的和为所有正数相加 s1
最大值情况为选取所有正数
对其进行减法
如果是正数则去除
如果是负数则加入
所以可以把所有数都取绝对值
将题目变为绝对值后数组第k个最小子序列和
二分找到limit值 使得不超过limit的元素和有k个
dfs对各个数值进行选择

def kSum(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    n=len(nums)
    s1 = 0
    s2 = 0
    for i in range(n):
        if nums[i]>=0:
            s1+=nums[i]
        else:
            nums[i]=-nums[i]
        s2+=nums[i]
    nums.sort()
    
    global cnt
    cnt = 0
    def dfs(i,t,limit):
        global cnt
        if i==n or cnt>=k-1 or t+nums[i]>limit:
            return
        cnt+=1
        dfs(i+1,t+nums[i],limit)
        dfs(i+1,t,limit)
    l,r = 0,s2
    while l<=r:
        mid=(l+r)//2
        cnt=0
        dfs(0,0,mid)
        if cnt>=k-1:
            r=mid-1
        else:
            l=mid+1
    return s1-l

3/10 299. 猜数字游戏

逐位比较
如果相同则公牛数+1
如果不同 则在两个map中分别记录字符出现次数
奶牛数即为每个字符在两个map中的较小值

def getHint(secret, guess):
    """
    :type secret: str
    :type guess: str
    :rtype: str
    """
    from collections import defaultdict
    n=len(secret)
    smap = defaultdict(int)
    gmap = defaultdict(int)
    bulls = 0
    for i in range(n):
        if secret[i]==guess[i]:
            bulls+=1
        else:
            smap[secret[i]] +=1
            gmap[guess[i]] +=1      
    cows = sum([min(smap[str(i)],gmap[str(i)]) for i in range(10)])
    ans = "{}A{}B".format(bulls,cows)
    return ans