LeetCode -- Sqrt(x) 代码分析
不少人跟我提过LeetCode 但是知道今天才尝试着在上面交了一个题,连交三遍,终于过了,激动ing....
链接地址:http://oj.leetcode.com/problems/sqrtx/
实现代码:
#include <iostream>#include <fstream>using namespace std;class Solution{public: int sqrt(int x) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if (x < 0) return -1; if (x == 0 || x == 1) return x; long long int start = 1;//不能用int 至于为啥,请看下面这位大神的解释 long long int end = x; long long mid; /* You should use "long long". Sometimes, "long" == "long int" == "int" or "short" == "short int" == "int". It depends on the system. */ while (start <= end) { mid = start + (end - start)/2; if (mid * mid <= x && (mid+1)*(mid+1) > x) return mid; else if (mid * mid < x) start = mid + 1; else end = mid - 1; } return 0; }};// 测试代码int main(){ freopen("input.txt","r",stdin); int test; Solution s; while (cin >> test) { cout << s.sqrt(test) << endl; } return 0;}//测试数据://-2 -1 0 1 2 3 4 5 6 7 8 9 10 -2147483647 2147483647