[boj] 13144. List of Unique Numbers (node.js)

7801 ワード
アルゴリズム#アルゴリズム# ダブルポインタ テキストリンク
サマリ
13144
入力
  • :長さNの数列
  • 所定の数列から1又は複数の連続する数字を抽出する場合
    • .
  • 出力:同じ数の
    • が複数回発生しない
    に答える
    連続して数字を抽出する場合なので、ダブルポインタを使います.
    説明する
    const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = input();
  const arr = input().split(" ").map(Number);
  let result = 0;
  const count = new Array(100000 + 1).fill(0);
  for (let L = 0, R = 0; L < N; L++) {
    while (R < N && count[arr[R]] == 0) {
      count[arr[R++]]++;
    }
    count[arr[L]] = 0;
    result += R - L;
  }
  console.log(result);
  process.exit();
});
  • は、count配列を用いて有効なナビゲーションを行い、2つのポインタL、R、およびすでに含まれている値を決定する.
    • Rを
  • 連続および重複しない要素の最大範囲に拡張した後、これ以上拡張できない場合は、範囲内に存在する1つまたは複数の連続する数値の個数を追加します.これはR−L距離計算式で簡単に計算できる.
    • Vueカスタム入力
    Python-パッケージ、モジュールパス