Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

字母板上的路径 #170

Open
louzhedong opened this issue Jul 28, 2019 · 0 comments
Open

字母板上的路径 #170

louzhedong opened this issue Jul 28, 2019 · 0 comments

Comments

@louzhedong
Copy link
Owner

习题

出处 LeetCode 算法第5040题

我们从一块字母板上的位置 (0, 0) 出发,该坐标对应的字符为 board[0][0]

在本题里,字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

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

  • 如果方格存在,'U' 意味着将我们的位置上移一行;
  • 如果方格存在,'D' 意味着将我们的位置下移一行;
  • 如果方格存在,'L' 意味着将我们的位置左移一列;
  • 如果方格存在,'R' 意味着将我们的位置右移一列;
  • '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

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

示例 1:

输入:target = "leet"
输出:"DDR!UURRR!!DDD!"

示例 2:

输入:target = "code"
输出:"RR!DDRR!UUL!R!"

提示:

  • 1 <= target.length <= 100
  • target 仅含有小写英文字母。

思路

从一个字母到另一个字母有一个最短的矩阵距离,只要按直线行走即可。

注意点:z这个点的位置比较特殊,因为z的右边没有其他点,所有从z不能往右移动,其他点也不可能向左移动到达z点

解答

/**
 * @param {string} target
 * @return {string}
 */
var alphabetBoardPath = function (target) {
  var result = '';
  var board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]
  var length = target.length;
  var currentX = 0;
  var currentY = 0;
  for (var i = 0; i < length; i  ) {
    for (var j = 0; j < board.length; j  ) {
      if (board[j].indexOf(target[i]) > -1) {
        var tempY = j;
        var tempX = board[j].indexOf(target[i]);
        if (currentX == tempX && currentY == tempY) {
          result  = '!';
        } else {
          if (currentX == 0 && currentY == 5) {
            var diffY = tempY - currentY;
            if (diffY > 0) {
              for (var p = 0; p < diffY; p  ) {
                result  = 'D'
              }
            } else {
              for (var p = 0; p < Math.abs(diffY); p  ) {
                result  = 'U'
              }
            }
            var diffX = tempX - currentX;
            if (diffX > 0) {
              for (var p = 0; p < diffX; p  ) {
                result  = 'R'
              }
            } else {
              for (var p = 0; p < Math.abs(diffX); p  ) {
                result  = 'L'
              }
            }
          } else {
            var diffX = tempX - currentX;
            if (diffX > 0) {
              for (var p = 0; p < diffX; p  ) {
                result  = 'R'
              }
            } else {
              for (var p = 0; p < Math.abs(diffX); p  ) {
                result  = 'L'
              }
            }
            var diffY = tempY - currentY;
            if (diffY > 0) {
              for (var p = 0; p < diffY; p  ) {
                result  = 'D'
              }
            } else {
              for (var p = 0; p < Math.abs(diffY); p  ) {
                result  = 'U'
              }
            }
          }
          result  = '!';
        }
        currentX = tempX;
        currentY = tempY;
      }
    }
  }
  return result;
};

console.log(alphabetBoardPath('zb'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant