贪心算法入门（三）
相关文章贪心算法入门（一）-CSDN博客
贪心算法入门（二）-CSDN博客
1.什么是贪心算法？
贪心算法是一种解决标题的计谋，它将复杂的标题分解为若干个步骤，并在每一步都选择当前最优的解决方案，最终希望能得到全局最优解。这种计谋的核心在于“最优”二字，意味着我们寻求的是以最少的时间和精力，快速得到精确的结果。
然而，“希望得到全局最优解”就表示贪心算法并不意味着一定能得到全局最优解。实际上，并不是全部标题都可以通过贪心计谋解决。为了确保贪心计谋的有效性，需要对其进行严酷的证明。而且，差别的标题往往需要接纳差别的贪心计谋。
如果你以为这一点仍旧比力抽象，接下来我将通过5道具体的例题来具体说明贪心算法的应用及其背后的思绪。
2. 按身高排序
2418. 按身高排序 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/87ea2783a5934e0083654130970e4069.png
这道题要求很简单，根据身高排序，但是输出的是名字。对身高排序很简单，可以直接用sort，但是真正需要排序的数组是name姓名数组。但是比力方法又是根据身高比力的，所以想一个办法绑定这两个数组。可以使用一个中心数组index下标数组，里面存放每个下标，然后对index数组排序，比力的规则可以自己写入用身高大小排序。排序之后的index数组就是按照身高下标来排序的了，比如index的值为2就表示身高最高的人的下标为2，那么应该先输出name的值。
2.1 代码实现
class Solution {
public String[] sortPeople(String[] names, int[] heights) {
int n = names.length;
Integer[] index = new Integer;
for(int i = 0; i < n; i++) index = i;
Arrays.sort(index, (a, b) -> heights - heights);
String[] ret = new String;
for(int i = 0; i < n; i++) ret = names];
return ret;
}
} 3. 优势洗牌
870. 优势洗牌 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/1153ded8a5cd4138898fccfc24a76ad6.png
标题解析：可以任意重组nums1的次序，而且该次序可以让nums1和nums2依次比力大小时，nums1优胜的次数更多。
该题的贪心计谋跟田忌赛马很像，可以对nums1和nums2数组都按从小到大排序。然后再依次比力如果第一个位置nums1就小于nums2，相当于两个数组最小的值比力nums1都输了，此时把这个最小的数去匹配nums2最大的数，然后nums1再用下一个数继续比力nums2的数。依次类推。这样做的长处就是知道nums1最小的数已经对于nums2中的任何数字都取得不了优胜了，那么就不要选择匹配当前nums2最小的数，选择匹配最大的数，这样就可以留着nums1最大的数去匹配nums2前面的数，增大优胜的概率。
https://i-blog.csdnimg.cn/direct/2ca1349c647d4dbe8b372e2c0ccc205b.png
上图为整个逻辑流程图，依次扫描nums1数组的每个数，每次扫描都可以确定扫描的数匹配nums2的哪一个数。匹配规则为当前nums1扫描的数小于等于nums2的数就让其匹配nums2的数，否则匹配nums2的数。
还需要注意的一点，这样的做法并不是最终答案，由于我们只能改变nums1的次序不能改变nums2的，要根据原有的nums2的次序，去填入nums1的值。所以该题依然需要一个中心变量下标数组去绑定两个数组下标的对应关系。
3.1 代码实现
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
Integer[] index = new Integer;
for(int i = 0; i < n; i++) index = i;
Arrays.sort(index, (i, j) -> nums2 - nums2);
Arrays.sort(nums1);
int[] ret = new int;
int right = n - 1, left = 0;
for(int x : nums1){
if(x> nums2]) ret] = x; // index表示当前nums2最小值的下标
else ret] = x; // index表示当前nums2最大值的下标
}
return ret;
}
} 4. 最长回文串
409. 最长回文串 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/9a9a7244dd4a4d2abbaf4a20c5e055fe.png
这道题要构造回文串，构成回文串有两种可能，一种是回文串中每个字母都是偶数，这样可以对称的分为两边构成回文，另有一种是偶数对称之后，中心单夹一个任意字母。
故这道题的贪心思绪很简单，起首就需要统计字符串中每个字母的个数，这里可以有一个优化的小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;
char[] ss = s.toCharArray();
int ret = 0;
for(char ch : ss){
hash += 1;
if(hash == 2){
ret += 2;
hash = 0;
}
}
return ret < s.length() ? ret + 1 : ret;
}
} 5. 增减字符串
942. 增减字符串匹配 - 力扣，然后（LeetCode）
https://i-blog.csdnimg.cn/direct/a97ac413827c415da2423f1d6a872c31.png
标题解析：输出的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;
int left = 0, right = n;
for(int i = 0; i < n; i++){
if(s.charAt(i) == 'I') ret = left++;
else ret = right--;
}
ret = left;
return ret;
}
} 6. 分发饼干
455. 分发饼干 - 力扣（LeetCode）
https://i-blog.csdnimg.cn/direct/91134ad0a43f41509c11a8805743b9d9.png
这道题跟优势洗牌思绪一样，就是对两个数组进行排序，然后依次比力，如果不满足当前孩子的胃口就让饼干数组今后一位继续比力知道满足为止。贪心的计谋就是只管用小的饼干尺寸去满足孩子胃口。
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 >= g){
i++; ret++;
}
}
return ret;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]