LeetCode题解随笔——二分查找、双指针、滑动窗口相关题目 不断更新
二分查找
LC704 二分查找
- 题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
# 在[left,right]区间内查找
while left <= right: # 定义了左闭右闭区间，这里就要等于，因为有意义
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target: # 中间值大，目标值在左边，mid已经验证不相等，取mid-1
right = mid-1
else: # 中间值小，目标在右侧，取mid+1
left = mid+1
return -1
LC35 搜索插入位置
-
题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left <= right:
middle = int((left+right) / 2)
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
# 二分查找找到最后，如果没找到的话，一定是right在left左边一个格，right=left-1. 此时返回right+1或者left即可。
return left
双指针
LC27 移除数组元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 双指针法
# 然后从题目的「要求/保留逻辑」出发，来决定当遍历到任意元素 x 时，应该做何种决策：
# 如果当前元素 num 与移除元素 val 相同，那么跳过该元素。
# 如果当前元素 num 与移除元素 val 不同，那么我们将其放到下标 idx 的位置，并让 idx 自增右移。
# 最终得到的 idx 即是答案。
idx = 0
for num in nums:
if num != val:
nums[idx] = num
idx += 1
return idx
LC26
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
# 数组删除操作挺有意思的，只要没出现要删的元素，就一直是慢指针自己赋值给自己。出现要删的元素了，慢指针就不动了，下一次赋值就覆盖了
i = 0
for j in range(len(nums)-1):
if nums[j] != nums[j+1]:
i += 1
nums[i] = nums[j+1]
return i+1
# 如果是删除重复，只保留k个，删除逻辑就是
# 1、如果 idxLC844 比较退格的字符串
用栈来实现比较方便，自己写的，详见LC
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
# 用一个栈保存字符
# 遇到字母就入栈，遇到#就从栈里弹出，栈为空时跳过
def calString(text):
stack = []
for c in text:
if c != ‘#‘:
stack.append(c)
else:
if len(stack) == 0:
continue
else:
stack.pop()
return stack
return calString(s) == calString(t)
LC11 盛水最多的容器
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
# 双指针 左右指针分别在两头 每次计算面积，更新最大面积
# 移动逻辑是 两个指针 高度小的那个移动，才能保证下一次的面积比这次的大
left, right = 0, len(height) - 1
area = 0
maxarea = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
maxarea = max(maxarea, area)
if height[left] <= height[right]:
left += 1
else:
right -= 1
return maxarea
滑动窗口
LC209 长度最小的子数组
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# 维护滑动窗口和 sum minlen
add = 0
minlen = len(nums) + 1
# 这里的终止条件要加上数组的和小于tar的情况，这种情况minlen不会更新。
if len(nums) == 0: return 0
if sum(nums) < target: return 0
start = 0
for end in range(len(nums)):
# 这里把数字加进去
add += nums[end]
# start往前走 窗口收缩的逻辑就是大于，只要大于就记录最小值，不断调整。
while add >= target:
minlen = min(minlen, end-start+1)
add -= nums[start]
start += 1
return minlen
LC904 水果成篮
求只包含两种元素的最长子数组的长度，滑动窗口+字典
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
# 只包含两个数字的最长子串的长度
# 滑动窗口 字典匹配
dic = {}
maxLen = 0
start = 0
for end in range(len(fruits)):
# 不断保存end遇到的新数字到字典中
tail = fruits[end]
dic[tail] = dic.get(tail, 0) + 1
# 水果种类小于等于2，符合要求，更新最大长度
if len(dic) <= 2:
maxLen = max(maxLen, end-start+1)
# 水果种类大于2，不断调整start位置直到满足要求
while len(dic) > 2:
head = fruits[start]
dic[head] -= 1
if dic[head] == 0:
del dic[head]
start += 1
return maxLen
原文：https://www.cnblogs.com/xhmorehair/p/15306599.html