贪心算法（2）

server/2024/11/26 3:20:40/

目录

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/server/144970.html

相关文章

Java技术分享

Java技术分享

剖析equals方法 1、对于Object来说&#xff0c;其equals()方法底层实现就是""&#xff0c;都是比较对象的引用是否相等&#xff0c;下为JDK源码。 Object c 1; Object d 1; boolean equals c.equals(d);public boolean equals(Object obj) {return (this obj);…
阅读更多...
【v5lite】调用onnx推理

【v5lite】调用onnx推理

前言一、主线程二、推理线程thred_nms（非极大值抑制阈值）的作用thred_cond（置信度阈值）的作用三、串口线程总览@改善版本总结前言 跟着博主导入的加以修改的，反正v5lite的版本要是1.4版本的，不然容易出现错误！ 后面再去把博主的博文导进来 树莓派4B运行yolov5lite转onn…
阅读更多...
java实现小程序接口返回Base64图片

java实现小程序接口返回Base64图片

文章目录 引言I java 接口返回Base64图片接口设计获取验证码图片-base64字符串获取验证码图片-二进制流arraybufferII 小程序端代码过期代码： 显示文件流图片（arraybuffer）知识扩展：微信小程序下载后端返回的文件流引言 场景： 图形验证码 背景: 接口返回arraybuffer的格式…
阅读更多...
Linux应用编程(C语言编译过程)

Linux应用编程(C语言编译过程)

目录 1. 举例 2.预处理 2.1 预处理命令 2.2 .i文件内容解读 3.编译 4.汇编 5.链接 5.1 链接方式 5.1.1 静态链接 5.1.2 动态链接 5.1.3 混合链接 1. 举例 Linux的C语言开发&#xff0c;一般选择GCC工具链进行编译&#xff0c;通过下面的例子来演示GCC如何使用&#…
阅读更多...
大语言模型---RewardBench 介绍；RewardBench 的主要功能；适用场景

大语言模型---RewardBench 介绍；RewardBench 的主要功能；适用场景

文章目录 1. RewardBench 介绍2. RewardBench 的主要功能3. 适用场景 1. RewardBench 介绍 RewardBench: Evaluating Reward Models是一个专门用于评估 Reward Models&#xff08;奖励模型&#xff09; 的公开平台&#xff0c;旨在衡量模型在多种任务上的性能&#xff0c;包括…
阅读更多...
Rust 力扣 - 2266. 统计打字方案数

Rust 力扣 - 2266. 统计打字方案数

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 这题可以先求按了多少次相同连续的按钮&#xff0c;所有的连续相同按钮表示的方案数的乘积就是本题答案 我们的关键问题就转换成了按n个连续相同按钮表示的方案数 设f(i)表示按i个连续相同按钮表示的方案数 如…
阅读更多...
P8692 [蓝桥杯 2019 国 C] 数正方形：结论，组合数学

P8692 [蓝桥杯 2019 国 C] 数正方形：结论，组合数学

题目描述 在一个 NNNN 的点阵上&#xff0c;取其中 44 个点恰好组成一个正方形的 44 个顶点&#xff0c;一共有多少种不同的取法&#xff1f; 由于结果可能非常大&#xff0c;你只需要输出模 10971097 的余数。 如上图所示的正方形都是合法的。 输入格式 输入包含一个整数 …
阅读更多...
第十章 JavaScript的应用课后练习

第十章 JavaScript的应用课后练习

第一题 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>实时走动的数字时钟</title><style type"text/css">body{margin: 0;padding: 0;height: 100vh;text-decoration: none;text-align: center;}.…
阅读更多...
最新文章

Copyright @ 2022~2023