23.2.12 LC每日一题 —— 极尽地高效利用题目中所提供的有效信息

高效利用题目中所提供的有效信息"/>

23.2.12 LC每日一题 —— 极尽地高效利用题目中所提供的有效信息

文章目录

• 23.2.12 LC每日一题 —— 极尽地高效利用题目中所提供的有效信息
• • 题目链接：
  • • 题目大意：
    • 注意：
    • 示例：
    • 参考代码（py3）：
• 总结

23.2.12 LC每日一题 —— 极尽地高效利用题目中所提供的有效信息

题目链接：

  1138. 字母板上的路径

题目大意：

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。
在本题里，字母板为board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]，如下所示。

我们可以按下面的指令规则行动：

• 如果方格存在，‘U’ 意味着将我们的位置上移一行；
• 如果方格存在，‘D’ 意味着将我们的位置下移一行；
• 如果方格存在，‘L’ 意味着将我们的位置左移一列；
• 如果方格存在，‘R’ 意味着将我们的位置右移一列；
• ‘!’ 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
  （注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

注意：

（1）1 <= target.length <= 100；
（2）target 仅含有小写英文字母。

示例：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"输入：target = "code"
输出："RR!DDRR!UUL!R!"

参考代码（py3）：

# 一开始想错了，这道题和 剑指 Offer 12. 矩阵中的路径 挺像的
class Solution:def alphabetBoardPath(self, target: str) -> str:i = j = 0ans = []for c in target:v = ord(c)-ord('a')x,y = v//5,v%5while j>y:j -= 1ans.append("L")while i>x:i -= 1ans.append("U")while j<y:j += 1ans.append("R")while i<x:i += 1ans.append("D")ans.append("!")return "".join(ans)              

总结

  这道题非常地典型一开始我想用 dfs 去做，但发现做着做着就出问题了，忘了记录重复的路不要再走，这道题啊！非常的具有技巧性，首先字母表示确定的，不仅格式固定，内容也极具规律；再者所检测的数据量较少，可以充分利用昨天的那篇blog中的 char 与 ascii 之间的关系简化运算，多思考多总结，学海无涯。