Python常用的算法——贪心算法（又称贪婪算法），你知道吗？(2)

# 我们转化思路，拼接字符串，比较结果

 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 

（编辑：ASP站长网）