704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

思路：

  • 主要是有三个指针来解决，分别是left，right，mid
  • 分别调整三个指针的指向来找到目标target
  • 如果mid比target小，left赋值为mid+1
  • 如果mid比target大，right赋值为mid-1
  • 如果mid=target，返回mid
  • 否则返回-1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 二分查找即 left right mid的值变化
#控制三个值之间的位置来找到mid
class Solution:
    def search(nums, target):
        left=0
        right=len(nums)-1
        while left<=right:
            mid=left+(right-left)//2
            if(nums[mid]<target):
                left=mid+1
            elif(nums[mid]>target):
                right=mid-1
            else:
                return mid
        return -1  # 未找到目标值
a=Solution
print(a.search([2,3,4,5,6],5))

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

思路：

  • 主要是有三个指针来解决，分别是left，right，mid
  • 分别调整三个指针的指向来找到目标target
  • 如果mid比target小，left赋值为mid+1
  • 如果mid比target大，right赋值为mid-1
  • 如果mid=target，返回mid
  • 否则nums数组中不存在该target，返回要插入的位置right+1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 插入值需要注意不存在值的情况
class Solution:
    def searchInsert(nums, target):
        left,right=0,len(nums)-1
        while left<=right:
            mid=left+(right-left)//2
            if(nums[mid]>target):
                right=mid-1
            elif(nums[mid]<target):
                left=mid+1
            else:
                return mid
        return right+1

a=Solution
print(a.searchInsert([2,3,4,5,6],7))

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？

示例 1：

  • 输入：nums = [5,7,7,8,8,10], target = 8
  • 输出：[3,4]

示例 2：

  • 输入：nums = [5,7,7,8,8,10], target = 6
  • 输出：[-1,-1]

示例 3：

  • 输入：nums = [], target = 0
  • 输出：[-1,-1]

思路：

  • 引入二分查找代码，找到目标target的一个index
  • 对left和right分别赋值index
  • 判断index的最左侧和最右侧的值是否等于target并赋值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from main import Solution

class  Solution1:
    def search1(nums, target):
        a=Solution
        index=a.search(nums,target)
        if index==-1:return [-1,-1]
        left,right=index,index
        while left>0:
            if nums[left-1]==target:
                left -= 1
            else:
                break
        while right<len(nums):
            if nums[right+1]==target:
                right += 1
            else:
                break
        return [left,right]
a=Solution1
print(a.search1([2,3,4,5,5,5,6,7],6))

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路：

  • 采用快慢指针的方式
  • 快指针每轮迭代都往前移动，当对应的值不等于val时，对慢指针进行赋值，此时慢指针移动一格

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 移除元素的思想主要是一个快指针和一个慢指针
# 快指针走在前面找到不等于val的就往前移
class Solution:
    def removeElement(nums, val):
        # 快慢指针
        fast = 0  # 快指针
        slow = 0  # 慢指针
        size = len(nums)
        while fast<size:
            if nums[fast] != val:
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow

a=Solution
print(a.removeElement([2,3,4,5,6,5,6],5))

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

思路：

  • 采用快慢指针的方式
  • 快指针每轮迭代都移动一格，当对应的值不为0时，对慢指针进行赋值，此时慢指针移动一格
  • 当快指针遍历完数组时，对慢指针以后的元素进行0填充

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def moveZeroes( nums):
        slow=0
        fast=0
        while fast<len(nums):
            if nums[fast]!=0:
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        while slow<len(nums):
            nums[slow]=0
            slow+=1
        return nums

a=Solution
print(a.moveZeroes([2,3,0,0,0,4,0,5,6]))

844.比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

1
2
3
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

1
2
3
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

1
2
3
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

思路：

  • 采用快慢指针的方式
  • 快指针每轮迭代都往前移动一格，当快指针遇到‘#’时，慢指针往后退一格，当不为‘#’时，对慢指针所对应的值进行赋值，同时慢指针往前移动一格
  • 当慢指针移到-1时重新赋值为0

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 双指针题目 主要是难点在于要区分是单纯的指针移动还是需要边移动边赋值
# 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
class Solution(object):
    def backspaceCompare(s, t):
        def com(s):
            fast=0
            slow=0
            s=list(s)
            while fast<len(s):
                if s[fast]!='#': # 当前指针不为'#'时，将fast的值赋值给slow
                    s[slow]=s[fast]
                    slow+=1
                else:            # 当前指针为'#'时，slow值回退一格
                    slow-=1
                if slow==-1:
                    slow=0
                fast+=1
            return s[:slow]
        a=''.join(com(s))
        b=''.join(com(t))
        if a==b:
            return True
        else :
            return False
a=Solution
print(a.backspaceCompare("y#fo##f","y#f#o##f"))

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路：

  • 采用左右指针的方式，同时使用一个新数组result来存储比较后的平方值
  • 左指针在最左侧，右指针在数组最右侧
  • 比较左右指针所对应的值的平方值的大小，当左大时，result末尾存储左数组的平方左指针右移一位，result末尾指针左移
  • 当右大时，result末尾存储右指针对应值的平方右指针左移一位，result末尾指针左移

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 这边额外构建一个数组用来存贮计算结果
# 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

class Solution(object):
    def sortedSquares(nums):
        slow=0
        fast=len(nums)-1
        zhizhen=len(nums)-1
        result=[0 for i in range(len(nums))]
        while fast>=slow:
            if pow(nums[fast],2)>=pow(nums[slow],2):
                result[zhizhen]=pow(nums[fast],2)
                fast-=1
            else:
                result[zhizhen]=pow(nums[slow],2)
                slow+=1
            zhizhen-=1
        return result
a=Solution
print(a.sortedSquares([-7,-3,2,3,11]))

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

1
2
3
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2 
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路：

  • 采用滑动窗口的思想，并使用sum1来记录窗口中数组的和，窗口使用快慢指针来控制窗口的起始
  • 遍历条件是fast<len(nums)
  • 当sum1>s时left右移一格，当sum1<s时right右移一格,当sum1=s时，记录子数组的长度同时slow右移一格

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def minSubArrayLen(target, nums):
        length=float("inf")
        sum1=nums[0]
        fast,slow=0,0
        while fast<len(nums):
            if sum1>target:
                sum1-=nums[slow]
                slow += 1
            elif sum1<target:
                fast+=1
                if fast==len(nums):
                    break
                sum1 += nums[fast]
            else:
                if fast-slow+1<length:
                    length=fast-slow+1
                sum1 -= nums[slow]
                slow+=1
        return 0 if length==float("inf") else length

a=Solution
print(a.minSubArrayLen(11,[1,2,3,4,5]))