- 浏览: 75816 次
文章分类
最新评论
-
wodentt:
....为什么楼主都英文的博客
用java解决百度之星移动火柴的问题 part 1 -
wensonzhou86:
思路明确,代码清晰,通俗易懂
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
carydeepbreathing:
代码比较干净
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
meiowei:
yangguo 写道i don't think it is a ...
用java解决百度之星移动火柴的问题 part 2 -
yangguo:
i don't think it is a good way ...
用java解决百度之星移动火柴的问题 part 2
The entire class is as follows:
There are possible places where we can speed up further, but hardly worth it.
java 代码
- /**
- * GOOGLE GLAT question #20:
- * Consider a function which, for a given whole number n, returns the number
- * of ones required when writing out all numbers between 0 and n. For example,
- * f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
- */
- public class CountOnesUseIteration
- {
- // Implementation notes:
- // There are various places we can optimize the code, however I don't
- // feel we need to do so since the implementation is fast enough.
- private static final int ITERATION_LIMIT = 10000;
- // This is used to check whether any given func value is between the
- // function values of 10^n and 2*10^n so that we know the corresponding
- // number starts with 1 or not, this fact will determine which formula
- // to use for reverse iteration.
- long[] x1 = new long[9];
- long[] x2 = new long[9];
- long[] y1 = new long[9];
- long[] y2 = new long[9];
- public CountOnesUseIteration()
- {
- for (int i=1; i<10; i++)
- {
- x1[i-1] = power(10, i);
- x2[i-1] = 2 * x1[i-1] - 1;
- y1[i-1] = numOfOnes(x1[i-1]);
- y2[i-1] = numOfOnes(x2[i-1]);
- }
- }
- public void countDigitOne()
- {
- long begin = System.currentTimeMillis();
- long loop = 10000000000L;
- int iterationTimes = 1;
- while (loop > 0 && iterationTimes < ITERATION_LIMIT)
- {
- long func = numOfOnes(loop);
- if (func == loop)
- {
- System.out.println("-----> found a fixed point: x=" + loop);
- // now skip this one and keep going for the next one.
- loop--;
- }
- else
- {
- if (func < loop) // we force this to go to the left.
- {
- loop = func;
- }
- else // func > loop
- {
- func = inverseFunc(loop);
- if (func < loop && numOfOnes(func) >= loop)
- {
- loop = func;
- }
- else
- {
- loop --; // if we can't find one, just decrement it.
- }
- }
- }
- iterationTimes++;
- }
- System.out.println("It takes " + (System.currentTimeMillis() - begin) + " milli");
- System.out.println("It takes " + iterationTimes + " iterations");
- }
- // function value
- private long numOfOnes(long x)
- {
- // recursion stops
- if (x <= 0) return 0;
- if (x == 1) return 1;
- int powerk = 0;
- long tenPowers = 1;
- long leadingDigit = x;
- while (leadingDigit >= 10)
- {
- leadingDigit /= 10;
- powerk++;
- tenPowers *= 10;
- }
- long reminder = x - leadingDigit * tenPowers;
- if (leadingDigit == 1)
- {
- return powerk * tenPowers / 10 + 1 + reminder + numOfOnes(reminder);
- }
- else
- {
- return leadingDigit * powerk * tenPowers / 10 + tenPowers + numOfOnes(reminder);
- }
- }
- // kind of inverse function value
- public long inverseFunc(long y)
- {
- // we are moving backward to find a x such that x < y <= f(x) and keep x as small as possible.
- // recursion default.
- if (y <= 0) return 0;
- if (y == 1) return 1;
- if (y == 2) return 10;
- // check whether y is in 1's range
- int m = isInOneRange(y);
- if (m != -1)
- {
- long tmp = y - (m + 1) * power(10, m) - 1;
- long inc = findRoot(tmp);
- return power(10, m + 1) + inc;
- }
- else
- {
- int k = numOfDigits(y) - 1;
- long tmp = y - power(10, k);
- long ak = tmp / (k * power(10, k - 1));
- if (ak > 9) ak = 9; // leave the rest to the recursion
- long remainder = tmp - ak * k * power(10, k - 1);
- long xRemainder = inverseFunc(remainder);
- return ak * power(10, k) + xRemainder;
- }
- }
- private int isInOneRange(long y)
- {
- // This is to check whether the func value is between the function values of 10^n and 2*10^n.
- // this can be done faster since it's sorted, but again I am lazy
- int k=-1;
- for (int i=0; i<9; i++)
- {
- if (y <= y2[i])
- {
- k = i;
- break; // first smaller, break out
- }
- }
- if (k==-1) return -1;
- if (y >= y1[k]) return k;
- else return -1;
- }
- private static int numOfDigits(long x)
- {
- int i = 0;
- while (x > 0)
- {
- x /= 10;
- i++;
- }
- return i;
- }
- private static long power(long base, int power)
- {
- long ret = 1;
- for (int i=1; i<=power; i++) ret *= base;
- return ret;
- }
- public long findRoot(long y)
- {
- // find a root for x + f(x) = y, where f is the number of one's function in the above.
- // we need a x such that x + f(x)>=y, the least x.
- // Note that x + f(x) is a mononically increasing function.
- long x0 = 0;
- long x1 = y;
- long x;
- while (x1 - x0 > 1)
- {
- x = x0 + (x1 - x0) / 2;
- long func = numOfOnes(x) + x;
- if (func == y) return x;
- if (func < y)
- {
- x0 = x;
- }
- else
- {
- x1 = x;
- }
- }
- if (x0 + numOfOnes(x0) == y) return x0;
- else return x1;
- }
- }
There are possible places where we can speed up further, but hardly worth it.
发表评论
-
Revisit 一道应聘智力题的编程求解, Einstein puzzle
2010-03-09 00:36 1361Another brain teaser, titled 一道 ... -
Another Google question - drop glassballs from a building 5
2007-05-13 04:01 1028Here are some results are the t ... -
Another Google question - drop glassballs from a building 4
2007-05-13 03:42 1479The test cases are divided into ... -
Another Google question - drop glassballs from a building 3
2007-05-13 03:33 1033The next step is to find the ac ... -
Another Google question - drop glassballs from a building 2
2007-05-13 03:02 1053Here is the code following the ... -
Another Google question - drop glassballs from a building 1
2007-05-12 04:43 1157Here is the question: 原题: ... -
Given n coins and a pan balance,find the only counterfeit 4
2007-02-27 05:54 1086The Utils class is composed of ... -
Given n coins and a pan balance,find the only counterfeit 3
2007-02-27 05:50 1438In the 1-ball case, if the stat ... -
Given n coins and a pan balance,find the only counterfeit 2
2007-02-27 05:29 1052Now it comes to the Scale class ... -
Given n coins and a pan balance, find the only counterfeit 1
2007-02-27 04:49 1291The problem is: There is one ... -
A Google's Interview Question - GLAT #20 series 3
2007-02-08 02:36 1033The roadmap to compute all fixe ... -
A Google's Interview Question - GLAT #20 series 2
2007-02-08 02:24 1007Now, we can deduct the recursio ... -
A Google's Interview Question - GLAT #20 series 1
2007-02-08 02:22 1103Question: Consider a function ...
相关推荐
shopid shopAllname fivescore scoreTaste scoreEnvironment scoreService avgPrice defaultReviewCount shopname branchName address phoneNo shopGroupId glat glng categoryName level2 level1 ...
idl代码与Matlab 辉光 Global airglOW模型,可以从Fortran 2003编译器中独立且轻松地进行访问。 可选提供脚本语言,包括: Python≥3.6 Matlab的 GNU八度≥4.2 IDL ...glat , glon , Q , Echar , Nb
接收 xyz 格式的点云,然后将其转换为具有纬度向量、经度向量、glat/glon 网格(使用 meshgrid)和 az(高度)矩阵的 MATLAB 样式的网格。 然后将这些保存到指定的输出 .mat 文件中。
它的构建允许任何人检查志愿者为数据库中或任何 GLON、GLAT 位置的任何主题(图像)创建的分类。 对于每个图像,您都可以看到原始志愿者绘图、聚类结果和该地区 SIMBAD 上的对象(这一点还没有完全完成)。 例如...
名人档案(辛弃疾、李清照)(1).docx
._moood UI KitAdobeXD源码下载设计素材UI设计
full_circle_appAdobeXD源码下载设计素材UI设计
Gym_Responsive_Landing_PageAdobeXD源码下载设计素材UI设计
sql,SQL(Structured Query Language,结构化查询语言)是一种标准化的语言,用于在关系数据库管理系统(RDBMS)中存取和操作数据。SQL 使得用户能够访问和操作数据库中的数据,包括数据的查询、插入、更新和删除,以及数据库结构的创建和修改。
一个很烂的项目但是获第二十二届江西省学生信息素养提升实践活动一等奖、第三十八届江西省青少年科技创新大赛二等奖
JAVA文件压缩与解压缩实践(源代码+论文)
Event_Responsive_Landing_PageAdobeXD源码下载设计素材UI设计
这是宁波创客大赛 Timer 项目的Github
汽车价格离群值检测.zip
大家好!这是近期通过前端技术实现的一个“酷炫黑白粒子空间旋转特效”,本资源包含完整的可执行代码(下载文件,解压后可以点击运行)和运行特效展示,该内容已经在博客中记录:https://xiexu.blog.csdn.net/article/details/132677358(预计于2025年发布)。欢迎正在学习前端的朋友下载练手~
JAVAWEB网络相册
codeforce Rudolf and the Another Competition的C语言写法(用了sort)
打印模板乐器五线谱A4打印模板高清待办练字模板PDF下载
物流大数据服务平台HTML模板源码 大数据大屏展示源码 VUE
FANUC 操作手册