LeetCode 每日一题 2024/11/11-2024/11/17

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

11/11 1547. 切棍子的最小成本

从左到右排序 dfs遍历区间[i,j]完成切割的最小成本

def minCost(n, cuts):
    """
    :type n: int
    :type cuts: List[int]
    :rtype: int
    """
    cuts.sort()
    cuts = [0]+cuts+[n]
    
    mem = {}
    def dfs(i,j):
        if (i,j) in mem:
            return mem[(i,j)]
        if i+1==j:
            return 0
        ans = float("inf")
        for k in range(i+1,j):
            ans = min(ans,dfs(i,k)+dfs(k,j))
        ans += cuts[j]-cuts[i]
        mem[(i,j)]=ans
        return ans
    return dfs(0,len(cuts)-1)

11/12 3258. 统计满足 K 约束的子字符串数量 I

如果一个长度为x的字符串满足约束 那么他的子字符串都满足
滑动窗口 固定右端点i 找到最小左端点l
可以得到以右端点结尾的符合子字符串有i-l+1个

def countKConstraintSubstrings(s, k):
    """
    :type s: str
    :type k: int
    :rtype: int
    """
    ans=0
    l = 0
    cnt=[0,0]
    for i,c in enumerate(s):
        cnt[ord(c)&1]+=1
        while cnt[0]>k and cnt[1]>k:
            cnt[ord(s[l])&1]-=1
            l+=1
        ans += i-l+1
    return ans
        

11/13 3261. 统计满足 K 约束的子字符串数量 II

滑动窗口
枚举每个结束位j 统计0,1个数
如果不满足对于当前i j开始不符合条件记录right[i]=j
将左端点i往右移动直至满足
对于[l,r]
右端点在j=right[l]之前的全部满足 (j-l+1)*(j-l)/2
j之后的子字符串使用前缀数组 pre[r+1]-pre[j]

def countKConstraintSubstrings(s, k, queries):
    """
    :type s: str
    :type k: int
    :type queries: List[List[int]]
    :rtype: List[int]
    """
    n=len(s)
    cnt=[0,0]
    right=[n]*n
    pre=[0]*(n+1)
    i=0
    for j in range(n):
        c=s[j]
        cnt[ord(c)&1]+=1
        while cnt[0]>k and cnt[1]>k:
            cnt[ord(s[i])&1]-=1
            right[i]=j
            i+=1
        pre[j+1]=pre[j]+j-i+1
    ans=[]
    for l,r in queries:
        j = min(right[l],r+1)
        v = (j-l+1)*(j-l)//2+pre[r+1]-pre[j]
        ans.append(v)
    return ans

11/14 3249. 统计好节点的数目

叶节点必定是好节点 dfs统计所有子节点个数

def countGoodNodes(edges):
    """
    :type edges: List[List[int]]
    :rtype: int
    """
    n=len(edges)+1
    g = [[] for _ in range(n)]
    for x,y in edges:
        g[x].append(y)
        g[y].append(x)
    ans = 0
    def dfs(x,p):
        global ans
        total = 1
        size = 0
        same = True
        for y in g[x]:
            if y==p:
                continue
            cur = dfs(y,x)
            if size==0:
                size=cur
            elif size!=cur:
                same = False
            total+=cur
        if same:
            ans+=1
        return total
    dfs(0,-1)
    return ans

11/15 3239. 最少翻转次数使二进制矩阵回文 I

分别判断每一行是回文 或者每一列是回文需要翻转的次数

def minFlips(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    n,m=len(grid),len(grid[0])
    ans1,ans2=0,0
    for i in range(n):
        l,r = 0,m-1
        while l<r:
            if grid[i][l]!=grid[i][r]:
                ans1+=1
            l+=1
            r-=1
    for j in range(m):
        l,r=0,n-1
        while l<r:
            if grid[l][j]!=grid[r][j]:
                ans2+=1
            l+=1
            r-=1
    return min(ans1,ans2)

11/16 3240. 最少翻转次数使二进制矩阵回文 II

对于某个位置i,j 对应位置i,n-1-j; m-1-i,j; m-1-i,n-1-j
四个位置要相同 如果四个综合为cnt 那么需要翻转最少min(cnt,4-cnt)
如果m,n都为奇数 中间位置必定为0
统计m,n为奇数时中间一行或一列 镜像位置不同的对数diff 以及镜像位置相同的1的个数cnt
如果cnt%4==0 那么将diff个1变为0即可
如果cnt%4不为0 必定是2
如果diff>0 将其中一对变为1 其余变为0 即更改diff次
如果diff=0 只能将cnt中两个1变为0

def minFlips(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    m,n=len(grid),len(grid[0])
    ans = 0
    for i in range(m//2):
        r,r2=grid[i],grid[-1-i]
        for j in range(n//2):
            cnt = r[j]+r[-1-j]+r2[j]+r2[-1-j]
            ans += min(cnt,4-cnt)
    
    if m%2 and n%2:
        ans += grid[m//2][n//2]
    diff = cnt=0
    if m%2:
        r = grid[m//2]
        for j in range(n//2):
            if r[j]!=r[-1-j]:
                diff+=1
            else:
                cnt+=r[j]*2
    if n%2:
        for i in range(m//2):
            if grid[i][n//2]!=grid[-1-i][n//2]:
                diff+=1
            else:
                cnt+=grid[i][n//2]*2
    return ans +(diff if diff else cnt%4)

11/17 825. 适龄的朋友

1.用户x不会对大于自己岁数的y发送好友请求
统计各个年龄各有多少人 存入m
将年龄从小到大排列 生成前缀和数组
统计每个年龄会加好友的区间 二分
2.因为年纪范围知道 计数排序 前缀和

def numFriendRequests1(ages):
    """
    :type ages: List[int]
    :rtype: int
    """
    from collections import defaultdict
    m = defaultdict(int)
    for age in ages:
        m[age]+=1
    ageList = list(m.keys())
    ageList.sort()
    presum = [0,m[ageList[0]]]
    
    for i in range(1,len(ageList)):
        presum.append(presum[i]+m[ageList[i]])
    ans = 0
    for loc,age in enumerate(ageList):
        num = m[age]
        minage = age*1.0/2+7 #大于minage
        if minage<age:
            ans += num*(num-1)
        l,r = 0,loc-1
        while l<=r:
            mid = (l+r)//2
            if ageList[mid]>minage:
                r = mid-1
            else:
                l = mid+1
        if l>=0 and loc>=0:
            ans += (presum[loc]-presum[l])*num
    return ans
    
def numFriendRequests(ages):
    """
    :type ages: List[int]
    :rtype: int
    """
    total = [0]*121
    for age in ages:
        total[age]+=1
    presum = [0]*121
    for i in range(1,121):
        presum[i] = presum[i-1]+total[i]
    ans = 0
    for age in range(15,121):
        if total[age]>0:
            minage = int(age/2+8)-1
            ans += total[age]*(presum[age]-presum[minage]-1)
    return ans