Python贪婪算法之Python算法题实战完美的代价

　　写在前面
　　最近也没什么事可做，就在备赛蓝桥杯（Python）。蓝桥杯主要考察的是算法题目。所以我也在网上找了些资源刷题，昨天当我刷到《完美的代价》这道题目的时候，我就被卡住了。怎么想也想不通，就连解题代码也看不懂。更搞笑的是，昨天晚上我睡觉的时候，就在思考这道题目，结果不到一分钟，我就入睡了。。。
　　今天起床后，我就在CSDN里面找寻思路，有些博主提到，《完美的代价》需要用到贪心算法，但是我也没正经学过相关的算法，所以就去研究了一下贪心算法，发现这个算法还有点意思呢
　　私信小编01即可获取大量Python学习资料Whatis贪心算法
　　贪心算法并不是一个具体的算法，而是一种算法的思想，或者说是解决问题的一种思路
　　要想弄明白贪心算法，可以从这两个关键点入手：贪心算法解决什么问题
　　解决求最优解问题。即此问题的最终的目的，是为了得到一个最优解。比如，从A地到B地之间的最短路径，100块钱可以在一个商场里买到的东西最多，等等之类的贪心算法是怎样的一种思路顾名思义，贪心算法，是一种很贪的算法。它的整体步骤，可以归纳为：将问题分解成多个小问题或者多个步骤在每个小问题或者步骤中，执行某种最优化策略，得到局部最优解所有每个步骤得到的最优化解，组合得到全局最优化解，不做回溯处理
　　贪心算法最大的特点，就是在每一步中取最优化的解，不会回溯处理。这样的策略，自然在执行速度上更快，但是因为这种方法的短视。会导致得的解并不是真正的全局最优解，但是贪心算法得到的依然是一个近似最优解01背包问题
　　问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高
　　通俗解释：假如你有一个只能承重100的背包，你往里面装一些重量和价值不等的东西，怎样才可以让你的背包中的价值最大
　　这个问题中就是关键在于，每个转入背包的东西，只能是被装入背包和不被装入背包两种状态，可以用01表示。所以叫01背包问题。其二，就是这个问题的两个限定。第一，背包的边界是明确，它只能承重那么多东西。第二，东西的边界是明确的，你只有那么一些东西可以选择
　　故而，这个问题其实有三种策略可以选择：每次装入的都是价值和重量比率最高的，也就是我们常说的性价比最高的每次装入的是当前可选择的东西中，价值最高的每次装入的是当前可选择东西中，重量最轻的
　　这三种策略中，策略一看起来最好的策略
　　但是，策略一的模糊化太大，需要根据特殊的情况，做出特殊的改变
　　策略二和策略三相同，本身上并没有太多不同。只是二者的视角不同完美的代价
　　我们了解贪心算法后，再来看看这道算法题吧问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换ad：mamda
　　第二次交换md：madma
　　第三次交换ma：madam（回文！完美！）输入格式
　　第一行是一个整数N，表示接下来的字符串的长度（N8000）
　　第二行是一个字符串，长度为N。只包含小写字母输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible样例输入
　　5hrmamad样例输出
　　3题目分析
　　题目给的关键字是贪心算法，贪心算法关键是要找到贪心策略。对于我们这题来说，要做的事情有两件：先判断这个字符串能不能够经过交换变成‘完美的回文字符串’每一步都使用贪心策略判断对于字符串长度是偶数的字符串，每个字符的数目都是偶数，一旦出现奇数，则输出impossible对于字符串长度是奇数的字符串，只能有一个字符的数目是奇数，一旦出现两个，则输出impossible判断实现比较简单，注意减少代码复杂度（题给字符串长度范围是8000，很容易运行超时）贪心策略
　　对于偶数的字符串，我们从第一个开始遍历，再倒序遍历出同样的，这个倒序遍历出来的序号，就是该移动的步数
　　我们把这个步数加到总步数之后，用pop弹出这个值，进行第二轮遍历
　　遍历用n2做大循环，用另一个序列做倒序序列，倒序序列更新后，原来的序列也要更新
　　对于奇数的字符串，其实贪心策略和偶数的时候一样，只不过我们一直遍历下去会有一个字符没有匹配，那么这个字符肯定是放在中间的，我们设置一个判断，假如剩余的该字符个数不是1，按照和偶数一样的遍历，如果该字符是1，直接移动到最中间的位置代码解析
　　题目了解清楚后，我们来看看代码部分
　　首先，判读输入的字符是否可以经过交换成‘完美的回文字符串’
　　我们可以通过上面给出的判断条件思路，写出一个判断函数defjudgehwen（n，s）：判断能不能组成回文数strset（。join（s））ifn20：对于字符串长度是偶数的字符串foriinstr：当某个字符的个数不是偶数执行下列判断ifs。count（i）2！0：print（Impossible）returnFalseelse：returnTrueelse：对于字符串长度是奇数的字符串tempset（）foriinstr：ifs。count（i）2！0：temp。add（i）把个数是奇数个的字符放进tempiflen（temp）1：print（Impossible）returnFalseelse：returnTrue
　　大家可以结合上面的文字思路和代码片段，进行理解
　　接着，就是进行步数的计算defgetstep（n，s，sv，res）：foriinrange（n2）：ifs〔i：〕。count（s〔i〕）！1：tempsv〔：ni〕。index（s〔i〕）是要移动的步数sv。pop（temp）restempssv〔：：1〕更新正序else：字符个数是1，直接移动到最中间位置resn2i需要移动的步数s〔i〕None下一步就可以像偶数一样处理相当于把这个元素删掉了svs〔：：1〕更新svreturnres
　　这里的代码可以结合，上面的图片进行理解
　　完整代码如下：defjudgehwen（n，s）：判断能不能组成回文数strset（。join（s））ifn20：对于字符串长度是偶数的字符串foriinstr：当某个字符的个数不是偶数执行下列判断ifs。count（i）2！0：print（Impossible）returnFalseelse：returnTrueelse：对于字符串长度是奇数的字符串tempset（）foriinstr：ifs。count（i）2！0：temp。add（i）把个数是奇数个的字符放进tempiflen（temp）1：print（Impossible）returnFalseelse：returnTruedefgetstep（n，s，sv，res）：foriinrange（n2）：ifs〔i：〕。count（s〔i〕）！1：tempsv〔：ni〕。index（s〔i〕）是要移动的步数sv。pop（temp）restempssv〔：：1〕更新正序else：字符个数是1，直接移动到最中间位置resn2i需要移动的步数s〔i〕None下一步就可以像偶数一样处理相当于把这个元素删掉了svs〔：：1〕更新svreturnresnint（input（请输入字符串的长度：））slist（input（请输入字符串：））svs〔：：1〕res0ifjudgehwen（n，s）：print（f最少需要移动的次数为：｛getstep（n，s，sv，res）｝）