数组基础#

1
def sliding_window(s):
2
    """
3
    滑动窗口通用模板
4
    s: 输入数组或字符串
5
    """
6
    # 窗口状态记录：如果是频次问题，用字典；如果是总和问题，用整数
7
    window = {}  # 或 window = 0 （如求和）
8

9
    left = 0
10
    result = 初始化结果  # 如 0 / float('inf') / "" / []，根据题意设定
11

12
    for right in range(len(s)):
13
        # 扩大窗口：将右边界元素加入窗口
14
        c = s[right]
15
        # 更新窗口状态
16
        window[c] = window.get(c, 0) + 1  # 或者 window += c（求和问题）
17

18
        # ✅ 当寻找最大子数组/子串时，可以在这里尝试更新结果
19
        # if 满足条件:
20
        #     result = max(result, 当前窗口大小或值)
21

22
        # 当窗口不满足题目要求的约束时，收缩左边界
23
        while left <= right and 窗口不满足条件:
24
            # ✅ 当寻找最小子数组/子串时，应在收缩前更新结果
25
            # if 满足条件:
26
            #     result = min(result, 当前窗口大小或值)
27

28
            # 收缩窗口：将左边界移出窗口
29
            d = s[left]
30
            left += 1
31

32
            # 更新窗口状态
33
            window[d] -= 1
34
            if window[d] == 0:
35
                del window[d]  # 或 window -= d（求和问题）
36

37
        # ✅ 当需要收集所有满足条件的子串/子数组时，在这里更新结果列表
38
        # if 满足条件:
39
        #     result.append(当前窗口或其他信息)
40

41
    return result

1
class Solution:
2
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3
        temp, left, res = 0, 0, float('inf')
4

5
        for right in range(len(nums)):
6
            # 扩大窗口：将右边界元素加入窗口
7
            temp += nums[right]
8

9
            # 当窗口和满足条件时，尝试收缩左边界
10
            # 需要考虑在什么时候需要缩小范围
11
            # 并且可能一直缩小，导致这里只能使用while而不是if
12
            while temp >= target:
13
                # 寻找最小长度，在收缩窗口前更新结果
14
                # 这时候temp必定大于等于target，更新结果
15
                res = min(res, right - left + 1)
16

17
                # 收缩窗口：将左边界元素移出窗口
18
                temp -= nums[left]
19
                left += 1
20

21
        return res if res != float('inf') else 0

1
class Solution:
2
    def totalFruit(self, fruits: List[int]) -> int:
3
        left, wid, res = 0, {}, 0
4

5
        for right in range(len(fruits)):
6
            # 扩大窗口：将右边界元素加入窗口
7
            wid[fruits[right]] = wid.get(fruits[right], 0) + 1
8

9
            # 当窗口中水果种类超过2种时，收缩左边界
10
            while len(wid) > 2:
11
                # 收缩窗口：将左边界元素移出窗口
12
                wid[fruits[left]] -= 1
13
                if wid[fruits[left]] == 0:
14
                    del wid[fruits[left]]
15
                left += 1
16

17
            # 寻找最大长度，在窗口合法时更新结果
18
            # 刚开始把res的更新放在while里面，当wid永远小于2的时候，res永远等于0,出现错误
19
            res = max(res, right - left + 1)
20

21
        return res

1
class Solution:
2
    def minWindow(self, s: str, t: str) -> str:
3
        # 统计目标字符串中每个字符的需求数量
4
        need = {}
5
        for char in t:
6
            need[char] = need.get(char, 0) + 1
7

8
        # valid用于记录有多少种字符已经达到需求
9
        left, min_len, valid, start = 0, float('inf'), 0, 0
10
        wid = {}  # 窗口中字符的计数
11

12
        for right in range(len(s)):
13
            # 扩大窗口：将右边界字符加入窗口
14
            c = s[right]
15
            wid[c] = wid.get(c, 0) + 1
16

17
            # 当某种字符达到需求数量后才更新valid
18
            if c in need and wid[c] == need[c]:
19
                valid += 1
20

21
            # 只有当窗口包含所有需求字符后才开始收缩
22
            while valid == len(need):
23
                # 寻找最小长度，在收缩窗口前更新结果
24
                if right - left + 1 < min_len:
25
                    start = left
26
                    min_len = right - left + 1
27

28
                # 收缩窗口：将左边界字符移出窗口
29
                d = s[left]
30
                left += 1
31

32
                # 当移除的字符刚好使某种字符数量不满足需求时，需要将valid减1
33
                if d in need and wid[d] == need[d]:
34
                    valid -= 1
35
                wid[d] -= 1
36

37
        return "" if min_len == float('inf') else s[start: start + min_len]

1
def traverse_2d_array(matrix):
2
    # 二维数组螺旋遍历通用模板
3
    if not matrix or not matrix[0]:
4
        return []
5

6
    res = []
7
    m, n = len(matrix), len(matrix[0])
8
    up, down, left, right = 0, m - 1, 0, n - 1
9

10
    while up <= down and left <= right:
11
        # 第一步：从左到右遍历上边界
12
        for i in range(left, right + 1):
13
            res.append(matrix[up][i])
14
        up += 1  # 上边界向下移动
15

16
        # 第二步：从上到下遍历右边界
17
        for i in range(up, down + 1):
18
            res.append(matrix[i][right])
19
        right -= 1  # 右边界向左移动
20

21
        # 第三步：从右到左遍历下边界（需要确保还有行）
22
        if up <= down:
23
            for i in range(right, left - 1, -1):
24
                res.append(matrix[down][i])
25
            down -= 1  # 下边界向上移动
26

27
        # 第四步：从下到上遍历左边界（需要确保还有列）
28
        if left <= right:
29
            for i in range(down, up - 1, -1):
30
                res.append(matrix[i][left])
31
            left += 1  # 左边界向右移动
32

33
    return res

1
class Solution:
2
    def generateMatrix(self, n: int) -> List[List[int]]:
3
        # 初始化n×n的零矩阵
4
        res = [[0] * n for _ in range(n)]
5

6
        # 使用四个边界来控制螺旋的方向
7
        up, down, left, right = 0, n - 1, 0, n - 1
8
        count = 1  # 要填入的数字
9

10
        while count <= n * n:
11
            # 从左到右填充上边界
12
            if up <= down:
13
                for i in range(left, right + 1):
14
                    res[up][i] = count
15
                    count += 1
16
                up += 1
17

18
            # 从上到下填充右边界
19
            if left <= right:
20
                for i in range(up, down + 1):
21
                    res[i][right] = count
22
                    count += 1
23
                right -= 1
24

25
            # 从右到左填充下边界
26
            if up <= down:
27
                for i in range(right, left - 1, -1):
28
                    res[down][i] = count
29
                    count += 1
30
                down -= 1
31

32
            # 从下到上填充左边界
33
            if left <= right:
34
                for i in range(down, up - 1, -1):
35
                    res[i][left] = count
36
                    count += 1
37
                left += 1
38

39
        return res

1
class Solution:
2
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
3
        res = []
4
        m, n = len(matrix), len(matrix[0])
5
        up, down, left, right = 0, m - 1, 0, n - 1
6

7
        # 当结果数组长度小于矩阵总元素数时继续遍历
8
        while len(res) < m * n:
9
            if up <= down:
10
                for i in range(left, right + 1):
11
                    res.append(matrix[up][i])
12
                up += 1
13
            if left <= right:
14
                for i in range(up, down + 1):
15
                    res.append(matrix[i][right])
16
                right -= 1
17
            if up <= down:
18
                for i in range(right, left - 1, -1):
19
                    res.append(matrix[down][i])
20
                down -= 1
21
            if left <= right:
22
                for i in range(down, up - 1, -1):
23
                    res.append(matrix[i][left])
24
                left += 1
25

26
        return res

1
def build_prefix_sum(arr):
2
    # 构建一维前缀和数组
3
    n = len(arr)
4
    prefix = [0] * n
5
    temp = 0
6
    for i in range(n):
7
        temp += arr[i]
8
        prefix[i] = temp
9
    return prefix
10

11
def range_sum(prefix, left, right):
12
    # 计算区间[left, right]的和
13
    if left == 0:
14
        return prefix[right]
15
    return prefix[right] - prefix[left - 1]

1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().split()
6
    index = 0
7

8
    n = int(data[index])
9
    index += 1
10
    arr = []
11
    for i in range(n):
12
        arr.append(int(data[index + i]))
13
    index += n
14

15
    p = [0] * n
16
    temp = 0
17
    for i in range(n):
18
        temp += arr[i]
19
        p[i] = temp
20

21
    results = []
22
    while index < len(data):
23
        a = int(data[index])
24
        b = int(data[index + 1])
25
        index += 2
26

27
        if a == 0:
28
            sum_value = p[b]
29
        else:
30
            sum_value = p[b] - p[a - 1]
31

32
        results.append(sum_value)
33

34
    for res in results:
35
        print(res)
36

37
if __name__ == "__main__":
38
    main()

1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().split()
6
    index = 0
7

8
    n, m = int(data[index]), int(data[index + 1])
9
    index += 2
10
    arr = [[0] * m for _ in range(n)]
11
    sum_val = 0
12

13
    for i in range(n):
14
        for j in range(m):
15
            arr[i][j] = int(data[index])
16
            sum_val += arr[i][j]
17
            index += 1
18

19
    row, col = [0] * n, [0] * m
20
    for i in range(n):
21
        for j in range(m):
22
            row[i] += arr[i][j]
23
    for i in range(n):
24
        for j in range(m):
25
            col[j] += arr[i][j]
26

27
    res = float('inf')
28

29
    row_cut = 0
30
    for i in range(n):
31
        row_cut += row[i]
32
        res = min(res, abs(sum_val - 2 * row_cut))
33

34
    col_cut = 0
35
    for i in range(m):
36
        col_cut += col[i]
37
        res = min(res, abs(sum_val - 2 * col_cut))
38

39
    print(res)
40

41
if __name__ == "__main__":
42
    main()