代码随想录算法训练营 Day 2
Published:
Q1. LeetCode 209
解法1: 暴力法
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
res = float('inf')
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
if s >= target:
res = min(res, j - i + 1)
break
return res if res != float('inf') else 0
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O(1)
Note：数据更新后Time Limit Exceeded(TLE)
解法2: 滑动窗口
思路：1. 类似于快慢指针，两个指针初始均设为0。慢指针与快指针分别表示窗口的两端；2. 首先移动快指针，固定慢指针，计算窗口中所有数的和；3. 当总和不小于target时，移动慢指针，找到对于当前快指针的最小窗口
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
res = float('inf')
s = 0
start = 0
for end in range(n):
s += nums[end]
# 使用while循环考虑需要移动多次慢指针的情况
while s >= target:
res = min(res, end - start + 1)
s -= nums[start]
start += 1
return res if res != float('inf') else 0
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Q2. Leetcode 59
难点：循环不变量 - 如何定义遍历区间，使得循环可以按照一定规则进行
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0] * n for _ in range(n)]
start = 0
loop = n // 2
offset = 1
num = 1
for l in range(loop):
# 左闭右开区间，因此在每个循环后需要将操作变量移动下个位置
for c in range(start, n - offset):
res[start][c] = num
num += 1
c += 1
for r in range(start, n - offset):
res[r][c] = num
num += 1
r += 1
for c in range(n - offset, start, -1):
res[n - offset][c] = num
num += 1
c -= 1
for r in range(n - offset, start, -1):
res[r][c] = num
num += 1
start += 1
offset += 1
if n % 2 != 0:
res[start][start] = num
return res
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O(1)
思考
假如矩阵的行数与列数不一样，应该怎么做？循环次数与最后的填充
Q3. KamaCoder 58
思路：
- 使用前缀和数组
- 通常前缀和数组会在最前面多加一位0，以便于逻辑写法统一
import sys
input = sys.stdin.read
def main():
data = input().split()
idx = 0
n = int(data[idx])
idx += 1
arr = []
for i in range(n):
arr.append(int(data[idx + i]))
idx += n
prefix = [0] * (n + 1)
s = 0
for i in range(n):
s += arr[i]
prefix[i + 1] = s
res = []
while idx < len(data):
a, b = int(data[idx]), int(data[idx + 1])
idx += 2
res.append(prefix[b + 1] - prefix[a])
for r in res:
print(r)
if __name__ == '__main__':
main()
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q4. KamaCoder 44
思路：依旧采用前缀和数组，但需要对行和列分别求前缀和，表示前i行或者前j列的总和
import sys
input = sys.stdin.read
def main():
data = input().split()
idx = 0
n, m = int(data[idx]), int(data[idx + 1])
idx += 2
s = 0
arr = []
for i in range(n):
row = []
for j in range(m):
num = int(data[idx])
idx += 1
s += num
row.append(num)
arr.append(row)
h = [0] * (n + 1)
for i in range(n):
h[i + 1] += h[i]
for j in range(m):
h[i + 1] += arr[i][j]
v = [0] * (m + 1)
for j in range(m):
v[j + 1] = v[j]
for i in range(n):
v[j + 1] += arr[i][j]
res = float('inf')
for i in range(n):
res = min(res, abs(s - 2 * h[i + 1]))
for j in range(m):
res = min(res, abs(s - 2 * v[j + 1]))
print(res)
if __name__ == '__main__':
main()
复杂度分析
时间复杂度：O($n*m$) 空间复杂度：O($\max{(n,m)}$)