LeetCode 每日一题 2025/5/5-2025/5/11

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

---

5/5 790. 多米诺和托米诺平铺

dp
假设dp[i][x]为第i列状态 0一个没有铺 1上方格子被铺 2下方格子被铺 3两个格子都被铺
dp[i][0] = dp[i-1][3]
dp[i][1] = dp[i-1][0]+dp[i-1][2]
dp[i][2] = dp[i-1][0]+dp[i-1][1]
dp[i][3] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]

def numTilings(n):""":type n: int:rtype: int"""MOD=10**9+7dp = [[0]*4 for _ in range(n+1)]dp[0][3]=1for i in range(1,n+1):dp[i][0] = dp[i-1][3]dp[i][1] = (dp[i-1][0]+dp[i-1][2])%MODdp[i][2] = (dp[i-1][0]+dp[i-1][1])%MODdp[i][3] = (dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3])%MODreturn dp[n][3]

---

5/6 1920. 基于排列构建数组

按照要求构建

def buildArray(nums):""":type nums: List[int]:rtype: List[int]"""return [nums[nums[i]] for i in range(len(nums))]

---

5/7 3341. 到达最后一个房间的最少时间 I

ans[x][y]记录到达x,y位置的最少时间
dijkstra 根据x,y得到到他周围最短时间

def minTimeToReach(moveTime):""":type moveTime: List[List[int]]:rtype: int"""import heapqn,m=len(moveTime),len(moveTime[0])ans=[[float("inf")]*m for _ in range(n)]ans[0][0]=0steps=[(1,0),(-1,0),(0,1),(0,-1)]l=[(0,0,0)]while True:d,i,j=heapq.heappop(l)if i==n-1 and j==m-1:return dif d>ans[i][j]:continuefor dx,dy in steps:x,y=i+dx,j+dyif 0<=x<n and 0<=y<m:newd = max(d,moveTime[x][y])+1if newd<ans[x][y]:ans[x][y]=newdheapq.heappush(l, (newd,x,y))

---

5/8 3342. 到达最后一个房间的最少时间 II

ans[x][y]记录到达x,y位置的最少时间
dijkstra 根据x,y得到到他周围最短时间
每走一步耗时在1,2之间变化 根据位置和的奇偶性可以判断 x+y偶数耗时1 奇数耗时2

def minTimeToReach(moveTime):""":type moveTime: List[List[int]]:rtype: int"""import heapqn,m=len(moveTime),len(moveTime[0])ans=[[float("inf")]*m for _ in range(n)]ans[0][0]=0steps=[(1,0),(-1,0),(0,1),(0,-1)]l=[(0,0,0)]while True:d,i,j=heapq.heappop(l)if i==n-1 and j==m-1:return dif d>ans[i][j]:continueadd = (i+j)%2for dx,dy in steps:x,y=i+dx,j+dyif 0<=x<n and 0<=y<m:newd = max(d,moveTime[x][y])+1+addif newd<ans[x][y]:ans[x][y]=newdheapq.heappush(l, (newd,x,y))

---

5/9 3343. 统计平衡排列的数目

https://leetcode.cn/problems/count-number-of-balanced-permutations/solutions/3670620/tong-ji-ping-heng-pai-lie-de-shu-mu-by-l-ki3d/?envType=daily-question&envId=2025-05-09

def countBalancedPermutations(num):""":type num: str:rtype: int"""from collections import Counterimport mathMOD=10**9+7num=list(map(int,num))total=sum(num)if total%2:return 0target = total//2cnt = Counter(num)n=len(num)maxOdd = (n+1)//2psum=[0]*11for i in range(9,-1,-1):psum[i]=psum[i+1]+cnt[i]mem={}def dfs(pos,cur,oddcnt):if (pos,cur,oddcnt) in mem:return mem[(pos,cur,oddcnt)]if oddcnt<0 or psum[pos]<oddcnt or cur>target:mem[(pos,cur,oddcnt)]=0return 0if pos>9:mem[(pos,cur,oddcnt)]=int(cur==target and oddcnt==0)return int(cur==target and oddcnt==0)evencnt=psum[pos]-oddcntans=0for i in range(max(0,cnt[pos]-evencnt),min(cnt[pos],oddcnt)+1):ways=math.comb(oddcnt,i)*math.comb(evencnt,cnt[pos]-i)%MODans += ways*dfs(pos+1, cur+i*pos, oddcnt-i)mem[(pos,cur,oddcnt)]=ans%MODreturn ans%MODreturn dfs(0,0,maxOdd)

---

5/10 2918. 数组的最小相等和

正整数最小为1
统计数组当前和 以及0的个数
将所有0变为1 返回较大的值
如果较小数组中没有0 则无法相等

def minSum(nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: int"""s1,s2=sum(nums1),sum(nums2)z1,z2=nums1.count(0),nums2.count(0)s1+=z1s2+=z2if s1>s2:if z2==0:return -1else:return s1elif s1<s2:if z1==0:return -1else:return s2return s1

---

5/11 1550. 存在连续三个奇数的数组

依次判断 i-1,i,i+1是否是奇数

def threeConsecutiveOdds(arr):""":type arr: List[int]:rtype: bool"""n=len(arr)for i in range(1,n-1):if arr[i-1]%2 and arr[i]%2 and arr[i+1]%2:return Truereturn False

---