力扣 – 劍指 Offer 17. 列印從1到最大的n位數
- 2021 年 10 月 18 日
- 筆記
- DFS, 全排列, 大數計算, 數組, 演算法
題目
劍指 Offer 17. 列印從1到最大的n位數
思路1
- 如果有n位,那麼最大值就是\(10^n-1\),即如果n是2,那麼最大就到輸出到99
- 考慮到大數情況,所以使用字元數組
- 還要把字元數組轉化成數字
程式碼
class Solution {
int position = 0;
public int[] printNumbers(int n) {
int count = 0;
int[] res = new int[(int)Math.pow(10, n) - 1];
char[] chars = new char[n];
for (int i = 0; i < n; i++) {
chars[i] = '0';
}
while (!increment(chars)) {
convertNumber(chars, res);
}
return res;
}
public boolean increment(char[] chars) {
// 是否溢出
boolean isOverFlow = false;
// 記錄進位
int takeOver = 0;
int length = chars.length;
for (int i = length-1; i >= 0; i--) {
// 記得加上進位的值
int sum = chars[i] - '0' + takeOver;
// 確保每次只increment只增加1
if (i == length-1) {
sum++;
}
if (sum >= 10) {
// 如果最高位的值還是大於等於10,說明溢出了
if (i == 0) {
isOverFlow = true;
break;
} else {
// 求余,記錄進位,寫回到數組中,然後進位繼續加到下一位
sum -= 10;
takeOver = 1;
chars[i] = (char)('0' + sum);
}
} else {
// 如果沒有溢出,直接寫入到數組中去即可
chars[i] = (char)('0' + sum);
break;
}
}
return isOverFlow;
}
// 將字元數組轉換成數字添加到結果集中
public void convertNumber(char[] chars, int[] output) {
// 用於判斷的,不把0計入
boolean isBeginning = false;
int length = chars.length;
StringBuilder sb = new StringBuilder();
for (char c : chars) {
if (!isBeginning && c != '0') {
isBeginning = true;
}
if (isBeginning) {
sb.append(c);
}
}
output[position++] = Integer.parseInt(sb.toString());
}
}
複雜度分析
- 時間複雜度:\(O(10^N)\)
- 空間複雜度:\(O(N)\)
思路2
- n位的所有十進位數都是0~9的全排列
- 排列的時候,最後還要考慮前面的0要去掉
- 遞歸的結束條件就是我們已經排列到了第n位了
程式碼
class Solution {
int[] res;
int position = 0;
public int[] printNumbers(int n) {
res = new int[(int)Math.pow(10, n) - 1];
// 為了去掉無效的0,所以從第1位開始
for (int digit = 1; digit <= n; digit++) {
for (char first = '1'; first <= '9'; first++) {
char[] num = new char[digit];
num[0] = first;
dfs(1, digit, num);
}
}
return res;
}
public void dfs(int index, int length, char[] num) {
if (index == length) {
res[position++] = Integer.parseInt(String.valueOf(num));
return;
}
for (char i = '0'; i <= '9'; i++) {
num[index] = i;
dfs(index+1, length, num);
}
}
}
複雜度分析
- 時間複雜度:\(O(10^N)\)
- 空間複雜度:\(O(N)\)