欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer 打印从1到最大的n位数

程序员文章站 2022-03-26 16:44:25
输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。1、法一:递归生成全排列,通过n和9的个数之间的关系截取。比如说生成 ...097 098 099 ... 9的个数分别为 1 1 2 。n-count 分别为2 2 1 当前的start为1,满足n - start == count 时 start向前一位,代表截取起始坐标前进一位。class Solution { StringBuilder res;......

输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

0.法0:递归生成全排列,打印去0 ,比较容易理解(和法一比较一下)

class Solution {
    StringBuilder str;
    int n;
    public void printNumbers(int n) {
        this.n =n;
        str = new StringBuilder();
        for(int i=0;i<n;i++){
            str.append('0');
        }
        dfs(0);
    }
    public void dfs(int k){

        if(k==n){
            printNum(str);   //填充完了  打印
            return;
        }
        for(int i=0;i<10;i++){
            str.replace(k,k+1,String.valueOf(i)); //第k位填充 0 1 2 3 ..9
            dfs(k+1);
        }

    }
    public  void printNum(StringBuilder str) {  //打印 去除0
        int index = 0;
        while (index<n && str.charAt(index) == '0')
                index ++ ;
        if (index==n)   //全0 跳过
            return;
        System.out.print(str.substring(index)+" ");
    }

    public static void main(String[] args) {
        Solution s=new Solution();
        s.printNumbers(3);
    }
}

 

1、法一:递归生成全排列,通过n和9的个数之间的关系截取。

比如说生成 ...097 098 099  ... 9的个数分别为 1 1 2  。n-count 分别为2 2 1  当前的start为1,满足n - start == count 时 start向前一位,代表截取起始坐标前进一位。

class Solution {
    StringBuilder res;
    int   start, n;   //截取开始的位置
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder();  //结果
        num = new char[n];          //n个字符
        start = n - 1;              //截取的起点 开始只有1位
        dfs(0,0);                 //递归遍历
        res.deleteCharAt(res.length() - 1); //删掉多余的,号
        return res.toString();
    }
    void dfs(int x,int count) {
        if(x == n) {                //比如说n=3 x代表下标 从0,1,2开始 到3结束递归
            //System.out.println(n+" "+String.valueOf(num)+" "+start+" "+count);
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res.append(s + ",");
            if(n - start == count) start--;        //如果9的个数到了 往前一位 如n=3 099 3-1 ==2
            return;
        }
        for(char i : loop) {
            num[x] = i;                   //递归赋值0...9
            if(i == '9') count++;         //9的个数+1
            dfs(x + 1,count);
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.printNumbers(3));
    }
}

2、模拟大数加法。(推荐掌握)

public class Solution {
    public String printNumbers(int n) {
        StringBuilder  res = new StringBuilder();
        StringBuilder str = new StringBuilder();
        // 将str初始化为n个'0'字符组成的字符串
        for (int i = 0; i < n; i++) {
            str.append('0');
        }
        while(!increment(str)){
            // 去掉左侧的0
            int index = 0;
            while (index < str.length() && str.charAt(index) == '0'){
                index++;
            }
            res.append(str.substring(index)).append(",");
        }
        return res.substring(0,res.length()-1);
    }
//    increment函数,若发生进位则一直进行for循环,直到不产生进位则break。如果i为0(即到了最高位)还发生了进位,
//    则设置isOverflow为true,并返回至主函数的while判断
//    str为全局变量,每次加1,不进位的话 就跳出,进位的话,赋0,i-1,下一层循环加1跳出, 下一次进入又从末位开始。
    public boolean increment(StringBuilder str) {
        boolean isOverflow = false;
        for (int i = str.length() - 1; i >= 0; i--) {
            char s = (char)(str.charAt(i) + 1);

            // 如果s大于'9'则发生进位
            if (s > '9') {
                str.replace(i, i + 1, "0");
                if (i == 0) {
                    isOverflow = true;
                }
            }
            // 没发生进位则跳出for循环
            else {
                str.replace(i, i + 1, String.valueOf(s));
                break;
            }

        }
        return isOverflow;
    }

    public static void main(String[] args){
        Solution s = new Solution();
        String ss=s.printNumbers(3);
        System.out.println(ss);
    }
}

 

本文地址:https://blog.csdn.net/yu1336199790/article/details/112240087

相关标签: leetcode 字符串