我想找到 1 和 n 之間的數字數量，這些數字是基數（二進制）中的有效數字。
1 ≤ n ≤ 10^9
例如，假設 n 等于 101。
Input: n = 101
在這種情況下，答案是 5
Output: 1, 10, 11, 100, 101 -> 5
另一個例子
Input: n = 13
Output: 1, 10, 11 -> 3
這是我的代碼...
#include <iostream>
using namespace std;
int main()
{
int n, c = 0;
cin >> n;
for (int i = 1; i <= n; i)
{
int temp = i;
bool flag = true;
while(temp != 0) {
int rem = temp % 10;
if (rem > 1)
{
flag = false;
break;
}
temp /= 10;
}
if (flag)
{
c ;
}
}
cout << c;
return 0;
}
但我想要更快的速度。
（只有一個回圈或可能沒有任何回圈）
提前致謝！
uj5u.com熱心網友回復：
將適合在d位數字的最高二進制數d1 d2 ... dn是
b1 b2 ... bn哪里
bi = 0 if di = 0, and
bi = 1 otherwise.
一個簡單的實作std::to_string：
int max_binary(int input) {
int res = 0;
auto x = std::to_string(input);
for (char di : x) {
int bi = x == '0' ? 0 : 1;
res = 2 * res bi;
}
return res;
}
uj5u.com熱心網友回復：
詳細資訊： 在每一步中，如果數字是 1，那么我們將數字的冪加 2。如果數字大于 1，那么對于該數字，所有情況都是可能的，我們也可以計算該數字本身并完全改變答案（-1 是因為我們不想計算 0）。
#include <iostream>
using namespace std;
int main()
{
long long int n, res = 0, count_digit = 0, power = 1;
cin >> n;
while(n != 0) {
int rem = n % 10;
if (rem == 1) {
res = power;
} else if (rem > 1) {
res = 2 * power - 1;
}
n /= 10;
power *= 2;
}
cout << res;
return 0;
}
uj5u.com熱心網友回復：
基本理念
讓你的號碼是dn,...,d1，那么請求號碼的數量可以計算如下 -
- 添加
2^i到總數中，如果di == 1 - 將總計數設定為
2^i - 1ifdi > 1（例如，20->2^2-1=3。因此，專案為01, 10, 11.
因此，代碼可能如下所示。
代碼
uint64_t countMatchingNumbers(uint64_t value) {
uint64_t num = 0;
uint64_t powerOfTwo = 1;
while (value > 0) {
uint8_t digit = value % 10;
if (digit == 1) {
num = powerOfTwo;
} else if (digit > 1) {
num = 2*powerOfTwo-1;
}
powerOfTwo <<= 1;
value /= 10;
}
return num;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344372.html
上一篇：提高python演算法的速度