검지 Offer-문제 17(Java 버전): 인쇄 1에서 최대 n 자릿수

3655 단어 검지 Offer-자바
참고: <검지 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();
    }
}

좋은 웹페이지 즐겨찾기