1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@skaudev(S Kaurova)

JavaScriptアルゴリズム問題のチートシート

1
Posted at

私はおそらく、アルゴリズム関連の問題で使われる多くの関数を覚えておくのが難しいと感じている唯一の人ではないと思います。そこでこの記事では、このトピックに関する知識を整理してみたいと思います。最近よく使われている JavaScript の search、sort などの関数を見ていきます。

sort()

このメソッドは配列の要素を辞書順で並べ替えます。つまり、すべての要素が文字列に変換され、その Unicode 値に基づいてソートされます。

注目すべき点として、配列に同じ文字の大文字と小文字（例えば「a」と「A」）が含まれている場合、Unicode 値が先に来るため「A」が先に並びます。

このメソッドには、要素の並び順を決めるコンパレータ関数を渡すこともできます。

arr.sort((a, b) => a - b);

ここで、結果が負の場合は a が b より前に来ます。結果が正の場合は b が a より前に来ます。
これにより、数値を昇順に並べ替えることができます。

このメソッドがよく使われる LeetCode 問題

  • Three Sum
  • Valid Anagram
  • Merge Intervals
  • Top K Frequent Elements

map()

既存の配列から新しい配列を作成し、新しい配列の各要素に対して指定した処理を適用するためによく使われるメソッドです。

const arr1 = [1, 2, 3]

const arr2 = arr1.map(element => element * 2) // [2, 4, 6]

現在の要素だけでなく、そのインデックスや元の配列自体も受け取ることができます。

例:

const arr2 = arr1.map((element, index, array) => {
  console.log("Element:", element)
  console.log("Index:", index)
  console.log("Original array:", array)
  return element * 2
})

このメソッドがよく使われる LeetCode 問題

  • Two Sum
  • Running Sum of 1d Array
  • FizzBuzz
  • Roman to Integer

filter()

このメソッドは新しい配列を作成しますが、指定した条件を満たす（true を返す）要素だけを元の配列から追加します。

例:

const arr = [1, 2, 3, 4, 5]

const evens = arr.filter(num => num % 2 === 0) // [2, 4]

map() と同様に、現在の要素、インデックス、元の配列を引数として受け取ることができます。

このメソッドがよく使われる LeetCode 問題

  • How Many Numbers Are Smaller Than the Current Number
  • Intersection of Two Arrays

reduce()

最もよく使われる配列メソッドの一つです。配列のすべての値を、指定した処理に基づいて一つの値にまとめます。

一般的な構文:

array.reduce((accumulator, current, index, array) => {
  return newAccumulator;
}, initialValue);

Accumulator はこれまでに計算された結果を表します。

例:

[1, 2, 3].reduce((sum, num) => sum + num, 0);

// 出力: 6

この場合、sum が accumulator、num が現在の値です。

以下は reduce を使ってハッシュマップを作成する例です。

["a", "b", "a", "c", "b", "a"].reduce((map, char) => {
  map[char] = (map[char] || 0) + 1;
  return map;
}, {});

このメソッドがよく使われる LeetCode 問題

  • Two Sum
  • Valid Anagram
  • First Unique Character in a String
  • Contains Duplicate
  • Group Anagrams
  • Intersection of Two Arrays II

reverse()

このメソッドは配列の要素の順序を逆にします。
split() や join() と一緒に使われることが多いです。

このメソッドがよく使われる LeetCode 問題

  • Reverse Integer
  • Reverse String
  • Reverse Words in a String

flat()

ネストされた配列をフラットな配列に変換するメソッドです。
デフォルトの深さは 1 で、最上位のレベルからフラット化が始まります。

例:

const arr = [1, [2, [3, 4]]]
arr.flat() // [1, 2, [3, 4]]

フラット化する階層の深さを指定することもできます。

arr.flat(2) // [1, 2, 3, 4]

このメソッドがよく使われる LeetCode 問題

  • Triangle
  • Pascal’s Triangle
  • Subsets II
  • Palindrome Partitioning

indexOf() / lastIndexOf()

配列内で指定された値のインデックスを調べるためのメソッドです。

  • indexOf() は最初に現れるインデックスを返します
  • lastIndexOf() は最後に現れるインデックスを返します

これらのメソッドでは === が使用されます。

このメソッドがよく使われる LeetCode 問題

  • Two Sum
  • Single Number

findIndex() / findLastIndex()

これらは indexOf と似ていますが、値ではなく条件を受け取ります。

例:

arr.findIndex(number => number > 3)
arr.findLastIndex(number => number > 3)

このメソッドがよく使われる LeetCode 問題

  • Find First and Last Position of Element in Sorted Array
  • Remove Element

find()

指定した条件を満たす最初の要素を返します。
見つからない場合は undefined を返します。

例:

arr.find(number => number > 3)

このメソッドがよく使われる LeetCode 問題

  • Single Number
  • Contains Duplicate
  • Remove Element

forEach()

配列の各要素に対して処理を実行するメソッドです。

arr.forEach((currentElement, index, array) => console.log(array))

このメソッドがよく使われる LeetCode 問題

  • Two Sum
  • Intersection of Two Arrays
  • Robot Return to Origin
  • Pascal’s Triangle

some() / every()

配列の要素が条件を満たしているかどうかを確認し、boolean を返します。

  • some() はいずれかの要素が条件を満たすかを確認します
  • every() はすべての要素が条件を満たすかを確認します

例:

const arr = [2, 4, 5]
const even = arr.some(number => number % 2 === 0)
const isEven = arr.every(number => number % 2 === 0)

このメソッドがよく使われる LeetCode 問題

  • Single Number
  • Contains Duplicate
  • Count Primes
  • Fizz Buzz

concat()

配列や文字列を結合するためのメソッドです。
スプレッド演算子の代わりとして使うこともできます。

例:

const arr1 = [3, 4]
const arr2 = [5, 6]
const combined = arr1.concat(arr2)

文字列の例:

"hi".concat(",", " ", "friend")

このメソッドがよく使われる LeetCode 問題

  • Merge Sorted Array
  • Intersection of Two Arrays
  • Pascal’s Triangle

push() / pop()

  • push() は配列の末尾に要素を追加します
  • pop() は配列の末尾の要素を削除します

shift() / unshift()

  • shift() は配列の先頭の要素を削除します
  • unshift() は配列の先頭に要素を追加します

Math.max() / Math.min()

最大値と最小値を返します。

Math.max(1, 2, 4)

配列を渡す場合:

const arr = [1, 2, 4]
Math.min(...arr)

このメソッドがよく使われる LeetCode 問題

  • Maximum Subarray
  • Triangle
  • Container With Most Water

Math.floor() / Math.ceil() / Math.round()

数値を整数に丸めるメソッドです。

  • Math.round() 最も近い整数に丸める
  • Math.floor() 下方向に丸める
  • Math.ceil() 上方向に丸める

このメソッドがよく使われる LeetCode 問題

  • Divide Two Integers
  • Sqrt(x)
  • Construct the Rectangle

split() / join()

split() は文字列を配列に分割するメソッドです。

string.split("")

例:

const string = "banana"
const arr = string.split("a")

join() は配列を文字列に戻します。

arr.join("a")
arr.join()

このメソッドがよく使われる LeetCode 問題

  • Reverse Words in a String
  • Valid Palindrome
  • Reverse String II
  • Reverse Words in a String III

slice() / substring()

既存の文字列から新しい文字列を作成するメソッドです。

string.slice(2,6)

slice() は負のインデックスもサポートしますが、substring() はサポートしません。

このメソッドがよく使われる LeetCode 問題

  • Longest Substring Without Repeating Characters
  • Longest Palindromic Substring
  • Length of Last Word
  • Add Binary

includes()

文字列に指定された部分文字列が含まれているかを確認します。

string.includes("Hi")
string.includes("Hi", 5)

このメソッドがよく使われる LeetCode 問題

  • Implement strStr()
  • Detect Capital
  • Backspace String Compare
  • Most Common Word

search()

このメソッドは、文字列の中から指定された文字列または正規表現に一致する部分を検索し、最初に一致した位置（インデックス）を返します。
一致するものが見つからない場合は、-1 が返されます。

includes() メソッドとは異なり、search() メソッドは booleanではなく、一致した位置を返します。
また、このメソッドは正規表現と一緒によく使用されます。

例:

string.search("Hi") // "Hi" が最初に現れるインデックスを返す

例:

const string = "Hello World"
string.search(/world/i) // 6 を返す（大文字・小文字を区別しない検索）

このメソッドがよく使われる LeetCode 問題

  • Implement strStr()
  • Detect Capital
  • Most Common Word
  • Valid Palindrome

startsWith()

文字列が特定の部分文字列で始まるかどうかを確認します。

string.startsWith("Hi")
string.startsWith("Hi", 5)

このメソッドがよく使われる LeetCode 問題

  • Longest Common Prefix
  • Word Search II
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?