JavaScriptでLeetCodeを始めました~Array編~[後編]

leetcode プログラミング

やっぱりブログは放置すると全く書かなくなるので、意識的に後編書きます！
ちなみにLeetCodeは引き続き進めてまして、今週末にはString終わりたいなって思っています。あと並行してNext.jsの勉強もしています。 Next.js、結構癖はありますが、使いこなすと間違いなく今のSPAよりはパフォーマンス出るのでしっかりと吸収したいです。ただ勉強しながら日常シーンでのユースケースに当てはめると、「これNext.jsで一からやらなくても、Gatsby.jsでいいな」って思うことが多いです。それだけNext.jsのラッパーとしてのGatsby.jsが優秀とも言えますが…。
閑話休題。LeetCodeのTop Interview Easy CollectionのArray編について後編を書いていきたいと思います！

Intersection of Two Arrays II

問題内容は、「2つのArrayを与えられた時、共通する要素を取り出せ」という感じです。 ミソとなるのが、一方のArrayが複数の要素を持ちつつ、もう一方が1つの場合でして、例えばAが[2, 2, 3]でBが[1, 2, 3]とします。この時、Aを軸にしてArrayを回すと以下のようになります。

  1. A[0] = 2の時、Bで同じ要素を探すｰ>B[1]
  2. A[1] = 2の時、Bで同じ要素を探すｰ>B[1]
  3. A[2] = 3の時、Bで同じ要素を探すｰ>B[2]

となり、[2, 2, 3]が返ってきます。しかし、Aには2が2つ含まれていますが、Bには1つしか含まれていないため、これは誤りです。 したがって、この問題では同じ添字の要素は2度と使わないように注意する必要があります。以上を踏まえたコードが以下になります。

const intersect = (nums1, nums2) => {
  let arr = [];
  nums1.forEach((_, i) => {
    const num = nums2.indexOf(nums1[i]);
    if (num > -1) arr = [...arr, nums1[i]];
    nums2[num] = Infinity;
  });
  return arr;
};

やっていることは上記の説明と一緒です。そして、同じ添字の要素を2度と使わないように、num2[num] = Infinityを代入することで要素を上書きしています。InfinityはJavaScriptで扱うあらゆる数字より大きいため、Infinityを入れることで逆にInfinityとマッチすることになったという問題は生じません。(逆にそうなるのは設計的にやばいと思います。)以上で、この問題をクリアできました。ちなみに、わざわざ別のArrayを用意しなくても、どちらにも同じ要素はあるのだから、一方をfilterすればええやんと思い至ったのが以下の解法になります。こちらで若干スピードは早くなりました。

// little bit improved
const intersect = (nums1, nums2) =>
  nums1.filter((item) => {
    const num = nums2.indexOf(item);
    if (num > -1) {
      nums2[num] = Infinity;
      return true;
    } else {
      false;
    }
  });

Plus One

配列で与えられた数字を文字列と解釈して、そこに1を足した結果を求めましょうという問題。 問題となるのが、配列で渡されるのでJavaScriptのnumberで扱える253-1以上の数字になるケースもある。当初はそこに思い至らず、弾かれてしまいました。 ここで本来であれば、stringを上手く扱って計算するのがこの問題で求められていることなのかもしれませんが、幸いにもJavaScriptにはBigIntがあります。

developer.mozilla.org

BigIntは253-1以上をJavaScriptで扱えるようにしてくれるオブジェクトです。通常のnumberと計算できなかったり、Mathオブジェクトの持つメソッドが使えなかったりしますが、今回のようなユースケースでは問題ありません。以下がBigIntを用いた解法になります。

const plusOne = (digits) => {
  if (digits.length > 15)
    return (BigInt(digits.join("")) + 1n).toString().split("");
  return (parseInt(digits.join("")) + 1).toString().split("");
};

digits.length > 15は、BigIntを用いるケースをここで選択しています。正確には、ここで選ばれるのは、250以上のケースですが、ここで一々配列を数字に直して253-1と比較するよりも配列で250以上のケースをBigIntにしてしまうほうがお手軽だろうと考え、この条件にしました。これにより解法は、

  1. 配列をjoinして文字列にする
  2. 文字列を数字に変換して1を加える
  3. それをさらに文字列にして、配列にする

というフローを経て求まることができます。

Move Zeroes

問題は、「数字の配列が与えられた時、0のみを配列の後ろに回せ」というものです。
実は、この問題はJavaScriptでは凄く簡単に行うことができます。JavaScriptのArrayオブジェクトが持つsort関数は引数を渡さない場合、昇順でソートを行います。しかし、sortの引数として比較をするためのコールバック関数を渡すと、そのロジックに基づいてソートを行ってくれます。

developer.mozilla.org

今回の場合は、配列の前の値と次の値を引数に受け取り、それをもとにソートするロジックを書きました、コードは以下のようになります。

const moveZeroes = (nums) => {
  nums.sort((pre, cur) => {
    if (pre === 0) {
      return 1;
    } else if (cur === 0) {
      return -1;
    }
  });
};

もし前の値と次の値を比較して、前の値が0ならば後ろに回すべきなので1を返します。(sortの比較関数では、0以上を返した場合、前の値と次の値を入れ替えます)対して、次の値が0であるならば順番はこのままで大丈夫ですので-1を返します。(0以下を返す場合は、順番はそのままになります)
これにより今の配列の順番はそのままに、0だけを後ろに回すことができました！Plus OneとMove ZerosはJavaScriptらしい良い解き方ができたのではないかと個人的に満足しています😊

Two Sum

「数字が要素の配列とtargetとなる数字が与えられる。配列から2つ選んだ数字を足し合わせて、targetの数字を導いた時、それぞれの数字について配列での添字を求めよ」という問題。解法については、当初はブルートフォースしか出てこなかったです。ただ少しでもパフォーマンスを良くしようと以下のように書きました。

const twoSum = function (nums, target) {
  let ans = [];
  dual: for (let index = 0; index < nums.length; index++) {
    const rest = target - nums[index];
    for (let i = index + 1; i < nums.length; i++) {
      if (nums[i] === rest) {
        ans = [index, i];
        break dual;
      }
    }
  }
  return ans;
};

JavaScriptのfor文にはlabelをつけることができます。今回の場合、外側のfor文にdualというlabelをつけました。その上でブルートフォースを行い、あるindexの時、target から一方の値を引いた残りをrestという変数に入れます。そして、残りの配列からもしrestとマッチする要素があった時にはそれぞれの値を配列にして、dualをbreakすることによりfor文全体を止めるというアプローチです。ただ、これではブルートフォースなのでパフォーマンスが出ません。 そこで解法を見ると、HashMapを用いた解法がありましたので、以下にベター解法として記します。

// HashMap
const twoSum = function (nums, target) {
  const map = new Map();

  for (let index = 0; index < nums.length; index++) {
    const rest = target - nums[index];
    if (map.has(rest)) {
      return [index, map.get(rest)];
    }
    map.set(nums[index], index);
  }
};

HashMap法ではもし今の値のrestをmapに見つけられなかった場合、mapにその値をキーとし、値には添字を入れてsetします。これにより、もしその添字が回答であったとしても、後にもう一方の添字がindexの時にmapから残りの添字を求めることができます。このmapによりfor文を2重にすることが避けられました。

Valid Sudoku

この問題は、恥ずかしながら問題を読み間違えて回答できませんでした。 問題は、与えられた数独が成り立つか成り立たないかを回答するだけなのですが、なぜか数独全てを回答せよと勘違いして、答えることができませんでした😓そこでYouTubeの解法を参照したのですが、そこで見つけた解法により「求めるべきは与えられた情報下で数独が成り立つか否か」ということに気づきました。同時にYouTubeの解法がめちゃくちゃ良かったのでそれを用いました。

www.youtube.com

今回はYouTubeに頼らざるを得ませんでしたが、次は自分でしっかり解きたいです😤 解法は以下の通りです。

const isValidSudoku = function (board) {
  const foundMap = new Map();
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const num = board[i][j];
      if (num !== ".") {
        if (
          foundMap.has(`found ${num} at row${i}`) ||
          foundMap.has(`found ${num} at column${j}`) ||
          foundMap.has(
            `found ${num} at subbox${Math.floor(i / 3)} & ${Math.floor(j / 3)}`
          )
        ) {
          return false;
        }
        foundMap.set(`found ${num} at row${i}`);
        foundMap.set(`found ${num} at column${j}`);
        foundMap.set(
          `found ${num} at subbox${Math.floor(i / 3)} & ${Math.floor(j / 3)}`
        );
      }
    }
  }
  return true;
};

Mapを作ります。そして、for文を2重に回し、1マスずつ確認していきます。もしマスに値が入っていた場合は、縦横周囲9マスに同じ値が入っているかを確認します。同じ値が入っていた場合は、数独として成り立たないとみなしfalseを返します。
逆に同じ値が見つからなかった場合は、その値をsetします。無事同じ値がなく全てのマスについて走査が終わればtrueを返します。 以上のシンプルなアルゴリズムですが、基本としてHashMapを用いること、そしてset時に値と添字情報をkeyとしてまとめること、また周囲9マスのためにそれぞれの添字を3で割った数字を用いていることなどの工夫が見られ勉強になりました。ここでの失敗を糧にHashMapを使う大切さを学べたので結果オーライかなって思ってます！✌️

Rotate Image

問題の内容は、「与えられたn × nのマトリックスについて右に90度回転させたときの形を答えよ」というものです。
内容自体はシンプルですし、アルゴリズムについては右に回転させた時の回転先を適切に退避させて、そこに移動してきた数字を代入しするという難しくないものです。ポイントとしては、何も考えずに移動させると移動させようとした値が既に他の値により入れ替わっておりマトリックスが崩れるというものです。また、退避させるための配列も元の値が他の値の移動により置き換わるので、それを考慮したアルゴリズムが必要です。 上記を意識し、外側から回転させて行く形でアルゴリズムを書いたものが以下になります。

const rotate = function (matrix) {
  // マトリックスの1行の長さが2の倍数のたびに増える
  const times = Math.floor(matrix.length / 2);
 // 退避用配列。2つ必要。
  let temp = [];
  let temp2 = [];

  for (let index = 0; index < times; index++) {
    for (let j = index; j < matrix.length - index; j++) {
      temp[j] = matrix[matrix.length - 1 - j][matrix.length - 1 - index];
      matrix[matrix.length - 1 - j][matrix.length - 1 - index] =
        matrix[index][matrix.length - 1 - j];
    }
    for (let k = index; k < matrix.length - index; k++) {
      temp2[k] = matrix[matrix.length - 1 - index][k];
      matrix[matrix.length - 1 - index][k] = temp[k];
    }
　// temp2はtemp1で最初の移動で動かした値によりアップデートされているので、
　// tempからオリジナルの値を持ってくる
    temp2[temp2.length - 1] = temp[0 + index];

    for (let l = index; l < matrix.length - index; l++) {
      temp[l] = matrix[l][index];
      matrix[l][index] = temp2[l];
    }
　// 上と同様で退避した値が既にアップデートされているので、temp2からオリジナルを持ってくる
    temp[temp.length - 1] = temp2[0 + index];
    for (let m = index; m < matrix.length - index; m++) {
      matrix[index][m] = temp[matrix.length - 1 - m];
    }
   // 都度ループを終えるたびに退避用配列を初期化する
    temp = [];
    temp2 = [];
  }
};

こちらで動くのですが、今考えるとHashMapでもっと楽に回転を制御できそうな気もします。特に移動により打ち消された値は、HashMapで保持すればもっと楽に回せそうな気がしました。計算量も多くスピードも奮わないので、今度、時間がある時にHashMap版を追記できればと思います！

まとめ

というわけで、Array編後編を書けました！
飽き性＆面倒くさがり屋なので元来ブログは向いていないのですが、何とか書き切れました！
来週にも頑張ってString編について書けるといいなと思います！自分の勉強のためにもがんばります！
もし本ブログをご覧になった方で「ここ間違っているよ」とか「ここもっとこういう風に書けるよ」などアドバイスがありましたら、ご指摘いただけると助かります。何分、まだまだ弱いエンジニアなので勉強できればと思います。
それでは、また一週間後ブログを書いていること祈って、今回は終わりたいと思います！🙏