Hard 计算0到n之间2的个数 @CareerCup
2024-10-16 20:44:28
一种是Brute force，O(nlogn)
另一种是找规律O(n)，见http://hawstein.com/posts/20.4.html
当某一位的数字小于2时，那么该位出现2的次数为：更高位数字x当前位数当某一位的数字大于2时，那么该位出现2的次数为：(更高位数字+1)x当前位数当某一位的数字等于2时，那么该位出现2的次数为：更高位数字x当前位数+低位数字+1package Hard; /**
* Write a method to count the number of 2s between 0 and n. 译文： 写一个函数，计算0到n之间2的个数。
*
*/
public class S18_4 { // O(n)
public static int count2s(int n){
int count = 0;
int factor = 1;
int low = 0, cur = 0, high = 0; while(n/factor != 0){
low = n - (n/factor) * factor; // 低位
cur = (n/factor) % 10; // 当前位
high = n / (factor*10); // 高位 if(cur < 2){
count += high * factor;
}else if(cur > 2){
count += (high+1) * factor;
}else{
count += high*factor + low + 1;
} factor *= 10;
} return count;
} //============================================= public static int numberOf2s(int n) {
int count = 0;
while (n > 0) {
if (n % 10 == 2) {
count++;
}
n = n / 10;
}
return count;
} // Brute force way O(nlogn)
public static int numberOf2sInRange(int n) {
int count = 0;
for (int i = 2; i <= n; i++) { // Might as well start at 2
count += numberOf2s(i);
}
return count;
} public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
int b = numberOf2sInRange(i);
int v = numberOf2sInRange(i);
System.out.println("Between 0 and " + i + ": " + v + ", " + b);
}
} }
最新文章
- pip install 报错原因
- Python 多线程 Condition 的使用
- [CareerCup] 13.6 Virtual Destructor 虚析构函数
- Face The Right Way---hdu3276（开关问题）
- Flink单机版安装与wordCount
- scp 传文件
- JavaScript中交换两个变量的值得三种做法（代码实现）
- Lintcode--006（交叉字符串）
- Jekins安装
- Nginx安装手冊以及图片server部署
- 读书有感——《从毕业生到程序员使用C#开发商业软件》
- JAVA中的常量定义在class中还是interface中比较合理？
- 分析MapReduce执行过程+统计单词数例子
- Jmeter-----【mac电脑】配置web浏览器的代理抓取请求
- Lua table遍历
- Python开发——8.模块
- [angularjs] angularjs系列笔记（五）Service
- DNA Evolution CodeForces - 828E（树状数组）
- Ansible 的安装
- 问题1——之Linux虚拟机ip地址消失