求职力扣刷题 day01---数组,二分法

704. 二分查找

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

**二分法有两种写法, 一种左闭右闭, 一种左闭右开,分别对应为 **

#左闭右闭
left, right = 0, n-1
while left <= right
#左闭右开
left, right = 0, n
while left < right
1
2
3
4
5
6

总之, 遵循循环不变量, 简单来说就是左闭右闭的话, 在循环中,就要target in 新赋值后的[left, right] ,左闭右开对应, target in 新赋值后的 [left, right)区间中

个人习惯于左闭右开, 因为这个可以去寻找第一个大于等于,小于等于的情况,相等的情况也可以

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] == target:
                return mid
            else:
                right = mid
        return -1
1
2
3
4
5
6
7
8
9
10
11
12

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。
写法一

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        #快慢指针
        #fast定义：寻找新数组元素，也就是不包含目标值val的元素
        #slow定义：指向更新 新数组的下标位置
        slow, fast = 0, 0
        while fast < len(nums):
            while fast < len(nums) and nums[fast] == val:
                fast += 1
            if fast < len(nums):
                nums[slow] = nums[fast]
                fast += 1
                slow += 1
        return slow 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

写法二(推荐)
很多时候快慢指针,也可以用for循环写

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        #快慢指针
        #fast定义：寻找新数组元素，也就是不包含目标值val的元素
        #slow定义：指向更新 新数组的下标位置
       	slow = 0
       	for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
       	return slow
1
2
3
4
5
6
7
8
9
10
11