검지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을 더하는 기능을 실현했다. 우리는 이 사고방식을 참고하여 두 숫자의 더하기 기능을 실현할 수 있다.또 주의해야 할 문제가 하나 더 있다. 만약 입력한 숫자에 마이너스가 있다면 우리는 어떻게 처리해야 합니까?
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.