LeetCode 每日一题 2024/1/29-2024/2/4

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

1/29 514. 自由之路

key中每一个字符都需要按一次 即m=len(key)
该值固定可以 最后加上即可
假设状态(i,j)为当前ring[i],key[j]
当两值相等时可以变换到(i,j+1)
否则左移 ((i-1+n)%n,j)
右移((i+1)%n,j)
从(0,0) 到(i,m)最短路径即为答案

def findRotateSteps(ring, key):
    """
    :type ring: str
    :type key: str
    :rtype: int
    """
    n,m=len(ring),len(key)
    mem = [[False]*(m+1) for _ in range(n)]
    mem[0][0]=True
    l = [(0,0)]
    step = 0
    while True:
        tmp = []
        for i,j in l:
            if j==m:
                return step
            if ring[i]==key[j]:
                if not mem[i][j+1]:
                    mem[i][j+1]=True
                    tmp.append((i,j+1))
                continue
            for nxt in [(i-1)%n,(i+1)%n]:
                if not mem[nxt][j]:
                    mem[nxt][j]=True
                    tmp.append((nxt,j))
        step+=1

1/30 2808. 使循环数组所有元素相等的最少秒数

可以选择将每一位置的数变为左右两侧的数
对每一个数值x记录其依次出现的位置
如果要将所有数变为x
需要的最少次数为两个x的最远距离除以二

def minimumSeconds(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    from collections import defaultdict
    m = defaultdict(list)
    n = len(nums)
    ans = n
    for i,v in enumerate(nums):
        m[v].append(i)
    for pos in m.values():
        mx = pos[0]+n-pos[-1]
        for i in range(len(pos)):
            mx = max(mx,pos[i]-pos[i-1])
        ans = min(ans,mx//2)
    return ans

1/31 2670. 找出不同元素数目差数组

从前到后判断有多少不同数目
从后往前同样判断一次

def distinctDifferenceArray(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    n = len(nums)
    ans = [0]*n
    m = {
   }
    for i,v in enumerate(nums):
        m[v]=1
        ans[i]=len(m)
    m={
   }
    for i in range(n-1,-1,-1):
        ans[i]-=len(m)
        m[nums[i]]=1
    return ans

2/1 LCP 24. 数字游戏

可以看做将nums[j]-j变成相同的数字
使用两个堆来存放数值
low用来存放小的 up用来存放大的
lows,ups分别为数值和
考虑每一个数 保持up中的数个数不多于low

def numsGame(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    import heapq
    n=len(nums)
    ans = [0]*n
    low,up=[],[]
    lows,ups=0,0
    mod = 10**9+7
    for i in range(n):
        x = nums[i]-i
        if len(low)==0 or -low[0]>=x:
            lows+=x
            heapq.heappush(low,-x)
            if len(low)>len(up)+1:
                ups -=low[0]
                heapq.heappush(up,-low[0])
                lows += heapq.heappop(low)
        else:
            ups+=x
            heapq.heappush(up,x)
            if len(low)<len(up):
                lows += up[0]
                heapq.heappush(low,-up[0])
                ups -= heapq.heappop(up)
        if (i+1)%2==0:
            ans[i] = (ups-lows)%mod
        else:
            ans[i]=(ups-lows-low[0])%mod
    return ans
        

2/2 1686. 石子游戏 VI

如果有两个石子i,j
alice价值 ia,ja
bob价值 ib,jb
两种情况 alice取i 或取j
差值为 ia-jb-(ja-ib) = ia+ib -(ja+jb)
如果大于0则alice先选i 优先选 ia+ib大的石头
将石头两个人的价值相加后倒序排列 两人依次选取

def stoneGameVI(aliceValues, bobValues):
    """
    :type aliceValues: List[int]
    :type bobValues: List[int]
    :rtype: int
    """
    v = [[a+b,a,b] for a,b in zip(aliceValues,bobValues)]
    v.sort(reverse=True)
    asum = sum(value[1] for value in v[::2])
    bsum = sum(value[2] for value in v[1::2])
    if asum>bsum:
        return 1
    elif asum==bsum:
        return 0
    else:
        return -1

2/3 1690. 石子游戏 VII

动态规划
先求出区间[i,i]的最大的得分差值
向外扩展 直至扩展到区间[0,n-1]

def stoneGameVII(stones):
    """
    :type stones: List[int]
    :rtype: int
    """
    n=len(stones)
    s = [0]*(n+1)
    dp=[[0]*n for _ in range(n)]
    for i in range(n):
        s[i+1] = s[i]+stones[i]
    for i in range(n-2,-1,-1):
        for j in range(i+1,n):
            dp[i][j] = max(s[j+1]-s[i+1]-dp[i+1][j],s[j]-s[i]-dp[i][j-1])
    return dp[0][n-1]
    

2/4 292. Nim 游戏

如果是4的倍数 先手必输 先手拿x个 后手拿4-x个 最后必定是后手拿到
否则 先手取若干个将其变成4的倍数 那么对手就变成了先手4的倍数

def canWinNim(n):
    """
    :type n: int
    :rtype: bool
    """
    return n%4!=0