LeetCode 每日一题 2024/7/8-2024/7/14

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

7/8 724. 寻找数组的中心下标

从左到右依次判断

def pivotIndex(nums):""":type nums: List[int]:rtype: int"""s=sum(nums)l,r=0,sfor i,num in enumerate(nums):r-=numif l==r:return il+=numreturn -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 = 0while i<n-1 and nums[i]<nums[i+1]:i+=1if i==n-1:return n*(n+1)//2ans = i+2j=n-1while j==n-1 or nums[j]<nums[j+1]:while i>=0 and nums[i]>=nums[j]:i-=1ans += i+2j-=1return 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 = 0while i<n-1 and nums[i]<nums[i+1]:i+=1if i==n-1:return n*(n+1)//2ans = i+2j=n-1while j==n-1 or nums[j]<nums[j+1]:while i>=0 and nums[i]>=nums[j]:i-=1ans += i+2j-=1return ans

7/12 2974. 最小数字游戏

依照规则 从小到大排序 奇数偶数位的数值调换

def numberGame(nums):""":type nums: List[int]:rtype: List[int]"""nums.sort()i = 0while i<len(nums):nums[i],nums[i+1]=nums[i+1],nums[i]i+=2return nums

7/13 3011. 判断一个数组是否可以变为有序

二进制1的个数相同的连续数值可以分为一组
每一组内必定可以实现有序
从头遍历 为了实现全部数组有序
排在后面小组的所有数值 必定需要大于前面小组的最大值
pmx记录前面小组的最大值 mx记录当前小组最大值

def canSortArray(nums):""":type nums: List[int]:rtype: bool"""n=len(nums)pmx = 0i = 0while i<n:mx = 0cnt = nums[i].bit_count()while i<n and nums[i].bit_counb()==cnt:x = nums[i]if x<pmx:return Falsemx=max(mx,x)i+=1pmx=mxreturn 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]*nfor 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 = 0for i in range(n):for j in range(m):new =  min(row[i],col[j])ans += new-grid[i][j]return ans