我正在嘗試解決以下問題。給定一個整數 n，列出所有 n 位數字，這樣每個數字都沒有重復的數字。例如，如果 n 為 4，則輸出如下：012301240125...987598764 位數字的總數為 5040我目前的方法是蠻力。我可以生成所有 n 位數字，然后使用 Set 列出所有沒有重復數字的數字。但是，我很確定有一種更快、更好、更優雅的方法來做到這一點。我在用 Java 編程，但我可以用 C 閱讀源代碼。
3 回答
慕碼人8056858
TA貢獻1803條經驗 獲得超6個贊
在數學上，你有10個所述第一數量，選項9為第二，8為第三，和7的第4位。所以，10 * 9 * 8 * 7 = 5040。
以編程方式，您可以使用一些組合邏輯生成這些。使用函數式方法通常會使代碼更簡潔；這意味著遞歸地構建一個新字符串，而不是嘗試使用 StringBuilder 或數組來不斷修改現有字符串。
示例代碼
以下代碼將生成排列，無需重復使用數字，無需任何額外的集合或映射/等。
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 的評論中提取這一點，因為它說得很好，有助于澄清解決方案。
所以為了解釋這里發生的事情 - 它正在遞歸一個帶有三個參數的函數：我們已經使用過的數字列表（我們正在構建的字符串 - c），我們還沒有使用過的數字列表（字符串r) 和目標深度或長度。然后當一個數字被使用時，它被添加到 c 并從 r 中刪除以供后續遞歸調用，因此您不需要檢查它是否已經使用，因為您只傳遞那些尚未使用的數字。
海綿寶寶撒
TA貢獻1809條經驗 獲得超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條經驗 獲得超4個贊
注意這里的對稱性：
0123
0124
...
9875
9876
9876 = 9999 - 123
9875 = 9999 - 124
所以對于初學者來說，你可以把工作切成兩半。
您可能能夠找到一個涵蓋場景的正則表達式，例如，如果一個數字在同一字符串中出現兩次，則它匹配/失敗。
正則表達式是否會更快，誰知道呢？
特別是對于四位數字，您可以嵌套 For 循環：
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));
（等等）
或者，對于更通用的解決方案，這是遞歸的方便性的一個很好的例子。例如，您有一個函數，它獲取先前數字的列表和所需的深度，如果所需數字的數量小于深度，則只需進行十次迭代的循環（通過您要添加的數字的每個值），如果該數字已不存在于列表中，然后將其添加到列表中并遞歸。如果您處于正確的深度，只需連接列表中的所有數字并將其添加到您擁有的有效字符串集合中。
添加回答
舉報
0/150
提交
取消