题目地址
https://www.nowcoder.com/test/16516564/summary
1. 大锤的自动校对程序
题目描述
我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：
- 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
- 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
- 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC
我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！ …… 万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……
请听题：请实现大锤的自动校对程序
输入描述: 第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。
后面跟随N行，每行为一个待校验的字符串。
输出描述: N行，每行包括一个被修复后的字符串。
输入例子1: 2 helloo wooooooow
输出例子1: hello woow
思路
第一想法是用正则实现，简单直接。
代码
const n = Number(readline());
let cur = ""
while(cur = readline()) {
console.log(cur.replace(/([a-z])\1{1,}/g, "$1$1").replace(/([a-z])\1([a-z])\2/g, "$1$1$2"))
}复杂度分析
- 时间复杂度：取决于正则引擎的实现
- 空间复杂度：取决于正则引擎的实现
2. 大锤特工
题目描述
我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议
- 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
- 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。
我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！ …… 万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！
请听题：给定N（可选作为埋伏点的建筑物数）、D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。 注意：
- 两个特工不能埋伏在同一地点
- 三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
输入描述: 第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）
输出描述: 一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模
输入例子1: 4 3 1 2 3 4
输出例子1: 4
例子说明1: 可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
输入例子2: 5 19 1 10 20 30 50
输出例子2: 1
例子说明2: 可选方案 (1, 10, 20)
思路
思路是：
- 固定两个端点，两个端点的距离是 X (X<=D)。
- 然后将第二个和三个特工塞到两个端点内的 X 个 空位即可。
- 在 X 个位置上塞两个人的组合数是 $C_X^(2)$， 即 $N*(N - 1) / 2$。
代码
实际上可以利用 dict，单调栈等技巧加速寻找右边界的过程。
n, dist = map(int, input().split())
nums = list(map(int, input().split()))
ans = l = 0
r = 2 # ∵ D >= 1
while l < n - 2:
while r < n and nums[r] - nums[l] <= dist:
r += 1
if r - 1 - l >= 2:
cnt = r - l - 1
ans += cnt * (cnt - 1) // 2
l += 1
print(ans % 99997867)复杂度分析
- 时间复杂度：$O(N ^ 2)$，加速之后可以到 $O(N)$
- 空间复杂度：$O(1)$
3. 雀魂
略
4.猫的运动
题目描述
小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。
因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。 现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。
输入描述: 第一行包含一个正整数N，代表测试用例的个数。
每个测试用例的第一行包含一个正整数M，代表视频的帧数。
接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2> 所有用例的输入特征总数和<100000
N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。 特征取值均为非负整数。
输出描述: 对每一个测试用例，输出特征运动的长度作为一行
输入例子1: 1 8 2 1 1 2 2 2 1 1 1 4 2 1 1 2 2 2 2 2 1 4 0 0 1 1 1 1 1 1
输出例子1: 3
例子说明1: 特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3
思路
用一个 dict 记录上一帧的最长特征运动，枚举这一帧的运动信息并更新 dict即可，在这个过程记录最大值，类似滚动数组。
代码
n = int(input())
while n > 0:
n -= 1
ans = 1
pre = {}
for _ in range(int(input())):
l = list(map(int , input().split()))
k = l[0]
cur = {}
for j in range(k):
k = (l[2 * j + 1], l[2 * j + 2])
if k in pre:
cur[k] = pre[k] + 1
ans = max(ans, cur[k])
else:
cur[k] = 1
pre = cur
print(ans)·复杂度分析
- 时间复杂度：$O(N * K)$，，其中 K 为所有帧的特征平均值
- 空间复杂度：$O(M)$，其中 M 为所有帧的特征最大值。
5. 小明的毕业旅行
题目描述
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
输入描述: 城市个数n（1<n≤20，包括北京）
城市间的车票价钱 n行n列的矩阵 m[n][n]
输出描述: 最小车费花销 s
输入例子1: 4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0
输出例子1: 13
例子说明1: 共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
思路
典型的旅行商问题（TSP）， DP即可解决。
copy 一个模板过来改改就行了。
代码
改成非递归的 bottom-up 性能更好
import functools
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
visited = 1 << (n - 1)
@functools.lru_cache(None)
def dp(fr, to):
if to == 0: return graph[fr][0]
ans = float('inf')
for i in range(1, n):
if ((to >> (i - 1)) & 1) == 1:
to ^= 1 << (i - 1) # mark visited
ans = min(ans, graph[fr][i] + dp(i, to))
to ^= 1 << (i - 1) # unmark
return ans
print(dp(0, visited - 1))
复杂度分析
- 时间复杂度：$O(2^N*N^2)$
- 空间复杂度：$O(2^N*N)$
6. 硬币找零
题目描述
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？
输入描述: 一行，包含一个数N。
输出描述: 一行，包含一个数，表示最少收到的硬币数。
输入例子1: 200
输出例子1: 17
例子说明1: 花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。
思路
完全背包问题，力扣硬币找零的简化版。
代码
n = 1024 - int(input())
dp = [1024] * (n + 1)
dp[0] = 0
for i in range(n + 1):
for coin in [1, 4, 16, 64]:
if i >= coin:
dp[i]= min(dp[i], dp[i - coin] + 1)
print(dp[-1])复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
代码
7.机器人跳跃
see: #423
更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
