数组矩阵杂题
原创
双指针
42. 接雨水
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6Solution
暴力法：n方，每个位置求左右最大值
以下方法O(3n)，res[i] = min(left_max, right_max)，一次性求好左边最大值和右边最大值
class Solution:
def trap(self, height) -> int:
if len(height) <= 2: return 0
left_max, right_max = [height[0]] + [0]*(len(height)-1), [0]*(len(height)-1) + [height[-1]]
res = 0
for i in range(1, len(height)):
left_max[i] = max(left_max[i-1], height[i])
for i in reversed(range(len(height)-1)):
right_max[i] = max(right_max[i+1], height[i])
for i in range(1, len(height)-1):
cur = min(left_max[i-1], right_max[i+1]) - height[i]
res += cur if cur>0 else 0
return resSolution - 双指针
class Solution(object):
def trap(self, height):
if not height: return 0
left, right = 0, len(height)-1
res = 0
left_max = height[0]
right_max = height[-1]
while left <= right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max < right_max:
res = res + left_max - height[left]
left += 1
else:
res = res + right_max - height[right]
right -= 1
return resFollow up是如果不是从天而降的雨水，而是一桶x unit的水，从给定的index往下倒水，最后困住多少水。只讲思路
11. 盛最多水的容器
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49Solution
思路(并不是自己想的)：Reference，左右双指针，l从前往后，r从后往前，每次移动l和r中较小的值，算当前面积
class Solution:
def maxArea(self, height: List[int]) -> int:
if not height: return 0
res = 0
l, r = 0, len(height)-1
while l < r:
res = max(res, (r-l)*min(height[l],height[r]))
if height[l] <= height[r]:
l += 1
else:
r -= 1
return res数组
239. 滑动窗口最大值 - H
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7Note: You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.
Follow up: Could you solve it in linear time?
Solution - 暴力
class Solution:
def maxSlidingWindow(self, nums, k: int):
if not nums: return []
res = []
for end in range(k, len(nums)+1):
start = end-k
res += [max(nums[start:end])]
return resSolution - 单调队列
On时间，Ok空间
from collections import deque
class MonotonicQueue:
def __init__(self):
self.data = deque()
def push(self, x):
while self.data and self.data[-1] < x:
self.data.pop()
self.data.append(x)
def max(self):
return self.data[0]
def pop(self, x):
if self.data and self.data[0] == x:
self.data.popleft()
class Solution(object):
def maxSlidingWindow(self, nums, k):
res =[]
window = MonotonicQueue()
for i in range(len(nums)):
if i < k-1:
window.push(nums[i])
else:
window.push(nums[i])
res += [window.max()]
window.pop(nums[i-k+1])
return res41. 缺失的第一个正数
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3Example 2:
Input: [3,4,-1,1]
Output: 2Example 3:
Input: [7,8,9,11,12]
Output: 1Note:
Your algorithm should run in O(n) time and uses constant extra space.
class Solution:
def firstMissingPositive(self, nums) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 151.上一个排列
Given a list of integers, which denote a permutation.
Find the previous permutation in ascending order.
The list may contains duplicate integers.
Example 1:
Input:[1]
Output:[1]Example 2:
Input:[1,3,2,3]
Output:[1,2,3,3]Example 3:
Input:[1,2,3,4]
Output:[4,3,2,1]Solution
从后往前找顺序的第一个i，然后找i后面比i小的最大值j，swap(i,j), reverse[i+1:]
class Solution:
def previousPermuation(self, nums):
if len(nums) <= 1: return nums
i = len(nums) - 1
while i > 0 and nums[i] >= nums[i - 1]:
i -= 1
if i == 0: return nums[::-1]
j = len(nums) - 1
while nums[j] >= nums[i - 1]:
j -= 1
nums[i-1], nums[j] = nums[j], nums[i-1]
return nums[:i] + list(reversed(nums[i:]))重新写吧朋友， Reference
Follow up: 下一个排列
238. 除自身之外的乘积
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]Note: Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
思路：遍历一遍算i位左边乘积，遍历一遍算i位右边乘积
矩阵
48. 旋转图像 - M
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]Solution
找规律直接计算对应位置
54. 螺旋矩阵 - M
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]Solution
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
res = []
while top <= bottom and left <= right:
#从左到右
for i in range(left, right+1):
res.append(matrix[top][i])
top += 1
if top > bottom: break
#从上到下
for i in range(top, bottom+1):
res.append(matrix[i][right])
right -= 1
if left > right: break
#从右到左
for i in range(right, left-1, -1):
res.append(matrix[bottom][i])
bottom -= 1
#从下到上
for i in range(bottom, top-1, -1):
res.append(matrix[i][left])
left += 1
return res思路：寻常思路，一直逆时针旋转
304. 2D区域和检索(不可变)
Range Sum Query 2D - Immutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12Note: You may assume that row1 ≤ row2 and col1 ≤ col2.
powcai， init里面一次性求好ij位置左上方的sum
等于黄色的部分总和 - 两个橙色总和 + 红色部分 （ 因为我们发现当我们减去橙色部分， 红色部分多删除一次）
Math
204. 计算质数
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.Solution
ladong， Onloglogn
class Solution(object):
def countPrimes(self, n):
if n<=2: return 0
isPrime = [True]*(n)
for i in range(2, int(n**0.5)+1):
if isPrime[i]:
# i 的倍数不可能是素数
for j in range(2*i, n, j + i):
isPrime[j] = False
cnt=0
for p in isPrime:
if p: cnt+=1
return cnt-2原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
