[검 지 offer] 면접 문제 17: 1 부터 최대 n 자리 까지 인쇄

전체 코드 주소
전체 코드 주소
제목.
숫자 n 을 입력 하고 1 에서 최대 n 자리 10 진 수 를 순서대로 출력 합 니 다.예 를 들 어 3 을 입력 하면 1, 2, 3 에서 가장 큰 세 자릿수 999 까지 출력 한다.
사고의 방향
해법 1 예 를 들 어 입력 숫자 3 은 다음 과 같은 숫자 로 배열 할 수 있다. 000 001 002. 997 998 999 는 바로 숫자의 전체 배열 을 인쇄 하 는 것 이다.그래서 재 귀적 으로 풀 수 있 습 니 다.
해법 2 가 점점 증가 하고 매번 최저 + 1 에 있 는 다음 에 숫자 10 이 나타 나 는 상황 을 처리 할 때 주의해 야 할 점 이 있 습 니 다. 인쇄 가 끝 난 것 을 어떻게 판단 하 는 지 두 가지 방법 이 있 습 니 다. 1. 문자열 로 알고리즘 을 비교 하고 '999... 99' 즉 가장 큰 숫자 와 비교 하면 시간 복잡 도 는 O (n) 이 고 취 할 수 없습니다. 2. 최고 위치 가 진 위 를 일 으 켰 는 지 판단 하고 시간 복잡 도 는 O (1) 입 니 다.나 는 이런 방법 을 사용한다.
코드 (해법 1)

public static void Print1ToMaxOfNDigits_1(int n) {
    if(n <= 0)
        return;
    char[] digits = new char[n];
    Print1ToMaxOfNDigits_1(digits, n-1);
}

/**
 *   ，     
 */
private static void Print1ToMaxOfNDigits_1(char[] digits, int index) {
    if(index == -1) {
        PrintDigit(digits);
        return;
    }
    for(int i = 0; i < 10; ++i) {
        digits[index] = (char) ('0' + i);
        Print1ToMaxOfNDigits_1(digits, index-1);
    }
}

/**
 *   digits，        0
 */
private static void PrintDigit(char[] digits) {
    boolean zeroFlag = true;
    for(int i = digits.length-1; i >= 0; --i) {
        if(digits[i] == '0' && zeroFlag)
            continue;
        System.out.print(digits[i]);
        zeroFlag = false;
    }
    if(zeroFlag == false) {
        System.out.print(' ');
    }
}

해법

public static void Print1ToMaxOfNDigits_2(int n) {
    if(n <= 0)
        return;
    char[] digits = new char[n];
    for(int i = 0; i < digits.length; ++i) {
        digits[i] = '0';
    }
    while(Increment(digits)) {
        PrintDigit(digits);
    }
}

/**
 *    
 */
private static boolean Increment(char[] digits) {
    digits[0] += 1;
    for(int i = 0; i < digits.length; ++i) {
        int num = digits[i] - '0';
        if(num == 10) {
            if(i == digits.length-1) {
                return false;
            }
            digits[i+1] += 1;
            digits[i] = '0';
        }
        else {
            break;
        }
    }
    return true;
}

/**
 *   digits，        0
 */
private static void PrintDigit(char[] digits) {
    boolean zeroFlag = true;
    for(int i = digits.length-1; i >= 0; --i) {
        if(digits[i] == '0' && zeroFlag)
            continue;
        System.out.print(digits[i]);
        zeroFlag = false;
    }
    System.out.print(' ');
}

테스트

public static void main(String[] args) {
    test1();
    test2();
}

private static void test1() {
    _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(1);
    System.out.println();
    _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(2);
    System.out.println();
    _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(3);
    System.out.println();
    System.out.println();
}

private static void test2() {
    _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(0);
    System.out.println();
    _17_Print1ToMaxOfNDigits.Print1ToMaxOfNDigits_1(-1);
    System.out.println();
}