LeetCode 66-70

66. Plus One

分析：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

从尾遍历数组，先让最个位数加1，如果加完之后不是10，那么直接返回数组。
如果是10，那么要进位。让下一位继续加1，不断重复。
如果最高位最后加完还是10，那么还要进一位。可以新建一个数组，数组大小多一位，然后最高位是1，其余位全是0。

Java：

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) {
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

67. Add Binary

分析：

给你两个二进制字符串，返回它们的和（用二进制表示）。

模拟加法，从最低位一直往最高位加，如果高位没有数了，则加0。每加一次之后存到StringBuilder中，最后反转一下字符串就是最终答案。

Java：

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; i++) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            res.append((char) (carry % 2 + '0'));
            carry /= 2;
        }
        if (carry > 0) {
            res.append("1");
        }
        res.reverse();
        return res.toString();
    }
}

68. Text Justification

分析：

以后再做。

Java：

69. Sqrt(x)

分析：

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
使用二分查找。lo先设为0，hi先设为x，

Java：

class Solution {
    public int mySqrt(int x) {
        int lo = 0, hi = x, res = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if ((long) mid * mid <= x) {
                res = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return res;
    }
}

70. Climbing Stairs

分析：

简单动态规划题。

Java：

class Solution {
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n - 1];
    }
}