This is the 25th day of my participation in the August Challenge

One, foreword

Hello everyone, this is the 14th article in a series called “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

  • Leetcode’s key Offer topic
  • Code cloud warehouse address

Second, the subject

Enter the number n to print out the largest n decimal digits in sequence. For example, if you type 3, you print 1, 2, 3 up to 999.

Example 1:

Input: n = 1 Output: [1,2,3,4,5,6,7,8,9]Copy the code

Description:

  • Return a list of integers instead of printing
  • N is a positive integer

Third, the problem solving

3.1 Idea 1: General for loops

I don’t care about the large number, I find the maximum, and I just go through it and print it.

3.1.1 code
    public static int[] printNumbers(int n) {
        int max = 9;
        int tmp=9;
        for (int i = 1; i <n; i++) {
            max=max*10+tmp;
        }
        int[] ints = new int[max];
        for (int i = 0; i <max ; i++) {
            ints[i]=i+1;
        }
        return ints;
    }

Copy the code
public static int[] printNumbers2(int n) {
    int max =1;
    for (int i = 0; i < n; i++) {
        max*=10;
    }
    int[] ints = new int[max-1];
    for (int i = 0; i <max-1 ; i++) {
        ints[i]=i+1;
    }
    return ints;
}
Copy the code
3.1.2 Execution Effect

3.2 Idea 2: Queues maintain arrays in real time

So the difficulty of this problem is to think about large numbers, and the whole point of this problem in the book is to think about how to deal with large numbers, what are large numbers, and if n=100, then neither int nor long can hold that data, so neither of those types can, you can use string to store large numbers, and then simulate and concatenate all the data, Looping, because leetcode needs to return an int array, so we need to convert it to an int array, but in reality, we can just print it.

The solution to this problem is really magical, dynamically maintaining the output of the queue, without considering whether to add 0 in the book.

You can prepare a queue that puts the numbers 1 through 9 in order, and then an input of n, assuming n is a three-digit number.

  • Take 1, place it in the array, and determine if 1 is less than 3. Yes, concatenate 10, 11, 12… 19 The data is queued.
  • Insert 2 into the array and check if 2 is less than 3. 29 The data is queued.
  • Repeat this until 10 comes in, finding that it is still less than 3 digits, then continue to put the array, and concatenate 100 through 109
  • The final 991-999 data is concatenated until the last 99.
  • Finally, the queue exits empty.

That is, every time I take a number, I add 10 digits to it, and then I stop adding digits until I reach the number of digits in the input, and then I go to the queue and output the result empty.

3.2.1 code
Public static int[] printNumbers3(int n) {int[] ans = new int[(int)(math.pow (10, n)) -1]; Queue<String> q = new LinkedList<>(); For (int I = 1; i <= 9; i++){ q.add(String.valueOf(i)); } int index = 0; while (! q.isEmpty()){ int size = q.size(); for (int i = 0; i < size; I++) {// put a digit in the queue, and then determine whether to concatenate the digit String STR = q.pll (); ans[index++]=Integer.parseInt(str); If (str.length()<n){for(int j=0; j<=9; j++){ q.add(str+j); } } } } return ans; }Copy the code
3.2.2 Execution Effect

Four, summary

The algorithm is not easy to solve. During the interview, it is necessary to make clear that this is actually a large number problem, and the solution of idea 2 in this question is very clever. While finding the rule of data stitching, it can also output the array in order.

This is the end of today’s brush questions, welcome to like comments exchange, sword finger Offer brush questions journey will continue to unfold!