LeetCode ２日目の復習やっていきます。

１日目の方に書き忘れてましたが、NeetCodeのRoadmapを参考に進めてます。

1. Two Sum

配列の内２つの数値を加算することで指定の値にできる要素の添え字を返す問題

自分のコード

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        const pare = target - nums[i];

        const pareIndex = nums.findIndex((ele, key) => key !== i && ele === pare);

        if (pareIndex !== -1) {
            return [i, pareIndex];
        }

    }
    
    return [];
};

配列をループして指定の値から引いた値が自身の要素以外に存在するか配列に存在するか確認している。計算量はO(n²)となっている。

ランキング上位のコード

function twoSum(nums: number[], target: number): number[] {
    let numberMap = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        let number = nums[i];
        let diff = target - number;

        if (numberMap.has(diff)) {
            return [numberMap.get(diff), i];
        }

        numberMap.set(number, i);
    }

    return [-1, -1]
};

これもハッシュを使うことで計算量を少なくできる。

間違ってるかもしれないけど、計算量的にはO(n)になるのかな？

工夫としてキーに値を入れている、そうすることで値のチェックがO(1)で出来るようになっている。

昨日ハッシュ使うぞーって言ったばっかりなのに使えなかったー

原理を理解しきれていないから応用できないのかな。。。

今日は１問だけです。ではまた！

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
};

今日の反省点

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

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

ではまた。

RYOSUKE.dev

LeetCode 2日目

1. Two Sum

LeetCode 1日目

217. Contains Duplicate

242. Valid Anagram