javascriptでatcoderするときにあったらよい関数一覧1

はじめに

atcoderでjavascriptをするという人はあまり多くないかもしれませんが、後世のためにまとめておきます。

1,nextpermutation

これは並び替えの全探索で必須になるレベルで重要です。c++にはあるんだけどなー...なお、仕組みは僕もまだよくわからない模様。

function next_permutation(arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) {
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] > arr[i]) {
          [arr[i], arr[j]] = [arr[j], arr[i]];
          const len = (arr.length - (i + 1)) >> 1;
          for (let k = 0; k < len; k++) {
            [arr[i + 1 + k], arr[arr.length - 1 - k]] = [
              arr[arr.length - 1 - k],
              arr[i + 1 + k],
            ];
          }
          return true;
        }
      }
    }
  }
  return false;
}

2,累積和

C問題なんかでこれを使うアルゴリズムの問題が良くたまに出ます。リストを入れたら0を先頭に累積和のリストが返されるのでぜひ使ってみてください。

function accumulate(arr){
  let length = arr.length
  let accarray = []
  let total = 0
  for(let i = 0;i<length;i++){
    total +=  arr[i]
    accarray.push(total)
  }
  return accarray
}

最後に

第2弾も書く予定です。ぜひ使ってみてください。