สมมติว่าเรามีจำนวนเต็มบวก N เราต้องหาจำนวนเต็มบวกที่น้อยกว่าหรือเท่ากับ N ที่มีตัวเลขซ้ำกันอย่างน้อย 1 หลัก
ดังนั้น หากอินพุตเท่ากับ 99 เอาต์พุตจะเป็น 9 เนื่องจากเรามีตัวเลขเช่น 11, 22, 33, 44, 55, 66, 77, 88, 99
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน A() ซึ่งจะใช้เวลา m, n,
-
ยกเลิก :=1
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ret :=ret * m
-
(ลด m ทีละ 1)
-
-
รีเทิร์น
-
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
กำหนดอาร์เรย์ arr
-
สำหรับการเริ่มต้น i :=N + 1 เมื่อ i> 0, อัปเดต i :=i / 10 ทำ −
-
แทรกองค์ประกอบแรกของ arr ที่ดัชนี i mod 10 ลงใน arr
-
-
ยกเลิก :=0
-
n :=ขนาดของ arr
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
-
ret :=ret + 9 * A(9, i - 1)
-
-
กำหนดการเยี่ยมชมหนึ่งชุด
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
หลัก :=arr[i]
-
สำหรับการเริ่มต้น j :=(ถ้าฉันเหมือนกับ 0, แล้ว 1 มิฉะนั้น 0) เมื่อ j <หลัก อัปเดต (เพิ่ม j โดย 1) ทำ -
-
ถ้า j มาเยี่ยม −
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
ret :=ret + A(9 - i, n - i - 1)
-
-
หากมีการเข้าชมหลัก −
-
ออกจากวง
-
-
ใส่ตัวเลขเข้าไป
-
-
กลับ 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
