记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
4/28 2302. 统计得分小于 K 的子数组数目
滑动窗口 固定右侧端点r
找到左侧端点l 使得[l,r]第一次满足条件
那么以l右侧的位置为左端点必定满足
def countSubarrays(nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n=len(nums)
ans=0
total=0
l=0
for r in range(n):
total+=nums[r]
while l<=r and total*(r-l+1)>=k:
total-=nums[l]
l+=1
ans+=r-l+1
return ans
4/29 2962. 统计最大元素出现至少 K 次的子数组
遍历记录最大元素出现的位置 ind
对于最大元素位置i1 在(i0,i1]间的所有位置都需要到ik为止才能满足
此时有(i1-i0)*(n-ik)个子数组
def countSubarrays(nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n=len(nums)
maxv=max(nums)
ind=[-1]
for i in range(n):
if nums[i]==maxv:
ind.append(i)
l,r=1,k
ans=0
while r<len(ind):
ans+=(ind[l]-ind[l-1])*(n-ind[r])
l+=1
r+=1
return ans
4/30 1295. 统计位数为偶数的数字
依次判断
def findNumbers(nums):
"""
:type nums: List[int]
:rtype: int
"""
def check(num):
b = 0
while num>0:
num=num//10
b+=1
return b%2==0
ans = 0
for num in nums:
if check(num):
ans+=1
return ans
5/1 2071. 你可以安排的最多任务数目
假设完成k个任务 选择k个值最小的任务 和k个力量最大的工人
二分来找到最大的k
check(mid)用来判断mid个是否满足
def maxTaskAssign(tasks, workers, pills, strength):
"""
:type tasks: List[int]
:type workers: List[int]
:type pills: int
:type strength: int
:rtype: int
"""
from sortedcontainers import SortedList
n=len(tasks)
m=len(workers)
tasks.sort()
workers.sort()
def check(mid):
p=pills
wk=SortedList(workers[m-mid:])
for i in range(mid-1,-1,-1):
if wk[-1]>=tasks[i]:
wk.pop()
else:
if p==0:
return False
rep=wk.bisect_left(tasks[i]-strength)
if rep==len(wk):
return False
p-=1
wk.pop(rep)
return True
l,r,ans=1,min(m,n),0
while l<=r:
mid=(l+r)//2
if check(mid):
ans=mid
l=mid+1
else:
r=mid-1
return ans
5/2 838. 推多米诺
广搜BFS
使用l,r两个集合记录当前向左向右倾倒的位置
每一个向左的位置-1 如果位置上的骨牌状态为.则暂时标记可以倾倒
向右的一样
判断向左向右倾倒的位置是否有重复 如果有重复
这个位置将不会倾倒 去除这些位置
将可以倾倒的位置标记后 下一轮重新操作
def pushDominoes(dominoes):
"""
:type dominoes: str
:rtype: str
"""
dmn = list(dominoes)
l,r = set(),set()
for loc,c in enumerate(dmn):
if c=="R":
r.add(loc)
elif c=="L":
l.add(loc)
n = len(dominoes)
while l or r:
tmpl,tmpr = set(),set()
for loc in l:
tmp = loc-1
if tmp>=0 and dmn[tmp]==".":
tmpl.add(tmp)
for loc in r:
tmp = loc+1
if tmp<n and dmn[tmp]==".":
tmpr.add(tmp)
same = tmpl&tmpr
tmpl -= same
tmpr -= same
for loc in tmpl:
dmn[loc]="L"
for loc in tmpr:
dmn[loc]="R"
l = tmpl
r = tmpr
return "".join(dmn)
5/3 1007. 行相等的最少多米诺旋转
遍历记录数值在top出现的次数t[x] 在bottoms出现b[x]次
并统计每个位置数值出现次数nums[x]如果某个位置top,bottoms相同 则只在nums中统计一次
如果需要满足条件则必定存在某个数值x nums[x]=len(tops)
如果交换到top需要n-t[x]次 到下层需要n-b[x] 取小值
def minDominoRotations(tops, bottoms):
"""
:type tops: List[int]
:type bottoms: List[int]
:rtype: int
"""
n=len(tops)
nums=[0]*7
t,b=[0]*7,[0]*7
for i in range(n):
t[tops[i]]+=1
b[bottoms[i]]+=1
nums[tops[i]]+=1
if tops[i]!=bottoms[i]:
nums[bottoms[i]]+=1
for i in range(1,7):
if nums[i]==n:
return min(n-t[i],n-b[i])
return -1
5/4 1128. 等价多米诺骨牌对的数量
依次遍历
def numEquivDominoPairs(dominoes):
"""
:type dominoes: List[List[int]]
:rtype: int
"""
m = {}
ret = 0
for a,b in dominoes:
if a>b:
a,b=b,a
tmp = m.get((a,b),0)
m[(a,b)] = tmp+1
for v in m.values():
if v>=2:
ret += (v-1)*v/2
return ret