GIS与Climate

V1

2022/09/21阅读:14主题:默认主题

算法60天:Day1-数组之二分查找

想成为一个程序员,算法与数据结构是必须掌握的知识。

算法相关的资源网上太多了,对于非科班的人员来说如何快速、高效的学习数据结构和算法是一件非常难的事儿。

先前都是自己摸索,没有系统的学习。这次跟着Carl师兄刷一遍代码随想录。

代码随想录(截图自参考【1】)
代码随想录(截图自参考【1】)

本系列是代码随想录算法训练营的学习笔记之day1,主要记录一下刷题的过程,以及核心知识点和一些值的记录的问题。

代码随想录的资源都是免费的,具体可以看参考链接【1】。

今日知识点

数组理论基础:

  • 存放相同类型数据;
  • 在内存上是连续的(二维数组视语言而定);
  • 数组元素不能删除,只能覆盖;

今日题目

  1. 二分查找(704)

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

链接:https://leetcode.cn/problems/binary-search

解题思路

  • 充分利用升序的特点,不断对数组进行二分,查找目标元素;
  • 要注意区间问题,也就是说你的判断条件能否遍历到所有的下标
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l,r = 0, len(nums)-1

        while l<=r:
            m = (l+r)//2
            if nums[m]>target:
                r = m-1
            elif nums[m]<target:
                l = m+1
            else:
                return m
        return -1
  1. 移除元素(27)

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

链接:https://leetcode.cn/problems/remove-element

解题思路

  • 要注意原地移除,也就是说不能创建新的数组,所以把要删除的元素放在数组后面即可,使用双指针法,具体使用的时候一个从前往后移动(l指针),一个从后往前移动(r指针),然后把待删除元素移动到后面,不是待删除元素的移动至前面(顺序可以改变,所以无所谓大小排序);
  • 因为要范围新长度,所以要判断最后时刻l指针的元素是否是待删除元素;
  • 要注意当输入数组为None或者空的特殊情况!
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums)==0:
            return 0
        l,r = 0,len(nums)-1
        while l<r:
            while l<r and nums[l]!=val:
                l += 1
            while l<r and nums[r]==val:
                r -= 1
            nums[l],nums[r]=nums[r],nums[l]
        if nums[l]==val:
            return l
        elif nums[l]!=val:
            return l+1

  • while的循环条件不需要使用=,因为l=r的时候两个指针已经重合,就到了最后一步;如果非要使用<=,则代码改为如下:
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums)==0:
            return 0
        l,r = 0,len(nums)-1
        while l<=r:
            while l<r and nums[l]!=val:
                l += 1
            while l<r and nums[r]==val:
                r -= 1
            nums[l],nums[r]=nums[r],nums[l]
            if l==r:
                if nums[l]==val:
                    return l
                elif nums[l]!=val:
                    return l+1

补充知识点

  1. OJ术语

掌握一些常用的术语缩写是非常重要的,下图整理了一些常用的算法刷题相关的术语:

OJ术语汇总-来自群友
OJ术语汇总-来自群友

今日思考

  1. 刷题要不要用库函数?

看清本质,事关核心知识点的考察的就不要用。

  1. 二分查找的时候区间的划分其本质是什么?

遍历到所有元素,做到查无遗漏。

参考

【1】代码随想录:https://programmercarl.com/

分类:

后端

标签:

数据结构与算法

作者介绍

GIS与Climate
V1

公众号:GIS与Climate,欢迎关注