07 打印1到最大的n位数

本文主要是介绍07 打印1到最大的n位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

本博文部分图片, 思路来自于剑指offer 或者编程珠玑

问题描述

这里写图片描述

思路

书中给出了三种思路
思路一 :
获取n位数能够表示的最大的数字, 然后构造一个循环, 打出来, 不过这个受到了变量能够表示的最大的数字的限制

思路二 : 使用n个char的字符数组, 然后将最大的位置的字符是否到达“‘9’+1”, 作为循环的结束条件, 每一个循环, 增加最低位置的字符[如果存在进位, 级联增加]

思路三 : 同样时使用n个char的字符数组, 不过这一次是递归的设置每一位字符的数据, 从而达到了遍历到最大的数字

剩下的是我的两种思路[基本上思想是一致的] :
思路一 : 实现一个自己的BIgInteger, 提供一个dec方法, 每一次减少1, 循环dec方法, 打印数据, 知道最高位int的数据小于0

思路二 : 实现一个自己的BIgInteger02, 提供一个inc方法, 每一次增加1, 循环inc方法, 打印数据, 直到最高位int的数据大于’最高位的int的最大数据’

为了最大限量的使用int, 所以对于BigInteger, 除了最高位int其他位的int的值为999999999, 对于BigInteger02, 每一位int的增长的最大值为99999999

参考代码

/*** file name : Test28Print1ToMaxNNumber.java* created at : 2:40:52 PM Jun 5, 2015* created by 970655147*/package com.hx.test04;public class Test28Print1ToMaxNNumber {// 打印出1-最大的n位数public static void main(String []args) {int n = 3;//      print1ToMaxNNumber01(n);
//      print1ToMaxNNumber02(n);
//      print1ToMaxNNumber03(n);
//      print1ToMaxNNumber04(n);print1ToMaxNNumber05(n);}// 能打印, 但是对于n的大小有限制, 不能超过(2147483648的位数-1)public static void print1ToMaxNNumber01(int n) {int ln = 1 << 6;int lnMask = ln - 1;int maxN = getMaxN(n);for(int i=0; i<maxN; i++) {Log.log(i);
//          if((i & lnMask) == lnMask) {
//              Log.enter();
//          }}}// 思路 : 使用字符数组  存放数据static char zero = '0';static char max = (char) (zero + 10);public static void print1ToMaxNNumber02(int n) {char[] chars = new char[n];for(int i=0; i<chars.length; i++) {chars[i] = zero;}while(chars[0] < max) {Log.log(chars);inc(chars);}}// 递归全排列public static void print1ToMaxNNumber03(int n) {int depth = 0;char[] chars = new char[n];recurselyPrint1ToMaxNNumber(depth, n, chars);}// 构建一个递减的BigIntegerpublic static void print1ToMaxNNumber04(int n) {BigInteger bigI = new BigInteger(n);while(bigI.gtZero() ) {Log.log(bigI);bigI.dec();}}// 构建一个递增的BigIntegerpublic static void print1ToMaxNNumber05(int n) {BigInteger02 bigI = new BigInteger02(n);while(bigI.ltMax() ) {Log.log(bigI);bigI.inc();}}// 递归遍历前n位数的全排列   数据存放在chars中private static void recurselyPrint1ToMaxNNumber(int depth, int maxLen, char[] chars) {if(depth == maxLen) {Log.log(chars);Log.enter();return ;}for(int i=0; i<10; i++) {chars[depth] = (char) (zero + i);recurselyPrint1ToMaxNNumber(depth + 1, maxLen, chars);}}// 增加chars表示的数据    确保idx!=0  是为了防止数组越界private static void inc(char[] chars) {int lastOne = chars.length - 1;chars[lastOne] ++;int idx = lastOne;while((chars[idx] == max) && (idx != 0) ) {chars[idx] = zero;chars[idx - 1] ++;idx --;}}// 获取n位数的最大的元素    比如 : n为2  maxN为99, n为3  maxN为999private static int getMaxN(int n) {int nine = 9;int res = nine;for(int i=1; i<n; i++) {res = res * 10 + nine;}return res;}// 根据此题目的要求  模拟递减的BigInteger[只适用于当前题目...]static class BigInteger {// 0, 9, 999999999的常量static int ZERO = 0;static int NINE = 9;static int ALL_NINE = 999999999;// 存放数据[存放9位数]int[] data;// 初始化public BigInteger(int n) {init(n);}private void init(int n) {int length = (n-1) / 9 + 1;data = new int[length];for(int i=length-1; i>0; i--) {data[i] = ALL_NINE;}int remain = n - (length - 1) * NINE;data[0] = getMaxN(remain);          }// 当前BigInteger递减1// 如果最后一个int不为0   则直接将其减1// 否则 向前面的int借位public void dec() {int lastOne = data.length - 1;int lastNonZero = lastOne - 1;if(data[lastOne] == ZERO) {while(data[lastNonZero] == 0) {lastNonZero --;}if(lastNonZero == -1) {throw new RuntimeException("value be zero...");}data[lastNonZero] --;for(int i=lastNonZero+1; i<data.length; i++) {data[i] = ALL_NINE;}} else {data[lastOne] --;}}// 当前BigInteger是否大于0   每一个int均大于0public boolean gtZero() {for(int i=data.length-1; i>=0; i--) {if(data[i] > 0) {return true;}}return false;}// Debugpublic String toString() {StringBuilder sb = new StringBuilder(data.length * 10);for(int i=0; i<data.length; i++) {sb.append(data[i] + " ");}return sb.toString();}}// 根据此题目的要求  模拟递增的BigInteger[只适用于当前题目...]static class BigInteger02 {// 0, 9, 999999999的常量static int ZERO = 0;static int NINE = 9;static int ALL_NINE = 999999999;// 存放数据[存放9位数]int[] data;int firstMaxInt;// 初始化public BigInteger02(int n) {init(n);}private void init(int n) {int length = (n-1) / 9 + 1;data = new int[length];int remain = n - (length - 1) * NINE;firstMaxInt = getMaxN(remain);          }// 当前BigInteger递增1// 如果最后一个int不为999999999   则直接将其加1// 否则 向前面的数据进位public void inc() {int lastOne = data.length - 1;if(data[lastOne] == ALL_NINE) {int idx = lastOne;while(data[idx] == ALL_NINE) {data[idx] = ZERO;data[idx-1] ++;idx --;}} else {data[lastOne] ++;}}// 当前BigInteger是否小于最大的n位整数public boolean ltMax() {if(data[0] <= firstMaxInt) {return true;}return false;}// Debugpublic String toString() {StringBuilder sb = new StringBuilder(data.length * 10);for(int i=0; i<data.length; i++) {sb.append(data[i] + " ");}return sb.toString();}}}