代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

发布时间:2024年01月24日

记录刷题Day1

704.二分查找

斜体样式了解了左闭右闭[left,right]和左闭右开[left,right)两种方式

  • 一、采用左闭右闭时,while条件中应遵从闭区间原则,为left< = right,具体代码如下:
    def search(self,nums,target):
        n=len(nums)
    #左闭右闭- 存在r==l的情况
        l=0
        r=n-1
        while(l<=r):
            mid=int(l+(r-l)/2)#防止溢出
            if(nums[mid]>target):#target在[mid+1,right]范围内,mid一定不是target,所以直接取mid+1
                l=mid+1
            elif(nums[mid]<target):#target在[left,mid-1]范围内,mid一定不是target
                r=mid-1
            else:
                return mid
        return -1
  • 二、左闭右开时,while条件和right的取值都有不同,因为选择了右开,那么右的取值就不需要-1。代码如下:
    def search2(self,nums,target):
        n=len(nums)
    #左闭右开- 不存在r==l
        l=0
        r=n
        while(l<r):
            mid=int(l+(r-l)/2)#防止溢出
            if(nums[mid]>target):# target在[middle + 1, right)中,右开所以直接取mid
                r=mid
            elif(nums[mid]<target):
                l=mid-1
            else:
                return mid
        return -1

27. 移除元素

前言:关于快慢指针,一开始只粗略看了Carl的思路就直接写,然后就发现逻辑不对,倒回去再仔细看了文章和视频,才捋清楚。弄清楚了快慢指针的作用,后面就迎刃而解。

快指针:用来遍历数组 以找到满足不等于目标值的元素,所以它怎么都会 +1让循环运作并结束。
慢指针:收集符合要求的元素,那么只有在符合要求的时候才会刷新数组并前进。所以slow++只会在刷新数组的时候,找到不等于val的元素时来+1.

class Solution(object):
    def removeElement(self, nums, val):
        n=len(nums)
        fast=0 #要遍历整个数组,怎么都会+1的
        slow=0 #收集符合要求的元素,那么只有在符合要求的时候才会刷新数组并前进
        while(fast<n):
            if(nums[fast]!=val):
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow

总结

还是得沉下心,读懂思路、弄清逻辑,然后刷题。这样时间不会浪费,并且可以多刷几个题型相似的来练习。

文章来源:https://blog.csdn.net/sinat_39417731/article/details/135833162
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。