记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
7/8 724. 寻找数组的中心下标
从左到右依次判断
def pivotIndex(nums):
"""
:type nums: List[int]
:rtype: int
"""
s=sum(nums)
l,r=0,s
for i,num in enumerate(nums):
r-=num
if l==r:
return i
l+=num
return -1
7/9 3102. 最小化曼哈顿距离
找到当前最大距离
判断移除该距离两个点中一个后的距离变换
def minimumDistance(points):
"""
:type points: List[List[int]]
:rtype: int
"""
def check(arr,i):
n=len(arr)
if arr[0][1]==i:
return arr[n-1][0]-arr[1][0]
elif arr[-1][1]==i:
return arr[n-2][0]-arr[0][0]
else:
return arr[-1][0]-arr[0][0]
sx=[(x-y,i) for i,(x,y) in enumerate(points)]
sy=[(x+y,i) for i,(x,y) in enumerate(points)]
sx.sort()
sy.sort()
v1 = sx[-1][0]-sx[0][0]
v2 = sy[-1][0]-sy[0][0]
ans = float("inf")
if v1>=v2:
i,j = sx[0][1],sx[-1][1]
ans = min(ans,max(check(sx,i),check(sy,i)))
ans = min(ans,max(check(sx,j),check(sy,j)))
else:
i,j = sy[0][1],sy[-1][1]
ans = min(ans,max(check(sx,i),check(sy,i)))
ans = min(ans,max(check(sx,j),check(sy,j)))
return ans
7/10 2970. 统计移除递增子数组的数目 I
找到数组最长严格递增的位置i 即前缀nums[0]~nums[i]严格递增
如果i是数组最后的位置 那么所有子数组都可以移除即 n*(n+1)/2
否则 只保留前缀的一部分nums[0]~nums[i] 可以有i+2种
如果是前缀加后缀 设后缀第一个数为nums[j] 移除最后一个数是nums[j-1]
从后往前枚举j 直到nums[j]>=nums[j+1]
保持nums[i]<nums[j]
def incremovableSubarrayCount(nums):
"""
:type nums: List[int]
:rtype: int
"""
n=len(nums)
i = 0
while i<n-1 and nums[i]<nums[i+1]:
i+=1
if i==n-1:
return n*(n+1)//2
ans = i+2
j=n-1
while j==n-1 or nums[j]<nums[j+1]:
while i>=0 and nums[i]>=nums[j]:
i-=1
ans += i+2
j-=1
return ans
7/11 2972. 统计移除递增子数组的数目 II
与昨天的一样
找到数组最长严格递增的位置i 即前缀nums[0]~nums[i]严格递增
如果i是数组最后的位置 那么所有子数组都可以移除即 n*(n+1)/2
否则 只保留前缀的一部分nums[0]~nums[i] 可以有i+2种
如果是前缀加后缀 设后缀第一个数为nums[j] 移除最后一个数是nums[j-1]
从后往前枚举j 直到nums[j]>=nums[j+1]
保持nums[i]<nums[j]
def incremovableSubarrayCount(nums):
"""
:type nums: List[int]
:rtype: int
"""
n=len(nums)
i = 0
while i<n-1 and nums[i]<nums[i+1]:
i+=1
if i==n-1:
return n*(n+1)//2
ans = i+2
j=n-1
while j==n-1 or nums[j]<nums[j+1]:
while i>=0 and nums[i]>=nums[j]:
i-=1
ans += i+2
j-=1
return ans
7/12 2974. 最小数字游戏
依照规则 从小到大排序 奇数偶数位的数值调换
def numberGame(nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums.sort()
i = 0
while i<len(nums):
nums[i],nums[i+1]=nums[i+1],nums[i]
i+=2
return nums
7/13 3011. 判断一个数组是否可以变为有序
二进制1的个数相同的连续数值可以分为一组
每一组内必定可以实现有序
从头遍历 为了实现全部数组有序
排在后面小组的所有数值 必定需要大于前面小组的最大值
pmx记录前面小组的最大值 mx记录当前小组最大值
def canSortArray(nums):
"""
:type nums: List[int]
:rtype: bool
"""
n=len(nums)
pmx = 0
i = 0
while i<n:
mx = 0
cnt = nums[i].bit_count()
while i<n and nums[i].bit_counb()==cnt:
x = nums[i]
if x<pmx:
return False
mx=max(mx,x)
i+=1
pmx=mx
return True
7/14
