Sqrt(x)

描述

Implement int sqrt(int x).

Compute and return the square root of x.

分析

二分查找

代码

  1. // Plus One
  2. // 时间复杂度O(n),空间复杂度O(1)
  3. public class Solution {
  4. public int[] plusOne(int[] digits) {
  5. return add(digits, 1);
  6. }
  7. private static int[] add(int[] digits, int digit) {
  8. int c = digit; // carry, 进位
  9. for (int i = digits.length - 1; i >= 0; --i) {
  10. digits[i] += c;
  11. c = digits[i] / 10;
  12. digits[i] %= 10;
  13. }
  14. if (c > 0) { // assert (c == 1)
  15. int[] tmp = new int[digits.length + 1];
  16. System.arraycopy(digits, 0, tmp, 1, digits.length);
  17. tmp[0] = c;
  18. return tmp;
  19. } else {
  20. return digits;
  21. }
  22. }
  23. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/divide-and-conquer/sqrt.html