贪心算法入门(三)

相关文章

贪心算法入门(一)-CSDN博客

贪心算法入门(二)-CSDN博客

1.什么是贪心算法?

        贪心算法是一种解决问题的策略,它将复杂的问题分解为若干个步骤,并在每一步都选择当前最优的解决方案,最终希望能得到全局最优解。这种策略的核心在于“最优”二字,意味着我们追求的是以最少的时间和精力,快速获得正确的结果。

        然而,“希望得到全局最优解”就表示贪心算法并不意味着一定能得到全局最优解。实际上,并不是所有问题都可以通过贪心策略解决。为了确保贪心策略的有效性,需要对其进行严格的证明。而且,不同的问题往往需要采用不同的贪心策略。

        如果你觉得这一点仍然比较抽象,接下来我将通过5道具体的例题来详细说明贪心算法的应用及其背后的思路。

2. 按身高排序

2418. 按身高排序 - 力扣(LeetCode)

这道题要求很简单,根据身高排序,但是输出的是名字。对身高排序很简单,可以直接用sort,但是真正需要排序的数组是name姓名数组。但是比较方法又是根据身高比较的,所以想一个办法绑定这两个数组。可以使用一个中间数组index下标数组,里面存放每个下标,然后对index数组排序,比较的规则可以自己写入用身高大小排序。排序之后的index数组就是按照身高下标来排序的了,比如index[0]的值为2就表示身高最高的人的下标为2,那么应该先输出name[2]的值。

2.1 代码实现

class Solution {public String[] sortPeople(String[] names, int[] heights) {int n = names.length;Integer[] index = new Integer[n];for(int i = 0; i < n; i++) index[i] = i;Arrays.sort(index, (a, b) -> heights[b] - heights[a]);String[] ret = new String[n];for(int i = 0; i < n; i++) ret[i] = names[index[i]];return ret;}
}

3. 优势洗牌

870. 优势洗牌 - 力扣(LeetCode)

题目解析:可以任意重组nums1的顺序,并且该顺序可以让nums1和nums2依次比较大小时,nums1优胜的次数更多。

该题的贪心策略跟田忌赛马很像,可以对nums1和nums2数组都按从小到大排序。然后再依次比较如果第一个位置nums1就小于nums2,相当于两个数组最小的值比较nums1都输了,此时把这个最小的数去匹配nums2最大的数,然后nums1再用下一个数继续比较nums2的数。依次类推。这样做的好处就是知道nums1最小的数已经对于nums2中的任何数字都取得不了优胜了,那么就不要选择匹配当前nums2最小的数,选择匹配最大的数,这样就可以留着nums1最大的数去匹配nums2前面的数,增大优胜的概率。

上图为整个逻辑流程图,依次扫描nums1数组的每个数,每次扫描都可以确定扫描的数匹配nums2的哪一个数。匹配规则为当前nums1扫描的数小于等于nums2[left]的数就让其匹配nums2[right]的数,否则匹配nums2[left]的数。

还需要注意的一点,这样的做法并不是最终答案,因为我们只能改变nums1的顺序不能改变nums2的,要根据原有的nums2的顺序,去填入nums1的值。所以该题依然需要一个中间变量下标数组去绑定两个数组下标的对应关系。

3.1 代码实现

class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums1.length;Integer[] index = new Integer[n];for(int i = 0; i < n; i++) index[i] = i;Arrays.sort(index, (i, j) -> nums2[i] - nums2[j]);Arrays.sort(nums1);int[] ret = new int[n];int right = n - 1, left = 0;for(int x : nums1){if(x  > nums2[index[left]]) ret[index[left++]] = x; // index[left]表示当前nums2最小值的下标else ret[index[right--]] = x; // index[right]表示当前nums2最大值的下标}return ret;}
}

4. 最长回文串

409. 最长回文串 - 力扣(LeetCode)

这道题要构造回文串,构成回文串有两种可能,一种是回文串中每个字母都是偶数,这样可以对称的分为两边构成回文,还有一种是偶数对称之后,中间单夹一个任意字母。

故这道题的贪心思路很简单,首先就需要统计字符串中每个字母的个数,这里可以有一个优化的小tip就是不适用map表来统计,而是使用数组来代替map表,因为大小字母的asc码值最大也不超过126,所以新建一个大小为126的int数组就可以将所有字母的个数统计完整。

继续优化:可以在循环字符串时一边统计字母个数时一边更新长度,因为只要统计到当前字母的个数等于2了,就可以把它往回文串里面加,让ret长度加2,然后再让hash表中该字母的个数重置为0。现在还有一个问题,当循环完成之后就是最终答案了吗?其实不是,因为循环里面统计长度的规则只考虑了偶数回文串的情况,这时需要判断ret的值是否小于字符串s的长度,如果小于说明还可以有单的字母加进去,这个字母可以是字符串中剩下字母中的任何一个。那么此时更新ret加1,否则直接返回ret。

4.1 代码实现

class Solution {public int longestPalindrome(String s) {int[] hash = new int[126];char[] ss = s.toCharArray();int ret = 0;for(char ch : ss){hash[ch] += 1;if(hash[ch] == 2){ret += 2;hash[ch] = 0;}}return ret < s.length() ? ret + 1 : ret;}
}

5. 增减字符串

942. 增减字符串匹配 - 力扣,然后(LeetCode)

 题目解析:输出的int数组中每个位置的值都是由0-n组成的,n为s字符串的长度。每个位置的值要根据s字符串的字母确定,例如示例1中,s字符串的长度为4,所以最终返回的int数组长度为n + 1。s字符串中第一个字母是I表示,int数组要进行上升,比如0到4就是一个上升。第二个字母是D表示要下降,4到1就是下降。以此类推。

贪心策略,遇到字母是I上升趋势的时候,确定当前int数组的数字为0-n中剩下可以挑选的数字中的最小的一个,因为选择最小的一个下一个位置的数字就只用受下一个字母的条件限制,而不用管上一个字母的限制,因为此时的任何数字都会比最小的数字大。拿示例1举例,第一个字母是I,如果此时int数组不选择0选择其他数字比如1。第二个字母是D,选择的数字不能是0和1,1被选过了,也不能选0因为0比1小,不满足第一个字母的I。但是如果第一次选择0,第二次选择数字的时候就不用考虑前一个字母的条件,因为剩下的数字1-n都比0大,所以只用考虑第二个字母D下降,同理此时应该选择最大的数字n,因为下一个选择的数字都可以从剩下的数中任意挑选,并且肯定满足条件。

5.1 代码实现

class Solution {public int[] diStringMatch(String s) {int n = s.length();int[] ret = new int[n + 1];int left = 0, right = n;for(int i = 0; i < n; i++){if(s.charAt(i) == 'I') ret[i] = left++;else ret[i] = right--;}ret[n] = left;return ret;}
}

6. 分发饼干

455. 分发饼干 - 力扣(LeetCode)

 这道题跟优势洗牌思路一样,就是对两个数组进行排序,然后依次比较,如果不满足当前孩子的胃口就让饼干数组往后一位继续比较知道满足为止。贪心的策略就是尽量用小的饼干尺寸去满足孩子胃口。

6.1 代码实现

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); Arrays.sort(s);int ret = 0;for(int i = 0, j = 0; i < g.length && j < s.length; j++){if(s[j] >= g[i]){i++; ret++;}}return ret;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/473800.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT仿QQ聊天项目,第三节,实现聊天界面

一&#xff0c;界面控件示意图 界面主要由按钮QPushButton,标签QLabel,列表QListWidget 要注意的是QListWidget既是实现好友列表的控件&#xff0c;也是实现聊天气泡的控件 二&#xff0c;控件样式 QPushButton#btn_name {border:none;}QPushButton#btn_close {border:1px;bac…

Gin 框架入门(GO)-1

解决安装包失败问题(*) go env -w GO111MODULE=on go env -w GOPROXY=https://goproxy.cn,direct 1 介绍 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架,运行速度非常快,Gin 最擅长的就是 Api 接口的高并发。 2 Gin 环境搭建 1.下载并安装 gin go get -u github.…

workerman的安装与使用

webman是一款基于workerman开发的高性能HTTP服务框架。webman用于替代传统的php-fpm架构&#xff0c;提供超高性能可扩展的HTTP服务。你可以用webman开发网站&#xff0c;也可以开发HTTP接口或者微服务。 除此之外&#xff0c;webman还支持自定义进程&#xff0c;可以做worker…

学习日记_20241117_聚类方法(高斯混合模型)

前言 提醒&#xff1a; 文章内容为方便作者自己后日复习与查阅而进行的书写与发布&#xff0c;其中引用内容都会使用链接表明出处&#xff08;如有侵权问题&#xff0c;请及时联系&#xff09;。 其中内容多为一次书写&#xff0c;缺少检查与订正&#xff0c;如有问题或其他拓展…

开源音乐分离器Audio Decomposition:可实现盲源音频分离,无需外部乐器分离库,从头开始制作。将音乐转换为五线谱的程序

今天给大家分析一个音频分解器&#xff0c;通过傅里叶变换和信封匹配分离音乐中的各个音符和乐器&#xff0c;实现音乐到乐谱的转换。将音乐开源分离为组成乐器。该方式是盲源分离&#xff0c;从头开始制作&#xff0c;无需外部乐器分离库。 相关链接 代码&#xff1a;https:…

多模态基础模型:从专家到通用助手

概要 本文对展示视觉和视觉语言能力的多模态基础模型的分类和演变进行了全面调查&#xff0c;重点关注从专业模型到通用助手的过渡。研究领域包括五个核心主题&#xff0c;分为两类。&#xff08;i&#xff09; 我们从对成熟研究领域的调查开始&#xff1a;为特定目的预先训练…

Nature Communications 基于触觉手套的深度学习驱动视触觉动态重建方案

在人形机器人操作领域&#xff0c;有一个极具价值的问题&#xff1a;鉴于操作数据在人形操作技能学习中的重要性&#xff0c;如何有效地从现实世界中获取操作数据的完整状态&#xff1f;如果可以&#xff0c;那考虑到人类庞大规模的人口和进行复杂操作的简单直观性与可扩展性&a…

ReactPress与WordPress:一场内容管理系统的较量

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress WordPress官网&#xff1a;https://wordpress.org/ ReactPress与WordPress&#xff1a;一场内容管理系统的较量 在当今数字化时代&#xff0c;内容管理系统&#xff08;CMS&#xff09;已成为…

解决Windows远程桌面 “为安全考虑,已锁定该用户账户,原因是登录尝试或密码更改尝试过多。请稍后片刻再重试,或与系统管理员或技术支持联系“问题

当我们远程连接服务器连接不上并提示“为安全考虑&#xff0c;已锁定该用户账户&#xff0c;原因是登录尝试或密码更改尝试过多。请稍候片刻再重试&#xff0c;或与系统管理员或技术支持联系”时&#xff0c;根本原因是当前计算机远程连接时输入了过多的错误密码&#xff0c;触…

Cyberchef配合Wireshark提取并解析TCP/FTP流量数据包中的文件

前一篇文章中讲述了如何使用cyberchef提取HTTP/TLS数据包中的文件,详见《Cyberchef配合Wireshark提取并解析HTTP/TLS流量数据包中的文件》,链接这里,本文讲述下如何使用cyberchef提取FTP/TCP数据包中的文件。 FTP 是最为常见的文件传输协议,和HTTP协议不同的是FTP协议传输…

vs2022搭建opencv开发环境

1 下载OpenCV库 https://opencv.org/ 下载对应版本然后进行安装 将bin目录添加到系统环境变量opencv\build\x64\vc16\bin 复制该路径 打开高级设置添加环境变量 vs2022新建一个空项目 修改属性添加头文件路径和库路径 修改链接器&#xff0c;将OpenCV中lib库里的o…

构建SSH僵尸网络

import argparse import paramiko# 定义一个名为Client的类&#xff0c;用于表示SSH客户端相关操作 class Client:# 类的初始化方法&#xff0c;接收主机地址、用户名和密码作为参数def __init__(self, host, user, password):self.host hostself.user userself.password pa…

【开源免费】基于SpringBoot+Vue.JS购物推荐网站(JAVA毕业设计)

博主说明&#xff1a;本文项目编号 T 073 &#xff0c;文末自助获取源码 \color{red}{T073&#xff0c;文末自助获取源码} T073&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…

PG-DERN 解读:少样本学习、 双视角编码器、 关系图学习网络

本文提出了一种用于 分子属性预测 的 少样本学习&#xff08;Few-shot Learning&#xff09; 模型—— PG-DERN&#xff0c;该模型结合了 双视角编码器&#xff08;Dual-view Encoder&#xff09; 和 关系图学习网络&#xff08;Relation Graph Learning Network&#xff09; 双…

RabbitMQ-死信队列(golang)

1、概念 死信&#xff08;Dead Letter&#xff09;&#xff0c;字面上可以理解为未被消费者成功消费的信息&#xff0c;正常来说&#xff0c;生产者将消息放入到队列中&#xff0c;消费者从队列获取消息&#xff0c;并进行处理&#xff0c;但是由于某种原因&#xff0c;队列中的…

Uni-APP+Vue3+鸿蒙 开发菜鸟流程

参考文档 文档中心 运行和发行 | uni-app官网 AppGallery Connect DCloud开发者中心 环境要求 Vue3jdk 17 Java Downloads | Oracle 中国 【鸿蒙开发工具内置jdk17&#xff0c;本地不使用17会报jdk版本不一致问题】 开发工具 HBuilderDevEco Studio【目前只下载这一个就…

Python中的with语句

with语句和上下文管理器 Python提供了 with 语句的写法&#xff0c;既简单又安全 文件操作的时候使用with语句可以自动调用关闭文件操作&#xff0c;即使出现异常也会自动关闭文件操作。 # 1、以写的方式打开文件 with open(1.txt, w) as f:# 2、读取文件内容f.write(hello wor…

SQL面试题——抖音SQL面试题 主播播出时长

主播播出时长 现有如下数据,主播id、房间号、播出的批次号,每个批次号进出房间的时间戳、分区时间: 每一次直播都有一个上播和下播,每个房间里,同一个批次号会有两条数据,分别记录了上播和下播时间,求每个主播的播出时长? 通过上面的数据,可以清晰的看出,同一个批次…

【汇编】c++游戏开发

由一起学编程创作的‘C/C项目实战&#xff1a;2D射击游戏开发&#xff08;简易版&#xff09;&#xff0c; 440 行源码分享来啦~’&#xff1a; C/C项目实战&#xff1a;2D射击游戏开发&#xff08;简易版&#xff09;&#xff0c; 440 行源码分享来啦~_射击c-CSDN博客文章浏览…

Uniapp 引入 Android aar 包 和 Android 离线打包

需求&#xff1a; 原生安卓 apk 要求嵌入到 uniapp 中&#xff0c;并通过 uniapp 前端调起 app 的相关组件。 下面手把手教你&#xff0c;从 apk 到 aar&#xff0c;以及打包冲突到如何运行&#xff0c;期间我所遇到的问题都会 一 一 进行说明&#xff0c;相关版本以我文章内为…