解题思路
这是一道数位统计题目,主要思路如下:
-
问题分析:
- 统计
到
中数字
出现的次数
的范围很大,需要优化算法
- 如
中包含
这些数字
- 需要统计每个位置上
出现的次数
- 统计
-
解决方案:
- 按位计算,从个位开始
- 对每一位,分三种情况:
- 当前位是0
- 当前位是1
- 当前位大于1
代码
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
long ans = 0;
int idx = 0; // 当前处理的位数
int right = 0; // 右边的数字
while(n) {
// 当前位的数字
int cur = n % 10;
// 左边的数字
int left = n / 10;
// 根据当前位的数字分三种情况
if(cur == 0) {
// 当前位是0,由左边数字决定
ans += left * pow(10, idx);
} else if(cur == 1) {
// 当前位是1,需要考虑右边的数字
ans += left * pow(10, idx) + right + 1;
} else {
// 当前位大于1
ans += (left + 1) * pow(10, idx);
}
// 更新右边的数字
right += cur * pow(10, idx);
n /= 10;
idx++;
}
cout << ans << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long ans = 0;
int idx = 0;
int right = 0;
while(n > 0) {
int cur = n % 10;
int left = n / 10;
if(cur == 0) {
ans += left * Math.pow(10, idx);
} else if(cur == 1) {
ans += left * Math.pow(10, idx) + right + 1;
} else {
ans += (left + 1) * Math.pow(10, idx);
}
right += cur * Math.pow(10, idx);
n /= 10;
idx++;
}
System.out.println(ans);
}
}
def count_ones(n: int) -> int:
ans = 0
idx = 0
right = 0
while n:
# 当前位的数字
cur = n % 10
# 左边的数字
left = n // 10
if cur == 0:
ans += left * (10 ** idx)
elif cur == 1:
ans += left * (10 ** idx) + right + 1
else:
ans += (left + 1) * (10 ** idx)
right += cur * (10 ** idx)
n //= 10
idx += 1
return ans
def main():
n = int(input())
print(count_ones(n))
if __name__ == "__main__":
main()
算法及复杂度
- 算法:数位统计
- 时间复杂度:
-
的位数
- 空间复杂度:
- 只需要常数空间