PDD 学霸批 算法
Problem 1
给定两个数组A和B，A几乎严格升序，即只需改变一个数就可以变成完全升序排列；
现需要从B数组中选取一个数将A中错误的数字替换，使得数组A完全严格升序排列（即不允许相同）；
找出B数组中满足要求的最大的数字，并输出最终的有序数组，如果不存在就输出NO。
大致思路
首先找到不符合严格升序的数字位置i，那么需要替换的元素只可能是nums1[i]和nums1[i-1]中的一个；
随后将nums2排序，从最大的元素开始扫描，如果nums1[i-1] < x < nums1[i+1] (替换第i个位置）或者nums[i-2] < x < nums[i]（替换第i-1个位置），则已经找到，返回即可；
这里需要注意下表边界的问题，所以在nums1的首位分别加上-inf和inf进行预防。
# -*- coding: utf-8 -*-
import sys
# python2中map返回的是list对象，可以直接使用；
# python3中map返回的是map对象，还需要再调用list转换为数组；
nums1 = list(map(int, sys.stdin.readline().strip().split()))
nums2 = list(map(int, sys.stdin.readline().strip().split()))
# find the wrong point
nums1 = [float('-inf')] + nums1 + [float('inf')]
n = len(nums1)
i = 1
while i < n:
if nums1[i] <= nums1[i-1]:
break
i += 1
# find the max replace number
nums2.sort(reverse=True)
j = 0
change = -1
while j < n:
if nums1[i-1] < nums2[j] < nums1[i+1]:
change = i
break
if nums1[i-2] < nums2[j] < nums1[i]:
change = i - 1
break
j += 1
if change == -1:
print('NO')
else:
nums1[change] = nums2[j]
print(" ".join(list(map(str, nums1[1:-1]))))
Problem2
给定一个字符串数组（数组长度大于1小于1024），所有字符均为大写字；
问给定的字符串数组是否能通过变更数组中元素顺序而达到首尾相连，形成一个环，环上相邻字符串首尾衔接的字符相同，输出为true或者false。
大致思路
首先用dict统计字符串的首尾，首字母为x，尾字母为y，dict的格式为count[x] = [y1, y2, …, yn] 使用DFS检查数组是否能成环，这里注意两点：
- 若数组可以成环，则从任意一个字符串开始都可以成环，所以只需从第一个开始，检查一次就可以了；
- 若包含首尾相同的字符串（如cc，cac），优先消耗这类字符串，否则会出现顺序问题；
# -*- coding: utf-8 -*- import sys import collections strs = sys.stdin.readline().strip().split() n = len(strs) count = collections.defaultdict(list) for s in strs: count[s[0]].append(s[-1]) def dfs(start, smap, num): if num == 0: return True if start not in smap: return False if start in smap[start]: end = start smap[start].remove(start) else: end = smap[start].pop() if not smap[start]: del smap[start] return dfs(end, smap, num-1) print(dfs(strs[0][0], count, n))
Problem 3
N个任务，每个任务需要
的时间，任务之间存在依赖关系；
每次只能执行一个任务，任务完成前不能暂停切换任务；
假设所有任务在0时刻都被接收，请安排执行顺序，确保平均返回时间最小。
大致思路
建立两个字典：
depends存放任务间的依赖关系，所有依赖a的任务都存放在a这个key对应的value里；
require存放每个任务依赖其他任务的数量；
维护一个就绪队列，队列中为require=0的任务，并且保证按照时间顺序排序，所需时间相同时，编号小的任务优先执行；
每次从队首弹出一个任务cur执行，执行完毕后将所有依赖cur的任务require-1，如果require为0了，加入到就绪队列。
# -*- coding: utf-8 -*-
import sys
import collections
n, m = list(map(int, sys.stdin.readline().strip().split()))
T = list(map(int, sys.stdin.readline().strip().split()))
depends = collections.defaultdict(list)
require = collections.defaultdict(int)
for _ in range(m):
a, b = list(map(int, sys.stdin.readline().strip().split()))
depends[a].append(b)
require[b] += 1
task = []
for t in range(n):
if t+1 not in require:
task.append((t+1, T[t]))
ans = []
while task:
task.sort(key=lambda x: (x[1], x[0]))
cur = task.pop(0)[0]
ans.append(cur)
if cur in depends:
for t in depends[cur]:
require[t] -= 1
if require[t] == 0:
task.append((t, T[t-1]))
print(" ".join(map(str, ans)))
Problem 4
N个长方体积木，第i个积木的长宽为
，重量为
；
现尝试搭积木，要求：
- 每一层积木边长都严格比下一层的积木边长小；
- 每块积木只能承受不超过自身重量7倍的积木；
问最高可以搭出多高的积木，输出层数。
大致思路
首先将边长、重量组合成二元组，依据边长排序； 定义dp状态，dp[i][j]表示到第i个积木为止，要搭出j层所需要的最小重量；这里的思路是不管搭多少层，要使最终搭得最高，必须在当前选择总重量最小的搭法；
状态方程为)
；前提条件为dp[i-1][j-1]处的总重量不超过当前积木重量的7倍；
初始化dp[i][0]=0，其余用无穷表示不可能搭出当前要求状态，每次更新状态时，若状态最终不等于无穷，则更新最高层数；
由于i个积木不可能搭出超过i的层数，所以只需要计算dp矩阵的下三角即可。
# -*- coding: utf-8 -*-
import sys
n = int(input())
L = list(map(int, sys.stdin.readline().strip().split()))
W = list(map(int, sys.stdin.readline().strip().split()))
item = [(L[i], W[i]) for i in range(n)]
item.sort(key = lambda x: x[0])
# dp[i][j]：up to i-th block, the minimum weight to build j-level
dp = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
dp[i][0] = 0
max_level = 1
for i in range(n):
for j in range(i):
if dp[i][j] <= 7 * item[i][1]:
dp[i+1][j+1] = min(dp[i][j+1], dp[i][j] + item[i][1])
else:
dp[i+1][j+1] = dp[i][j+1]
if dp[i+1][j+1] != float('inf'):
max_level = max(max_level, j+1)
print(max_level)
5道手撕666，面试官找你刷题来了