구 1 - n 직접 1 출현 횟수

제목: 정수 n 을 입력 하여 1 부터 n 까지 n 개의 정수 10 진법 에서 1 이 나타 나 는 횟수 를 구하 십시오.
예 를 들 어 12 를 입력 하면 1 부터 12 까지 이 정수 에 1 이 포 함 된 숫자 는 1, 10, 11, 12 로 1 이 모두 5 번 나 왔 다.
분석: 널리 알려 진 구 글 면접 문제 다.가장 직관 적 인 방법 으로 해답 을 구 하 는 것 은 그리 어렵 지 않 지만 유감스럽게도 효율 이 높 지 않다.효율 이 높 은 알고리즘 을 얻 으 려 면 비교적 강 한 분석 능력 이 필요 하고 쉬 운 일이 아니다.물론 구 글 의 면접 문제 중 간단 한 것 도 몇 개 없다.
먼저 우 리 는 가장 직관 적 인 방법 을 살 펴 보고 각각 1 에서 n 까지 의 정수 중 1 이 나타 나 는 횟수 를 구한다.한편, 하나의 정 수 를 구 하 는 십 진법 은 중 1 이 나타 난 횟수 를 나타 내 면 본 시험 시리즈 의 22 번 째 문제 와 비슷 하 다.우 리 는 매번 정수 의 비트 숫자 가 1 인지 아 닌 지 를 판단 한다.이 숫자 가 10 보다 크 면 10 을 나 눈 후에 한 자리 숫자 가 1 인지 아 닌 지 를 판단 한다.이 사고방식 을 바탕 으로 다음 과 같은 코드 를 쓰기 어렵 지 않다.

int NumberOf1(unsigned int n);

/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in the integers between 1 and n
// Input: n - an integer
// Output: the number of 1 in the integers between 1 and n
/////////////////////////////////////////////////////////////////////////////
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
      int number = 0;

      // Find the number of 1 in each integer between 1 and n
      for(unsigned int i = 1; i <= n; ++ i)
            number += NumberOf1(i);

      return number;
}

/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(unsigned int n)
{
      int number = 0;
      while(n)
      {
            if(n % 10 == 1)
                  number ++;

            n = n / 10;
      }

      return number;
}

이 사고방식 의 매우 뚜렷 한 단점 은 모든 숫자 가 1 이 이 숫자 에 나타 난 횟수 를 계산 해 야 하기 때문에 시간 복잡 도 는 O (n) 이다.입력 한 n 이 매우 클 때 대량의 계산 이 필요 하고 연산 효율 이 매우 낮다.우 리 는 불필요 한 계산 을 피하 기 위해 규칙 을 찾 아 보 았 다.
우 리 는 조금 큰 숫자 21345 를 예 로 들 어 분석 했다.우 리 는 1 부터 21345 까지 의 모든 숫자 를 2 단, 즉 1 - 1235 와 1346 - 21345 로 나 누 었 다.
1346 - 21345 중 1 이 나 온 횟수 를 먼저 살 펴 보 자.1 의 출현 은 두 가지 상황 으로 나 뉜 다. 하 나 는 1 이 최고 (만 위) 에 나타난다.1 부터 21345 까지 의 숫자 중 1 은 10000 - 1999 라 는 10000 개의 숫자 만 자리 에 나타 나 모두 10000 (104) 번 이 나 타 났 다.또 다른 경 우 는 1 이 최고 위 를 제외 한 다른 자리 에 나 타 났 다.예 를 들 어 1346 - 21345. 이 20000 개의 숫자 중 뒤의 네 자리 중 1 이 나타 난 횟수 는 2000 회 (2 * 103, 그 중에서 2 의 첫 번 째 수 치 였 다. 103 은 숫자의 뒷 네 자리 숫자 중 한 자리 가 1 이 고 나머지 세 자리 숫자 는 0 에서 9 까지 10 개의 숫자 를 임의로 선택 할 수 있 으 며 배열 조합 으로 총 횟수 는 2 * 103) 임 을 알 수 있 기 때문이다.
1 부터 1345 까지 의 모든 숫자 중 1 이 나타 난 횟수 에 대해 우 리 는 재 귀적 으로 구 할 수 있다.이것 도 우리 가 왜 1 - 21345 를 1 - 1235 와 1346 - 21345 두 단락 으로 나 누 어야 하 는 이유 이다.21345 의 최고 위 치 를 없 애 면 1345 를 얻 을 수 있 기 때문에 우 리 는 재 귀 적 인 사 고 를 사용 하 는 데 편리 하 다.
여기 서 또 하나의 특수 한 상황 을 분석 할 때 주의해 야 한다. 앞에서 우리 가 예 를 들 면 가장 높 은 자 리 는 1 보다 큰 숫자 이 고 이때 가장 높 은 자리 1 이 나타 난 횟수 는 104 (다섯 자리 수 에 대해 말하자면) 이다.그런데 최고 자리 가 1 이 라면?예 를 들 어 12345 를 입력 하면 10000 에서 12345 까지 이 숫자 들 중에서 1 만 자리 에서 나타 나 는 횟수 는 104 번 이 아니 라 2346 번 이다. 즉, 가장 높 은 숫자 를 제외 한 나머지 숫자 에 1 을 더 하 는 것 이다.
앞의 분석 을 바탕 으로 우 리 는 다음 과 같은 코드 를 쓸 수 있다.참고 코드 에서 프로 그래 밍 이 편리 하도록 나 는 숫자 를 문자열 로 바 꾸 었 다.

#include <iostream>
#include "string.h"
#include "stdlib.h"
#include <stdio.h>
using namespace std;
int NumberOf1(const char* strN);
int PowerBase10(unsigned int n);

/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1BeforeBetween1AndN_Solution2(int n)
{
      if(n <= 0)
            return 0;

      // convert the integer into a string
      char strN[50];
      sprintf(strN, "%d", n);

      return NumberOf1(strN);
}
/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: strN - a string, which represents an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(const char* strN)
{
      if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
            return 0;

      int firstDigit = *strN - '0';
      unsigned int length = static_cast<unsigned int>(strlen(strN));

      // the integer contains only one digit
      if(length == 1 && firstDigit == 0)
            return 0;

      if(length == 1 && firstDigit > 0)
            return 1;

      // suppose the integer is 21345
      // numFirstDigit is the number of 1 of 10000-19999 due to the first digit
      int numFirstDigit = 0;
      // numOtherDigits is the number of 1 01346-21345 due to all digits
      // except the first one
      int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2);
      // numRecursive is the number of 1 of integer 1345
      int numRecursive = NumberOf1(strN + 1);

      // if the first digit is greater than 1, suppose in integer 21345
      // number of 1 due to the first digit is 10^4. It's 10000-19999
      if(firstDigit > 1)
            numFirstDigit = PowerBase10(length - 1);

      // if the first digit equals to 1, suppose in integer 12345
      // number of 1 due to the first digit is 2346. It's 10000-12345
      else if(firstDigit == 1)
            numFirstDigit = atoi(strN + 1) + 1;

      return numFirstDigit + numOtherDigits + numRecursive;
}

/////////////////////////////////////////////////////////////////////////////
// Calculate 10^n
/////////////////////////////////////////////////////////////////////////////
int PowerBase10(unsigned int n)
{
      int result = 1;
      for(unsigned int i = 0; i < n; ++ i)
            result *= 10;
      return result;
}
int main()
{
   int num =  NumberOf1BeforeBetween1AndN_Solution2(112452);
   cout<<num<<endl;

}