我正在嘗試解決以下問題。給定一個整數(shù) n，列出所有 n 位數(shù)字，這樣每個數(shù)字都沒有重復(fù)的數(shù)字。例如，如果 n 為 4，則輸出如下：012301240125...987598764 位數(shù)字的總數(shù)為 5040我目前的方法是蠻力。我可以生成所有 n 位數(shù)字，然后使用 Set 列出所有沒有重復(fù)數(shù)字的數(shù)字。但是，我很確定有一種更快、更好、更優(yōu)雅的方法來做到這一點。我在用 Java 編程，但我可以用 C 閱讀源代碼。
3 回答
慕碼人8056858
TA貢獻1803條經(jīng)驗 獲得超6個贊
在數(shù)學(xué)上，你有10個所述第一數(shù)量，選項9為第二，8為第三，和7的第4位。所以，10 * 9 * 8 * 7 = 5040。
以編程方式，您可以使用一些組合邏輯生成這些。使用函數(shù)式方法通常會使代碼更簡潔；這意味著遞歸地構(gòu)建一個新字符串，而不是嘗試使用 StringBuilder 或數(shù)組來不斷修改現(xiàn)有字符串。
示例代碼
以下代碼將生成排列，無需重復(fù)使用數(shù)字，無需任何額外的集合或映射/等。
public class LockerNumberNoRepeats {
public static void main(String[] args) {
System.out.println("Total combinations = " + permutations(4));
}
public static int permutations(int targetLength) {
return permutations("", "0123456789", targetLength);
}
private static int permutations(String c, String r, int targetLength) {
if (c.length() == targetLength) {
System.out.println(c);
return 1;
}
int sum = 0;
for (int i = 0; i < r.length(); ++i) {
sum += permutations(c + r.charAt(i), r.substring(0,i) + r.substring(i + 1), targetLength);
}
return sum;
}
}
輸出：
...
9875
9876
Total combinations = 5040
解釋
從@Rick 的評論中提取這一點，因為它說得很好，有助于澄清解決方案。
所以為了解釋這里發(fā)生的事情 - 它正在遞歸一個帶有三個參數(shù)的函數(shù)：我們已經(jīng)使用過的數(shù)字列表（我們正在構(gòu)建的字符串 - c），我們還沒有使用過的數(shù)字列表（字符串r) 和目標深度或長度。然后當(dāng)一個數(shù)字被使用時，它被添加到 c 并從 r 中刪除以供后續(xù)遞歸調(diào)用，因此您不需要檢查它是否已經(jīng)使用，因為您只傳遞那些尚未使用的數(shù)字。
海綿寶寶撒
TA貢獻1809條經(jīng)驗 獲得超8個贊
回溯法也是一種蠻力法。
private static int pickAndSet(byte[] used, int last) {
if (last >= 0) used[last] = 0;
int start = (last < 0) ? 0 : last + 1;
for (int i = start; i < used.length; i++) {
if (used[i] == 0) {
used[i] = 1;
return i;
}
}
return -1;
}
public static int get_series(int n) {
if (n < 1 || n > 10) return 0;
byte[] used = new byte[10];
int[] result = new int[n];
char[] output = new char[n];
int idx = 0;
boolean dirForward = true;
int count = 0;
while (true) {
result[idx] = pickAndSet(used, dirForward ? -1 : result[idx]);
if (result[idx] < 0) { //fail, should rewind.
if (idx == 0) break; //the zero index rewind failed， think all over.
dirForward = false;
idx --;
continue;
} else {//forward.
dirForward = true;
}
idx ++;
if (n == idx) {
for (int k = 0; k < result.length; k++) output[k] = (char)('0' + result[k]);
System.out.println(output);
count ++;
dirForward = false;
idx --;
}
}
return count;
}
SMILET
TA貢獻1796條經(jīng)驗 獲得超4個贊
注意這里的對稱性：
0123
0124
...
9875
9876
9876 = 9999 - 123
9875 = 9999 - 124
所以對于初學(xué)者來說，你可以把工作切成兩半。
您可能能夠找到一個涵蓋場景的正則表達式，例如，如果一個數(shù)字在同一字符串中出現(xiàn)兩次，則它匹配/失敗。
正則表達式是否會更快，誰知道呢？
特別是對于四位數(shù)字，您可以嵌套 For 循環(huán)：
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (j != i) {
for (int k = 0; k < 10; k++) {
if ((k != j) && (k != i)) {
for (int m = 0; m < 10; m++) {
if ((m != k) && (m != j) && (m != i)) {
someStringCollection.add((((("" + i) + j) + k) + m));
（等等）
或者，對于更通用的解決方案，這是遞歸的方便性的一個很好的例子。例如，您有一個函數(shù)，它獲取先前數(shù)字的列表和所需的深度，如果所需數(shù)字的數(shù)量小于深度，則只需進行十次迭代的循環(huán)（通過您要添加的數(shù)字的每個值），如果該數(shù)字已不存在于列表中，然后將其添加到列表中并遞歸。如果您處于正確的深度，只需連接列表中的所有數(shù)字并將其添加到您擁有的有效字符串集合中。
添加回答
舉報
0/150
提交
取消