小数点を検索

10531 ワード
アルゴリズム#アルゴリズム# js プログラマ テキストリンク
問題の説明
一桁と書かれた紙片が散らばっている.ばらばらの紙切れを貼って、いくつかの小数点を作ることができることを見たいです.
各紙片の数字の文字シリアル番号を指定すると、紙片で作成できるいくつかの数を返すための解法関数を完了します.
せいげんじょうけん
numbersは、長さが1または7未満の文字列です.
numbersは0から9まで数字で構成されています.
「013」とは、0から3の数字の紙切れが散らばっていることを意味します.
I/O例
numbers return
"17" 3
"011" 2
I/O例説明
例1
[1,7]小数[7,17,71]を作成できます.
例2
[0,1,1]は小数点を作成することができる[1101].
11と011は同じ数字と見なされます.
function solution(numbers) {
  let answer = 0;
  const n = numbers.length;
  const totalNumbers = new Set(); // Set 을 사용해서 반복되는 것은 포함 x
  // nPr: 순열 전체 탐색 1 < r <= n
  for (let r = 1; r <= n; r++) {
    const copy = new Array(r).fill(0);
    const selected = new Array(n).fill(0);
    permutation(0, numbers, copy, selected, r, n, totalNumbers);
  }

  // Set을 반복문으로 탐색
  for (let val of totalNumbers.values()) {
    if (isPrime(val)) {
      answer++;
    }
  }
  return answer;
}

// 순열 함수
const permutation = (idx, numbers, copy, selected, r, n, totalNumbers) => {
  if (idx == r) {
    const num = Number(copy.join(""));
    totalNumbers.add(num);
    return;
  }
  for (let i = 0; i < n; i++) {
    if (selected[i] === 0) {
      selected[i] = 1;
      copy[idx] = numbers[i];
      permutation(idx + 1, numbers, copy, selected, r, n, totalNumbers);
      selected[i] = 0;
    }
  }
};

// 소수 판별
function isPrime(num) {
  // 0, 1의 경우 fast return
  if (num === 1 || num === 0) return false;
  // num 의 제곱근 범위까지 반복문 돌려서 나눠서 나머지가 0인지 탐색
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}
解の順序
1.すべての数値の組合せを順番に参照->数値セットのみをスキャン
2.集合中の数字の組み合わせを小数で判別し、trueの場合++
学識
  • 小数点を探す方法は、エラトスドネスのふるいのほかにもあります.
  • シーケンスnpr 1に詳しい.
    • 少数の判別
    forサイクルを不適切に使用すると、速度が千倍遅くなります