今日头条 2018 AI Camp 5月26 日在线笔试编程题第一道——最佳路径

阅读文本需要大概 8. 2 分钟

如有问题或建议，请公众号留言

题目

给定一个 n*m 的矩阵 A ，矩阵中每一个元素为一个十六进制数。寻找一条从左上角都右下角的路径，每次只能向右或者向下移动，使得路径上所有数字之积在 16 进制下的后缀 0 最少。

输入描述：

第一行：n, m (2

接下来 n 行，每行 m 个 16 进制整数

输出描述：

第一行：最少后缀 0 的个数(十进制)

第二行：路径方案，从左上角开始，">" 代表向右移动，"V" 代表向下移动。 如果有多种方案，输出字典序最小的方案(">" 的字典序小于 "V")。

示例：

输入

3 3

3 2 8

c 8 8

2 a f

输出

说明

从左上角到右下角的所有路径中， 0x3 * 0x2 * 0x8 * 0x8 * 0xf = 0x1680 后缀 0 最少为 1， 且路径 “>>VV” 的字典序最小。

思路

1.首先需要设计一个函数来判断十六进制数字末尾零的个数。可以分为两种情况，小于 16 的数只有 0 末尾有一个零；大于等于 16 的数如果最后一位是 0，则肯定可以被 16 整除，若末尾是 0，我们对这个十六进制数向右移一位，也即除以 16，再看倒数第二位是否是零，这样一直往前判断直到某一位非零为止。

2.路径判断则用动态规划来实现。定义两个变量，第一个变量保存从左上角到每一个位置处的乘积，第二个变量保存是怎样从前一步到当前位置的，只有向右或者向下两种情况，用枚举表示。第一行只能向右走，第一列只能向下走，这是初始化情况。然后从第二行第二列开始进行判断，每一步比较从左边来的乘积和从上边来的乘积末尾含有零的个数，若二者不相等，则保存乘积和移动方向到相应变量中。若向下和向右二者相等，则需要分别向上和向左回溯到左上角倒序求出移动方向，然后从头开始比较，选择字典序小的路径作为最终的移动方向。

样例展示(从左到右分别是原始数字、十六进制乘积和移动方向)

第二行第二个位置，从左边来是 24×8 = 120，末尾有 1 个 0；从上边来是 6×8 = 30，也有 1 个 0。

从左边来路径是 V>，从右边来路径是 >V，由于 > 字典序小于 V，因此最终移动方向为 >V。

代码实现

文章仅为个人见解，如有错误，欢迎交流与指正！

欢迎点赞和转发！