二分#背包#快排#LCS详解

2024-06-10 14:36
文章标签 详解 二分 背包 快排 lcs

本文主要是介绍二分#背包#快排#LCS详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二分#背包#快排#LCS详解

文章目录

  • 二分#背包#快排#LCS详解
    • 1. 二分搜索
    • 2. 01背包问题
    • 3. 快速排序
    • 4. 最长公共子序列

1. 二分搜索

在处理大规模数据集时,查找操作的效率显得尤为重要。二分搜索是一种在有序数组中查找目标值的高效算法,其时间复杂度为O(log n)。

二分搜索通过每次比较目标值与数组中间元素的大小来缩小搜索范围。每次比较后,搜索范围缩小一半,直到找到目标值或搜索范围为空。

二分搜索适用于以下场景:

  1. 快速查找有序数组中的目标值。
  2. 数据库系统中常用二分搜索在B树或B+树索引中查找记录。
  3. 需要在算法中频繁查找数据的场景,如在排序数据中查找特定元素。

力扣 LCR 068. 搜索插入位置
给定一个排序的整数数组 nums 和一个整数目标值 target ,请在数组中找到 target ,并返回其下标。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:
输入: nums = [1], target = 0
输出: 0

提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

案例代码

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l,r=0,len(nums)-1while l<=r:mid=(l+r)//2if nums[mid]==target:return midelif nums[mid]>target:r=mid-1else :l=mid+1return l

2. 01背包问题

C/C++详解地址:01背包和完全背包

背包问题是一类经典的优化问题,涉及在给定容量的背包中选择物品以使得背包内物品的总价值最大化。

0/1背包问题通过动态规划解决,使用一个二维数组 dp 来记录每个子问题的解。dp[i][w] 表示前 i 个物品在背包容量为 w 时的最大价值。

背包问题适用于以下场景:

  1. 在有限资源下,如何选择最优方案以获得最大收益。
  2. 在有限资金下选择投资组合以最大化收益。
  3. 在有限预算下选择项目组合以最大化回报。

例题
在这里插入图片描述

动态规划:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)

Python代码实现

n,v=map(int,input().split())
dp=[[0]*(v+1) for i in range(n+1)] # [[0]*cols for i in range(rows)]for i in range(1,n+1):wi,vi=map(int,input().split())for j in range(0,v+1):if j>=wi:dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi)else:dp[i][j]=dp[i-1][j]print(dp[n][v])

3. 快速排序

快速排序是一种高效的排序算法,其平均时间复杂度为O(n log n)。快速排序通过分治法将数组分成两部分,递归地排序每部分。

快速排序通过选择一个基准元素(pivot),将数组分为两部分,一部分小于基准元素,另一部分大于基准元素。然后递归地对这两部分进行排序。

快速排序适用于以下场景:

  1. 处理大规模数据集的排序任务。
  2. 大多数编程语言的内置排序函数都采用了快速排序或其变种。
  3. 在数据分析和处理过程中,对数据进行排序以便后续操作。

力扣 4. 排序数组
给你一个整数数组 nums,请你将该数组升序排列。

示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

python代码示例

class Solution:def sortArray(self, nums: List[int]) -> List[int]:def partition(arr, low, high):pivot = arr[low]                                        left, right = low, high     while left < right:while left<right and arr[right] >= pivot:          right -= 1arr[left] = arr[right]                             while left<right and arr[left] <= pivot:         left += 1arr[right] = arr[left]                        arr[left] = pivot          return leftdef randomPartition(arr, low, high):pivot_idx = random.randint(low, high)                   arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]     return partition(arr, low, high)def quickSort(arr, low, high):if low >= high:            return     mid = randomPartition(arr, low, high)   quickSort(arr, low, mid-1)            quickSort(arr, mid+1, high)quickSort(nums, 0, len(nums)-1)             return nums

4. 最长公共子序列

C/C++详解地址:LCS、LIS模型详解

最长公共子序列(LCS)是指在两个序列中,找出长度最长的公共子序列。

LCS通过动态规划解决,使用一个二维数组 dp 来记录每个子问题的解。dp[i][j] 表示 text1[0..i-1]text2[0..j-1] 的LCS长度。

LCS适用于以下场景:

  1. 文本比较:在文本处理和比较中,用于查找两个文本的相似度。
  2. 版本控制:在版本控制系统中,用于计算两个版本之间的差异。
  3. 生物信息学:在基因序列分析中,用于查找DNA序列的相似部分。

python代码示例

def LCS(a, b):n = len(a)m = len(b)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, m + 1):if a[i - 1] == b[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[n][m]n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))result = LCS(a, b)
print(result)

如果对Golang、Mysql、Linux感兴趣的小伙伴,也可以关注我的公众号0.o
在这里插入图片描述

这篇关于二分#背包#快排#LCS详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

一文详解如何从零构建Spring Boot Starter并实现整合

《一文详解如何从零构建SpringBootStarter并实现整合》SpringBoot是一个开源的Java基础框架,用于创建独立、生产级的基于Spring框架的应用程序,:本文主要介绍如何从... 目录一、Spring Boot Starter的核心价值二、Starter项目创建全流程2.1 项目初始化(

Spring Boot3虚拟线程的使用步骤详解

《SpringBoot3虚拟线程的使用步骤详解》虚拟线程是Java19中引入的一个新特性,旨在通过简化线程管理来提升应用程序的并发性能,:本文主要介绍SpringBoot3虚拟线程的使用步骤,... 目录问题根源分析解决方案验证验证实验实验1:未启用keep-alive实验2:启用keep-alive扩展建

Java异常架构Exception(异常)详解

《Java异常架构Exception(异常)详解》:本文主要介绍Java异常架构Exception(异常),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. Exception 类的概述Exception的分类2. 受检异常(Checked Exception)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ