まいにちLeetCode
yukaTypescriptと効率的なアルゴリズムの学習のためにLeetCodeを毎日一題解きます◎
頑張って思い出しつつ頑張ります！
思考のメモなのでぐちゃぐちゃです。
Top Interview 150
yukaTemplate
## #hoge[「hoge」](hoge): hoge
### コード
```ts
hogehoge
```
### 学び
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);
};
2024/01/15
#27「Remove Element」: Easy
学び
spliceのtime complexityは
forの中でsplice使うだけで
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;
};
#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;
};
#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;
};
#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)
そうっぽい。
うわ違うわ。rotateだから
計算量は
だから早い人のコードは
てかこの手法すごいな…