二分#背包#快排#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

相关文章

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

Java使用ANTLR4对Lua脚本语法校验详解

《Java使用ANTLR4对Lua脚本语法校验详解》ANTLR是一个强大的解析器生成器,用于读取、处理、执行或翻译结构化文本或二进制文件,下面就跟随小编一起看看Java如何使用ANTLR4对Lua脚本... 目录什么是ANTLR?第一个例子ANTLR4 的工作流程Lua脚本语法校验准备一个Lua Gramm

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4: