子串 & 数组 & 矩阵（精选答案）

子串

(1) 和为 k 的子数组（前缀和）

"""
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数
输入：nums = [1,2,3], k = 3
输出：2
"""
res = 0
presums = collections.defaultdict(int)
presums[0] = 1
presum = 0
for num in nums:
    presum += num
    # 每个前缀和 presum-k 代表着一个和为 k 的子数组
    res += presums[presum-k]
    presums[presum] += 1
return res

(2) 滑动窗口最大值（优先队列）

"""
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧，返回滑动窗口中的最大值
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
"""
res = []
q = collections.deque()
for i, num in enumerate(nums):
    # 维护 q 的单调性
    while q and nums[q[-1]] <= num:
        q.pop()
    q.append(i)
    if i-q[0] >= k:
        q.popleft()
    if i >= k-1:
        res.append(nums[q[0]])
return res

(3) 最小覆盖子串

"""
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
"""
need = collections.Counter(t)   
missing = len(t)                
left = 0                       
start = 0                      
min_len = float('inf')          
for right, char in enumerate(s):
    if need[char] > 0:
        missing -= 1
    need[char] -= 1
    while missing == 0:
        if right-left+1 < min_len:
            start = left
            min_len = right-left+1
        need[s[left]] += 1
        if need[s[left]] > 0:
            missing += 1
        left += 1
return "" if min_len == float('inf') else s[start:start+min_len]

数组

(1) 最大子数组和

"""
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
"""
res = float('-inf')
pre_sums = float('-inf')
for num in nums:
    pre_sums = max(pre_sums+num, num)
    res = max(res, pre_sums)
return res

(2) 合并区间

"""
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
"""
intervals.sort(key=lambda p: p[0])
res = []
for p in intervals:
    if res and res[-1][-1] >= p[0]:
        res[-1][-1] = max(res[-1][-1], p[1])
    else:
        res.append(p)
return res

(3) 轮转数组

"""
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
"""
def reverse(i, j):
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1
n = len(nums)
k %= n
reverse(0, n-1)
reverse(0, k-1)
reverse(k, n-1)

(4) 除了自身以外数组的乘积

"""
给你一个整数数组 nums，返回 数组 reswer ，其中 reswer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积
"""
n = len(nums)
pre = [1] * n
suf = [1] * n
for i in range(1, n):
    pre[i] = pre[i-1] * nums[i-1]
for i in range(n-2, -1, -1):
    suf[i] = suf[i+1] * nums[i+1]
return [p*s for p, s in zip(pre, suf)]

(5) 缺失的第一个正数

"""
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。
输入：nums = [1,4,0]
输出：2
"""
for a in nums:
    while 0 < a <= len(nums) and a != nums[a-1]:
        nums[a-1], a = a, nums[a-1]
for i in range(len(nums)):
    if i+1 != nums[i]:
        return i+1
return len(nums)+1

(6) 排序问题

def quicksort(nums, left, right):
    if left >= right:
        return
    pivot = random.randint(left, right)
    nums[left], nums[pivot] = nums[pivot], nums[left]
    pivot = left
    i, j = left, right
    while i < j:  
        while i < j and nums[j] >= nums[pivot]:  
            j -= 1
        while i < j and nums[i] <= nums[pivot]: 
            i += 1
        nums[i], nums[j] = nums[j], nums[i]  
    nums[pivot], nums[j] = nums[j], nums[pivot] 
    quicksort(nums, left, j-1) 
    quicksort(nums, j+1, right) 
    return

def mergesort(nums, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    mergesort(nums, left, mid)
    mergesort(nums, mid + 1, right)
    merge(nums, left, mid, right)

def merge(nums, left, mid, right):
    temp = []
    i = left       
    j = mid + 1     
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            temp.append(nums[i])
            i += 1
        else:
            temp.append(nums[j])
            j += 1
    while i <= mid:
        temp.append(nums[i])
        i += 1
    while j <= right:
        temp.append(nums[j])
        j += 1
    for k in range(len(temp)):
        nums[left + k] = temp[k]

矩阵

(1) 矩阵置零

"""
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
"""
zero_pos = []  
for ind, row in enumerate(matrix):
    for idx, val in enumerate(row):
        if val == 0:
            zero_pos.append(idx)
            matrix[ind] = [0] * len(row)  
        else:
            continue
for pos in set(zero_pos):
    for row in range(len(matrix)):
        matrix[row][pos] = 0  

(2) 螺旋矩阵

"""
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
"""
if not matrix: return []
l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
while True:
    for i in range(l, r + 1): res.append(matrix[t][i])
    t += 1
    if t > b: break
    for i in range(t, b + 1): res.append(matrix[i][r])
    r -= 1
    if l > r: break
    for i in range(r, l - 1, -1): res.append(matrix[b][i])
    b -= 1
    if t > b: break
    for i in range(b, t - 1, -1): res.append(matrix[i][l])
    l += 1
    if l > r: break
return res

# another solution
result = []
while matrix:
    result += matrix.pop(0)
    matrix = list(zip(*matrix))[::-1]
return result

(3) 旋转图像

"""
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
"""
n = len(matrix)
for i in range(n//2):
    for j in range((n+1)//2):
        tmp = matrix[i][j]
        matrix[i][j] = matrix[n-1-j][i]
        matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
        matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
        matrix[j][n-1-i] = tmp

(4) 搜索二维矩阵

"""
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
"""
i, j = 0, len(matrix[0])-1
while i < len(matrix) and j >= 0:
    if matrix[i][j] == target:
        return True
    elif matrix[i][j] < target:
        i += 1
    else:
        j -= 1
return False