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

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

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

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

def sumDigitDifferences(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n=len(nums)
    ans = 0
    while nums[0]>0:
        m = [0]*10
        for i in range(n):
            m[nums[i]%10]+=1
            nums[i]//=10
        for 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 = 0
    neg = 0
    pos = 0
    zero = 0
    ans = 0 
    for num in nums:
        if num<0:
            neg += 1
            preneg = num
        elif num==0:
            zero+=1
            continue
        else:
            pos+=1
        if ans==0:
            ans = num
        else:
            ans *= num
    if neg==1 and pos==0:
        if zero>0:
            return 0
        else:
            return ans
    return 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 = 0
    nums.sort()
    for k in range(n+1):
        if k>0 and nums[k-1]>=k:
            continue
        if k<n and nums[k]<=k:
            continue
        ans+=1
    return 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 = 0
    dp = [[-1]*51 for _ in range(n)]
    for i in range(n):
        dp[i][0]=1
        for l in range(k+1):
            for j in range(i):
                add = 0
                if nums[i]!=nums[j]:
                    add = 1
                if 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 defaultdict
    dp=defaultdict(lambda:[0]*(k+1))
    zd=[0]*(k+1)
    
    for num in nums:
        tmp = dp[num]
        for j in range(k+1):
            tmp[j]+=1
            if 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]

9/8 977. 有序数组的平方

计算每个数平方即可

def sortedSquares(nums):
    """
    :type A: List[int]
    :rtype: List[int]
    """
    return sorted([x**2 for x in nums])