4.14 字节笔试 中等偏难

字节第四次春招笔试一共四道编程题，难度中等偏上，对于算法基础薄弱的同学来说很有挑战性，需要有一些算法功底。

code放在 gz号了 ：offer小飞龙

如果同学们有什么算法上的问题，可以找小飞龙咨询呦，无偿答疑！

题目就以大意的形式给出

• 第一题 

题目大意：

给你一个数组，你可以选择其中的一个区间，并将区间中的每个字符翻转，（定义翻转一个数字指数字正着读变成倒着读，例如”1234"变成”4321”"1430"变成”341”，不包含前导零）求操作后区间和最大可能值

题解：

求出每一个翻转后的数与原数的差值，然后就是经典的最大区间和问题，记录最大答案即可。

（有一个小坑：所选区间不能为空）

code：code放在 gz号了 ：offer小飞龙

• 第二题

题目大意：给你一个字符矩阵，只允许你走"日"字，类似象棋中的马，（

如果当前的坐标是(x0, y0)，那么落点的坐标(x,y)必须满足|x-x0| +|y-y0|= 3且 x≠x0, y≠y0）你可以任选起点，问有多少种走的方案使得路径字符串为"byte"

题解：

从每个字符'b'开始做DFS即可

code：code放在 gz号了 ：offer小飞龙

• 第三题

题目大意：小红在一个长度为n的数组上，初始在第一个元素，她准备前往最后一个元素。

小红有一个弹力鞋，她每次可以利用弹力鞋向右弹跳，初始弹力鞋只能跳 1的距离，每跳一次弹力鞋能跳的距离翻倍。例如，第一次跳的距离恰好是1，第二次跳的距离恰好是2，第三次跳的距离恰好是4，以此类推。另外小红可以随时将弹力鞋弹跳的距离重置为 1。

现在数组上有若干个单向传送阵，小红可以随时使用这些传送阵向右传送 (传送后弹力鞋的距离强制重置为 1)。

小红想知道，自己需要至少弹跳多少次可以到达最后一个元素?

题解：简单DP，我们考虑每个节点的两种转移情况：1.从之前的节点跳2的幂次，消耗幂次的次数 2.通过传送门过来，不消耗次数

dp[i]表示从起点到i点的最小次数

对于情况1我们对于每个节点向后更新从当前点开始每个幂次的节点的答案

对于情况2直接更新对应传送终点的最小值即可

code：code放在 gz号了 ：offer小飞龙

• 第四题

题目大意：给你一个长度为n且仅包含"red"三种字符的字符串，给出q次询问，每次给出l，r，每次询问让你求出所给区间重新排列后能够组成的不同回文字符串的个数

题解：组合数学，满足回文仅包含两种情况，1.长度为奇数，仅有一个单字符，在串中间，两边对称 2.长度为偶数，两边对称

那么我们只需要求出每个字符成对的数量，然后组合数学计算即可

（注意取模，求逆元）

code：code放在 gzh了 ：offer小飞龙

​