【剑指offer-Java版】12打印1到最大的n位数

╰半夏微凉° 2022-08-21 08:57 131阅读 0赞

打印1到最大的n位数：比较简单了，但是考虑n 很大的时候n位的最大999…9可能会超出表示范围  
大数问题-需要使用字符串或者数组模拟大数加法

public class _Q12 {
    
        public void PrintFromOneToMaxN(int n){
            if(n <= 0) return ;
    
            char digit[] = new char[n];
    
            for(int i=0; i<digit.length; i++) digit[i] = '0';
    
            while(!Increment(digit)){
                PrintNumber(digit);
            }
        }
        char base[] = {
       '0','1','2','3','4','5','6','7','8','9'};
        private boolean Increment(char digit[]){
            boolean isOverfolw = false;
    
            int carry = 0;
            int sum = 0;
            for(int i=(digit.length-1); i>=0; --i){
    
                if(i == digit.length-1) { sum++;}
    
                sum = sum + (digit[i] - '0') + carry;
    
                if(sum >= 10){ // 由于此处仅仅是每次增加1，所以sum只能是10
    
                    if(i == 0) { isOverfolw = true; break;}
    
                    digit[i] = base[sum % 10]; // 此处实际也就是'0'
                    carry = sum / 10;
                    sum = 0;
                }else{
                    digit[i] = base[sum % 10];
                    break; // 某一位不会发生进位之后，其前面的更高位也不会发生进位
                }
            }
    
            return isOverfolw;
        }
    
        private void PrintNumber(char digit[]) {
            int start = 0;
            // 寻找第一个非0起点
            for (int i = 0; i < digit.length; i++) {
                if (digit[i] == '0') { continue; } 
                else { start = i; break; }
            }
    
            for (int i = start; i < digit.length; i++) {
                System.out.print(digit[i]);
            }
            System.out.println();
        }
    }

测试代码：

public class _Q12Test extends TestCase {
        
    
        _Q12 oneToN = new _Q12();
    
        public void test(){
            oneToN.PrintFromOneToMaxN(3);
        }
        }