收获:

• 抓住循环不变量
• 双指针入门, 学会精准定义

• 704
• 思路
• 错误解法
• 解题方法
• Code
• 27
• 思路
• 解题方法
• Code

704

Problem: 704. 二分查找

思路

讲述看到这一题的思路

思路比较混乱, 没有抓住循环不变量, 要有数学的严谨

错误解法

我的错误写法1: 循环不变量不统一

def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1 #左臂右闭区间
        while l<r:  #左闭右开区间=>矛盾!
            m = int((l+r+1)/2)
            a = nums[m]
            if a==target:
                return m
            elif a>target:
                r=m
            else:
                l=m
        return -1

我的错误写法2.0:

def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while l<r:
            m = int((l+r)/2)
            a = nums[m]
            if a==target:
                return m
            elif a>target:
                r=m-1 #左闭右开区间, r=m
            else:
                l=m+1
        return -1

解题方法

描述你的解题方法

抓住循环不变量, 采用左闭右开区间

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)
        while l<r:
            m = int((l+r)/2)
            a = nums[m]
            if a==target:
                return m
            elif a>target:
                r=m
            else:
                l=m+1
        return -1
            

27

Problem: 27. 移除元素

思路

讲述看到这一题的思路

双指针

解题方法

描述你的解题方法

关键: 如何定义快指针和慢指针

• i: 用于遍历
• j: 新数组的最后一个

Code

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        j = -1
        length = len(nums)
        while i < length:
            if nums[i] != val:
                j = j+1
                nums[j] = nums[i]
                i = i+1
            else:
                while i < length and nums[i] == val:
                    i += 1
                if i<length:
                    j += 1
                    nums[j] = nums[i]
                    i += 1                  
        return j+1