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

はじめに

前回からの続きです。まだまだよく使う関数が出てくるので見ていってください。

二分探索

ほかから取ってきました。使わさせていただいています。よく使うので持ってて悪いことはありません。引数には(配列,知りたい要素)を入れてください。sortされたリストしかできません。

const isOK = (arr, mid, key) => arr[mid] >= key;
const lower_bound = (arr, key) => {
  let ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ok = arr.length; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ok - ng > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK(arr, mid, key)) ok = mid;
    else ng = mid;
  }
  /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
  return ok;
};
const isOK2 = (arr, mid, key) => arr[mid] > key;
const upper_bound = (arr, key) => {
  let ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ok = arr.length; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ok - ng > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK2(arr, mid, key)) ok = mid;
    else ng = mid;
  }
  /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
  return ok;
};

キュー

jsのリストはスタックです。スタックを2つ使うことによってキューを作成できます。これを使ってbfsを簡単に実装できるようになります。自作なのでバグが起きるかもしれないので自己責任で使ってください。

class Queue {
  #stackPush = [];
  #stackPop = [];

  push(value) {
    this.#stackPush.push(value);
  }

  shift() {
    if (this.#stackPop.length === 0) {
      while (this.#stackPush.length > 0) {
        this.#stackPop.push(this.#stackPush.pop());
      }
    }
    return this.#stackPop.pop();
  }
  length (){
    if (this.#stackPop.length === 0) {
      while (this.#stackPush.length > 0) {
        this.#stackPop.push(this.#stackPush.pop());
      }
    }
    return this.#stackPop.length;
  }
}

最後に

本当にjavascriptで書いている人が少ないので同士を増やしたいです。BigIntは使いにくいけど...