Python常用的算法——贪婪算法（又称贪默算法），你知道吗？

# 我们转化思绪，拼接字符串，较量功效

 a = '128' 
b = '1286' 
 # 字符串相加 
a + b = '1281286' 
b + a = '1286128' 
  
a + b if a + b > b + a else b + a 

数字拼接代码如下：

from functools import cmp_to_key 
  
li = [32, 94, 128, 1286, 6, 71] 
  
def xy_cmp(x, y): 
 # 个中1暗示x>y，-1,0同理 
 if x+y < y+x: 
 return 1 
 elif x+y > y+x: 
 return -1 
 else: 
 return 0 
  
def number_join(li): 
 li = list(map(str, li)) 
 li.sort(key=cmp_to_key(xy_cmp)) 
 return "".join(li) 
  
print(number_join(li)) # 94716321286128 

4 勾当选择题目

假设有 n 个勾当，这些勾当要占用统一片园地，而园地在某时候只能供一个勾当行使。

每一个勾当都有一个开始时刻 Si 和竣事时刻 Fi (标题中时刻以整数暗示)暗示勾当在 [Si, fi) 区间占用园地。(留意：左开右闭)

问：布置哪些勾当可以或许使该园地举行的勾当的个数最多?

贪婪结论：最先竣事的勾当必然是最优解的一部门。

证明：假设 a 是全部勾当中最先竣事的勾当，b是最优解中最先竣事的勾当。

假如 a=b，结论创立

假如 a!=b，则 b 的竣事时刻必然晚于 a 的竣事时刻，则此时用 a 替代掉最优解中的 b ，a 必然不与最优解中的其他勾那时刻重叠，因此替代后的解也是最优解。

代码如下：

# 一个元组暗示一个勾当，（开始时刻，竣事时刻） 
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), 
 (8, 12), (2, 14), (12, 16)] 
  
# 担保勾当是凭证竣事时刻排好序,我们可以本身先排序 
activities.sort(key=lambda x:x[1]) 
  
def activity_selection(a): 
 # 起首a[0] 必定是最早竣事的 
 res = [a[0]] 
 for i in range(1, len(a)): 
 if a[i][0] >= res[-1][1]: # 当前勾当的开始时刻小于便是最后一个入选勾当的竣事时刻 
 # 不斗嘴 
 res.append(a[i]) 
 return res 
  
res = activity_selection(activities) 
print(res) 

5 最大子序和

求最大子数组之和的题目就是给定一个整数数组(数组元素有负有正)，求其持续子数组之和的最大值。下面行使贪婪算法逐个遍历。

代码如下：

def maxSubarray(li): 
 s_max, s_sum = 0, 0 
 for i in range(len(li)): 
 s_sum += li[i] 
 s_max = max(s_max, s_sum) 
 if s_sum < 0: 
 s_sum = 0 
  
 return s_max 

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!