训练营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