LeetCode 每日一题 2024/3/18-2024/3/24

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

---

3/18 303. 区域和检索 - 数组不可变

前缀和
nums[x]记录0~x的元素和
计算i~j之间的元素和为nums[j]-nums[i-1]即可

class NumArray(object):def __init__(self, nums):""":type nums: List[int]"""pre = 0self.nums = [0]for n in nums:pre+=nself.nums.append(pre)def sumRange(self, i, j):""":type i: int:type j: int:rtype: int"""return self.nums[j+1]-self.nums[i]

---

3/19 1793. 好子数组的最大分数

双指针
为了确定l,r 两个都从k开始向左向右移动
比较哪一边的数值较大则往哪边移动
minv记录当前区间最小值

def maximumScore(nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)minv = nums[k]ans = nums[k]l = r = kfor _ in range(n-1):if r == n-1 or l>0 and nums[l-1]>nums[r+1]:l-=1minv = min(minv,nums[l])else:r+=1minv = min(minv,nums[r])ans = max(ans,minv*(r-l+1))return ans

---

3/20 1969. 数组元素的最小非零乘积

每一次操作 并不会改变元素的和
而在元素和不变的情况下 要想使得乘积最小应该尽可能最大化元素的差值
最大的元素为 2p-1 无论怎么交换 差值不会变大 不考虑
剩余元素可以首尾配对 x与2p-1-x配对 一个数只保留最低位1 剩余的给另一个
可以得到 1 和 2**p-2 两个值相乘
最后乘积为(2^p-1)*(2p-2)⁽²(p-1)-1)

def minNonZeroProduct(p):""":type p: int:rtype: int"""MOD=10**9+7if p==1:return 1def power(x,n):x_init = xb = []while n>0:r = n%2b.insert(0,r)n = n//2for i in range(1,len(b)):x = x*x%MODif b[i]==1:x = x*x_init%MODreturn xbase = 2**pnum = base//2-1x = (base-2)%MODans = 1ans = power(x,num)%MODans = (ans*((base-1)%MOD))%MODreturn ans

---

3/21 2671. 频率跟踪器

hash表记录次数
num[i]记录数字i出现的次数
cnt[q]记录频率为q的数字个数

class FrequencyTracker(object):def __init__(self):self.num = {}self.cnt = {}def add(self, number):""":type number: int:rtype: None"""self.cnt[self.num.get(number,0)] = self.cnt.get(self.num.get(number,0),0)-1self.num[number] = self.num.get(number,0)+1self.cnt[self.num.get(number,0)] = self.cnt.get(self.num.get(number,0),0)+1def deleteOne(self, number):""":type number: int:rtype: None"""if self.num.get(number,0)==0:returnself.cnt[self.num.get(number,0)]= self.cnt.get(self.num.get(number,0),0)-1self.num[number]  = self.num.get(number,0)-1self.cnt[self.num.get(number,0)]= self.cnt.get(self.num.get(number,0),0)+1def hasFrequency(self, frequency):""":type frequency: int:rtype: bool"""return self.cnt.get(frequency,0)>0

---

3/22 2617. 网格图中最少访问的格子数

对于grid[i][j] 已知到这个位置最少需要f步
向右走 最远到达该行的grid[i][j]+j
向下走 最远到达该列的grid[i][j]+i
在这一行 维持一个最小堆 保存rowh=(f,grid[i][j]+j) 表示上一步走了f的最远可以到达位置
列同理colh
接下来考虑 如何得到grid[i][j]最少需要f
分别处理rowh,colh
对于堆顶最小f 它的距离如果到不了当前的位置i/j 则将其弹出
最后可以得到行、列分别能够到达当前位置的两个最小f 即rowh[0][0],colh[0][0]
对于当前的最小步数f = min(rowh[0][0],colh[0][0])+1

def minimumVisitedCells(grid):""":type grid: List[List[int]]:rtype: int"""import heapqm,n=len(grid),len(grid[0])if m==1 and n==1:return 1colhs = [[] for _ in range(m)]for i,row in enumerate(grid):rowh=[]for j,(g,colh) in enumerate(zip(row,colhs)):while rowh and rowh[0][1]<j:heapq.heappop(rowh)while colh and colh[0][1]<i:heapq.heappop(colh)f = float("inf") if i or j else 1if rowh:f = rowh[0][0]+1if colh:f = min(f,colh[0][0]+1)if g and f<float("inf"):heapq.heappush(rowh,(f,g+j))heapq.heappush(colh,(f,g+i))return f if f<float("inf") else -1

---

3/23 2549. 统计桌面上的不同数字

n<=100
最差的情况 对于已有数字x 下一天x-1必定会出现在桌面上
x,x-1,x-2…,2
所以在10^9内 如果n>1则2~n都会出现在桌面上
如果n=1 则只有1

def distinctIntegers(n):""":type n: int:rtype: int"""return 1 if n==1 else n-1

---

3/24 322. 零钱兑换

dp[i]表示凑成金额i需要的最少硬币数
将硬币从小到大排序
依次考虑面值i 是否存在面值i-coin

def coinChange(coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""coins.sort()dp = [float("inf")]*(amount+1)dp[0]=0for i in range(coins[0],amount+1):tmp=float("inf")for j in coins:if j<=i:tmp = min(tmp,dp[i-j])else:breakif tmp<float("inf"):dp[i]=tmp+1return -1 if dp[amount]==float("inf") else dp[amount]

---