[daily question] question 24: print from 1 to the maximum n digits

Title Description

Enter the number N and print out the decimal number from 1 to the maximum n digits in sequence. For example, if you enter 3, 1, 2 and 3 will be printed up to the maximum 3 digits 999.

Example 1:

input: n = 1
 output: [1,2,3,4,5,6,7,8,9]

explain:

  • Instead of printing, return a list of integers
  • n is a positive integer

Problem solution

Method 1: divide and conquer algorithm / Full Permutation

Problem solving ideas:

The title requires to print "list from 1 to maximum n digits", so the following two questions need to be considered:

  1. The relationship between the largest n digits (marked as end) and N digits: for example, the largest 1 digit is 9, the largest 2 digits are 99, and the largest 3 digits are 999. You can exit the formula: end = 10^n - 1
  2. Large number out of range problem: when n is large, end will exceed the value range of int32 integer, and the numbers beyond the value range cannot be stored normally. However, since this problem requires to return int type array, it is equivalent to that all numbers are within the value range of int32 integer by default, so the problem of large number out of range is not considered.

Therefore, you only need to define the interval [1,10^n - 1] and step 1, generate the result list res through the for loop and return it.

code

class Solution {
    public int[] printNumbers(int n) {
        int end = (int)Math.pow(10, n) - 1;
        int[] res = new int[end];
        for(int i = 0; i < end; i++)
            res[i] = i + 1;
        return res;
    }
}

Complexity analysis

  • Time complexity O(10^n): it takes O(10^n) time to generate a list with a length of 10^n.
  • Space complexity O(1): additional space of O(1) size is required to establish the list (the list is used as the return result, and the additional space is not included)

Other knowledge points

Large number printing solution:

In fact, the main test point of this question is printing when large numbers cross the boundary. The following three problems need to be solved:

  1. Variable types representing large numbers:

    • No matter short/int/long... Any variable type, the value range of numbers is limited. Therefore, a large number indicates that the String type is applied.
  2. String set to generate numbers:

    • When using int type, each round can generate the next number by + 1, and this method cannot be applied to String type. Moreover, the carry operation efficiency of String type numbers is low. For example, 9999 to 10000 need to be judged from one bit to thousands, and carry 4 times.
    • The observation shows that the generated list is actually a full arrangement of n bits 0 - 9, so the carry operation can be avoided and the String list of numbers can be generated recursively.
  3. Generate full permutation recursively:

    • Based on the idea of branching algorithm, first fix the high bit and recurse to the low bit. When the single bit has been fixed, add a numeric string. For example, when n = 2 (number range 1 - 99), fix the ten bits as 0 - 9, turn on recursion in sequence, fix the single bits 0 - 9, terminate recursion and add a numeric string.

class Solution {
    StringBuilder res;
    int count = 0, 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(); // Numeric string
        num = new char[n]; // Defines a list of characters of length n
        dfs(0); // Turn on Full Permutation recursion
        res.deleteCharAt(res.length() - 1); // Delete the last extra comma
        return res.toString(); // Convert to string and return
    }
    void dfs(int x) {
        if(x == n) { // Termination condition: all bits have been fixed
            res.append(String.valueOf(num) + ","); // Splice num and add to the end of res, separated by commas
            return;
        }
        for(char i : loop) { // Traverse '0' - '9‘
            num[x] = i; // Fixed bit x as i
            dfs(x + 1); // Open fixed position x + 1
        }
    }
}

In this method, the numeric strings are separated by commas and form a long string together. The returned numeric set string is as follows:

Input: n = 1
 Output:"0,1,2,3,4,5,6,7,8,9"

Input: n = 2
 Output:"00,01,02,...,10,11,12,...,97,98,99"

Input: n = 3
 Output:"000,001,002,...,100,101,102,...,997,998,999"

It can be seen from the observation that the current generation method still has the following problems:

  1. For example, 00, 01, 02,... Should be displayed as 0, 1, 2,..., that is, the redundant 0 in the high position should be deleted;
  2. This method starts from 0, and the title requirement list starts from 1;

The solutions to the above two problems are as follows:

  1. Delete high redundant 0:

    • Definition of left boundary of string: declare that the variable start specifies the left boundary of the string to ensure that there is no high-order redundant 0 in the added digital string num[start:]. For example, when n = 2, 1 - 9, start = 1, 10 - 99, start = 0.
    • Change law of start on the left boundary: it can be seen from the observation that when all bits of the output number are 9, the next number needs to advance 1 to the higher order. At this time, the start on the left boundary needs to be reduced by 1 (that is, the excess 0 on the high order is reduced by one). For example, when n = 3 (the number range is 1 - 999), the left boundary start needs to be minus 1: "009" carry to "010" and "099" carry to "100". If the number of 9 in the number is nine and all bits are nine, the judgment condition can be expressed by the following formula, n - start = nine
    • Method of statistics of nine: when the x-th bit is fixed, when i = 9, execute nine = nine + 1, and recover nine = nine - 1 before backtracking.
  2. The list starts with 1

    • On the basis of the above methods, judge whether the numeric string is "0" before adding it. If it is "0", skip it directly.

Complexity analysis:

  • Time complexity O(10^n): the number of recursively generated permutations is 10^n.
  • Space complexity O(n): the character list num uses additional space of linear size.

code:

In order to correctly represent large numbers, the return value of the following code is a long string spliced from a set of numeric strings.

class Solution {
    StringBuilder res;
    int nine = 0, count = 0, 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];
        start = n - 1;
        dfs(0);
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res.append(s + ",");
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

This question requires the output of an array of type int. To run through, you can convert the numeric string ss to type int before adding it. The code is as follows:

class Solution {
    int[] res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public int[] printNumbers(int n) {
        this.n = n;
        res = new int[(int)Math.pow(10, n) - 1];
        num = new char[n];
        start = n - 1;
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

Source of solution

Author: jyd
Link: leetcode-cn.com/problems/da-yin-co...
Source: LeetCode

Topic source

Source: LeetCode
Link: leetcode-cn.com/problems/da-yin-co...

Tags: leetcode

Posted by starvator on Tue, 24 May 2022 18:20:56 +0300