记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
3/24 2255. 统计是给定字符串前缀的字符串数目
依次判断
def countPrefixes(words, s):
"""
:type words: List[str]
:type s: str
:rtype: int
"""
ans=0
for w in words:
if s.startswith(w):
ans+=1
return ans
3/25 2711. 对角线上不同值的数量差
模拟每一个位置的数值
def differenceOfDistinctValues(grid):
"""
:type grid: List[List[int]]
:rtype: List[List[int]]
"""
n,m=len(grid),len(grid[0])
ans=[[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
left=set()
x,y=i-1,j-1
while x>=0 and y>=0:
left.add(grid[x][y])
x-=1
y-=1
right=set()
x,y=i+1,j+1
while x<n and y<m:
right.add(grid[x][y])
x+=1
y+=1
ans[i][j]=abs(len(left)-len(right))
return ans
3/26 2829. k-avoiding 数组的最小总和
为了总和最小 并且两个数值相加不等于k
小于k的数可以取前一半 k//2
剩余的数 等于k后择取连续的即可 k,k+1,k+2…
def minimumSum(n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
num = k//2
if num>=n:
return (1+n)*n/2
else:
return (1+num)*num/2+(2*k+n-num-1)*(n-num)/2
3/27 2712. 使所有字符相等的最小成本
对于某个位置x s[x]!=s[x+1]
必须要进行翻转操作 0~x 或者x+1~n 从而使得s[x]=s[x+1]
操作并不会影响其他相邻位置是否相同的状态
所以从头遍历 遇到不相同的进行最有操作min(x,n-x)
def minimumCost(s):
"""
:type s: str
:rtype: int
"""
n=len(s)
ans=0
for i in range(1,n):
if s[i-1]!=s[i]:
ans+=min(i,n-i)
return ans
3/28 2716. 最小化字符串长度
根据题意 即为将字符去重
def minimizedStringLength(s):
"""
:type s: str
:rtype: int
"""
return len(set(s))
3/29 2360. 图中的最长环
依次遍历 如果出现遍历过的节点说明存在环
def longestCycle(edges):
"""
:type edges: List[int]
:rtype: int
"""
n=len(edges)
tag=[0]*n
cur = 0
ans=-1
for i in range(n):
if tag[i]>0:
continue
loc=i
start=cur
while loc!=-1:
cur+=1
if tag[loc]>0:
if tag[loc]>start:
ans=max(ans,cur-tag[loc])
break
tag[loc]=cur
loc=edges[loc]
return ans
3/30 2109. 向字符串添加空格
依次遍历 到位置加入空格
def addSpaces(s, spaces):
"""
:type s: str
:type spaces: List[int]
:rtype: str
"""
n = len(s)
m = len(spaces)
loc = 0
ans = []
for i in range(n):
c = s[i]
if loc==m:
ans.append(c)
else:
if i==spaces[loc]:
ans.append(" ")
loc+=1
ans.append(c)
return "".join(ans)