双指针
42. 接雨水
Trapping Rain Water
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:
代码语言：javascript复制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)，一次性求好左边最大值和右边最大值
代码语言：javascript复制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 - 双指针
labuladong的讲解
代码语言：javascript复制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. 盛最多水的容器
Container With Most Water
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:
代码语言：javascript复制Input: [1,8,6,2,5,4,8,3,7]
Output: 49Solution
思路(并不是自己想的)：Reference，左右双指针，l从前往后，r从后往前，每次移动l和r中较小的值，算当前面积
代码语言：javascript复制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
Sliding Window Maximum
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:
代码语言：javascript复制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 - 暴力
代码语言：javascript复制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空间
代码语言：javascript复制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 res巨好的单调队列讲解 Python答案
41. 缺失的第一个正数
First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
代码语言：javascript复制Input: [1,2,0]
Output: 3Example 2:
代码语言：javascript复制Input: [3,4,-1,1]
Output: 2Example 3:
代码语言：javascript复制Input: [7,8,9,11,12]
Output: 1Note:
Your algorithm should run in O(n) time and uses constant extra space.
代码语言：javascript复制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:
代码语言：javascript复制Input:[1]
Output:[1]Example 2:
代码语言：javascript复制Input:[1,3,2,3]
Output:[1,2,3,3]Example 3:
代码语言：javascript复制Input:[1,2,3,4]
Output:[4,3,2,1]Solution
从后往前找顺序的第一个i，然后找i后面比i小的最大值j，swap(i,j), reverse[i 1:]
代码语言：javascript复制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:
代码语言：javascript复制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.)
powcai
思路：遍历一遍算i位左边乘积，遍历一遍算i位右边乘积
矩阵
48. 旋转图像 - M
Rotate Image
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:
代码语言：javascript复制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:
代码语言：javascript复制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
powcai
找规律直接计算对应位置
54. 螺旋矩阵 - M
Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
代码语言：javascript复制Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]Solution
两种解法-powcai
代码语言：javascript复制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:
代码语言：javascript复制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 Primes
Count the number of prime numbers less than a non-negative number, n.
Example:
代码语言：javascript复制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
