LeetCode 每日一题 2025/8/11-2025/8/17

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

---

8/11 2438. 二的幂数组中查询范围内的乘积

将n转换为二进制 如果第k位为1 那么包含2^k
得到所有元素后 预处理res[i][j]保存 [i~j]的积

def productQueries(n, queries):""":type n: int:type queries: List[List[int]]:rtype: List[int]"""MOD=10**9+7bins,cur=[],1while n>0:if n%2==1:bins.append(cur)n//=2cur*=2m=len(bins)res=[[0]*m for _ in range(m)]for i in range(m):cur=1for j in range(i,m):cur=cur*bins[j]%MODres[i][j]=curans=[]for l,r in queries:ans.append(res[l][r])return ans

---

8/12 2787. 将一个数字表示成幂的和的方案数

dp 背包
从前i个数字中选取j个数字

def numberOfWays(n, x):""":type n: int:type x: int:rtype: int"""MOD=10**9+7dp=[0]*(n+1)dp[0]=1for i in range(1,n+1):v=i**xif v>n:breakfor j in range(n,v-1,-1):dp[j]=(dp[j]+dp[j-v])%MODreturn dp[n]

---

8/13 326. 3 的幂

不断除以3 出现余数说明不满足

def isPowerOfThree(n):""":type n: int:rtype: bool"""while n>1:if n%3==0:n=n//3else:return Falsereturn True if n==1 else False

---

8/14 1780. 判断一个数字是否可以表示成三的幂的和

假设n = 3^a+3b+3^c+… a<b<c
每一轮除以3 经过a轮后得到 1+3^(b-a)+3(c-a)
此时余数为1 因为幂不同 所以在同一轮中余数只能为0或1
如果得到余数2说明不满足

def checkPowersOfThree(n):""":type n: int:rtype: bool"""while n>0:if n%3==2:return Falsen//=3return True

---

8/15 342. 4的幂

条件：
1.不能为负数
2.二进制只能出现1个1
3.1需要在二进制的奇数位 1 100 10000 看出规律 包含偶数个0

def isPowerOfFour(n):""":type n: int:rtype: bool"""if n <0 :return Falseif n&(n-1)>0:return Falses = bin(n)[2:]return  s.count('0')%2==0

---

8/16 1323. 6 和 9 组成的最大数字

从最高位开始往后遇到的第一个6变成9
6变9多了3 根据位置增加10^i*3

def maximum69Number (num):""":type num: int:rtype: int"""cur=0i=-1ori = numwhile num:if num%10==6:i=curcur+=1num//=10return ori if i==-1 else ori+3*(10**i)

---

8/17 837. 新 21 点

dp
最大能够抽到k+maxPts-1
dp[x]代表从x开始获胜的概率
dp相邻项计算差分
dp[i]-dp[i+1] = (dp[i+1]-dp[i+maxPts+1])/maxPts

def new21Game(n, k, maxPts):""":type n: int:type k: int:type maxPts: int:rtype: float"""if k==0:return 1.0dp=[0.0]*(k+maxPts)for i in range(k,min(n,k+maxPts-1)+1):dp[i]=1.0dp[k-1]=float(min(n-k+1,maxPts))/maxPtsfor i in range(k-2,-1,-1):dp[i]=dp[i+1]-(dp[i+maxPts+1]-dp[i+1])/maxPtsreturn dp[0]

---