資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中具有重複數字的數字
假設我們有一個正整數N，我們必須找到小於或等於N且至少有一個重複數字的正整數的個數。
因此，如果輸入是99，則輸出將是9，因為我們有11、22、33、44、55、66、77、88、99這樣的數字。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式A()，它將接收m, n作為引數：
ret := 1
for i := 0 to n-1 do −
ret := ret * m
m := m - 1
return ret
在主方法中執行以下操作：
定義一個數組arr
for i := N + 1 downto 1 do −
將arr的第一個元素插入到arr的索引i mod 10處
ret := 0
n := arr的長度
for i := 1 to n-1 do −
ret := ret + 9 * A(9, i - 1)
定義一個集合visited
for i := 0 to n-1 do −
digit := arr[i]
for j := (if i == 0 then 1 else 0) to digit -1 do −
if j in visited then −
忽略以下部分，跳到下一次迭代
ret := ret + A(9 - i, n - i - 1)
if digit in visited then −
退出迴圈
將digit插入到visited中
return N - ret
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int A(int m, int n){
int ret = 1;
for (int i = 0; i < n; i++) {
ret *= m;
m--;
}
return ret;
}
int numDupDigitsAtMostN(int N){
vector<int> arr;
for (int i = N + 1; i > 0; i /= 10) {
arr.insert(arr.begin(), i % 10);
}
int ret = 0;
int n = arr.size();
for (int i = 1; i < n; i++) {
ret += 9 * A(9, i - 1);
}
set<int> visited;
for (int i = 0; i < n; i++) {
int digit = arr[i];
for (int j = i == 0 ? 1 : 0; j < digit; j++) {
if (visited.count(j))
continue;
ret += A(9 - i, n - i - 1);
}
if (visited.count(digit))
break;
visited.insert(digit);
}
return N - ret;
}
};
main(){
Solution ob;
cout << (ob.numDupDigitsAtMostN(99));
}輸入
99
輸出
9
更新於：2020年6月4日
573 次瀏覽
廣告