leetcode 퀴즈
1568 단어 leetcode
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding
[11,22,33,44,55,66,77,88,99] 예를 들어 n=3, 우리가 구한 것은 0-999 사이에 얼마나 유일무이한 숫자가 있는지이다.우리는 100에서 999 사이에 얼마나 많은 유일무이한 숫자가 있는지 분리해서 0에서 99의 결과를 더하면 된다.같은 이치로 0-99를 구하고, 먼저 10-99를 구한 다음에 0-9의 결과를 더하면, 우리는 이미 0-9의 결과가 10이라는 것을 알고 있기 때문에 10-99만 요구하면 된다.먼저 첫 번째 숫자를 보면 수치를 얻을 수 있는 범위는 1-9로 모두 9가지가 가능하다. 두 번째 숫자의 수치를 얻을 수 있는 범위는 0-9이고 이론적으로 10개의 수를 얻을 수 있지만 첫 번째 숫자와 중복되는 상황을 고려하면 9개만 얻을 수 있기 때문에 10-99 사이의 유일한 숫자는 9x9=81개이다.이제 100-999 사이를 돌아보면 10-99를 토대로 바로 3위 숫자를 보면 0-9, 앞의 두 자리 숫자가 중복될 수 있기 때문에 8개만 뽑을 수 있기 때문에 100-999 사이의 유일무이한 숫자는 81 X 8 = 648개에 불과할 것이다. 여기에 앞의 0-99 사이의 개수를 더하면 0-999 사이의 유일무이한 숫자는 648 + 81 + 10 = 739개이다.순서대로 유추하면 3을 초기값으로 하고 n에 한 자리를 더 추가하면 이 위치에서 선택할 수 있는 숫자의 개수는 -1이고 코드는 다음과 같다.
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if (n == 0)
{
return 1;
}
if (n == 1)
{
return 10;
}
vector dp(n + 1, 0);
dp[2] = 91;
for (int i = 3; i < n + 1; ++i)
{
int sum = 81;
for (int j = 3; j <= i; ++j)
{
sum *= (11 - j);
}
dp[i] = sum + dp[i - 1];
}
return dp[n];
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
