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、如果 idx<k 肯定都保留
# 2、如果这个数与前面第k项不相同,就保留; 言外之意跟前面第k个相等就跳过,等下一次赋值把他覆盖
def solve(k):
    idx = 0
    for n in nums:
        if idx < k or nums[u-k] != n:
            nums[idx] = n
            idx += 1
    return idx
return solve(2)

LC844 比较退格的字符串

用栈来实现比较方便,自己写的,详见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

LeetCode题解随笔——二分查找、双指针、滑动窗口相关题目 不断更新

上一篇:《贝贝GO》服务条款


下一篇:能不能快点?