题目

1. 贪心算法问题: 根据身高重建队列2. 动态规划问题: 三角形最小路径和3. 动态规划问题: 合唱团(网易笔试编程)4. 不同排序算法应用问题

1. 贪心算法问题: 根据身高重建队列

# encoding=utf-8 """ Date:2019-07-18 13:43 User:LiYu Email:liyu_5498@163.com """ info = [ [7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2] ] def high_sort(info): # 先按照身高从大到小排序[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]] high_sort_info = sorted(info, key=lambda x: x[0], reverse=True) new_info = [] for i in range(len(high_sort_info)): # 如果该人前面比他高的等于他的位次，则不变 if high_sort_info[i][1] == i: new_info.insert(i, high_sort_info[i]) # print(new_info) # 不等于，则他的位置应该为索引是 比他高的人数 的位置 else: new_info.insert(high_sort_info[i][1], high_sort_info[i]) # print(new_info) print(new_info) high_sort(info)

2. 动态规划问题: 三角形最小路径和

# encoding=utf-8 """ Date:2019-07-18 14:16 User:LiYu Email:liyu_5498@163.com """ delta = [ [2], [3, 4], [6, 5, 7], [4, 1, 8, 3] ] way = [0, 0, 0, 0] def min_way(delta): way[0] = 1 way_sum = 1 for i in range(1, 4): # 拿到上一个值和它的索引 last_num = way[i - 1] last_num_index = delta[4 - i].index(last_num) # 如果上一个值是上一个列表的第一个或最后一个 # 选当前列表的前一个或最后一个 if last_num_index == 0: way[i] = delta[4 - i - 1][last_num_index] way_sum += way[i] elif last_num_index == len(delta[4 - i]) - 1: way[i] = delta[4 - i - 1][last_num_index - 1] way_sum += way[i] # 如果不是，选上一个值索引对应的值和前一个值 else: a = delta[4 - i - 1][last_num_index - 1] b = delta[4 - i - 1][last_num_index] way[i] = min(a, b) way_sum += way[i] # print(last_num_index) # print(last_num) print(way) print(way_sum) min_way(delta)

3. 动态规划问题: 合唱团(网易笔试编程)

# encoding=utf-8 """ Date:2019-07-18 14:48 User:LiYu Email:liyu_5498@163.com """ n = int(input('请输入学生个数:\n')) energy_input = input('请输入%s个学生的能力值:\n' % n) term_input = input('请输入想要源区的学生个数和最大学生标号的最大值:\n') energy = [int(i) for i in energy_input.split(' ')] k, d = int(term_input.split(' ')[0]), int(term_input.split(' ')[1]) # n = 5 # energy = [-7, 4, -7, 9, -9] # k, d = 2, 2 dp = [(i, i) for i in energy] # 初始化[(max, min), (max, min), (max, min),...] for i in range(1, k): # 对学生数量从1到k进行循环，循环一次，得到i个学生以各个编号结尾的最大最小乘积，保存在dp中 # 以i=1为例，dp_保存着第0个学生的能力值，j从1到n-1循环 dp1 = dp[:i] # 子问题(前i-1个人)的最大最小乘积，从底向上，避免重复计算 for j in range(i, n): # i个学生中的最大编号j从i到n-1开始循环 temp = [] for z in range(j - d, j): # 最大间隔为d（本次值到前d个有效） if z < 0: continue else: # 可选区间内的每个数之前计算出的最大最小值（存在dp中）和本次的值相乘存到temp temp.append(energy[j] * dp[z][0]) temp.append(energy[j] * dp[z][1]) # 最小值如果为负，本次的数也为负，乘积可能最大，需要记录 # print('temp') # print(temp) dp1.append((max(temp), min(temp))) # 添加了本次这个数计算出的最大最小值，循环结束后dp1中为i个学生的最大最小值 # print('dp1') # print(dp1) dp = dp1 # 循环结束之后dp1中为i个学生的最大最小值，更新数据到dp,全部循环结束就是k个学生的最大最小乘积 # print('dp') # print(dp) print(max([max(each) for each in dp]))

4. 不同排序算法应用问题

排序的优化原则: 1). 需要被排序的总数比较小的时候, 适合插入排序和选择排序; 2). 需要被排序的总数很大的时候,建议使用归并排序; 3). 需要被排序的数据基本有序的时候,适合直接插入排序调整一下即可; 4). 有重复且范围较小或者位数比较固定, 考虑基数排序或者桶排序 问题描述 1: 全班有 40 人, 每排 6 个人,每次收作业要求学号按顺序排列好之后交给老师, 方便统计. 请说出你的解决方案。

答： 可以使用归并排序，作业分成六祖，每组先排序； 然后三三合并，成为两组，再排序； 最后把两组合并，排序即可。

问题描述 2: 封装所有的排序算法到自定义模块 mySort,参考模块与包的知识, 实现打包功能。 如果可以发布到 pypi 网站上.

setup.py文件： 打包发布： 测试：