まいにちLeetCode

ピン留めされたアイテム

Typescriptと効率的なアルゴリズムの学習のためにLeetCodeを毎日一題解きます◎
頑張って思い出しつつ頑張ります！
思考のメモなのでぐちゃぐちゃです。
Top Interview 150

Template

## #hoge[「hoge」](hoge): hoge
### コード
```ts
hogehoge
```

### 学び

yuka

2024/01/14

#88「Merge Sorted Array」: Easy

学び

コード

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    nums1.splice(m, n);
    for (let i = 0; i < n; i++) {
        nums1.push(nums2[i]);
    }
    nums1.sort((a, b) => a - b);
};

yuka

2024/01/15

#27「Remove Element」: Easy

学び

spliceのtime complexityは $O(n)$ らしい。
forの中でsplice使うだけで $O(n^2)$ になっちゃうってことか…
ECMAScript Language Specification#sec-array.prototype.splice
たしかに3回くらいループ回ってるわ

Solutionで評価の高い人のコードが美しかった

function removeElement(nums: number[], val: number): number {
    let j = 0;
    for( let n of nums )if( n !== val ) nums[j++] = n
    return j
};

自分がCから入ってるからなんだろうけど、Python使っててもinで回すのになかなか慣れなくて標準のこの形で書いちゃってた
便利だから使えるようになろう

コード

function removeElement(nums: number[], val: number): number {
    let k: number = nums.length;
    let l: number;
    for (let i = 0; i < nums.length; i++) {
        l = i - (nums.length - k);
        if (nums[l] == val) {
            nums.splice(l, 1);
            nums.push(0);
            k--;
        }
    }
    return k;
};

yuka

#26「Remove Duplicates from Sorted Array」: Easy

学び

昨日の評価が高い人のコードをパクってみた。
結構スッキリいい感じにかけたんじゃない？

厳密等価(===)と等価(==)の違いが気になった。!==で比較してる人が大半だった。そっちに合わせたほうが良いか？

厳密等価(===)

厳密等価演算子 (===) は、二つのオペランドが等しいことを検査し、論理値で結果を返します。等価演算子とは異なり、厳密等価演算子はオペランドの型が異なる場合、常に異なるものと判断します。

等価(==)

等価演算子 (==) は、二つのオペランドが等しいことを検査し、論理値で結果を返します。厳密等価演算子とは異なり、オペランドの型が異なる場合には型の変換を試みてから比較を行います。

基本的には厳密等価を使うのが推奨されているらしい。異なる型同士を比較する際は明示的に型を合わせる。

コード

function removeDuplicates(nums: number[]): number {
    let j: number = 1;
    let i: number = nums[0];
    for (let n of nums) {
        if (n != i) {
            nums[j++] = n;
            i = n;
        }
    }
    return j;
};

yuka

#80「Remove Duplicates from Sorted Array II」: Medium

コード

方針：前後と比較
3つ以上並んでいる箇所がない
→前後と比較して少なくともどちらか一方は異なる数字である

なんかごちゃごちゃして嫌
最後のreturnの前とか何やってんのって感じだし

function removeDuplicates(nums: number[]): number {
    let j: number = 1;

    if (nums.length === 1) return j;

    for (let k = 1; k < nums.length - 1; k++) {
        if (nums[k] !== nums[k - 1] || nums[k] !== nums[k + 1]) {
            nums[j++] = nums[k];
        }
    }
    nums[j++] = nums[nums.length - 1];
    return j;
};

学び

これコード→学びで書いたほうがコードの説明書いてその学びって流れになるからいい感じ

最初に処理対象外の条件を集めて書いておくのってガード節って言うのね
ネストが増えるのはなるべく避けたいもんね

綺麗だった他の方のコード

これの何がすごいって残す数が可変ってとこ。
2つ前と比較すれば2個残るし3つ前と比較すれば3個残る。

const removeDuplicates = (nums: number[]): number => {
  let j:number = 2;

  for (let i = 2; i < nums.length; i++) {
    if (nums[i] !== nums[j - 2]) {
      nums[j++] = nums[i];
    }
  }
  
  return j;
};

yuka

#169「Majority Element」: Easy

コード

これだとSpace ComplexityがO(n)になる

function majorityElement(nums: number[]): number {
    const numsMap = new Map<number, number>();
    let len_half: number = nums.length / 2;
    for (let n of nums) {
        if (numsMap.has(n)) {
            numsMap.set(n, numsMap.get(n) + 1);
        } else {
            numsMap.set(n, 1);
        }
    }
    for (let n of nums) {
        if (numsMap.get(n) >= len_half) {
            return n;
        }
    }
};

↓ なるべく分岐を無くす

function majorityElement(nums: number[]): number {
    const numsMap = new Map<number, number>();
    let len_half: number = nums.length / 2;
    for (let n of nums) {
        let freq = (numsMap.get(n) ?? 0) + 1;
        numsMap.set(n,freq);
        if (freq >= len_half) {
            return n;
        }
    }
};

Boyer-Moore majority vote algorithm

function majorityElement(nums: number[]): number {
    let candidate;
    let count = 0;
    
    for (const num of nums) {
        if (count === 0) {
            candidate = num;
        }
        
        count += (num === candidate) ? 1 : -1
    }
    
    return candidate;
};

学び

forEachとforの違い
Mapオブジェクト
Null合体演算子
三項演算子

yuka

#189「Rotate Array」: Easy

コード

ぱっと思いついたのは単純に後ろからpopして前に入れるのだけど、遅い方のやり方みたい。

/**
 Do not return anything, modify nums in-place instead.
 */
function rotate(nums: number[], k: number): void {
    let n: number;
    for (let i = 0; i < k; i++) {
        n = nums.pop()
        nums.unshift(n);
    }
    return;
};

めちゃはやいけどなんだこれ…

/**
 Do not return anything, modify nums in-place instead.
 */
function rotate(nums: number[], k: number): void {
  k = k % nums.length;
  let l = 0;
  let r = nums.length - 1;
  // reverse full given array
  // from [1,2,3,4,5,6,7] to [7,6,5,4,3,2,1]
  nums = reverseArr(nums, l, r);

  // reverse part from 0 to k - 1;
  // from [7,6,5,4,3,2,1] to [5,6,7,4,3,2,1]
  l = 0;
  r = k - 1;
  nums = reverseArr(nums, l, r);

  // reverse part from k to the end;
  // from [5,6,7,4,3,2,1] to [5,6,7,1,2,3,4]
  l = k;
  r = nums.length - 1;
  nums = reverseArr(nums, l, r);
};

function reverseArr(nums: number[], l: number, r: number): number[] {
    while(l < r) {
    let temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
    l++;
    r--;
  }

  return nums;
}

学び

unshiftってnを配列の長さとするとtime complexityは $O(n)$ ？

そうっぽい。
$k=<n$ だから自分のやつは $O(n^2)$ になってるってことか。
うわ違うわ。rotateだから $k>n$ の可能性もあるんだ。何回もぐるぐるするのね。
計算量は $O(n \cdot k)$ になるのか。
だから早い人のコードは $k = k % nums.length;$ で $k=<n$ に変換してるんだわ。
てかこの手法すごいな…

#88「Merge Sorted Array」: Easy

学び

コード

#27「Remove Element」: Easy

学び

コード

#26「Remove Duplicates from Sorted Array」: Easy

学び

厳密等価(===)

等価(==)

コード

#80「Remove Duplicates from Sorted Array II」: Medium

コード

学び

綺麗だった他の方のコード

#169「Majority Element」: Easy

コード

Boyer-Moore majority vote algorithm

学び

#189「Rotate Array」: Easy

コード

学び

unshiftってnを配列の長さとするとtime complexityはO(n)？

unshiftってnを配列の長さとするとtime complexityは $O(n)$ ？