面试题12：打印1到最大的n位数##
剑指offer题目12，题目如下
输入数字n，按顺序打印出1到最大的n位十进制数，比如输入3，则打印出1,2,3一直到最大的三位数999
方法一###
和面试题11《数值的整数次方》类似，乍看觉得都是简单题目，找出最大的n位数，开始逐个打印，写出代码
public static void method_1(int n )
{
int num = 1;
int i = 1;
while(i <= n)
{
num *= 10
i++;
}
for(i = 1;i < num; i++)
System.out.print(i +" ");
}
n的范围小还好，若n的取值很大，即需要考虑大数问题，这就是一个陷阱。正确的做法是使用字符串模拟数字的加法。
方法二###
字符串模拟数字加法需要建立一个字符数组，每一个都存储'0'到'9'某一个字符，首先把字符数组中每一位初始化 ‘0’，然后每一次为字符数组做+1操作，最后打印出来。其中的核心操作是
- 1.为字符数组做
+1操作 - 2.打印数组
代码如下：
public static void method_2(int n)
{
if(n <= 0)
return;
char num[] = new char[n];
for(int i = 0; i < num.length; i++)
num[i] = '0';
int times = 0; //
while(!increment(num))//数组+1
{
print(num); //输出数组
times ++;
if(time % 10 == 0)//10个换行
{
System.out.println();
times = 0;
}
}
}
剑指offer原书中给出数组+1的方法increment很巧妙，一种方法是字符串数组与最大的N位数99…99匹配，相等则终止递增，但时间复杂度为O(n)，另一种方法是在最高位（最左边位）发生了进位，返回True，则就达到了最大的n位数，时间复杂度为O(1)，代码如下
///模拟整数加法
public static boolean increment(char num[])
{
int remider = 0; //进位，5+7 = 12，此时remider=1
for(int i =num.length - 1; i >= 0;i--)
{
int count = num[i] - '0' + remider;
if(i == num.length - 1) //最后一位发生变化
count += 1;
if(count >= 10)
{
if(i == 0)
return true; //最高位发生进位
else
{
count -= 10;
remider = 1;
num[i] = (char) ('0' + count);
}
}
else
{
num[i] = (char) ('0' + count);
break;
}
}
return false;
}
接下开考虑如何打印数字，由于数字由字符数组表示，位数不足n的前面用0补位，比如 当输入的n=3时，数字66的数组表示方式是066，因此在输出的时候遇到前面首数字前面为0的应该跳过去不打印
public static void print(char num[])
{
for(int i = 0;i <= num.length - 1;i++)
{
if(num[i] != '0')
{
for(int j = i;j <= num.length - 1;j++)
{
System.out.print(num[j]);
}
System.out.print(" ");
break;
}
}
}
结果：
方法三###
先给出一个问题，求0~100中数字7出现的个数
可以把数字化成这样00,01,02...98,99，每一数位都是由0到9排列一遍，总共出现100 * 2 = 200个数字，由于0~9这10个数出现的次数相等，则7出现了 200/10 = 20次。
同理，可以在所有的数字前面补0，就会得到n位数字，每一位都是0~9的全排列，只是排在数字前面的0我们不打印出来，由于每一位都是0-9的全排列，可以想到使用递归思路，求数字的全排列Permutation也是类似思想，但有少许区别
// 使用递归
public static void method_3(int n)
{
if(n <= 0)
return;
char num[] = new char[n];
for(int i = 0; i < 10; i++)
{
num[0] = (char) (i + '0');//第0位 全排列0~9
recursive(num,n ,0);
}
}
public static void recursive(char num[],int length ,int index) //index全排列到第几位了
{
if(index == length - 1)
{
System.out.println();
print(num);
return;
}
for(int i = 0; i < 10; i++)
{
num[index + 1] = (char) (i + '0');
recursive(num,length,index + 1);
}
}
总结###
题目简单么？这可要比这些天做的各大公司笔试题算法题目简单太多了，有些公司出的题需要看半天才能表达的意思。这么容易理解的题目如果真是bug free 的做出来还真是有些难度，本节两个关键点：
- 字符串模拟整数的加法
- 递归方法全排列数字