Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The problem

Prints 1 to the largest number of n digits

Power button link

Leetcode-cn.com/problems/da…

Review key points

Large number problems, recursive thinking

Idea 1

First of all, I’m going to determine its maximum value, which is 10 to the n minus 1, based on the bits I pass in

Then, use the for loop to iterate over the number from 1 to this maximum

Time complexity: O(10N)

Code 1

public int[] printNumbers(int n) { if (n <= 0) return new int[]{}; Int end = (int) math.pow (10, n) -1; 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; }Copy the code

Idea 2

We can use the idea of a complete arrangement of numbers, and we can use recursion to complete the complete arrangement

For example, if n is 2, the order from highest to lowest is

00, 01, 02,… ,

10, 11, 12, …, 19

Of course, when we use the character array to complete the arrangement, we should be careful to remove the superfluous 0

When a number is 1 bit, we can intercept 1 bit from the end of the string

When the number is 2 bits, we can intercept 2 bits from the end of the string

Code 2

Int [] res; Int count = 0; Int nine = 0; Int start = 0; int start = 0; / / num for single permutation storage character array / / loop of 0-9 digital char [] num, loop = {' 0 ', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; public int[] printNumbers2(int n) { if (n <= 0) return new int[]{}; // Initialize an array with 10 to the n elements res = new int[(int) math.pow (10, n) -1]; // Initialize an array with 10 to the n elements res = new int[(int) math.pow (10, n) -1]; Num = new char[n]; // To print numbers from low to high, start from the last element of the array start = n-1; // enable full array DFS (0, n); return res; } void DFS (int x, int n) {if(x == n) { String s = string.valueof (num).substring(start); // Convert the string to integer data and store it in the return value if(! s.equals("0")) res[count++] = Integer.parseInt(s); If (n-start == nine) start--; if(n-start == nine) start--; return; } for(char i : loop) { if(i == '9') nine++; /* * 00, 01, 02, 03... , 09 * 10, 11, 12, 13... , 19 * */ num[x] = i; dfs(x + 1, n); } nine--; }Copy the code

conclusion

To solve a large number problem, we need to convert it to a string or an array of characters. If the problem does not have a limited range of values, or you can enter integers of any size, you should consider large numbers, which can be converted to strings or character arrays.