LeetCode 209. 长度最小的子数组
子数组是一个连续的,很容易想到滑动窗口
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
windowSum = 0
left, right = 0, 0
res = float('inf')
while right < len(nums):
push = nums[right]
windowSum += push
right += 1
while windowSum >= target:
res = min(res, right - left)
pop = nums[left]
windowSum -= pop
left += 1
return res if res != float('inf') else 0
拓展
如果 nums 数组中包含负数,则窗口扩大时元素和不见得就增大,窗口缩小时元素和不见得就减小,这种情况就不能单纯使用滑动窗口技巧了,可能需要混合动态规划和单调队列来做。
862. 和至少为 K 的最短子数组
LeetCode 1425. 带限制的子序列和
LeetCode 53. 最大子数组和
这里给出的是滑动窗口解法
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
windowSum = 0
res = float("-inf")
left = right = 0
while right < len(nums):
push = nums[right]
windowSum += push
right += 1
res = max(res, windowSum)
while windowSum < 0:
pop = nums[left]
windowSum -= pop
left += 1
return res
LeetCode 59. 螺旋矩阵 II
模拟题,做这一题之前可以先试试 LeetCode 54. 螺旋矩阵
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[None for _ in range(n)] for _ in range(n)]
idx = 1
a, b, x, y = 0, 0, n - 1, n - 1
for _ in range(n ** 2):
for j in range(b, y + 1):
matrix[a][j] = idx
idx += 1
a += 1
for i in range(a, x + 1):
matrix[i][y] = idx
idx += 1
y -= 1
for j in range(y, b - 1, -1):
matrix[x][j] = idx
idx += 1
x -= 1
for i in range(x, a - 1, -1):
matrix[i][b] = idx
idx += 1
b += 1
return matrix
LeetCode 54. 螺旋矩阵
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix) - 1, len(matrix[0]) - 1
x, y = 0, 0
res = []
while x <= m and y <= n:
for j in range(y, n + 1):
if x <= m and y <= n:
res.append(matrix[x][j])
x += 1
for i in range(x, m + 1):
if x <= m and y <= n:
res.append(matrix[i][n])
n -= 1
for j in range(n, y - 1, -1):
if x <= m and y <= n:
res.append(matrix[m][j])
m -= 1
for i in range(m, x - 1, -1):
if x <= m and y <= n:
res.append(matrix[i][y])
y += 1
return res
KamaCoder 44. 开发商购买土地
前缀和思想
import sys
def find(matrix):
m, n = len(matrix), len(matrix[0])
preSum_matrix = [[None for _ in range(n)] for _ in range(m)]
preSum_matrix[0][0] = matrix[0][0]
for i in range(m):
for j in range(n):
up = preSum_matrix[i - 1][j] if i - 1 >= 0 else 0
left = preSum_matrix[i][j - 1] if j - 1 >= 0 else 0
left_up = preSum_matrix[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0
preSum_matrix[i][j] = matrix[i][j] + up + left - left_up
res = float('inf')
for i in range(m - 1):
if res == 0:
return 0
res = min(res, abs(preSum_matrix[m - 1][n - 1] - preSum_matrix[i][n - 1] * 2))
for j in range(n - 1):
if res == 0:
return 0
res = min(res, abs(preSum_matrix[m - 1][n - 1] - preSum_matrix[m - 1][j] * 2))
return res
if __name__ == "__main__":
lines = sys.stdin.read().strip().splitlines()
idx = 0
res = []
while idx < len(lines):
m, n = map(int, lines[idx].strip().split())
idx += 1
matrix = []
for _ in range(m):
line = list(map(int, lines[idx].strip().split()))
matrix.append(line)
idx += 1
res.append(str(find(matrix)))
sys.stdout.write("\n".join(res))
标签:59,matrix,idx,int,res,随想录,range,LeetCode,left
From: https://www.cnblogs.com/li508q/p/18417346