LeetCode 1日目

LeetCode TypeScript

LeetCode１日目にやった内容を振り返っていきます～

自分のコードの振り返りとランキング上位の実装との比較をやっていきます。

217. Contains Duplicate

数値の配列が渡されて、同じ数値が出現すればtrueなければfalseという問題

制約:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

自分のコードはこんな感じ

function containsDuplicate(nums: number[]): boolean {
  let hasDuplicate: boolean = false;

  // 数値の配列を走査
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      // 数値が同じ場合、falseを返却しループを停止
      if (nums[i] == nums[j]) {
        hasDuplicate = true;
        break;
      }
    }
  }

  return hasDuplicate;
};

愚直な実装、、Map関数くらい使えばいいのに。。。 これでも制約上は問題なかったけど実行速度が6900ms、遅すぎる。。

ランキング上位の実装などを見たところ、SetオブジェクトやMapオブジェクトを利用している。

なぜ実行速度が速くなるかというと。。

Setは、オブジェクトと配列の長さを比較するだけなので速くて

Mapは、Arrayのように要素一つ一つを確認する必要がないから速いらしい

分かり易い解説は以下参照

100倍速い!? Set, Mapでパフォーマンス改善 | 株式会社ヌーラボ(Nulab inc.)

function containsDuplicate(nums: number[]): boolean {
    // 重複を削除したObjectを生成
    const uniqueSet = new Set(nums);
    return uniqueSet.size !== nums.length;
};

ハッシュテーブルつかうぞー！

さて次の問題は、、

242. Valid Anagram

sとtの二つの文字列が渡されて、tがsのアナグラムならtrue、そうでなければfalseとする

制約:

  • 1 <= s.length, t.length <= 5 * 10^4
  • sandtconsist of lowercase English letters.

自分のコード

function isAnagram(s: string, t: string): boolean {
    // 配列にスプレッド
    let sToArray = [...s];
    let tToArray = [...t];
    // s, tの文字列をソート
    sToArray.sort();
    tToArray.sort();

    // 文字列に変換
    let sToString = sToArray.toString();
    let tToString = tToArray.toString();

    if (sToString == tToString) {
        return true;
    }

    return false;
};

こっちも単純に文字列を配列にしてソートして文字列に戻して比較しているだけの実装

実行速度は110ms、メモリは50.1MB

実行速度もメモリもあと少し改善する余地がある模様。

ランキング上位の解答確認したところ、tとsのアルファベットの出現回数を加算、減算するだけでよいとのこと。 たしかに制約条件の２個目にまんま記載がある。。

ということで改修版ドン！

function isAnagram(s: string, t: string): boolean {
    // 文字数が違えば、アナグラムでないのでfalse
    if (s.length !== t.length) {
        return false;
    }

    // 計算用の配列生成
    let alphabetCount = [...Array(26)].map(() => 0);

    // アルファベットの出現回数計算
    for(let i = 0; i < s.length; i++) {
        // 文字列s,tのASCIIコードを取得
        let sCode = s.charCodeAt(i) - 97;
        let tCode = t.charCodeAt(i) - 97;

        // 出現回数を計算
        alphabetCount[sCode]++;
        alphabetCount[tCode]--;
    }

    // アルファベットの出現回数が全て0ならアナグラム
    const isAnagram = alphabetCount.every((element) =>  element === 0);

    return isAnagram
};

今日の反省点

  • 配列よりもハッシュテーブルが使えないか検討しましょう。
  • 制約条件をよく読みましょう。

同じ失敗はしないように気を付けなければ・・・

ではまた。