判断一个数是否是 Step Sum
2023-02-18 16:36:44 时间
判断一个数是否是 Step Sum
作者:Grey
原文地址:
题目说明
何为 Step Sum?
比如:680 这个数
680 + 68 + 6 = 754,
所以 680 这个数的 Step Sum 是754,
给定一个正数 num,判断它是不是某个数的 Step Sum。
主要思路
使用二分法来解决这个问题,思路如下
如果一个数 x 的 Step Sum 为 m,
另外一个数 y 的 Step Sum 为 n,
如果 x 大于 y,则 m 一定大于 n。
给定一个数 num,我们可以求 0 到 num 的中点位置 mid,看 mid 这个位置的 Step Sum 是不是给定的 num,如果是,直接返回 true,如果中点位置的 Step Sum 大于 num,则考虑在左半边继续二分,如果中点位置的 Step Sum 小于 num,则考虑在右半边继续二分。
public class Code_0111_IsStepSum {
public static boolean isStepSum(int stepSum) {
int i = 0;
int j = stepSum;
while (i <= j) {
int mid = i + ((j - i) >> 1);
int value = stepSumOf(mid);
if (value == stepSum) {
return true;
} else if (value < stepSum) {
i = mid + 1;
} else {
// value > stepSum
j = mid - 1;
}
}
return false;
}
public static int stepSumOf(int num) {
int v = 0;
while (num != 0) {
v += num;
num = num / 10;
}
return v;
}
}
经过对数器验证
import java.util.HashMap;
public class Code_IsStepSum {
public static boolean isStepSum(int stepSum) {
int i = 0;
int j = stepSum;
while (i <= j) {
int mid = i + ((j - i) >> 1);
int value = stepSumOf(mid);
if (value == stepSum) {
return true;
} else if (value < stepSum) {
i = mid + 1;
} else {
// value > stepSum
j = mid - 1;
}
}
return false;
}
public static int stepSumOf(int num) {
int v = 0;
while (num != 0) {
v += num;
num = num / 10;
}
return v;
}
public static int stepSum(int num) {
int sum = 0;
while (num != 0) {
sum += num;
num /= 10;
}
return sum;
}
// for test
public static HashMap<Integer, Integer> generateStepSumNumberMap(int numMax) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i <= numMax; i++) {
map.put(stepSum(i), i);
}
return map;
}
// for test
public static void main(String[] args) {
int max = 10000000;
int maxStepSum = stepSum(max);
HashMap<Integer, Integer> ans = generateStepSumNumberMap(max);
System.out.println("测试开始");
for (int i = 0; i <= maxStepSum; i++) {
if (isStepSum(i) ^ ans.containsKey(i)) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}
未打印任何出错信息。代码通过。
更多
参考资料
相关文章
- 面试问关于Handler的这些问题你知道吗?
- 记录一到当时没做出来的 “解析Json计算表达式值” 的算法题
- 别慌,大学是你乘风破浪的最佳时机————一个准大三的信息与计算科学专业学长想说的一些话
- 一图帮你了解什么是信息与计算科学专业
- 多功能可充电移动照明LED驱动控制IC方案
- 刨根问底 Redis, 面试过程真好使
- 知行之桥2022版本升级之页面变化以及监控邮件答疑
- 刨根问底 Kafka,面试过程真好使
- JCR1区,IF 5分+,自引率低,国人友好,无版面费!
- 隐私计算-Paillier半同态加密算法解密加速优化
- <七>1:全面掌握Const的用法
- 什么是计算机网络
- NGINX常见的变量说明
- NGINX的配置和基本使用
- ubuntu1804搭建FTP服务器的方法
- CentOS 7 创建自签名证书
- Ubuntu1804、20.04使用systemback打包镜像的实现
- NGINX信号管理
- NGINX的编译安装
- 实现NFS共享存储的wordpress