算法练习- 其他算法练习6

数字序列比大小

• A、B两人一人一个整数数组，长度相等，元素随即；
• 两人随便拿出一个元素（弹出），比较大小，赢的得一分，输的减去一分，否则分值都不变；
• B每取一个元素都明示，求A赢B时的最大分值；

输入：
n 数组长度
arr1
arr2
输出：
求A赢B时的最大分值

示例1
输入：
3
4 8 10
3 6 4
输出：
3

示例2
输入：
4
3 6 2 10
2 5 7 11
输出：
3

思路：

• 对两个数组排序，并使用一个flag表示A 有能赢B 的元素；
• arr_b弹出第一个值，arr_a中取能赢arr_b的最小值；
• score_a 累加1；
• 示例可以找arr_a排序后元素全小于arr_b；全大于arr_b；有大于有小于arr_b;

python:

n = int(input().strip())
arr_a = list(map(int, input().strip().split()))
arr_b = list(map(int, input().strip().split()))
arr_a.sort()
arr_b.sort()score_a = score_b = 0flag = True # 表示A能赢B
while flag and arr_b:flag = Falsee_b = arr_b.pop(0)i = 0# 取保证A赢的最小元素while i < len(arr_a) and arr_a[i] <= e_b: # 只有大于才算赢i += 1if i < len(arr_a):flag = Truearr_a.pop(i)score_a += 1score_b -= 1print(score_a)

 

最佳植树距离

• 给定一些适合种树的坐标点和树苗数量；
• 让树苗均匀分开，确定最佳的种树距离；

示例1
输入：
7 坐标的数量
1 5 3 6 10 7 13 坐标
3 树苗数量
输出：
6 最佳的植树距离

思路：

• coords坐标数组升序排序；
• 植树距离最小为1，最大max_dist为【最大坐标-最小坐标】；
• for dist in range(1, max_dist+1)；
  • for i in range(coords[0], coords[-1]+1, dist):
  • used_trees += 1 并且保存植树的坐标位置
• used_tree > has_tree continue;
• used_tree == has_tree 判断是否合法坐标；
• used_tree < has_tree 距离太大 break

python：

coord_n = int(input().strip())
coords = list(map(int, input().strip().split()))
coords.sort()
trees_m = int(input().strip())find_best_dist = Falsemax_dist = coords[-1] - coords[0]
dist = 1
for dist in range(1, max_dist+1):used_trees = 0pos_list = []for i in range(coords[0], coords[-1] + 1, dist):used_trees += 1pos_list.append(i)if used_trees > trees_m: # 说明当前间距太小continueelif used_trees == trees_m:# 如果当前位置都是有效位置，且以均匀种植完所有的树苗，则breakif all([True if i in coords else False for i in pos_list]):find_best_dist = Truebreakelse:breakif find_best_dist:print(dist)
else:print(-1)

 

文艺汇演

• 一个人只能观看一场演出，不能迟到、早退；
• 连续观看的演出至少有15分钟的间隔；
• 根据时间表，计算最多可以看几场演出；

示例1
输入：
2 演出场数
720 120 开始时间-持续时间
840 120 开始时间-持续时间
输出：
1

示例2
输入：
5
20 120
80 120
130 70
140 60
200 50
输出：
2

示例3
输入：
4
20 200
30 30
50 45
110 60
输出：
2

思路：

• 动态规划
• 所有场次按照开始时间升序排序
• 后一场的开始时间与前一场的结束时间比较，是否有15分钟的间隔；
  • 有则可以看，取后面这一场的结束时间，作为后续比较；
  • 间隔不足，则选择看结束时间最早的那一场，刷新结束时间；

python:

def calc_max_plays(arr):global n, can_see_numif n == 1: # 场次是>=1return# 结束时间end_time = arr[0][0] + arr[0][1]cur = 1while cur < n:if arr[cur][0] - end_time >= 15:# 可以看 则刷新结束时间can_see_num += 1end_time = arr[cur][0] + arr[cur][1]else:# 选择场次（最早结束的场次）end_time = min(end_time, arr[cur][0] + arr[cur][1])cur += 1returnif __name__ == '__main__':# 所有场次数n = int(input().strip())plays = []for i in range(n):start_last = list(map(int, input().strip().split()))plays.append(start_last)# 按照开始时间排序plays = sorted(plays, key=lambda i:i[0])print(plays)can_see_num = 1# 计算最多场次calc_max_plays(plays)print(can_see_num)

 

计算误码率

• 误码率 = 错误比特数 / 总比特数；以字符串表示总位数，错误字符数，即为错误比特数；
• 字符串会被压缩，如2A3B4D5X 表示“AABBBDDDDXXXXX”;
• 第一次输入原始的压缩字符串，第二次输入出错的压缩字符串；
• 解压后两个字符串长度相等，计算误码率；

示例1
输入：
3A3B
2A4B
输出：
1/6

示例2
输入：
5Y5Z
5Y5Z
输出：
0/10

示例3
输入：
4Y5Z
9Y
输出：
5/9

思路：

• 还原字符串，并逐一对比，统计所有字符个数和错误字符个数；
• 输出误码率比例；

python:

s1 = "5Y5Z"
s2 = "5Y5Z"s1_restore = ""
s2_restore = ""s1_char_num = 0
for i in s1:if i.isdigit():s1_char_num = int(i)else:s1_restore += i * s1_char_nums2_char_num = 0
for i in s2:if i.isdigit():s2_char_num = int(i)else:s2_restore += i * s2_char_num# 两者恢复后长度相等
n = len(s1_restore)
error_num = 0
for i in range(n):if s1_restore[i] != s2_restore[i]:error_num += 1print(f"{error_num}/{n}")

 

二维伞的雨滴效应

• 输入一个正整数数组，无0，无重复，数组最小长度为1；
• 判断是否为二叉排序树，是则输出1，并输出左右子树的叶子节点值；
• 不是二叉排序树，则输出0 0 0，中间空格分隔；

示例：
输入：
8 3 1 6 4 7 10 14 13
输出：
1 1 13

思路：

• 构造二叉搜索树，前序遍历结果与数组对比，一致则数组为二叉搜索树的前序遍历结果；
• 前序遍历，最后一个数是最右侧叶子节点；
• 中序遍历，第一个节点为最左侧叶子节点；

python:

class TreeNode(object):def __init__(self, data, left=None, right=None):self.data = dataself.left = leftself.right = right# 构造二叉排序树
def insert_node(root, val):if root is None:return TreeNode(val)if val > root.data:# 右边插入root.right = insert_node(root.right, val)else:root.left = insert_node(root.left, val)return root# 中序遍历
# 左子树、root、右子树if __name__ == '__main__':# 构造二叉树排序树alist = [8, 3, 1, 6, 4, 7, 10, 14, 13]root = Nonefor i in alist:root = insert_node(root, i)root2 = rootin_order_list = []# 中序遍历stack = []while root or stack:while root:in_order_list.append(root.data)# 根节点入栈stack.append(root)root = root.leftroot = stack.pop()root = root.rightoutput_list = []if alist == in_order_list:output_list.append(1)# 中序遍历  获取最左侧的叶子节点pre = Nonewhile root2:pre = root2root2 = root2.leftoutput_list.append(pre.data if pre.right is None else 0)# 前序获取最右边叶子节点output_list.append(in_order_list[-1])else:output_list = [0, 0, 0]print(output_list)

 

阿里巴巴找黄金宝箱4

• 有0-N个箱子排成一个环，每个箱子有自己对应的编号；
• 输出每一个箱子后第一个比自己编号大的数；
• 多个数以，分隔输出；

示例1：
输入：
2,5,2
输出
5,-1,5

示例2：
输入：
3,4,5,6,3
输出
4,5,6,-1,4

思路：

• 单调栈，从栈顶到栈底，递增为单调递增栈；否则为单调递减栈；
• 单调栈解决大小关系；

python: