训练营Day2| 前缀和 滑动窗口
滑动窗口
思路: 加一个右侧的item,试图删除最多的左侧item
res+=nums[right] if res<target: right+=1 else: while res>=target: res-=nums[left] left+=1 leng = min(leng,right-left+2) right+=1
螺旋矩阵
思路: 一圈一圈遍历。每一圈的遍历可以通过 startPoint 和边长唯一确定。
curLen = n-1 count=0 num=1 while curLen>0: startI,startJ=count,count for i in range(curLen): res[startI][startJ+i]=num num+=1
开发商购买土地
思路: 前缀和预处理。一共有(n-1)+(m-1)种分法。提前通过前缀和预处理好数字然后遍历所有分法就可以。
[n, m] = [int(c) for c in input().split()] res = [0]*n for i in range(n): res[i] = [int(c) for c in input().split()] def getSumPeri(res): sumPeri = [0]*n for i in range(n): if i >0: sumPeri[i]+=sumPeri[i-1] for j in range(m): sumPeri[i]+=res[i][j] return sumPeri def getSumPerj(res): sumPerj=[0]*m for j in range(m): if j>0: sumPerj[j]+=sumPerj[j-1] for i in range(n): sumPerj[j]+=res[i][j] return sumPerj def solve(sumPeri,sumPerj): minCount = float('inf') for i in range(n): minCount=min(minCount,abs(sumPeri[-1]-2*sumPeri[i])) for j in range(m): minCount=min(minCount,abs(sumPerj[-1]-2*sumPerj[j])) return minCount