[算法]谷歌笔试题：Beautiful Numbers
2024-10-11 11:20:18
题目描述
思路
这道题就是在说，由多个1组成的数是beautiful的，现在想求出r进制中的r，使得给出的数字转换成r进制，得到beautiful的数字，如果有多种方式转换，那么取1的个数最多的那种情况，也就是r最小的情况。
这道题其实就是10进制和r进制的转化，这里就不详述了，但是注意题目中的一点就是给了两种数据集，小数据集的N最大为1000，大数据集的N最大为10^18，大数据集非常棘手。
先看看小数据集的常规思路，就从二进制开始进行循环，每次循环判断一下该进制下进行转换得到的数字是否为beautiful的，见下面第一个代码。这种思路的时间复杂度是NlogN，因为N最大为1000，所以很快。
再看看大数据集，如果我们采用上面那种方式的话，N为10^18，这样带进去差不多是64*10^18的计算，假设计算机1秒执行10^8次计算，这样的耗时也是非常巨大的。
因此对于大数据集的思路是，我们先看一下，10^18的数字，转成二进制，最多的话，也是64个1，所以我们就设开始是64个1，然后递减，计算每次该个数的1能不能由某一进制转换成功。在计算进制的过程中，可以采用二分查找，这样总共的时间复杂度就是logN*logN*logN，相当于64*64*64，还是非常小的。最后因为可能数据溢出，所以用long，用long也可能在计算过程中溢出，所以做了一下处理，这里同样可以采用BigInteger。
代码
小数据集的代码（常规思路）：
package interview.google; import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner; public class BeautifulNumber { public static void main(String[] args) {
Scanner in = new Scanner(
new BufferedReader(new InputStreamReader(System.in)));
int cases = in.nextInt();
for (int i = 1; i <= cases; ++i) {
long n = in.nextLong();
System.out.println("Case #" + i + ": "
+ beautiful(n));
}
} private static long beautiful(long n) {
for (long radix = 2; radix < n; radix++) {
if (isBeautiful(n, radix)) {
return radix;
}
} throw new IllegalStateException("Should not reach here.");
} private static boolean isBeautiful(long n, long radix) {
while (n > 0) {
if (n % radix != 1) {
return false;
}
n /= radix;
}
return true;
}
}
大数据集的代码（同样适用于小数据集）：
package interview.google; import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner; public class BeautifulNumberLarge { public static void main(String[] args) {
Scanner in = new Scanner(
new BufferedReader(new InputStreamReader(System.in)));
int cases = in.nextInt();
for (int i = 1; i <= cases; ++i) {
long n = in.nextLong();
System.out.println("Case #" + i + ": "
+ beautiful(n));
}
} private static long beautiful(long n) {
for (int bits = 64; bits >= 2; bits--) {
long radix = getRadix(n, bits);
if (radix != -1) {
return radix;
}
} throw new IllegalStateException("Should not reach here.");
} /**
* Gets radix so that n is 111...1 (bits 1 in total) in that
* radix.二分查找，最大值需要+1.
*
* @return the radix. -1 if there's no such radix.
*/
private static long getRadix(long n, int bits) {
long minRadix = 2;
long maxRadix = n;
while (minRadix < maxRadix) {
long m = minRadix + (maxRadix - minRadix) / 2;
long t = convert(m, bits);
if (t == n) {
return m;
} else if (t < n) {
minRadix = m + 1;
} else {
maxRadix = m;
}
}
return -1;
} /**
* Returns the value of 111...1 (bits 1 in total) in radix.
*/
private static long convert(long radix, int bits) {
long component = 1;
long sum = 0;
for (int i = 0; i < bits; i++) {
if (Long.MAX_VALUE - sum < component) {
sum = Long.MAX_VALUE;
} else {
sum += component;
} if (Long.MAX_VALUE / component < radix) {
component = Long.MAX_VALUE;
} else {
component *= radix;
}
}
return sum;
}
}
最新文章
- 我用ANDROID STUDIO开发，页面上总包这个警告，很烦！网上说是sdk版本问题，但是我是基于25开发的，最小版本也是19，有没有老司机啊？3克油
- 20161117__Z
- Java 集合系列14之 Map总结(HashMap, Hashtable, TreeMap, WeakHashMap等使用场景)
- python中cPickle的用法
- LeeCode-Invert Binary Tree
- ##DAY3 自定义视图、视图控制器、视图控制器指定视图、loadView、 viewDidLoad、MVC、屏幕旋转、内存警告
- 信息设计工具IDT创建从SAP Business Object到SAP HANA的连接
- 写好你的JavaScript
- 我的Java开发学习之旅------&gt;Base64的编码思想以及Java实现
- SpringBoot-异常问题总结
- PostgreSQL 与 PostGIS
- 前端工程化基础-vue
- 《精通Oracle SQL(第2版)》PDF
- prometheus + grafana安装部署（centos6.8）
- haxe相关的计划安排
- MSI/MSI-X Capability结构 （转）
- 4. 深入 Python 流程控制
- JS基础-数据类型-运算符和表达式-变量和常量
- python(27) 抓取淘宝买家秀
- [Cnbeta]BAT财报对比