程序员进阶之算法练习（十九）

前言

这周很忙，但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。

这次A、B、C都是很合适的面试题。

正文

A. Memory and Crow 题目链接 题目大意： 给出n个数字。（a[1], a[2], ..., a[n]） a[i]和b[i]的关系如下。 a[i] = b[i] - b[i+1] + b[i+2] - b[i+3].... 给出数组a[i]，求数组b[i]。 n (2 ≤ n ≤ 100 000) a[i] ( - 1e9 ≤ a[i] ≤ 1e9)

** Examples** ** input** 5 6 -4 8 -2 3 ** output** 2 4 6 1 3 ** input** 5 3 -2 -1 5 6 output 1 -3 4 11 6

题目解析： 根据通项公式，知道b[n] = a[n]；（因为不能存在b[n+1]) 然后倒着求b[i], b[i] = a[i] + a[i+1]；

B. Memory and Trident 题目链接 ** 题目大意：** 输入一个字符串s，由 'L', 'R', 'U', or 'D'组成，分别表示点P在原点的向左、右、上、下前进一步。 修改字符串的序列，每次操作能修改一个字符为其他字符（L/R/U/D），问点P按照字符串s移动后能回到原点的最小操作次数； 如果可以，输出做小操作次数； 如果不能，则输出-1；

** Examples** ** input** RRU ** output** -1 ** input** UDUR ** output** 1

** 题目解析：** 先考虑不能情况。 如果字符串的长度为奇数，那么必然不能回到原点。 如果字符串的长度为偶数，那么必然有解。（最多把所有的字符串变成UDUD） 然后分开考虑，L 和 R 相对， U 和 D 相对。 求出在x方向和y方向的需要修改的字符数量。 容易知道我们可以把需要修改的数量加起来，然后除以2可以得到修改的次数。（两个方向的需要修改数量，必然为偶数）

C. Memory and De-Evolution 题目链接 题目大意： 有两个正三角形，边长分别为x，y。 现在可以对三角形进行操作，每次操作可以改变三角形的一条边长度（为整数），变成另外一个三角形。 问让正三角形x 变成 正三角形y 的最小操作次数。 x and y (3 ≤ y < x ≤ 100 000)

** Examples** ** input** 6 3 ** output** 4 样例解释：666 -> 663 -> 643 -> 343 -> 333 总共需要操作4次

** 题目解析：** 三角形的性质:两边之和大于第三边。 反过来考虑，把三角形y变成三角形x。（操作步数是一致的） 那么自然可以想到一种贪心：每次把最小的边变得最大。 每次操作完排序，再对最小的进行变大。 直到最小的边也等于x。

D. Memory and Scores 题目链接 ** 题目大意：** A 和 B玩一个游戏，游戏分成t轮。 初始时，A和B的分数为a和b； 每轮游戏，A和B都可以从[-k, k]的区间里面选择一个整数加到自己的分数； 问最后有多少种可能，A的分数大于B的分数。 （只要某一轮A或者B的分数不同，即视为不同的可能）

a, b, k, and t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100) 结果mod 1 000 000 007 (1e9 + 7)。

Example ** input** 1 2 2 1 ** output** 6 ** 样例解释：** In the first sample test, A starts with 1 and B starts with 2. If B picks  - 2, A can pick 0, 1, or 2 to win. If B picks  - 1, A can pick 1 or 2 to win. If B picks 0, A can pick 2 to win. If B picks 1 or 2, A cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which A wins.

** 题目解析：** 容易知道，每次的选择都是[-k, k]，那么总共就有(2k + 1)个选择； t轮之后就是(2k+1)^t个选择。 接下来考虑去重，存在一轮分数不同，即是在第i轮的时候，选择不同的数字。 那么，我们用dp[i][j]来表示 前i轮，分数等于j的选择个数。 这样就可以统计出t轮之后，分数为j的不同选择个数。 先是对A dp出t次后的结果，再对B dp出t次后的结果。这两个都是O(NK^2)。 最后再对dpB[n][j] 统计下所有∑dpA[n][c]，c > j，然后相乘，得到B为j的时候，A赢的选择数。 最后累加j = [-k * k / 2, k * k / 2]的和即可。

** 小技巧：** 1、为了方便计算，把所有的状态都加上一个offset，这样-k*k/2 就变成正数，避免dp过程中访问到下标是负的情况； 2、为了状态转移更快，dpA[i][j] 可以存分数为1到j的和，这样分数为j的值可以通过dpA[i][j] - dpA[i][j - 1]求出。

总结

趁着写文章，回顾下这四个题目，发现A/B/C对于我来说都是很简单题目，D需要一些思考和细节的考虑，算中等题。 但是对某些牛，可能他做D的难度就和我做前三个的难度差不多。 差距是哪里？？ 1、角度，大牛思考更全面，能用最适当的思路去解决问题； 2、熟练度，像offset、mod、累加这些trick大牛一眼就看穿并且熟练地实现； 3、复杂度，大牛经常面对很多更复杂的情况，再回过来处理这些题目就更为容易； 或许还有其他原因，但是就这三点就值得深思。 如果是要做题目，应该先看到出题人的思路，顺着这个方向查看设置的trick，在有具体的解法后要完善好细节再实现； 如果是工作开发，则是要理解产品的需求，从用户的角度观察未来可能的变化，在设计好具体的解决方案后，再进行开发； 三思而后行，这是非常难以坚持的要求。