力扣 - 剑指 Offer 17. 打印从1到最大的n位数
2024-09-01 17:03:44
题目
思路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)\)
最新文章
- ORACLE索引失效原因归纳[转]
- gnuplot Python API
- Flash Player 19.0.0.124 Beta + IHTMLDocument3 IHTMLDocument2 ->get_innerHTML
- IFrame 获取内容
- Java带包编译运行
- 三个入侵的必备小工具-lcx.exe、nc.exe、sc.exe
- 《C语言深度剖析》学习笔记----C语言中的符号
- python面向对象具体解释(上)
- MapReduce(十五): 从HDFS阅读本文的源代码分析
- 大批量烧写openwrt系统
- 用C语言绘制一条标准的余弦曲线
- html跳动的心实现代码
- Tensorflow object detection API 搭建物体识别模型（三）
- Codeforces 1093D. Beautiful Graph【二分图染色】+【组合数】
- PHP对接微信支付采坑
- Jetty 9的使用
- 程序员面试50题—sizeof的用法(6)
- os.stat(filename).st_size 文件信息
- BZOJ5102 POI2018Prawnicy（堆）
- 让一个div始终固定在页面的某一固定位置的方法