LeetCode 每日一题 2023/6/5-2023/6/11

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

6/5 2460. 对数组执行操作

依次执行

def applyOperations(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    n = len(nums)
    for i in range(n-1):
        if nums[i]==nums[i+1]:
            nums[i]=2*nums[i]
            nums[i+1]=0
    ans = [0]*n
    loc = 0
    for i in range(n):
        if nums[i]>0:
            ans[loc]=nums[i]
            loc+=1
    return ans

6/6 2352. 相等行列对

将所有行的状态保存
遍历所有列 查看该状态有几个行存在

def equalPairs(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    from collections import defaultdict
    n = len(grid)
    line = defaultdict(int)
    for l in grid:
        v = tuple(l)
        line[v] +=1
    ans = 0
    for i in range(n):
        v = tuple([grid[x][i] for x in range(n)])
        ans += line[v]
    return ans

6/7 2611. 老鼠和奶酪

计算每一块奶酪被1号老鼠吃比2号老鼠吃要多的得分
选择得分差值为正最高的k个

def miceAndCheese(reward1, reward2, k):
    """
    :type reward1: List[int]
    :type reward2: List[int]
    :type k: int
    :rtype: int
    """
    n = len(reward1)
    l=[(reward1[i]-reward2[i],i) for i in range(n)]
    l.sort(reverse=True)
    s = sum(reward2)
    for i in range(k):
        s += l[i][0]
    return s

6/8 1240. 铺瓷砖

filled[i]使用m位二进制 来表示第i行被覆盖的状态
遍历每个位置i,j 未被覆盖则找到能够添加的最大边长mx
遍历每种可能情况1~mx

def tilingRectangle(n, m):
    """
    :type n: int
    :type m: int
    :rtype: int
    """
    global ans
    filled = [0]*n
    ans = n*m
    def dfs(i,j,num):
        global ans
        if j==m:
            i,j=i+1,0
        if i==n:
            ans = num
            return
        if filled[i]>>j & 1:
            dfs(i,j+1,num)
        elif num+1<ans:
            r,c=0,0
            for k in range(i,n):
                if filled[k]>>j&1:
                    break
                r+=1
            for k in range(j,m):
                if filled[i]>>k&1:
                    break
                c+=1
            mx = min(c,r)
            for w in range(1,mx+1):
                for k in range(w):
                    filled[i+w-1] |= 1<<(j+k)
                    filled[i+k] |= 1<<(j+w-1)
                dfs(i,j+w,num+1)
            for x in range(i,i+mx):
                for y in range(j,j+mx):
                    filled[x] ^= 1<<y
    dfs(0,0,0)
    return ans

6/9 2699. 修改图中的边权

dijkstra
如果未知路径全为1 最短路径任然大于target则无解
如果未知路径全为无穷 最短路径任然小于target则无解
进行两次搜索
https://leetcode.cn/problems/modify-graph-edge-weights/solutions/2278296/xiang-xi-fen-xi-liang-ci-dijkstrachou-mi-gv1m/

def modifiedGraphEdges(n, edges, source, destination, target):
    """
    :type n: int
    :type edges: List[List[int]]
    :type source: int
    :type destination: int
    :type target: int
    :rtype: List[List[int]]
    """
    g = [[] for _ in range(n)]
    for i,(x,y,_) in enumerate(edges):
        g[x].append((y,i))
        g[y].append((x,i))
    
    dis = [[float("inf"),float("inf")] for _ in range(n)]
    dis[source]=[0,0]
    
    def dijkstra(k):
        mem = [False]*n
        while True:
            x = -1
            for y,(b,d) in enumerate(zip(mem,dis)):
                if not b and (x<0 or d[k]<dis[x][k]):
                    x = y
            if x==destination:
                return
            mem[x] = True
            for y,ind in g[x]:
                wt = edges[ind][2]
                if wt ==-1:
                    wt=1
                if k==1 and edges[ind][2]==-1:
                    w = delta+dis[y][0]-dis[x][1]
                    if w>wt:
                        edges[ind][2] = wt = w
                dis[y][k] = min(dis[y][k],dis[x][k]+wt)
    dijkstra(0)
    delta = target - dis[destination][0]
    if delta<0:
        return []
    dijkstra(1)
    if dis[destination][1]<target:
        return []
    
    for e in edges:
        if e[2]==-1:
            e[2]=1
    return edges

6/10