Leetcode 167. 两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解题思路：
双指针算法，一个指针从左往右遍历，一个从右往左遍历，直到两个指针上的数值相加为target。
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
n = len(numbers)
left = 0
right = n-1
while left != right:
if numbers[left] + numbers[right] > target:
right -= 1
elif numbers[left] + numbers[right] < target:
left += 1
else:
return [left + 1, right + 1]
Leetcode 88. 合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解题思路：双指针算法，两个指针分别从两个数组的最大数的地方开始遍历，然后把最大值放到nums1的末尾，注意最后nums1已经遍历完但nums2还没有遍历完时，需要把nums2剩下的部分复制到nums1中去。
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
p = m + n - 1
p1 = m - 1
p2 = n - 1
while p1 >= 0 and p2 >= 0 and p >= 0:
if nums1[p1] >= nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
elif nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
while p2 >= 0 and p >= 0:
nums1[p] = nums2[p2]
p -= 1
p2 -= 1
return nums1
Leetcode 26. 删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。
解题思路：双指针算法，一个指针进行遍历，另一个指针记录unique元素的位置。
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return len(nums)
p1 = 0
p2 = 0
nums[p2] = nums[p1]
p1 += 1
p2 += 1
while p1 <= len(nums) - 1:
if nums[p1] == nums[p1-1]:
p1 += 1
else:
nums[p2] = nums[p1]
p2 += 1
p1 += 1
return p2
Leetcode 76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
class Solution:
def minWindow(self, s: 'str', t: 'str') -> 'str':
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
start = 0
end = 0
min_len = float("inf")
counter = len(t)
res = ""
while end < len(s):
if lookup[s[end]] > 0:
counter -= 1
lookup[s[end]] -= 1
end += 1
while counter == 0:
if min_len > end - start:
min_len = end - start
res = s[start:end]
if lookup[s[start]] == 0:
counter += 1
lookup[s[start]] += 1
start += 1
return res
Leetcode 32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解题思路：
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
left = 0
right = 0
for i in range(n):
if s[i] == '(':
left += 1
else:
right += 1
if left == right:
ans = max(ans, right * 2)
if left < right:
left = 0
right = 0
left = 0
right = 0
for i in range(n-1, -1, -1):
if s[i] == '(':
left += 1
else:
right += 1
if left == right:
ans = max(ans, right * 2)
if right < left:
left = 0
right = 0
return ans
Leetcode 155. 最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解题思路：构建两个栈，一个存储最小值，一个存储所有值。
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack_min = []
self.stack_value = []
def push(self, x: int) -> None:
self.stack_value.append(x)
if self.stack_min == [] or x <= self.stack_min[-1]:
self.stack_min.append(x)
def pop(self) -> None:
if self.stack_min[-1] == self.stack_value[-1]:
self.stack_min = self.stack_min[:-1]
self.stack_value = self.stack_value[:-1]
def top(self) -> int:
return self.stack_value[-1]
def getMin(self) -> int:
return self.stack_min[-1]
Leetcode 42. 接雨水
解题思路：图片.png
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
ans = 0
left_max = [0 for _ in range(n)]
right_max = [0 for _ in range(n)]
if n == 0:
return n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
for i in range(n):
ans += (min(left_max[i], right_max[i]) - height[i])
return ans
Leetcode 84. 柱状图中的最大矩形
图片.png
解题思路：单调栈
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
stack = [-1]
ans = 0
for i in range(len(heights)):
while heights[i] < heights[stack[-1]]:
top = stack.pop()
h = heights[top]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)
return ans
Leetcode 239. 滑动窗口最大值
图片.png
解题思路：单调队列
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if nums == [] or k == 0:
return None
n = len(nums)
ans = []
queue = []
for i in range(n):
if queue != [] and queue[0] == i - k:
queue.pop(0)
while queue != [] and nums[queue[-1]] < nums[i]:
queue.pop()
queue.append(i)
if i >= k - 1:
ans.append(nums[queue[0]])
return ans
Leetcode 918. 环形子数组的最大和
图片.png
class Solution:
def maxSubarraySumCircular(self, A: List[int]) -> int:
curMax, sumMax, curMin, sumMin, total = 0, -float("inf"), 0, float("inf"), 0
for a in A:
curMax = max(a + curMax, a)
sumMax = max(sumMax, curMax)
curMin = min(a + curMin, a)
sumMin = min(sumMin, curMin)
total += a
return max(sumMax, total-sumMin) if sumMax>0 else sumMax
