LeetCodeでよく使うJavaScript
最近、LeetCodeをよくやっていてJavaScriptで解いています。
300問ほど解いたのでそのときに使ったJavaScriptの表現を共有します。
JavaScriptで競技プログラミングを始める人には役立つと思います。
20020年4月時点のLeetCodeのランタイムがnodeのv10.15.0なのでそのバージョンを実行環境とします。
コードの実行
nodeで実行できます。特定バージョンのノードのインストールはnodenvなどで行うと便利です。
$ node -v
v10.15.0
$ node
> console.log('hello world')
hello world
変数と宣言
複数の変数を同時に宣言する場合は以下のようにします。
let foo = 0, bar = 0, baz = 1
配列を変数に代入させることもできます。
(;を最後につけているのは次の行のコードによっては意図しない動作をするためです)
let [i, j] = [0 ,0];
ネストしていても代入することができます。
let [i, [j, k]] = [1, [2, 3]];
数値・演算・数学
小数点切り捨ての割り算はできないのでMath.floorもしくはMath.truncを使います。
ただしマイナスの割り算は異なる結果がでるので気をつけてください。
筆者はほとんどの場合Math.truncを使っています。
5 / 2 // = 2.5
Math.floor(5 / 2) // = 2
Math.trunc(5 / 2) // = 2
Math.floor(- 5 / 2) // = -3
Math.trunc(- 5 / 2) // = - 2
2^3などの階乗は**で実現できます。
2 ** 3 // = 8
logは以下をよく使います。
Math.log(Math.E) // = 1
Math.log2(4) // = 2
Math.log(1000) // = 3
logの底の変換公式はこちらです。
文字列
x番目の文字列を取り出すには以下でできます。
let s = "abc"
s[1] // ="b"
部分文字列は以下で取得できます。sliceの引数にマイナスの値を入れると末尾から部分文字列を取得できます。
(sliceとsubstringの違いはStackoverflowに詳しくのっています)
"abcdef".substring(1, 3) // = 'ab'
"abcdef".slice(-3) // = def
重要な点として範囲外でも値を返します。
この動作はエラー処理が簡易な一方、例外が起こらないのでプログラムのミスに気づきにくいという問題もあります。
"abcedf".substring(0, 7) // = 'abcedf'
"abcedf".substring(7, 7) // = ''
文字列の比較は、<, >, ==でできます。
localeCompareも様々なオプションとともに使えます。
ソートで使う場合は、localeCompareのほうが返り値をそのまま使えるので便利かもしれません。
"a" < "b" // = true
"a".localeCompare("b") // = -1
アルファベットを大文字から小文字にするにはtoLowerCaseを使います。
小文字を大文字にするにはtoUpperCaseを使います。
"a".toUpperCase() // = "A"
"A".toUpperCase() // = "a"
文字列の前後の空白を取り除くにはtrimを使います。
文字列内の複数のスペースを1つのスペースにしたい場合はreplaceと正規表現を使います。
" a ".trim() // = "a"
"a b".replace(/\s+/g, " ") // = "a b"
文字列のUTF-16 code unitを取得したいときはcharCodeAtを使います。
"a".charCodeAt(0) // = 97
"A".charCodeAt(0) // = 65
数値から文字列にする場合はTemplate literalsを使うと便利です。その他にもtoStringでも変換できます。
let a = 10
`${a}` // = "10"
a.toString() // = "10"
文字列を数値に変換するにはparseIntを使います。少数の場合はparseFloatを使います。
変換できない場合はNaNが返るので判定すれば文字列が数値かどうか確かめれます。
parseInt("123") // = 123
parseInt("123.4") // = 123
parseFloat("123.4") // = 123.4
isNaN(parseInt("123")) // = false
isNaN(parseInt("abc")) // = true
乱数を生成するときはMath.random()を使います。Math.random()は0 <= x < 1までの少数xを返します。
整数xで0 <= x <= 9の乱数を返したいときは以下のようにします。
Math.floor(Math.random() * 10)
整数の最大・最小を返すには以下のようにします。最大は2^53 - 1で最小は`- (2^53 - 1)です。
なぜこのような値になっているかはNumber.MAX_SAFE_INTEGERのドキュメントを参照してください。
Number.MAX_SAFE_INTEGER // = 9007199254740991
Number.MIN_SAFE_INTEGER // = -9007199254740991
2^53 - 1より大きな値を正確に扱いたいときはBigIntを使ってください。数値の末尾にnをつけてもBigIntに変換できます。
100n
BigInt(100)
大きな数値を3桁ごとにカンマで区切りたいときはtoLocaleStringを使います。
(1000).toLocaleString() // = "1,000"
2進数、8進数、16進数を表すには以下のようにします。
0b11 // = 3
0o10 // = 8
0xf // = 15
ビット演算
整数を32ビット2進数の文字列で表現するにはtoString(2)とpadStartを使います。
整数がマイナスの場合は
(4).toString(2).padStart(32, "0") // = '00000000000000000000000000000100'
(-1 >>> 0).toString(2) // = '11111111111111111111111111111111'
2進数の文字列から数値にするにはparseInt(x, 2)を使います。
parseInt('00000000000000000000000000000100', 2) // = 4
基本的なビット演算は次のようになります
&: AND|: OR^: XOR~: NOT<<: 左シフト>>: 符号を保ったま右シフト>>>: ゼロパディングの右シフト
5 & 4 // = 4
5 | 2 // = 7
5 ^ 7 // = 2
~1 // = -2
2 << 1 // = 4
4 >> 1 // = 2
-4 >> 1 // = -2
4 >>> 1 // = 2
-4 >>> 1 // = 2147483646
アルゴリズムの実装で特定のビットのみを変更したいときがあります。
よく使うのは一番右の1ビットのみをたてるときです。
xの一番右のビットのみをたてるにはx & -xでたてれます。
6 & (-6) // = 2
一番右のビットをさげたいときはx & (x - 1)で下げれます。
6 & (6 - 1) // = 4
1バイトのビットをO(1)で反転(reverse)させるには以下でできます。
let byte = 1
(byte * 0x0202020202 & 0x010884422010) % 1023 // = 128
配列
配列のコピーはsliceでできます。
const a = [1, 2, 3]
const b = a.slice(0)
b[0] = 4
a // = [1, 2, 3]
b // = [4, 2, 3]
最初のx個の要素を取得したり、最後のx個の要素を取得するのにもsliceが使えます。
const a = [1, 2, 3, 4, 5]
a.slice(0, 2) // [1, 2]
a.slice(-2) // [4, 5]
存在しないインデックスにアクセスするとundefinedがかえされます。
const a = []
a[0] === undefined // = true
a[0] == null // = true
配列の最初の要素を取得し削除するにはshiftを使い、最後の要素を取得し削除するにはpopを使います。
const a = [1, 2, 3]
a.shift() // = 1
a // = [2, 3]
a.pop() // = 3
a // = [2]
特定のインデックスを削除したい場合はspliceを使います。
const a = [1, 2, 3]
a.splice(2, 1) // = [2]
a // = [1, 3]
配列の複数インデックスの要素の値を入れ替えるには以下のようにします。
const a = [1, 2, 3]
[a[0], a[1]] = [a[1], a[0]];
a // = [ 2, 1, 3 ]
配列に特定の要素が含まれているかどうかはincludesを使います。
const a = [1, 2, 3]
a.includes(1) // = true
a.includes(4) // = false
長さnの配列を0で初期化するには以下のようにします。
const n = 5
Array(n).fill(0) // = [0, 0, 0, 0, 0]
要素の値をインデックスと同じにしたい場合は以下のようにできます。
[...Array(5).keys()].map(v => v) // = [ 0, 1, 2, 3, 4 ]
二次元配列の場合は以下のようにします。
Array(3).fill(Array(2).fill(0))で宣言するとa[0][0]を変更した際にa[1][0]なども同様に変更されてしまいますので気をつけてください。
const a = [...Array(3)].map(_ => Array(2).fill(0)) // = [ [ 0, 0 ], [ 0, 0 ], [ 0, 0 ] ]
a[0][0] = 1
a // = [ [ 1, 0 ], [ 0, 0 ], [ 0, 0 ] ]
ネストされた配列をフラットにする場合はreduceを使います。node 12以上の場合はflatが使えます。
[1, [1,2], [3,4]].reduce((p, c) => p.concat(c), []) // = [ 1, 1, 2, 3, 4 ]
配列には要素に対して順に適用できる便利なメソッドもあります。
- every: 適用した結果がすべてtrueならtrue
- some: 適用した結果のどれかがtrueならtrue
- filter: 適用した結果がtrueのものだけ返す
- map: 適用した結果を返す
- reduce: 適用し単一の値にして返す
[0, 1, 2, 3, 4].every(v => v >= 0) // = true
[0, 1, 2, 3, 4].some(v => v <= 0) // = true
[0, 1, 2, 3, 4].filter(v => v % 2 == 0) // = [0, 2, 4]
[0, 1, 2, 3, 4].filter(v => v * 2) // = [0, 2, 4, 6, 8]
[1, 2, 3].reduce((p, c) => p + c, 0) // = 6
配列の値をソートする場合はsortを使います。
呼び出しもとの配列の要素をそのまま書き換えるので注意してください。
書き換えられたくないときはslice(0)などをつかってコピーしてください。
const a = [5, 1, 2, 4, 3]
a.sort((a, b) => a - b)
a // [ 1, 2, 3, 4, 5 ]
辞書
{}でも一部動作しますがオブジェクトをキーとして渡すと想定通りに動作しないのでMapを使いましょう。
const m = new Map()
m.get(1) // = undefined
m.set(1, "one")
m.get(1) // = "one"
m.has(1) // = true
m.size // = 1
m.delete(1)
m.size // = 0
辞書の各要素に対して処理を行うときは以下のようにします。
const m = new Map([[1, "one"], [2, "two"]])
for (const [k, v] of m.entries()) {
// 処理
}
辞書の値のみを配列にしたいときはArray.fromを使います。
const m = new Map([[1, "one"], [2, "two"]])
Array.from(m.values()) // = [ 'one', 'two' ]
セット
const s = new Set([1, 2, 3])
s.has(1) // = true
s.has(4) // = false
s.add(4)
s.has(4) // = true
s.delete(4)
各要素に対して処理を行うときは以下のようにします。
const s = new Set([1, 2, 3])
for (const v of s) {
// 処理
}
配列の値をユニークな配列にしたい場合もセットを使えます。
const a = [1, 1, 2, 2, 3]
Array.from(new Set(a)) // = [1, 2, 3]
時間
Unix Timeを取得するにはgetTimeを使います。返り値はミリセカンドです。
(new Date()).getTime()
正規表現
"1112111"を同じ数字ごとの配列に分けたい場合は以下のようにします。
"1112111".match(/((.)\2*)/g) // = [ '111', '2', '111' ]