검지 Offer-문제 17(Java 버전): 인쇄 1에서 최대 n 자릿수
3655 단어 검지 Offer-자바
제목: 1부터 최대 n자리까지 숫자 n을 입력하고 1부터 최대 n자리까지 10진수를 순서대로 출력합니다.예를 들어 3을 입력하면 1, 2, 3이 최대 세 자릿수인 999까지 출력된다.
주요 사고방식: 1부터 가장 큰 n자리수는 사실 n개가 0에서 9까지의 전체 배열이다. 숫자의 한 자리를 0에서 9까지 배열하면 모든 수를 얻을 수 있고 총수는 10n10n이다.귀속을 사용하여 전체 배열을 실현할 수 있다.
키포인트: 반복
시간 복잡도: O(10n 10n)
public class PrintOneToMaxOfNDigits
{
public static void main(String[] args)
{
int n = 3;
print1ToMaxOfNDigits(n);
}
private static void print1ToMaxOfNDigits(int n)
{
if (n <= 0)
return;
char[] numbers = new char[n];
for (int i = 0; i < 10; ++i)
{
numbers[0] = (char) (i + '0');
printByRecursively(numbers, n, 0);
}
}
private static void printByRecursively(char[] numbers, int length, int index)
{
if (index == length - 1)
{
printNumber(numbers); // n,
return;
}
for (int i = 0; i < 10; ++i)
{
numbers[index + 1] = (char) (i + '0');
printByRecursively(numbers, length, index + 1);
}
}
private static void printNumber(char[] numbers)
{
boolean isBeginWithZero = true;
for (char number : numbers)
{
// 0
if (isBeginWithZero && number != '0')
isBeginWithZero = false;
if (!isBeginWithZero)
{
System.out.print(number);
}
}
System.out.println();
}
}