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
原文地址：https://blog.csdn.net/zkt286468541/article/details/143787895
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！