贪心算法（2）

embedded/2024/11/25 21:42:57/

目录

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/embedded/140484.html

相关文章

Java项目实战II基于微信小程序的南宁周边乡村游平台（开发文档+数据库+源码）

Java项目实战II基于微信小程序的南宁周边乡村游平台（开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 随着城市化…
阅读更多...
Python 编程开发（01）：Bash 命令行基本操作

Python 编程开发（01）：Bash 命令行基本操作

Bash 是一种功能强大的 shell 语言&#xff08;或命令行语言&#xff09;&#xff0c;广泛用于 Unix 和 Unix-like 操作系统&#xff0c;如 Linux 和 macOS。它提供了一个交互式界面&#xff0c;允许用户输入命令以执行各种操作&#xff0c;如文件管理、程序执行、网络配置等。…
阅读更多...
MySQL 数据库连接池爆满问题排查与解决

MySQL 数据库连接池爆满问题排查与解决

目录 MySQL 数据库连接池爆满问题排查与解决 一、问题影响 二、问题确认 三、收集信息 四、SQL 语句分析 五、应用层代码分析 六、连接池配置检查 七、监控工具使用 八、案例分析 在实际的应用开发中&#xff0c;我们可能会遇到 MySQL 数据库连接池爆满的情况。这种情…
阅读更多...
node.js中使用express.static()托管静态资源

node.js中使用express.static()托管静态资源

express.static()定义 express.static(root, [options])是一个中间件函数&#xff0c;负责为Express应用提供静态资源服务。它允许你指定一个或多个目录作为静态资源的根目录&#xff0c;当客户端请求这些资源时&#xff0c;Express会查找并返回对应的文件。 安装express npm i…
阅读更多...
周末总结(2024/11/24)

周末总结(2024/11/24)

工作 人际关系核心实践&#xff1a; 要学会随时回应别人的善意&#xff0c;执行时间控制在5分钟以内 坚持每天早会打招呼 遇到接不住的话题时拉低自己&#xff0c;抬高别人(无阴阳气息) 朋友圈点赞控制在5min以内&#xff0c;职场社交不要放在5min以外 职场的人际关系在面对利…
阅读更多...
计算机网络（14）ip地址超详解

计算机网络（14）ip地址超详解

先看图&#xff1a; 注意看第三列蓝色标注的点不会改变&#xff0c;A类地址第一个比特只会是0&#xff0c;B类是10&#xff0c;C类是110&#xff0c;D类是1110&#xff0c;E类是1111. IPv4地址根据其用途和网络规模的不同&#xff0c;分为五个主要类别&#xff08;A、B、C、D、…
阅读更多...
HarmonyOS Next 简单上手元服务开发

HarmonyOS Next 简单上手元服务开发

HarmonyOS Next 简单上手元服务开发 万物互联时代&#xff0c;人均持有设备量不断攀升&#xff0c;设备种类和使用场景更加多样&#xff0c;使得应用开发、应用入口变得更加复杂。在此背景下&#xff0c;应用提 供方和用户迫切需要一种新的服务提供方式&#xff0c;使应用开发…
阅读更多...
oracle的静态注册和动态注册

oracle的静态注册和动态注册

oracle的静态注册和动态注册 静态注册&#xff1a; 静态注册 : 指将实例的相关信息手动告知 listener 侦 听 器 &#xff0c; 可以使用netmgr,netca,oem 以及直接 vi listener.ora 文件来实现静态注册&#xff0c;在动态注册不稳定时使用&#xff0c;特点是&#xff1a;稳定&…
阅读更多...
最新文章

Copyright @ 2022~2023