검지offer-3-면접12:1부터 최대 n자리까지 인쇄

9738 단어 검지offer
  • 제목
  • 분석
  • 면접관의 함정에 뛰어들어 대수를 고려하지 않았다
  • 문자열에 디지털 덧셈을 시뮬레이션하는 해법
  • 문제를 디지털 배열로 바꾸는 해법 귀속 코드를 더욱 간결하게
  • 테스트 용례 코드
  • 본제 시험점
  • 확장
  • 관련 제목
  • 제목.


    숫자 n을 입력하여 1에서 최대 n까지의 십진수를 순서대로 인쇄합니다.예를 들어 3을 입력하면 1, 2, 3이 가장 큰 세 자리, 즉 999까지 출력된다.

    분석하다.


    면접관의 함정에 빠져 대수 문제를 고려하지 않았다


    제목은 보기에 매우 간단하다.이 문제를 본 후 가장 생각하기 쉬운 방법은 먼저 가장 큰 n자리를 구한 다음에 하나의 순환으로 1부터 하나씩 인쇄하는 것이다.따라서 다음과 같은 코드를 쉽게 쓸 수 있다.
    void print1ToMaxOfNDigits_1( int n )
    {
        int number = 1;
        int i = 0;
        while( i++ < n )
            number *= 10;
        for( i=1;i<number; ++i )
            cout << i << "\t";
    }

    처음 보면 문제가 없는 것 같지만 이 문제를 자세히 분석하면 면접관이 n의 범위를 정하지 않은 것을 발견할 수 있다.n을 크게 입력했을 때 가장 큰 n자리를 구하려면 정형(int)이나 장정형(long long)이 넘칠까요?대수 문제를 고려해야 한다는 얘기다.

    문자열에 디지털 덧셈을 시뮬레이션하는 해법


    분석을 통해 이 문제를 해결하려면 큰 수를 표현해야 한다고 생각할 수 있다.가장 자주 사용하고 가장 쉬운 방법은 문자열이나 수조로 큰 수를 표현하는 것이다.다음은 문자열로 대수 고문단을 해결한다.
    문자열로 숫자를 표시할 때 가장 직관적인 방법은 문자열 안의 모든 문자가'0'에서'9'사이의 어떤 문자로 숫자 중의 한 사람을 나타내는 것이다.숫자가 가장 큰 것은 n자리이기 때문에 길이 n+1의 문자열이 필요합니다. (문자열 중 마지막은 끝 기호 '\0' 입니다.)실제 숫자가 n자리가 되지 않을 때 문자열의 앞부분에서 0을 보충합니다.
    우선 우리는 문자열의 모든 숫자를 '0' 으로 초기화한 다음에 매번 문자열에 표시된 숫자에 1을 더해서 인쇄한다.따라서 우리는 두 가지 일을 할 수 있다. 하나는 문자열이 표현한 숫자에 아날로그 덧셈을 하는 것이고, 다른 하나는 문자열이 표현한 숫자를 출력하는 것이다.위의 분석을 바탕으로 다음과 같은 코드를 작성할 수 있습니다.
    void print1ToMaxOfNDigits( int n )
    {
        if( n <= 0 )
            return;
        char *number = new char[ n+1 ];
        memset( number, '0', n );
        number[ n ] = '\0';
    
        //Increment            number   1
        while( !Increment( number ) )
        {
            PrintNumber( number ); //   number
        }
        delete []number;
    }

    인크리에이션과 관련해서는 number에서 1을 늘리는 것을 언제 멈추는지, 즉 최대 n자리인'999...99'(n개 9)에 도달했는지 알아야 한다.가장 간단한 방법은 매번 증가할 때마다 라이브러리 함수strcmp를 호출하여 수치를 나타내는 문자열인number와 가장 큰 n자리 '999... 99' 를 비교하는 것이다. 만약 같으면 이미 가장 큰 n자리 수에 이르렀고 증가를 중지하는 것이다.strcmp를 호출하는 것은 간단하지만, 길이가 n인 문자열의 시간 복잡도는 O (n) 이다.
    "999...99"에 1을 더할 때만 첫 번째 문자(아래 0 표시)에 진위가 생기고, 다른 모든 경우 첫 번째 문자에 진위가 생기지 않는다.따라서 1을 추가할 때 첫 번째 문자에 진위가 생겼다는 것을 발견하면 가장 큰 n자리수입니다. 이 때 Increment는true를 되돌려줍니다. 따라서 함수Print1ToMax OfNdigits의while 순환이 종료됩니다.매번 1씩 증가한 후에 가장 큰 n자리까지 왔는지 아닌지를 신속하게 판단하는 것은 본 문제의 작은 함정이다.다음은 Increment 함수의 참조 코드로, 최대 n 자릿수에 도달했는지 O(1) 시간으로 판단할 수 있습니다.
    bool Increment( char * number )
    {
        bool isOverflow = false;
        int nTakeOver = 0;
        int nLength = strlen( number );
        for( int i=nLength -1; i>=0; i-- )
        {
            int nSum = number[i] - '0' + nTakeOver ;
            if( i==nLength - 1 )
                nSum++;
            if( nSum >= 10 )
            {
                if( i==0 ) isOverflow = true;
                else
                {
                    nSum -= 10;
                    nTakeOver = 1;
                    number[i] = '0' + nSum;
                }
            }
            else
            {
                number[i] = '0' + nSum;
                break;
            }
        }
        return isOverflow;
    }

    다음은 문자열로 표시된 숫자를 어떻게 인쇄하는지 고려합니다.라이브러리 함수 printf는 문자열을 쉽게 출력할 수 있지만, 이 문제에서 printf를 호출하는 것은 가장 적합한 해결 방안이 아닙니다.앞에서 언급한 바와 같이 숫자가 n자리가 부족할 때 우리는 숫자의 앞에서 0을 보충하고 인쇄할 때 이 보충된 0은 인쇄해서는 안 된다.예를 들어 3을 입력할 때 숫자 98은 문자열로 098을 표시하는데 098을 직접 출력하면 우리의 습관에 맞지 않는다.이를 위해 함수PrintNumber를 정의했습니다. 이 함수에서 문자열의 끝까지 첫 번째 0이 아닌 문자를 만났을 때만 인쇄를 시작합니다.
    void PrintNumber( char * number )
    {
        bool isBeginning0 = true;
        int nLength = strlen( number );
        for( int i=0; i<nLength; ++i)
        {
            if(isBeginning0 && number[i] !='0' )
                isBeginning0 = false;
            if( !isBeginning0 )
                cout << number[i] ;
        }
        cout << "\t" ;
    }

    문제를 디지털 배열의 해법으로 바꾸어 코드를 더욱 간결하게 하다


    상술한 사고방식은 비교적 직관적이지만 정수의 덧셈을 모의했기 때문에 코드가 좀 길다.면접 몇 십 분 만에 이렇게 긴 코드를 완전하고 정확하게 쓰는 것은 많은 지원자들에게 쉬운 일이 아니다.다음에 우리는 사고방식을 바꾸어 이 문제를 고려한다.만약 우리가 숫자 앞에서 0을 보충한다면 n위의 모든 십진수는 사실 n개가 0에서 9까지의 전체 배열이라는 것을 발견할 수 있을 것이다.즉, 우리는 숫자의 한 사람 한 사람을 0-9에서 한 번 배열하면 모든 십진수를 얻을 수 있다.다만 우리가 인쇄할 때, 숫자가 앞에 배열되어 있는 0은 인쇄하지 않는다
    전체 배열은 귀환으로 쉽게 표현할 수 있으며 숫자의 한 자리 한 자리가 0-9의 한 수일 수도 있고 다음 자리를 설정할 수도 있다.귀환이 끝나는 조건은 우리가 이미 숫자의 마지막 자리를 설정한 것이다.
    void Print1ToMaxOfNDigits( int n )
    {
        if( n<= 0 )
            return;
        char *number = new char[ n+1 ];
        number[ n ] = '\0';
    
        for( int i=0; i<10; ++i )
        {
            number[0] = i + '0';
            Print1ToMaxOfDigitsRecursively( number, n, 0 );
        }
        delete []number;
    }
    
    void Print1ToMaxOfNDigitsRecursively( char* number, int length, int index )
    {
        if( index==length-1 )
        {
            PrintNumber( number );
            return;
        }
        for( int i=0; i<10; ++i )
        {
            number[index+1] = i+'0';
            Print1ToMaxOfNDigitsRecursively( number, length, index+1 );
        }
    }

    테스트 용례 & 코드


    (1) 기능 테스트(1, 2, 3 입력...)
    (2) 특수 입력 테스트(입력-1,0)

    본제 시험장


    (1) 대수 문제를 해결하는 능력.면접관이 이 문제를 낼 때 지원자가 큰 문제라는 것을 깨닫고 적당한 데이터 표시 방식을 정의하여 큰 문제를 해결할 수 있기를 기대한다.
    (2) 만약에 지원자가 첫 번째 사고방식, 즉 숫자에 1씩 인쇄하는 사고방식을 채택한다면 면접관은 그가 가장 큰 n자리에 도달했는지 판단할 때 사용하는 방법을 주목할 것이다.지원자는 서로 다른 방법의 시간 효율 차이가 매우 크다는 것을 주의해야 한다
    (3) 지원자가 두 번째 사고방식을 채택하면 면접관은 그가 귀속 방법으로 문제를 해결하는 능력을 고찰한다.
    (4) 지원자가 숫자를 출력할 때 숫자 맨 앞에 있는 0이 출력되는지도 주목한다.지원자들이 소프트웨어를 디자인하고 개발할 때 사용자의 사용 습관을 고려하는지 알 수 있다.일반적으로 우리의 소프트웨어 디자인과 개발은 대부분의 사용자의 인간관계 습관에 부합해야 한다.

    본제 확장


    앞의 코드에서, 우리는 모두char형 문자로 십진수 숫자의 한 자리를 표시한다.8개bit의char형 문자는 최대 256개의 문자를 나타낼 수 있지만, 10진수 숫자는 0-9의 10개의 숫자에 불과하다.따라서char형 문자열로 십진수를 표시하는 숫자는 메모리를 충분히 이용하지 못해 낭비가 있었다.더 효율적인 방식으로 대수를 나타낼 수 있습니까

    관련 문제


    이 함수에서 임의의 두 정수의 덧셈을 실현할 수 있는 함수를 정의합니다.두 개의 수를 입력하는 크기 범위를 한정하지 않았기 때문에, 우리도 그것을 대수 문제로 처리해야 한다.앞의 코드의 첫 번째 사고방식에서 문자열이 표시하는 숫자에 1을 더하는 기능을 실현했다. 우리는 이 사고방식을 참고하여 두 숫자의 더하기 기능을 실현할 수 있다.또 주의해야 할 문제가 하나 더 있다. 만약 입력한 숫자에 마이너스가 있다면 우리는 어떻게 처리해야 합니까?

    좋은 웹페이지 즐겨찾기