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

2024-04-23 14:20

本文主要是介绍代码随想录算法训练营day1 | 704. 二分查找、27. 移除元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,需要移动其他元素的地址。

那么二维数组在内存的空间地址是连续的么?不同编程语言的内存管理是不一样的,以C++为例,在C++中二维数组是连续分布的。

704. 二分查找

看题解之前

二分查找,前提是有序数组。数组元素重复的话返回值不唯一

区间的定义不要改变,根据区间定义确定边界条件

使用左闭右闭
  1. while left <= right 左闭右闭的情况下,left==right是有效的
  2. if target < nums[mid]: right = mid - 1 此时mid已经不满足条件,在左闭右闭的情况下,需要移动到有效区间上
  3. if target > nums[mid]: left = mid + 1
  4. 初始化 right = len(nums) - 1
class Solution:def search(self, nums: List[int], target: int) -> int:# 左闭右闭区间left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if target < nums[mid]:right = mid - 1elif target > nums[mid]:left = mid + 1else:return midreturn -1
使用左闭右开
  1. while left < right 左闭右开的情况下,left==right是没有意义的
  2. if target < nums[mid]: right = mid 此时mid不满足条件,在左闭右开的情况下,right可以移动到mid上
  3. if target > nums[mid]: left = mid + 1 左区间一直是有效的
  4. 初始化 right = len(nums)
class Solution:def search(self, nums: List[int], target: int) -> int:# 左闭右开区间left = 0right = len(nums)while left < right:mid = left + (right - left) // 2if target < nums[mid]:right = midelif target > nums[mid]:left = mid + 1else:return midreturn -1

看题解之后

区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)

35.搜索插入位置

有序数组且数组元素不重复,可以使用二分查找。只有最后返回的时候不一样,返回left的值

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 左闭右闭区间left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if target < nums[mid]:right = mid - 1elif target > nums[mid]:left = mid + 1else:return midreturn leftclass Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 左闭右开区间left = 0right = len(nums)while left < right:mid = left + (right - left) // 2if target < nums[mid]:right = midelif target > nums[mid]:left = mid + 1else:return midreturn left

34. 在排序数组中查找元素的第一个和最后一个位置

有序数组,但是数组元素不唯一,找到元素的第一个和最后一个位置。有序数组的话就可以使用二分查找了,重复元素会让题目变得复杂

直接看题解,先寻找左右边界,然后根据寻找到的左右边界进行判定

情况一:

target 在数组范围的右边或者左边,例如数组{3, 4, 5},target为2或者数组{3, 4, 5},target为6,此时应该返回{-1, -1}

此时代码中在寻找左右边界时有一个边界为初始值

情况二:

target 在数组范围中,且数组中不存在target,例如数组{3,6,7},target为5,此时应该返回{-1, -1}

此时代码left_border = 0, right_border = 1

情况三:

target 在数组范围中,且数组中存在target,例如数组{3,6,7},target为6,此时应该返回{1, 1}

此时代码left_border = 0, right_border = 2

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 寻找左边界def getLeftBorder(nums, target):# 左闭右闭区间left = 0right = len(nums) - 1left_border = -2while left <= right:mid = left + (right - left) // 2if target <= nums[mid]:right = mid - 1left_border = rightelse:left = mid + 1return left_borderdef getRightBorder(nums, target):# 左闭右闭区间left = 0right = len(nums) - 1right_border = -2while left <= right:mid = left + (right - left) // 2if target < nums[mid]:right = mid - 1else:left = mid + 1right_border = leftreturn right_borderleft_border = getLeftBorder(nums, target)right_border = getRightBorder(nums, target)# 情况一if left_border == -2 or right_border == -2:return [-1, -1]# 情况三if right_border - left_border > 1:return [left_border+1, right_border-1]# 情况二return [-1, -1]

69.x 的平方根

思路:使用二分查找的思路,left=0,right=x,得到mid,mid的平方和x进行比较。主要是思考返回值

class Solution:def mySqrt(self, x: int) -> int:left = 0right = xwhile left <= right:mid = left + (right - left) // 2if mid * mid > x:right = mid - 1elif mid * mid < x:left = mid + 1else:return midreturn right

看了其中一个题解,这种提前确定答案的也比较好理解

  • mid * mid > x时,mid肯定不能满足条件,r=mid-1
  • mid * mid <= x时,mid有可能满足条件
class Solution:def mySqrt(self, x: int) -> int:l, r, ans = 0, x, -1while l <= r:mid = (l + r) // 2if mid * mid <= x:ans = midl = mid + 1else:r = mid - 1return ans

367.有效的完全平方数

这个题目和平方根实质是一样的,更简单一点,都不用考虑返回值

class Solution:def isPerfectSquare(self, num: int) -> bool:left = 1right = numwhile left <= right:mid = left + (right - left) // 2if mid * mid == num:return Trueelif mid * mid < num:left = mid + 1else:right = mid - 1return False

27. 移除元素

暴力法:第一层循环遍历每个元素,在遇到val时,循环后移所有元素

双指针法:快指针对应循环遍历,慢指针对应排除掉val元素后的序列

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

26.删除排序数组中的重复项

class Solution:def removeDuplicates(self, nums: List[int]) -> int:# 使用快慢指针,快指针进行循环遍历,慢指针对应删除重复元素后的序列slow = 1for i in range(1, len(nums)):if nums[i] != nums[slow-1]:nums[slow] = nums[i]slow += 1return slow

283.移动零

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 和移除元素一个意思,val==0的特殊情况slow = 0for i in range(len(nums)):if nums[i] != 0:nums[slow] = nums[i]slow += 1# 对剩下的元素赋值为0for i in range(slow, len(nums)):nums[i] = 0

844.比较含退格的字符串

可以使用栈的思路;也可以从字符串后面开始比较,定义常量skip记录当前待删除的字符的数量

977.有序数组的平方

指针指向两端,数值大的放在结果数组结尾

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:res = [0] * len(nums)i = 0j = len(nums) - 1index = jwhile i <= j:if nums[i] * nums[i] <= nums[j] * nums[j]:res[index] = nums[j] * nums[j]j -= 1else:res[index] = nums[i] * nums[i]i += 1index -= 1return res

这篇关于代码随想录算法训练营day1 | 704. 二分查找、27. 移除元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929031

相关文章

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN