TypeScriptでLeetCodeを始めました~Sorting and Searching編~ - ムスリムエンジニアbebetaroのブログ

最近体調が良くないので、今日は省エネ更新です…😷
リモートワークが続いているので、なるべく体の不調には気をつけていたつもりなのですが、崩れる時には崩れちゃいますね…。私事ですが、9月に子供も生まれる予定ですので、健康が何より一番だと痛感しています…。睡眠、食事、運動、ストレス、この4つが適切な状態であることが大事なので、みなさんもお気をつけ下さい🙏 さて、それでは早速問題に移りたいと思います。

Merge Sorted Array
First Bad Version
まとめ

Merge Sorted Array

「２つのソート済配列nums1, nums2が渡される。nums2をnums1に組み込んで1つの配列にせよ」という問題です。これはin-placeなので新規に配列を作ってはだめで、必ずnums1を操作する必要があります。また、nums1には操作するためのダミー要素として0が挿入されています。これを踏まえて以下のように解きました！

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  for (let index = m; index < m + n; index++) {
    nums1[index] = nums2[index - m];
  }
  nums1.sort((a, b) => a - b);
}

nums1のうち、元々nums1の値を持っている範囲は重要ではなく気にかけるべきなのは、nums2の値が代入される部分です。したがって、nums1の走査をmから行い、そこにnums2の値を最初から入れていきます。ここでは順番を気にしません。その後、配列の元々持っているsort関数で昇順にすることで答えが導けます！(in-placeなので返り値もないです) シンプルかつ簡単な問題ですね！

First Bad Version

「あなたはとあるプロダクトマネージャーである。あなたの製品は現在バージョンnまでリリースしているが、とあるバージョンから不良品が混入している事がわかった。渡されたバージョンが不良品か否かを判定するisBadVersion関数が渡されるので、どこからが不良品かを導き出せ。」という問題です。
個人的には、このようなストーリーのある問題のほうが面白くて好きです😄
さて、問題ですが、とりあえず0..nまで毎回確認すると試行回数が多すぎてTLEになります。そこで試行回数をなるべく減らす必要があるため、二分探索でバージョンを見つけることにしました。以下がそのコードになります。

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function (n) {
    let low = 1;
    let high = n;

    while (high > low) {
      const mid = Math.floor((low + high) / 2);
      if (isBadVersion(mid)) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return high;
  };
};

現在の取りうる最小値をlow(初期値はバージョンの取りうる最小値1)とし、最大値をhigh(初期値はバージョンの最大値n)とする。
lowの値がhighより大きくなるまでループを回し、毎回現在のlowとhighでその中間値midを算出し、midをisBadVersionにかけた結果がtrueであればそのバージョン以降は全て不良品とわかるので、highをmidにアップデートする。また、逆に結果がfalseであればそこまでは不良品ではないとわかるので、lowをmid+1にアップデートする。highをアップデートする時にはmidが答えのバージョンとなりうるのでそのまま入りますが、lowはmidが不良品ではないと分かっているので1を足しています。この繰り返しにより、最終的にlowがhighを上回った時にはhighが取りうる最小値になっているため、highを返します。

まとめ

今回はSorting and Searchingをまとめました！問題数自体は少ないのですが、内容的には実際に使えそうな場面も想定できる内容ばかりだったように思います。このような問題のMediumレベルを安定的に解けるようになるのが当面の目標って感じですね！最近はLeetCode ContestだけではなくDaily Challengeにも挑戦しているので、このまま様々な問題の傾向や解き方を吸収してその目標に近づきたいと思います！💪