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

LeetCode始めました

世間は緊急事態宣言も解除され、徐々に街に活気が戻りつつある今日この頃いかがお過ごしでしょうか🐹
自分はリモートワークが苦になりませんし、早朝など人を避ける時間にウォーキングやジョギングすれば運動不足も解消できるので、もうずっとリモートワークでいいです。というか、現職のリモートワークが解除されても、可能な限りリモートワークは続けようと画策しています。止める理由もないので😤
さて、リモートワークで通勤時間が空いた分、余暇が生まれました。当初はAndroid開発の勉強したりN予備校Scalaを勉強していたのですが、最近海外で働きたい欲が芽生えまして、スタディサプリとLeetCodeに励んでいます。

LeetCodeはエンジニア向けのコーディングインタビューで使われた実際の問題をまとめているサイトです。有料な部分もありますが、無料でほとんど遊べます。あと回答などで有料じゃないと分からないときもググれば親切な人が解説してくれています😍
というわけで、せっかくLeetCodeに取り組むのならば自身の復習とアウトプットを兼ねて、JavaScriptを用いてLeetCodeに取り組んだ成果をブログに残していきたいと思います。現在のテーマは、Top Interview Questionsという定番問題一覧のEasy(難しすぎると心が折れるからね😘)を上から順番に解いていくという感じです。今回は、「Array」編です!

1. Remove Duplicates from Sorted Array

記念すべき初めての問題です。問題内容は、「渡された配列から複製された要素を取り除いて、ユニークな数だけの配列の長さを返せ」です。
当初は、以下のようにfilterを用いて単純な配列の長さを返していました。

const WrongRemoveDuplicates = (nums) =>
  nums.filter((val, index) => val !== nums[index + 1]).length;

しかし、それでは回答が通らずよくよく調べてみると、渡された配列を変える必要がありそう🤔ということに気づきます。(in-placeという言葉が出てきたらそんな感じで回答する必要があるみたいです)

そこで、以下のようにnumsに再代入を試みました。

const WrongRemoveDuplicates2 = (nums) => {
  nums = nums.filter((val, index) => val !== nums[index + 1]).length;
  return nums.length;
};

しかし、これもうまくいかない。よくよく見てみると、配列の参照を渡すわけであり、これはnumsに別の配列を与えただけで大本のnumsは変更されていないのですね。(ここに至るまでに謎すぎて回答を見て、やっとこの考えに辿り着きました…)
というわけで、「大本のnumsを変えるために、直接渡されたnumsの各要素を修正する必要がある。また、配列の長さは変更しないので、長さを管理する変数が必要」との理解にいたり、最終的に以下のような実装にしました。

/**
 * @param {number[]} nums
 * @return {number}
 */
const removeDuplicates = (nums) => {
  let ans = 0;
  nums.forEach((_, index) => {
    if (nums[index] !== nums[index + 1]) {
      nums[ans] = nums[index];
      ans++;
    }
  });
  return ans;
};

これでパフォーマンスは上位1%になるのでOKかと思っています。

f:id:bebe-taro:20200524175703p:plain
leetcode_remove_duplication

2.Best Time to Buy and Sell Stock II

2つ目の問題は、「与えられた配列でBuyとSellを最適なタイミングで行った場合の最大利益を答えよ」という問題です。
1つ目の問題は、アルゴリズムについては分かるけど、回答方法がわからないという問題でした。しかし、こちらはブルートフォースすら上手くいかず、マジで回答が分からず詰んだ問題です。結局、2時間ほど悩んで答えが出なかったので、諦めて答えを見ました。

まず、ブルートフォースに行ったやり方ですが、普通にランタイムエラーとなりました。なので、この問題はそもそもブルートフォースにやる事が間違っているとここで気づきます(そもそも計算量的にブルートフォースで試みるのは多くの場面で悪手ですが…)

//  Brute force => Runtime Error
const maxProfit = (prices) => {
  const calculate = (prices, s) => {
    if (s >= prices.length) {
      return 0;
    }
    let max = 0;
    for (let start = 0; start < prices.length; start++) {
      let maxProfit = 0;
      for (let i = start + 1; i < prices.length; i++) {
        if (prices[i] > prices[start]) {
          let profit = calculate(prices, i + 1) + prices[i] - prices[start];
          if (profit > maxProfit) {
            maxProfit = profit;
          }
        }
      }
      if (maxProfit > max) {
        max = maxProfit;
      }
    }
    return max;
  };
  return calculate(prices, 0);
};

回答に載っていて、実際に使用できるのは、①ピークバレー法と②Simple One Pass法です。

この2つの方法に共通する考えとして、「谷の時に買って次の山の時に即座に売ることが最大利益に繋がる」という点に気づけなかったことが一番の敗因と思い知りました。もっと勉強が必要ですね😭

ピークバレー法とSimple One Pass法の回答は以下のようになります。どちらも速度はあまり出せませんでした。
違いとしては、ピークバレー法は愚直にその都度谷と山を探して計算していますが、Simple One Pass法は、「現在の値と一個前を比較して現在の値の方が大きければ、それはもう山と谷やろ」という具合にシンプルに捉えていることによりコードがすっきりしています。
個人的にはSimple OnePass法の方が好きですね☺️

// Peak-Valley
const maxProfit = (prices) => {
  let i = 0;
  let valley = 0;
  let max = 0;

  while (i < prices.length - 1) {
    while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
    valley = prices[i];
    while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
    max += prices[i] - valley;
  }

  return max;

};
const maxProfit = (prices) => {
  let maxprofit = 0;
  prices.forEach((_, i) => {
    const num = i + 1;
    if (prices[num] > prices[num - 1])
      maxprofit += prices[num] - prices[num - 1];
  });
  return maxprofit;
};

3. Rotate Array

この問題が初めて自力で解けた問題です。 内容としては、「配列と数字が与えられる。数字の回数分、配列の後半部分を前にシフトしろ」という問題です。具体例としては、nums = [1,2,3,4,5,6,7], k = 3のときは、回答が[5,6,7,1,2,3,4] となるようにします。そして、以下が自分の回答になります。

const rotate = (nums, k) => {
  Array(k)
    .fill(0)
    .forEach(() => {
      nums.unshift(nums.pop());
    });
};

解説しますと、与えられた数字分の長さを持つ空配列を作り、その配列にforEachを回させて、あとはpop関数により後ろにある要素を吐き出させ、それをすぐさまunshiftで配列の先頭に差し込むといった具合です。JavaScriptの関数を上手く使えて個人的には気に入っているのですが、パフォーマンスは発揮しませんでした。popunshitは結構重たいのでしょうか?その後、アルゴリズムをいじった結果、以下のコードで上位30%程度の速さは出るようになりました。

const rotate = (nums, k) => {
  // 変数挟むほうが早くなる
  const arr = [
    ...nums.slice(nums.length - k, nums.length),
    ...nums.slice(0, nums.length - k),
  ];
  arr.forEach((_, i) => {
    nums[i] = arr[i];
  });
};

こちらを解説しますと、slice関数を用いることで、numsから変数k以後とk以前で配列を分けます。その後、スプレッド演算子で新たに配列を作り、その値をforEachでnumsに渡しています。最後のnumsに渡すところがイケてない感じしますが、速度はこっちの方が速いんですよね…。とはいえ、実務では30ms程度なので、可読性の良い方を採用したいですね。

4. Contains Duplicate

「与えられた配列に同じ値が含まれていれば、true を返し、ユニークな値だけならばfalseを返す」という問題。
「値がバラけててアレやけど、ソートしたら前後の値を比較するだけで分かるやんけ!」と天啓が舞い降りてきたことにより、3番目の問題に続いて一発クリアできた。ただメモリ消費量は少ないものの、速さは上位50%程度なので、まあ普通ぐらい…😅

const containsDuplicate = (nums) => {
  nums.sort();
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) {
      return true;
    }
  }
  return false;
};

上位50%程度が悔しくて、なんとか改善できないかとreduceMapを使った解法を試みるも、速度が改善できないどころか悪化したので諦める…。そもそも一番最初に考えついた解法も後々答えを確認すると、模範解答と同じだったため他に模範解答を提出している人たちとバッティングして上位層には食い込めないのかなーっと思っています。ただせっかくreduceMapの解法を書いたので、成仏がてらここに書いときます。

// reduce
const containsDuplicate = (nums) => {
  let ans = false;
  nums.length > 1 &&
    nums.sort().reduce((pre, cur) => {
      if (pre === cur) {
        ans = true;
      }
      return cur;
    });
  return ans;
};

前回の値と今回の値を比較し、同じならans変数にtrueを入れる。常に現在の値をreduceの返り値とする。今考えると、単純にfor文を回すからパフォーマンスが悪化して当然である。

// Map
const containsDuplicate = (nums) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) return true;
    map.set(nums[i]);
  }
  return false;
};

Mapを用いてもし値が既にあるならば、true見つからずにfor文が終わればfalseアルゴリズム。個人的にはスマートで気に入っている。あと他の問題でもHashMapを使えばクリアできる事が多いので、HashMapは信頼している。ただこの問題には奮わず、速度は悪化してしまった。残念。

5.Single Number

「与えられた配列の中で重複のないユニークな値を取り出しなさい」という問題。
ここらへんの問題は、割と実務でも似たようなケースを取り扱うことがあるため、普通に解くことができた印象。実際には、以下のようにして回答した。

const singleNumber = function (nums) {
  const map = new Map();
  nums.forEach((val) => {
    if (map.has(val)) {
      map.set(val, 2);
    } else {
      map.set(val, 1);
    }
  });
  for (const [key, value] of map.entries()) {
    if (value === 1) return key;
  }
};

先程も使ったMapを用います!配列をforEachで回して、出てくる値を既に持っていた場合は、その値をキーに2というバリューでセットします。(ここ適当に2にしましたが、NonUniqueなどの文字列使う方が丁寧かなと思います)また、初めての場合は、1をセットします。こうして、forEachが終わった後、Mapの値を精査して1なものがあれば、そのキーを唯一のユニークな値として返すことができます。
個人的には、結構上手くやれた印象を持ったこの問題ですが、実際のパフォーマンスは下位20%でした。なかなか改善も捗らず、答えを見たところ次のような解法がありました。

const singleNumber = function (nums) {
  let bit = 0;
  nums.forEach((val) => {
    bit ^= val;
  });
  return bit;
};

これ何しているかわかりますか?ちなみに自分は初見ではこのような解法思いつきもしないし、JSでやれるとも思っていませんでした。
^はJSでXORを行うための演算子なのですが、これで次々と配列の値と初期値0をXORしていくと、配列内にある重複した値は打ち消し合い0になり、初期値の0と打ち消しあった0のXORは0のままであるため、最終的にユニークな値と0のXORにより答えが求まるという解法です。いや、本当、ビット演算子なんて普段はなかなか使わないし思いつきもしないですが、実際使えると便利な場面ってこうやって出てくるんだなと実感しました。こういう解法出てくるぐらいにもっとJS勉強していきたいですね。参考までに、MDNのビット演算子ページからXORを解説している部分のURL貼っておきます。

developer.mozilla.org

ちなみに、ビット演算子の計算を用いても、上位50%には及びませんでした…😱
ただソースコード見るとやっていることは変わらないので、結構運というか結果を演算しているサーバーの調子次第かなっと思い、これ以降パフォーマンスはそんなに気にならなくなりました。

前編のまとめ

というわけで、Top Interview Questions Array編の前半を終わりました。
ちょっと長くなりましたので、今回はここで切って近い内に後編についてもまとめたいと思います!
Easy問題は確かに問題内容が簡素で、やり方さえ見えれば簡単に解けるのですが、如何せん自分の不慣れな面もあり結構悩むところも多かったです。ただ、Array問題11問を解いていく中でソートやHashMapを使うという点は身についたので、これらを武器に他の問題にも挑戦していきたいと思っています!また、今後他の問題を解き進めていく中で、もっと手法にも詳しくなりビット演算子とかちゃんと使えるようになれれば本望です☺️まだまだ道は長いですが、頑張っていきたいですね✌️