当前位置：首页 > news >正文

LeetCode 每日一题 2024/9/2-2024/9/8

news 来源：原创 2024/9/20 7:58:05

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

9/2 3153. 所有数对中数位不同之和

依次统计每一位上所有数值的个数
n=len(nums)
如果数值x出现m次那么有n-m种情况会出现该位是不同的
累加最后因为重复计算除以二

def sumDigitDifferences(nums):""":type nums: List[int]:rtype: int"""n=len(nums)ans = 0while nums[0]>0:m = [0]*10for i in range(n):m[nums[i]%10]+=1nums[i]//=10for x in range(10):ans += (n-m[x])*m[x]return ans//2

9/3 2708. 一个小组的最大实力值

乘积最大选择所有正数和偶数个负数
从小到大排列将所有非零数都相乘记录最接近0的负数preneg
如果最终答案为负除以preneg

def maxStrength(nums):""":type nums: List[int]:rtype: int"""nums.sort()preneg = 0neg = 0pos = 0zero = 0ans = 0 for num in nums:if num<0:neg += 1preneg = numelif num==0:zero+=1continueelse:pos+=1if ans==0:ans = numelse:ans *= numif neg==1 and pos==0:if zero>0:return 0else:return ansreturn ans if ans>=0 else ans//preneg

9/4 2860. 让所有学生保持开心的分组方法数

选中的人nums尽可能小将nums从小到大排序
如果选中k个需要满足nums[k-1]<k nums[k]>k

def countWays(nums):""":type nums: List[int]:rtype: int"""n=len(nums)ans = 0nums.sort()for k in range(n+1):if k>0 and nums[k-1]>=k:continueif k<n and nums[k]<=k:continueans+=1return ans

9/5 3174. 清除数字

栈遇到数字弹出顶部字符

def clearDigits(s):""":type s: str:rtype: str"""st = []for c in s:if c.isdigit():st.pop()else:st.append(c)return ''.join(st)

9/6 3176. 求出最长好子序列 I

dp[i][j] 表示以nums[i]结尾的最长序列中有j个数字与最后一个数字不同

def maximumLength(nums, k):""":type nums: List[int]:type k: int:rtype: int"""n=len(nums)ans = 0dp = [[-1]*51 for _ in range(n)]for i in range(n):dp[i][0]=1for l in range(k+1):for j in range(i):add = 0if nums[i]!=nums[j]:add = 1if l-add>=0 and dp[j][l-add]!=-1:dp[i][l] = max(dp[i][l],dp[j][l-add]+1)ans = max(ans,dp[i][l])return ans

9/7 3177. 求出最长好子序列 II

dp[i][j]表示以nums[i]结尾
有j个数字与其在序列中的后一个数字不相等的最长合法序列的长度
枚举x<i 如果nums[x]=nums[i] dp[i][j]=max(dp[x][j]+1)
否则dp[i][j]=max(dp[x][j-1]+1)
zd[j] 表示到位置i之前有j个数与后一个不等的最长序列长度
即dp[i][j]=max(zd[j]+1)

def maximumLength(nums, k):""":type nums: List[int]:type k: int:rtype: int"""from collections import defaultdictdp=defaultdict(lambda:[0]*(k+1))zd=[0]*(k+1)for num in nums:tmp = dp[num]for j in range(k+1):tmp[j]+=1if j>0:tmp[j]=max(tmp[j],zd[j-1]+1)for j in range(k+1):zd[j]=max(zd[j],tmp[j])return zd[k]