算法贪心算法

前言

一，贪心算法的介绍

二，LeetCode 455 ------- 饼干分发

三，蓝桥杯 55 完美代价

总结

前言

这里主要讲贪心算法的基础知识和两个习题

一，贪心算法的介绍

贪心算法是一种求解最优化问题的算法思想，它通过逐步选择局部最优解来求解全局最优解。每一步选择的都是当前最好的选择，并且不考虑后续可能会产生的影响。换句话说，贪心算法每一步都做出“局部最优”的选择，而不会回溯或尝试去优化之前的决策

总的来说就是局部最优到全局最优

贪心算法存在两个极端，就是非常简单与非常难，为什么怎么说呢？因为简单的话就是与我们的生活常识有关，非常难就是与我们的生活常识没有什么关系，非常难，尤其是这个局部最优，你不知道你选择的局部最优是不是正确的

我们以一个生活常识来讲解一下贪心算法
现在我们有一沓钞票，然后我们要取5个钞票在这一沓钞票里面，最后取的五张钞票要为最大的金额，我要怎么取钞票

我们看到这个问题的时候，卧槽，这么简单，这那是什么算法呀，太简答了吧，就是每一次取面额最大的那一张，那不就是最后的金额为最大的，这个每次取最大金额在这沓钞票这个就是局部最优，最后导致最后的金额最大，这个就是全局最优

下面我们来看两个贪心算法的题目来感受一下贪心算法

二，LeetCode 455 ------- 饼干分发

题目
假设你是一位很棒的家长，想要给你的孩子们一些小饼干，但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1：

输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足
所以你应该输出1

示例 2：

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2
你拥有的饼干数量和尺寸都足以让所有孩子满足
所以你应该输出2

贪心算法思路

运用我们贪心算法的话，我们只要找到合适的一个局部最优解，并且你觉得没有任何的情况来反驳它的话，就去试试可不可行，如果你选择用数学归纳法或者反证法来证明你这个情况是否为局部最优解的话，那就太浪费时间了

策略：用最大的饼干去喂最大胃口的孩子

我们只要每次把最大的饼干去喂最大胃口的孩子就好了，这个就是局部最优解，然后最后得出有几个孩子，这个就是全局最优解，这个题目的容器里面的数字，题目是自己会帮助你写好的，所以我们只需要写下思路就好了
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int result = 0;int index = s.size() - 1;for (int i = g.size() - 1; i >= 0; i--) {if (index >= 0 && s[index] >= g[i]) {result++;index--;}}return result;}
};
首先我们要对容器里面的数字进行排序，然后for循环是逐步寻找最大且饼干可以喂包的孩子
注：只要最大的那个饼干都喂不包这个孩子，那么这个后面的饼干都喂不饱，这个就是for循环为什么一直走，饼干序列不动
然后如果可以喂饱，就可以移动到下一个饼干，然后最终的结果返回就好了

三，蓝桥杯 55 完美代价

问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)
输入格式
　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母
输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible
样例输入
5
mamad
样例输出
3

输入样例:

在这里给出一组输入。例如：

5

mamad

输出样例：

3

这个题目就是相对比较复杂，但是我们还是可以利用贪心算法来解决

首先我们要排除不可能实现回文的字符串，那就是你的奇数个字母的个数只可以为一个，不可以为多个，这里我们就用哈希表来解决，别急，即使不知道，我也会讲，接下来你们都可以使用这个方法去解那种有计数的题目
 int n = s.length();// 统计字符频次unordered_map<char, int> freq;for (char c : s) {freq[c]++;}// 检查是否能构成回文int oddCount = 0;for (auto& p : freq) {if (p.second % 2 != 0) {oddCount++;}}if (oddCount > 1) return -1;  // 不能构成回文串
首先我们有这个unordered_map<keytype，valuetype>name，这个就是你key是标志，value为值
然后我们命名名字为freq就是出现频率的意思

然后我们就会有个for（char c：s）这个就是逐步的把s里面的每一个字母输入到c里面去，然后
freq[ c ]++这就是再map里面的c这个字母里面的值进行++就是加1，我们需要记录出现频率，这个：就是一个分隔符号
然后我们就记录这个奇次的个数有一几个

然后auto&p：freq，这个auto是c++里面的一个语法，这个是系统根据上下文来自己判断这个p为什么类型，&就是引用，就是不创建副本，对原来的p进行操作

然后就是p.second，这个就是value，first为字母

然后判断这个值就好了
接下来我们判断是可以回文的，就用贪心算法计算就好了

贪心算法局部最优就是不断地交换里面各个字母，然后得到最终地字符串

贪心算法地策略：

从字符串的两端开始向中间检查。假设我们要把字符 s[i] 和 s[N-i-1] 配对。
如果这两个字符相等，那么无需做任何操作，继续向内移动。
如果不相等，就要寻找与 s[i] 或 s[N-i-1] 匹配的字符，并将它们交换到对应的位置。
    int left = 0, right = n - 1;int swaps = 0;// 使用双指针逐步构建回文while (left < right) {if (s[left] == s[right]) {left++;right--;}else {int l = left, r = right;// 寻找匹配的字符while (r > l && s[r] != s[left]) {r--;}if (r == l) {  // 如果找不到配对的字符swap(s[l], s[l + 1]);swaps++;}else {// 交换到合适的位置for (int i = r; i < right; i++) {swap(s[i], s[i + 1]);swaps++;}left++;right--;}}}return swaps;
首先我们判断是否相等
    while (left < right) {if (s[left] == s[right]) {left++;right--;}
然后不相等就判断是奇数的字母还是偶数的字母
我们就while寻找到那个字母，如果最终为1了，就是为奇数的字母，然后把奇数的字母往中间移动
如果不为1就是就是为偶数的字母，然后把那个字母往对称的位置进行移动，移动偶数的字母才可进行左右++和- -

完整代码

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;int minSwapsToPalindrome(string s) {int n = s.length();// 统计字符频次unordered_map<char, int> freq;for (char c : s) {freq[c]++;}// 检查是否能构成回文int oddCount = 0;for (auto& p : freq) {if (p.second % 2 != 0) {oddCount++;}}if (oddCount > 1) return -1;  // 不能构成回文串int left = 0, right = n - 1;int swaps = 0;// 使用双指针逐步构建回文while (left < right) {if (s[left] == s[right]) {left++;right--;}else {int l = left, r = right;// 寻找匹配的字符while (r > l && s[r] != s[left]) {r--;}if (r == l) {  // 如果找不到配对的字符swap(s[l], s[l + 1]);swaps++;}else {// 交换到合适的位置for (int i = r; i < right; i++) {swap(s[i], s[i + 1]);swaps++;}left++;right--;}}}return swaps;
}int main() {int n;string s;cin >> n;cin >> s;int result = minSwapsToPalindrome(s);if (result == -1) {cout << "Impossible" << endl;}else {cout << result << endl;}return 0;
}