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

Python贪婪算法之Python算法题实战 -《完美的代价》写在前面最近也没什么事可做,就在备赛蓝桥杯(Python).蓝桥杯主要考察的是算法题目.所以我也在网上找了些资源刷题,昨天当我刷到《完美的代价》

大家好,欢迎来到IT知识分享网。

写在前面

最近也没什么事可做,就在备赛蓝桥杯(Python).蓝桥杯主要考察的是算法题目.所以我也在网上找了些资源刷题,昨天当我刷到《完美的代价》这道题目的时候,我就被卡住了.怎么想也想不通,就连解题代码也看不懂.更搞笑的是,昨天晚上我睡觉的时候,就在思考这道题目,结果不到一分钟,我就入睡了…

今天起床后,我就在CSDN里面找寻思路,有些博主提到,《完美的代价》需要用到贪心算法,但是我也没正经学过相关的算法,所以就去研究了一下贪心算法,发现这个算法还有点意思呢

私信小编01即可获取大量Python学习资料

What is 贪心算法

贪心算法并不是一个具体的算法,而是一种算法的思想,或者说是解决问题的一种思路
要想弄明白贪心算法,可以从这两个关键点入手:

  1. 贪心算法解决什么问题
    解决求最优解问题。即此问题的最终的目的,是为了得到一个最优解。比如,从A地到B地之间的最短路径,100块钱可以在一个商场里买到的东西最多,等等之类的
  2. 贪心算法是怎样的一种思路顾名思义,贪心算法,是一种很“贪”的算法。它的整体步骤,可以归纳为:将问题分解成多个小问题或者多个步骤在每个小问题或者步骤中,执行某种最优化策略,得到局部最优解所有每个步骤得到的最优化解,组合得到全局最优化解,不做回溯处理

贪心算法最大的特点,就是在每一步中取最优化的解,不会回溯处理。这样的策略,自然在执行速度上更快,但是因为这种方法的短视。会导致得的解并不是真正的全局最优解,但是贪心算法得到的依然是一个近似最优解

0-1背包问题

问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高

通俗解释:假如你有一个只能承重100的背包,你往里面装一些重量和价值不等的东西,怎样才可以让你的背包中的价值最大

这个问题中就是关键在于,每个转入背包的东西,只能是被装入背包和不被装入背包两种状态,可以用0-1表示。所以叫0-1背包问题。其二,就是这个问题的两个限定。第一,背包的边界是明确,它只能承重那么多东西。第二,东西的边界是明确的,你只有那么一些东西可以选择

故而,这个问题其实有三种策略可以选择:

  1. 每次装入的都是价值和重量比率最高的,也就是我们常说的性价比最高的
  2. 每次装入的是当前可选择的东西中,价值最高的
  3. 每次装入的是当前可选择东西中,重量最轻的

这三种策略中,策略一看起来最好的策略
但是,策略一的模糊化太大,需要根据特殊的情况,做出特殊的改变
策略二和策略三相同,本身上并没有太多不同。只是二者的视角不同

完美的代价

我们了解贪心算法后,再来看看这道算法题吧

问题描述

回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。

交换的定义是:交换两个相邻的字符
  例如mamad
  第一次交换 ad : mamda
  第二次交换 md : madma
  第三次交换 ma : madam (回文!完美!)

输入格式

第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串,长度为N.只包含小写字母

输出格式

如果可能,输出最少的交换次数。
否则输出Impossible

样例输入

5
mamad

样例输出

3

题目分析

题目给的关键字是贪心算法,贪心算法关键是要找到贪心策略。对于我们这题来说,要做的事情有两件:

  1. 先判断这个字符串能不能够经过交换变成‘完美的回文字符串’
  2. 每一步都使用贪心策略

判断

  • 对于字符串长度是偶数的字符串,每个字符的数目都是偶数,一旦出现奇数,则输出impossible
  • 对于字符串长度是奇数的字符串,只能有一个字符的数目是奇数,一旦出现两个,则输出impossible
  • 判断实现比较简单,注意减少代码复杂度(题给字符串长度范围是8000,很容易运行超时)

贪心策略

对于偶数的字符串,我们从第一个开始遍历,再倒序遍历出同样的,这个倒序遍历出来的序号,就是该移动的步数
我们把这个步数加到总步数之后,用pop弹出这个值,进行第二轮遍历
遍历用n/2做大循环,用另一个序列做倒序序列,倒序序列更新后,原来的序列也要更新

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

对于奇数的字符串,其实贪心策略和偶数的时候一样,只不过我们一直遍历下去会有一个字符没有匹配,那么这个字符肯定是放在中间的,我们设置一个判断,假如剩余的该字符个数不是1,按照和偶数一样的遍历,如果该字符是1,直接移动到最中间的位置

代码解析

题目了解清楚后,我们来看看代码部分
首先,判读输入的字符是否可以经过交换成‘完美的回文字符串’
我们可以通过上面给出的判断条件思路,写出一个判断函数

def judge_hwen(n,s): # 判断能不能组成回文数 _str = set("".join(s)) if n % 2 == 0: # 对于字符串长度是偶数的字符串 for i in _str: # 当某个字符的个数不是偶数执行下列判断 if s.count(i) % 2 != 0: print("Impossible") return False else: return True else: # 对于字符串长度是奇数的字符串 temp = set() for i in _str: if s.count(i) % 2 != 0: temp.add(i) # 把个数是奇数个的字符放进temp if len(temp) > 1: print("Impossible") return False else: return True

大家可以结合上面的文字思路和代码片段,进行理解


接着,就是进行步数的计算

def get_step(n,s,sv,res): for i in range(n // 2): if s[i:].count(s[i]) != 1: temp = sv[:n-i].index(s[i]) # 是要移动的步数 sv.pop(temp) res += temp s = sv[::-1] # 更新正序 else: # 字符个数是1,直接移动到最中间位置 res += n //2 -i # 需要移动的步数 s[i] = None # 下一步就可以像偶数一样处理 相当于把这个元素删掉了 sv = s[::-1] # 更新sv return res

这里的代码可以结合,上面的图片进行理解

完整代码如下:

def judge_hwen(n,s): # 判断能不能组成回文数 _str = set("".join(s)) if n % 2 == 0: # 对于字符串长度是偶数的字符串 for i in _str: # 当某个字符的个数不是偶数执行下列判断 if s.count(i) % 2 != 0: print("Impossible") return False else: return True else: # 对于字符串长度是奇数的字符串 temp = set() for i in _str: if s.count(i) % 2 != 0: temp.add(i) # 把个数是奇数个的字符放进temp if len(temp) > 1: print("Impossible") return False else: return True def get_step(n,s,sv,res): for i in range(n // 2): if s[i:].count(s[i]) != 1: temp = sv[:n-i].index(s[i]) # 是要移动的步数 sv.pop(temp) res += temp s = sv[::-1] # 更新正序 else: # 字符个数是1,直接移动到最中间位置 res += n //2 -i # 需要移动的步数 s[i] = None # 下一步就可以像偶数一样处理 相当于把这个元素删掉了 sv = s[::-1] # 更新sv return res n = int(input("请输入字符串的长度:")) s = list(input("请输入字符串:")) sv = s[::-1] res = 0 if judge_hwen(n,s): print(f"最少需要移动的次数为:{get_step(n,s,sv,res)}")

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/47741.html

(0)
上一篇 2024-09-15 21:45
下一篇 2024-09-18 17:33

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信