代码随想录算法训练营第一天 | 704.Binary Search, 27.Remove Element

 day1大纲：第一章 数组part01

LeetCode 704 Binary Search 链接

核心点：二分法、二分法边界条件

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1

        start = 0
        end = len(nums) - 1
        
        while(start <= end):
            mid = ( start + end ) // 2

            if target < nums[mid]:
                end = mid - 1
            elif target > nums[mid]:
                start = mid + 1
            else:
                return mid
                
        return -1

• 二分法思路很简单，但写的时候，边界条件常常成为很容易出错的点，因此我想清楚多练习。
• 首先选择“左闭右闭”的思路，“左闭右闭”是指左边界left和右边界right都能取到。在本题，左边界left=0一直可以取到，有边界right=len(nums)-1.而如果是左闭右开，则右边界right=len(nums),取不到。
• 在“左闭右闭”，while循环=合法条件。即left<=right合法，就是while条件。
• 对于while内部的if条件，因为target < nums[mid]，因此已经排除了答案是nums[mid]的可能，因此肯定是mid-1.
• 2504：在写各种括号内的条件时，事关越界的判断要放在前面，这样能避免“真的越界”而导致的报错；
• 2504:一个刷了好几道题的有用经验，当你不知道循环的条件是否有等号时，则只要是合法的情况都算；

Leetcode 27. Remove Element

核心点：快慢指针

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0

        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

• 这题非常巧妙，暴力解决的话，你还要考虑你用来替换的新元素会不会还是val，所以我甚至不知道怎么写，感觉太多循环和if嵌套了。
• 我原来的思路局限在，如何找到无效元素（值为val），然后用后面的有效元素覆盖过来。
• 老师的妙绝方法是，我找到有效的元素，放到最新合适的位置。
• 时隔1年多后重新做这道题，我直接用了最佳算法，但写法略笨，用了两种while循环过滤不符合的下标，但过程中出现了“下表越界”错误，因此提示，
  • (1)当使用while时（尤其是子while），变量自增，一定在括号内加入变量越界判断；
  • (2)若前面有while对一个变量自增，下面还要用这个变量，那下面要加入变量越界判断；

还有59天，加油！