简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Implement
int sqrt(int x).
Compute and return the square root of x.
» Solve this problem刚开始木有理解题意，以为要精确到小数多少位，然后用double输出，但是看到是int的返回值，瞬间简单了不少，只要算出最接近square root的整数就可以了。但是有细节要注意，比如输入的x特别大的时候，假如已经超过了int的最大值，这个时候我们怎么处理？以及如何判断二分查找结束的条件，都是很关键的。
因为整数的乘法可能导致溢出，而溢出的监测和整数加法直接判断是否小于0是不同的，因为整数的乘法有可能多次溢出，当奇书次溢出时是负数，当偶数次溢出时时整数。比如
2147395599 如果用是否小于0来终止二分的话，它的平方根会返回617921965，而不是46339。
所以，二分的终点确定比较重要，在运算中想通过是否小于0来判断溢出，是不可靠的，最好的办法就是在二分之前，要求end小于sqrt(INT_MAX)。sqrt(INT_MAX)是个常量，所以不算cheat。
更快的方法是牛顿迭代，不过这个太偏数学了。详情见http://www.2cto.com/kf/201206/137256.html
牛顿迭代法。顿时觉得神人总是无处不在，那个找出那个最接近sqrt数的那位大哥太神奇了，自己都不明觉厉。哈哈～～
No comments:
Post a Comment