记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
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+7
dp = [[0]*4 for _ in range(n+1)]
dp[0][3]=1
for i in range(1,n+1):
dp[i][0] = dp[i-1][3]
dp[i][1] = (dp[i-1][0]+dp[i-1][2])%MOD
dp[i][2] = (dp[i-1][0]+dp[i-1][1])%MOD
dp[i][3] = (dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3])%MOD
return 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 heapq
n,m=len(moveTime),len(moveTime[0])
ans=[[float("inf")]*m for _ in range(n)]
ans[0][0]=0
steps=[(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 d
if d>ans[i][j]:
continue
for dx,dy in steps:
x,y=i+dx,j+dy
if 0<=x<n and 0<=y<m:
newd = max(d,moveTime[x][y])+1
if newd<ans[x][y]:
ans[x][y]=newd
heapq.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 heapq
n,m=len(moveTime),len(moveTime[0])
ans=[[float("inf")]*m for _ in range(n)]
ans[0][0]=0
steps=[(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 d
if d>ans[i][j]:
continue
add = (i+j)%2
for dx,dy in steps:
x,y=i+dx,j+dy
if 0<=x<n and 0<=y<m:
newd = max(d,moveTime[x][y])+1+add
if newd<ans[x][y]:
ans[x][y]=newd
heapq.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 Counter
import math
MOD=10**9+7
num=list(map(int,num))
total=sum(num)
if total%2:
return 0
target = total//2
cnt = Counter(num)
n=len(num)
maxOdd = (n+1)//2
psum=[0]*11
for 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)]=0
return 0
if pos>9:
mem[(pos,cur,oddcnt)]=int(cur==target and oddcnt==0)
return int(cur==target and oddcnt==0)
evencnt=psum[pos]-oddcnt
ans=0
for i in range(max(0,cnt[pos]-evencnt),min(cnt[pos],oddcnt)+1):
ways=math.comb(oddcnt,i)*math.comb(evencnt,cnt[pos]-i)%MOD
ans += ways*dfs(pos+1, cur+i*pos, oddcnt-i)
mem[(pos,cur,oddcnt)]=ans%MOD
return ans%MOD
return 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+=z1
s2+=z2
if s1>s2:
if z2==0:
return -1
else:
return s1
elif s1<s2:
if z1==0:
return -1
else:
return s2
return 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 True
return False