算法训练营Day 1

704. 二分查找

一定要有区间的概念，注意区间边界，要不然很容易搞错边界条件，惯用写法：左闭右闭。

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

左闭右开:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = len(nums)
        left = 0
        while left < right:
            mid = (right - left) // 2 + left
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid
            else:
                return mid
            print(left, mid, right, nums[mid])
        return -1

题目链接：https://leetcode.cn/problems/binary-search/
文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

27. 移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left=0, right=0;
        while(right < nums.size()){
            if(nums[right]!=val){
                nums[left] = nums[right];
                left++;
            }
            right++;
        }
        return left;
    }
};

python:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left = 0
        for num in nums:
            if num != val:
                nums[left] = num
                left += 1
        return left

还有个优化版本， 减少重复赋值操作，但没太看懂。

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP