阅读量:1
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
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 807. 保持城市天际线
找出每一行 每一列的最大高度
对于位置i,j 最大高度为min(第i行的max,第j列的max)
def maxIncreaseKeepingSkyline(grid): """ :type grid: List[List[int]] :rtype: int """ n,m = len(grid),len(grid[0]) col,row = [0]*m,[0]*n for i in range(n): for j in range(m): row[i] = max(row[i],grid[i][j]) col[j] = max(col[j],grid[i][j]) ans = 0 for i in range(n): for j in range(m): new = min(row[i],col[j]) ans += new-grid[i][j] return ans 