LeetCodeノート:526。美しいアレンジメント
Leetcode Notes 526 Beautiful Arrangement
問題:
1からNまでのN個の整数があるとします。この配列のi番目の位置(1≤i≤N)に次のいずれかが当てはまる場合、これらのN個の数値によって正常に構築される配列として美しい配列を定義します。
- i番目の位置の数はiで割り切れます。
- iはi番目の位置の数で割り切れます。
Nが与えられた場合、いくつの美しいアレンジメントを構築できますか?
例1:入力:2
出力:2
説明:
最初の美しいアレンジメントは[1、2]です。
1番目の位置(i = 1)の数は1であり、1はi(i = 1)で割り切れます。
2番目の位置(i = 2)の数は2であり、2はi(i = 2)で割り切れます。
2番目の美しい配置は[2、1]です:
1番目の位置(i = 1)の数は2であり、2はi(i = 1)で割り切れます。
2番目の位置(i = 2)の数は1であり、i(i = 2)は1で割り切れます。
注意:
- Nは正の整数であり、15を超えることはありません。
本旨:
1からNまでのN個の整数があるとします。N個の整数が配列を形成できる場合、すべてのi番目のビット(1≤i≤N)が次の2つの要件のいずれかを満たすことを定義します。
- i番目の位置の数はiで割り切れる可能性があります。
- iはi番目の位置の数で割り切れる可能性があります。
さて、Nに、いくつの美しいアレンジをすることができますか?
例1:入力:2
出力:2
説明:
最初の美しいアレンジメントは[1、2]です。
最初の位置(i = 1)の数は1であり、1はi(i = 1)で割り切れます。
2番目の位置(i = 2)の数は2であり、2はi(i = 2)で割り切れます。
2番目の美しい配置は[2、1]です:
最初の位置(i = 1)の数は2であり、2はi(i = 1)で割り切れます。
2番目の位置(i = 2)の数は1であり、1はi(i = 2)で割り切れます。注意:
- Nは正の数であり、15を超えることはありません。
考え:
数える方法がわからない可能性はたくさんあると思いますが、これは再帰的なバックトラックによって実現できます。
私たちの考えでは、1位からN位まで、対応する未配置の数字を見つける必要があり、各ビットには多くの数字があり、リリース後は配置できないため、常に配置します。最後に、数字を入れることができれば、それは美しい配置であり、全体の結果は1つ増加します。
この種の考え方は、再帰によって実現できます。再帰的に、現在の位置でリリースされていない番号を判断できます。リリースがある場合は、記録する番号が必要です。この位置に配置された各番号について、それが1つとしてカウントされるべきかどうかを知る前に、すべてがそれを終了できるかどうかを再帰的に確認し続ける必要がある可能性があります。すべてが終了すると、1つとしてカウントされます。合計した場合は、1つ追加できます。
ここでの場所は0からではなく、1から計算されることに注意してください。
コード(Java):
public class Solution { public int countArrangement(int N) { int[] num = new int[N] int res = findWay(num, 1) return res } public int findWay(int[] num, int index) { if (index == num.length+1) return 1 int total = 0 for (int i = 0 i コレクション: https://github.com/Cloudox/LeetCode-Record