面試遇到的問題 HackerRank: keyboard

題目:

每天，電子商務公司的員工需要在3 x 3 的數字鍵盤上輸入一組數字才能進入建築物。每天，鍵盤上的數字都會重新排列。使用以下規則計算輸入字符串所需的總時間：

• 移動手指到第一個按鍵需要 0 秒，按下手指所在位置的按鍵需要 0 秒。
• 他們可以在一秒內將手指從一個位置移動到任何相鄰的按鍵。相鄰的按鍵包括對角線上的按鍵。
• 移動到非相鄰按鍵是通過一系列移動到相鄰按鍵完成的。(可以藉由相鄰按鍵移動到其相鄰，更遠的按鍵)(所需時間會跟著增加)

函數具有以下參數：

• string s：要輸入的數字
• string keypad：9 個數字，其中每組 3 個數字表示當天鍵盤上的一行，由上至下，由左至右

return：

• int：表示輸入數字所需的最小時間的整數。

說明:

給你一個數字打亂的3X3鍵盤，計算輸入完數字所需的時間。

從當前數字移動到上下左右(包含斜)的位置需要1秒的移動時間，再更外面需要2秒(移動到前一個數字需1秒，再移動至更外側再加1秒)。輸入同一數字不需移動所以秒數不會增加。

以上圖舉例，從5移動到任一數字均只需1秒。而由9移動到3則需2秒(9到6, 6 到3)

想法:

先依照keypad參數建置3X3的2d陣列，位置示意圖如下:

位置示意圖

在建置2d陣列的同時，也將當前數字的座標位置儲存進hashMap當中。

建置完成後，遍歷s參數，在取得當前數字的同時也取得下一個要輸入的數字，並從hashMap取得在鍵盤上各自的座標位置。

接著就是本題的重點了，要如何判斷秒數呢?其實很簡單，透過取得兩座標的x座標之差與y座標之差，再選取其中的最大值，即所需的秒數。

遍歷s參數後，回傳總秒數即可。

code:

function keyboard(s, keypad) {
  // creating a 3x3 2d array
  const matrix = new Array(3).fill(null).map(() => new Array(3));
  const hashMap = {};

  let res = 0;

  // filling the 2d array with the keypad
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      matrix[i][j] = keypad[i * 3 + j];
      hashMap[keypad[i * 3 + j]] = [i, j];
    }
  }
  // looping through the input 's' and finding the distance between the current and next character
  for (let i = 0; i < s.length - 1; i++) {
    const curStr = s[i];
    const [curX, curY] = hashMap[curStr];
    const nextStr = s[i + 1];
    const [nextX, nextY] = hashMap[nextStr];

    // if the current and next character are the same, we skip it
    if (nextStr === curStr) continue;
    // adding the distance to the result
    res += Math.max(Math.abs(nextX - curX), Math.abs(nextY - curY));
  }

  return res;
}

心得:

本來以為是要用graph的思路去解，浪費了很多時間導致這題沒做完，結果沒想到竟然可以用這種解法，看來我還太菜了…