贪心算法（2）

news/2024/11/25 19:39:38/

目录

K次取反后最大化的数组和

题解：

代码：

按身高排序（田忌赛马的预备）

题解：

代码：

方法一：

方法二： 

优势洗牌（田忌赛马）

题解：

代码：

最长回文串

题解：

代码：

增减字符串匹配

题解：

代码： 

分发饼干（田忌赛马）

题解：

代码：

最优除法

题解：

代码：

K次取反后最大化的数组和

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

题解：

为了最大化数组和，就要对数组中最小的 k 个数取反，我们统计出数组中负数的个数 m，

如果 m >= k，那么我们只需要对这 k 个负数取反，就可以得到最大的数组和；

如果 m < k，我们结合具体例子讨论，如下图所示，m = 4，

将所有的负数取反后，操作数剩下 k - m 次， 为了得到最大的数组和，我们只需要考虑如何操作取反后数组的最小值：

  • 如果  k - m 为偶数，那么我们无需操作取反后数组的最小值，因为负负得正，数组和不变；
  • 如果  k - m 为奇数，那么取反后数组的最小值取负值即可。

代码：

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int minNum=INT_MAX,ret=0,n=nums.size(),m=0;for(auto x:nums){if(x<0) m++;minNum=min(minNum,abs(x));//找出绝对值最小的数}if(m>k)//负数的个数大于k，反转前k小负数{sort(nums.begin(),nums.end());for(int i=0;i<k;i++)ret+= -nums[i];for(int i=k;i<n;i++)ret+=nums[i];}else//负数的个数小于等于k，有的数字被多次反转{for(auto x:nums)ret+=abs(x);//反转所有负数if((k-m)%2)//有的数被反转奇数次{ret-=minNum*2;}}return ret;}
};

按身高排序（田忌赛马的预备）

2418. 按身高排序 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/sort-the-people/description/

题解：

这道题有两种方法：

方法一：

用 pair 或者 struct 创建一个二元组，二元组的内容为姓名和对应的身高，将所有的二元组放入数组中，再对数组根据身高排序，排序后按照顺序把名字提取出来即可。

或者用哈希表，定义 map< int, string > hash，把身高和姓名放进哈希表中，再根据身高排序即可。

方法二：

因为姓名、身高和下标是一一对应的关系，如果只是对身高排序，身高和下标原本的对应关系就被打乱了，就无法根据身高的下标找到对应的姓名了。

如图所示，原本 165 、John 对应 1 号下标，只对身高排序后，下标为 1 的身高变为 170，John 再次根据下标 1 去找自己的身高时，身高变成 170 了。 

为了保留身高、姓名和下标的对应关系， 我们可以重开一个数组 tmp，tmp 存的是身高数组的下标，新建一个排序规则，根据身高对下标排序，但不改变身高数组。

如下图，由于下标为 1 的身高165 小于 下标为 2 的身高 170，所以交换 tmp 中元素 1 和 2 的位置，tmp 排序后的最终顺序为 [ 0, 2, 1 ]，然后遍历 tmp 数组，height[ tmp[0] ] 就是 Mary，height[ tmp[1] ] 就是 Emma，height[ tmp[2] ] 就是 John。

代码：

方法一：

class Solution {
public:struct person{string name;int height;}p[1010];vector<string> sortPeople(vector<string>& names, vector<int>& heights) {int n=names.size();for(int i=0;i<n;i++){p[i].name=names[i];p[i].height=heights[i];}sort(p,p+n,[](const struct person a,const struct person b){   return a.height>b.height;   });for(int i=0;i<n;i++){names[i]=p[i].name;}return names;}
};

方法二： 

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {int n=names.size();vector<int> tmp(n);for(int i=0;i<n;i++){tmp[i]=i;//初始化}sort(tmp.begin(),tmp.end(),[&](int a,int b){   return heights[a]>heights[b]; });vector<string> ret;for(int i=0;i<n;i++){ret.push_back(names[tmp[i]]);}return ret;}
};

优势洗牌（田忌赛马）

870. 优势洗牌 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/advantage-shuffle/description/

题解：

我们对 nums1 和 nums2 排升序，以示例二为例，排序后 nums1 = [ 8, 12, 24, 32 ] ，nums2 = [ 11, 13, 25, 32 ]，我们 用 i 遍历 nums1 ，用 left 指向 nums2 的较小数，right 指向 nums2 的较大数：

  • 如果 nums1[ i ] > nums2[ left ] ，说明 nums1[ i ] 有优势，i++，left++，去匹配下一对优势数；
  • 如果 nums1[ i ] <= nums2[ left ]，说明该数没有优势，没有优势的数应该去拖累 nums2 的较大数，即 nums1[ i ] 和 nums2[ right ] 匹配，然后 i++，right -- . 因为 nums2[ left ]  后面的数更大，nums1[ i ] 更没有优势了，继续匹配还不如去拖累较大数。

为了不打乱nums2 的下标和数字的相对位置，在排序 nums2 时，用了 按身高排序的 排序方法，即只排序下标。

代码：

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size();vector<int> index(n);for(int i=0;i<n;i++)index[i]=i;sort(nums1.begin(),nums1.end());//排升序sort(index.begin(),index.end(),[&](const int a,const int b){return nums2[a]<nums2[b];});vector<int> ret(n);int left=0,right=n-1;for(auto x:nums1){if(x>nums2[index[left]])ret[index[left++]]=x;elseret[index[right--]]=x;}return ret;}
};

最长回文串

409. 最长回文串 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-palindrome/description/

题解：

为了得到回文串，就需要让字符串对称轴左右两侧的字母一一对应。

从下图可以看出，

  • 如果回文串的长度为偶数，则每个字母的个数为偶数；
  • 如果回文串的长度为奇数，则除了对称轴上的字母的个数为奇数之外，其余字母的个数为偶数。

统计提供的字符串 s 的每个字母出现的次数，

  • 如果某字母出现的次数为偶数，说明这个字母可以直接加入回文串；
  • 如果某字母出现的次数为奇数，为了得到最长的回文串， 只放入偶数个该字母，且这个偶数要尽可能大。

上述过程得到的回文串的长度为偶数，我们可以考虑一下对称轴上是否可以放一个字母，这里有一个小巧思，

  • 如果得到的回文串的长度 ==  s 的长度，说明 s 中每个字母出现的次数都是偶数，已经没有多余的字母可以让我们放在对称轴上了；
  • 如果得到的回文串的长度 <  s 的长度，说明 s 中至少存在一个字母出现的次数为奇数，我们只需要让个数为奇数个的这个字母放在对称轴上，放一个就可以了，最后让回文串的长度 +1。

代码：

class Solution {
public:int longestPalindrome(string s) {int ret=0;vector<int> count(256);for(auto x:s)count[x]++;for(auto x:count){ret+=(x/2*2);}return ret<s.size()?ret+1:ret;}
};

增减字符串匹配

942. 增减字符串匹配 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/di-string-match/description/

题解：

定义两个指针 left 和 right，left 初始化为 0，right 初始化为 1，用 i 遍历字符串 s，将结果存在数组 ret 中：

  • 如果 s[ i ] == ' I '，说明 ret[ i+1 ] > ret[ i ] ，即上升趋势，如果 ret[ i ] 的数字选得很大，上升的趋势很快，若后面出现连续的上升趋势，剩下的数字可能没办法满足上升的需求了，所以需要选择比较小的数字，减缓上升的趋势，而 left 指向的就是比较小的数，故 ret[ i ] = left，left++，指向下一个数；
  • 如果 s[ i ] == ' D '，说明 ret[ i+1 ] < ret[ i ] ，即下降趋势，如果 ret[ i ] 的数字选得很小，下降的趋势很快，若后面出现连续的下降趋势，剩下的数字可能没办法满足下降的需求了，所以需要选择比较大的数字，减缓下降的趋势，而 right 指向的就是比较小的数，故 ret[ i ] = right，right --，指向下一个数；
  • 因为 s 的长度为 n，而我们需要排 n+1 个数，最后 left 和 right 一定会相遇，指向同一个数，把这个数放在数组最后即可。

代码： 

class Solution {
public:vector<int> diStringMatch(string s) {int n=s.size();vector<int> ret;int left=0,right=n;for(int i=0;i<n;i++){if(s[i]=='I')   {ret.push_back(left);    left++;}else{ret.push_back(right);   right--;}}ret.push_back(left); return ret;}
};

分发饼干（田忌赛马）

455. 分发饼干 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/assign-cookies/description/

题解：

和田忌赛马的思路大同小异，对胃口 g 和饼干 s 排序，用 i 遍历 g，用 j 遍历 s，

  • 如果 g[ i ] > s[ j ] ，说明当前饼干不符合该小孩的胃口，后面的小孩的胃口就更不符合了，直接舍弃该饼干，即 j++；
  • 如果 g[ i ] <= s[ j ]，说明当前饼干符合该小孩的胃口，该饼干直接给该小孩即可，即 i++，j++.

代码：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int ret=0;  int n1=g.size(),n2=s.size();sort(g.begin(),g.end());//排升序sort(s.begin(),s.end());//排升序int i=0,j=0;while(i<n1 && j<n2){if(g[i]>s[j])   j++;else{i++;    j++;    ret++;}}return ret;}
};

最优除法

553. 最优除法 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/optimal-division/description/

题解：

加括号就是为了尽可能地把除数转为被除数，把放在分母的数放到分子上。

代码：

class Solution {
public:string optimalDivision(vector<int>& nums) {string ret;ret+=to_string(nums[0]);int n=nums.size();if(n==2)ret+="/"+to_string(nums[1]);else if(n>2){ret+="/("+to_string(nums[1]);for(int i=2;i<n;i++){ret+="/"+to_string(nums[i]);}ret+=")";}return ret;}
};

http://www.ppmy.cn/news/1549893.html

相关文章

Python毕业设计选题：基于django+vue的企业it资产管理系统

Python毕业设计选题：基于django+vue的企业it资产管理系统

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 管理员登录 管理员功能界面 员工管理 设备信息管理 设备借用管理 软件信息管理 软件…
阅读更多...
基于python的机器学习（四）—— 聚类（一）

基于python的机器学习（四）—— 聚类（一）

目录 一、聚类的原理与实现 1.1 聚类的概念和类型 1.2 如何度量距离 1.2.1 数据的类型 1.2.2 连续型数据的距离度量方法 1.2.3 离散型数据的距离度量方法 1.3 聚类的基本步骤 二、层次聚类算法 2.1 算法原理和实例 2.2 算法的Sklearn实现 2.2.1 层次聚类法的可视化实…
阅读更多...
重绘重排、CSS树DOM树渲染树、动画加速 ✅

重绘重排、CSS树DOM树渲染树、动画加速 ✅

浏览器下载完页面中的所有组件&#xff0c;HTML标记、JavaScript、CSS、图片后&#xff0c;之后会解析并生成两个内部数据结构&#xff1a;DOM树和渲染树。DOM树表示页面结构&#xff0c;渲染树表示DOM节点如何显示。 ——《高性能JavaScript》 DOM树中的每一个需要显示的节点在…
阅读更多...
OAI-5G开源通信平台实践(五）

OAI-5G开源通信平台实践(五）

参考资料及进阶学习 open5GS 以下为基于oai 5GC + oai gnb + nrue rfsim 在docker中的搭建流程 ci-scripts/yaml_files/5g_rfsimulator develop oai / openairinterface5G GitLab (eurecom.fr) 多UE运行 https://github.com/EpiSci/oai-lte-5g-multi-ue-proxy L2 sim…
阅读更多...
【SQL】【数据库】语句翻译例题

【SQL】【数据库】语句翻译例题

SQL自然语言到SQL翻译知识点 以下是将自然语言转化为SQL语句的所有相关知识点&#xff0c;分门别类详细列出&#xff0c;并结合技巧说明。 1. 数据库操作 创建数据库 自然语言&#xff1a;创建一个名为“TestDB”的数据库。 CREATE DATABASE TestDB;技巧&#xff1a;识别**“创…
阅读更多...
C51数字时钟/日历---LCD1602液晶显示屏

C51数字时钟/日历---LCD1602液晶显示屏

题目要求&#xff1a; 数字电子日历/时钟设计 设计一个基于MCS51的电子日历和时钟。 基本要求 &#xff08;1&#xff09; 可通过按键在日历和时间之间切换显示&#xff1b; &#xff08;2&#xff09; 可由按键调整日期和时间 &#xff08;3&#xff09; 可整点报时&#x…
阅读更多...
docker pull命令拉取镜像失败的解决方案

docker pull命令拉取镜像失败的解决方案

docker pull命令拉取镜像失败的解决方案 简介&#xff1a; docker pull命令拉取镜像失败的解决方案 docker pull命令拉取镜像失败的解决方案 一、执行docker pull命令&#xff0c;拉取镜像失败 报错信息&#xff1a;error pulling image configuration: Get https://produc…
阅读更多...
Linux-Nginx虚拟主机

Linux-Nginx虚拟主机

文章目录 虚拟主机路由规则 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Linux专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月21日9点32分 虚拟主机 配置不同域名不同端口号访问到不同内容 mkdir /data/nginx{1..3} #创建三个…
阅读更多...
最新文章

Copyright @ 2022~2023