字节跳动春招实习笔试题解(0508)

type

status

date

slug

summary

📝 主旨内容

最小攻击次数(贪心，模拟)

有n个自爆怪，每只怪物血量为ai，并且怪物死亡时(血量小于等于0)会发生自爆，对其他怪物造成等同于其初始血量的伤害。小杰每次攻击可以对任意一只怪物造成1点伤害。她想知道，最少攻击多少次可以击杀全部怪物?

输入描述

第一行输入一个正整数n，代表怪物的数量

第二行输入n个正整数ai，代表每只怪物的血量。

1<n<10^5，1<ai< 10^9

输出描述

一个正整数，代表小杰的最小攻击次数

输入

输出

说明

对第1只怪物、第2只怪物名攻击次即可。攻击第1只怪物时，第1只怪物死亡时白爆，对第 2、3 只怪物备造成1点伤害。此时第2只怪物血量只剩1点，再攻击一次即可。然后第2只怪物自爆，对第3只怪物造成2点伤害，第3只怪物也死亡。

💡

攻击肯定有先后顺序的，如果先攻击最大的，那打完就直接结束战斗了，举出一个简单的反例，2 3 10，优先打大的需要十次，打小的只需要2+1+5=8

恢复全排列(枚举)

小杰有一个长为n的排列p，但大白熊将其隐藏了起来。现在大白熊给了小杰一个长度为n-1的数组a，其中a[i]=p[i] + p[i+1] 小杰想用数组a还原出排列p来，你能帮帮她吗

输入描述

输入包含两行。第一行一个正整数n(1≤n≤ 2 x 10^3)

表示排列p 的长度。

第二行n-1个正整数ai(1<ai<n+(n-1))，表示题中所述数组a的元素。

输出描述

输出包含一行n个数字，表示还原出来的排列p。如果有多解，请输出字典序最小的解，但如果无解，请输出 -1。

示例 1

输入

输出

💡

n最大是2000，直接枚举1~n做完第一个数，就可以求得完整数组，判断是否是1~n的排列即可

马走日的最小点和(Dijkstra)

小杰在一个矩阵的左上角，她准备跳到右下角。小杰必须按照象棋的"马"的规则移动，即如果当前的坐标是(x0,y0)，那么落点的坐标(x,y)必须满足|x-x0| +|y - y0| = 3且x ≠xo,y ≠y0。小杰每跳一步就会收集落点的数字加入到总和里。她想知道最终最小的总和是多少?

输入描述

第一行输入两个正整效n,n、代表矩阵的行数和列数接下来的几行，每行输入m个正整数aij，代表矩阵的元素。

1≤n,m≤800 1≤aij≤ 10^9

输出描述

如果无法到达，请输出-1。否则输出一个正整数，代表最终的最小点和

输入

输出

说明

1+7+4=12

💡

因为不是只能往右下跳，可以反复横跳走最小的点，所以不能用DP(有后效性，即一个状态依赖于未知状态)

💡

当作最短路来做，边的规则给定了，求从左上角到左下角的权值和最小的路径，需要注意要用堆优化快速找到最小的权值进行拓展，否则复杂度是O(n^3)

好子序列的数量(DP)

小杰定义一个字符串是"好串"，当且仅当该字符串包含"ab"子序列。

现在小杰拿到了一个仅由'a'和"b'组成的字符串。他想知道，该字符串有多少子序列是好串?

定义字符串的子序列为:字符串从左到右取若干字符(在原串中可以不连续)组成的新串。例如，"arcaea"的子序列有"ace"等

输入描述

一个仅包含'a'和'b'的字符串，长度不超过10^5

输出描述

好子序列的数量。由于答案可能过大，请对10^9+7取模。

示例 1

输入

输出

说明

长度为4的子序列"abab"是好串。长度为3的子序列共有4个，都是好串，长度为2的子序列仅"ab"是好串，共有3个"ab"子序列。答案是1+4+3=8。

💡

去掉字符串最后一个字符，发现得到了一个规模更小的问题，可以用动态规划来解决

💡

分别对有'a'的子序列的数量，既没有a也没有ab的子序列的数量，有'ab'的子序列的数量分别进行计数，看三个数如何在遍历中更新

🤗 总结归纳

整体难度中等，最后一题比较难想到

📝 主旨内容

最小攻击次数(贪心，模拟)

恢复全排列(枚举)

马走日的最小点和(Dijkstra)

好子序列的数量(DP)

🤗 总结归纳

📎 参考文章