A non-negative integer is called heavy if the average value of its digits in decimal representation exceeds 7. Assume that 0 has an average value of its digits equal to 0.
For example, the number 8,698 is heavy because the average value of its digits is (8+6+9+8)/4 = 7.75. The number 53,141 has an average value of its digits of (5+3+1+4+1)/5 = 2.8, so it is not heavy.
Write a function:
class Solution { public int heavy_decimal_count(int A,int B); }
that, given two non-negative integers A and B, returns the number of heavy integers within the interval [A..B] (both ends included).
Assume that:
- A is an integer within the range [0..200,000,000];
- B is an integer within the range [0..200,000,000];
- A ≤ B.
For example, given A=8,675 and B=8,689 the function should return 5, because there are five heavy integers within the range [8,675..8,689]:
8675 avg=6.50
8676 avg=6.75
8677 avg=7.00
8678 avg=7.25 HEAVY
8679 avg=7.50 HEAVY
8680 avg=5.50
8681 avg=5.75
8682 avg=6.00
8683 avg=6.25
8684 avg=6.50
8685 avg=6.75
8686 avg=7.00
8687 avg=7.25 HEAVY
8688 avg=7.50 HEAVY
8689 avg=7.75 HEAVY
Complexity:
- expected worst-case time complexity is O((log(A)+log(B))3);
- expected worst-case space complexity is O(log(A)+log(B)).
这个不确定,高手可以指教。
方案一:
public int heavy_decimal_count(int A,int B) {
int result = 0;
int n = B - A;
for(int i = 0; i <= n; i++) {
int t = A + i;
if(t == 0) {
continue;
}
int w = 0;
double sum = 0;
while(t > 0) {
sum += (t % 10);
t = t / 10;
w++;
};
if((sum / w) > 7) {
result++;
}
}
return result;
}
方案二:
public int heavy_decimal_count(int A,int B) {
int result = 0;
int x = A;
double sum = 0;
Vector<Integer> v = new Vector<Integer>(9);
if(x == 0) {
v.add(0);
} else {
while(x > 0) {
int ys = (x % 10);
v.add(ys);
sum += ys;
x = x / 10;
};
if(sum / v.size() > 7) {
result++;
}
}
int n = B - A;
for(int i = 1; i <= n; i++) {
int jw = 0;
for(int j = 0; j < v.size(); j++) {
if(v.get(j) + 1 == 10) {
v.set(j, 0);
jw++;
if(jw < v.size()) {
continue;
} else {
v.add(1);
}
} else {
v.set(j, v.get(j) + 1);
}
break;
}
sum = sum - (9 * jw) + 1;//这个是关键,不需要每次循环求和,而是根据上一个数的结果得到下一个数的结果,其中jw表示相当上一个数,当前数做了几次进位操作
if(sum / v.size() > 7) {
result++;
}
}
return result;
}
分享到:
相关推荐
磁盘调度算法包括: 1.先来先服务算法 2.电梯(扫描)算法 3复制请求队列 4.最短路径优先算法
Simple算法3个典型算例,详细讲解。二维、结构网格单相流SIMPLE 算法的C语言实现。
java算法全卷(包括基本算法和图算法)
算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法
1.1. 一次计算最小二乘算法 3 1.2. 递推最小二乘算法 3 2. 遗忘因子最小二乘算法 6 2.1. 一次计算法 6 2.2. 递推算法 6 3. 限定记忆最小二乘递推算法 9 4. 偏差补偿最小二乘法 11 5. 增广最小二乘法 13 6. 广义最小...
3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、...
1.2 群智能算法 3 1.3 模拟退火算法 5 1.4 禁忌搜索算法 5 1.5 神经网络算法 6 参考文献 6 第2章 遗传算法 9 2.1 引言 9 2.2 遗传算法理论 10 2.2.1 遗传算法的生物学基础 10 2.2.2 遗传算法理论...
动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法.
由于SHA3算法的详细介绍非常的少,本文档主要用于深入理解SHA3算法的原理。
算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法算法
3. 通过编程,会在C/C++环境下完成用DDA算法、中点bresenham算法及bresenham算法对任意直线段的扫描转换。 实验设备及实验环境 计算机(每人一台) VC++6.0或其他C/C++语言程序设计环境 实验学时:2学时 实验内容 用...
社区划分算法的python3实现, 包括KL算法、 COPAR、Louvain 算法、LFM算法、InfoMap算法等
LFU算法LFU算法LFU算法LFU算法LFU算法
基于c++语言的聚类算法实现,1.k-means聚类算法 2.层次聚类算法 3.SOM聚类算法 4.FCM聚类算法
模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+...
SM3算法原理,朋友亲自整理的,供大家交流学习。
A5算法A5算法A5算法A5算法A5算法A5算法A5算法A5算法A5算法A5算法A5算法
分配算法 首次适应算法 最佳适应算法 循环首次适应算法 有流程图 源代码
POS算法POS算法POS算法POS算法POS算法
Python复现遗传算法、蚁群优化算法、粒子群算法、禁忌搜索算法 详细算法介绍链接:https://blog.csdn.net/qq_44186838/article/details/109181453