每日5题Day14 - LeetCode 66 - 70

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：66. 加一 - 力扣（LeetCode）

class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 1;
        List res = new ArrayList<>();
        //反着来，把低位的元素先放进list中
        for(int i = digits.length - 1; i > -1; i--){
            res.add((digits[i] + carry) % 10);
            carry = (digits[i] + carry) / 10;
        }
        //最高位可能要进位
        if(carry == 1){
            res.add(carry);
        }
        //因为刚才反了，所以最后要反着放回来
        int[] ress = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ress[res.size() - 1 - i] = res.get(i);
        }
        return ress;
    }
}

---

第二题：67. 二进制求和 - 力扣（LeetCode）

class Solution {
    public String addBinary(String a, String b) {
        //和上一题相同，反着来
        if (a.length() == 0 && b.length() == 0) {
            return "";
        }
        if (a.length() == 0 || b.length() == 0) {
            return a.length() == 0 ? b : a;
        }
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}

---

第三题：68. 文本左右对齐 - 力扣（LeetCode）

写不来，就用宫水三叶的解法吧

class Solution {
    public List fullJustify(String[] words, int maxWidth) {
        List ans = new ArrayList<>();
        int n = words.length;
        List list = new ArrayList<>();
        for (int i = 0; i < n; ) {
            // list 装载当前行的所有 word
            list.clear();
            list.add(words[i]);
            int cur = words[i++].length();
            while (i < n && cur + 1 + words[i].length() <= maxWidth) {
                cur += 1 + words[i].length();
                list.add(words[i++]);
            }
 
            // 当前行为最后一行，特殊处理为左对齐
            if (i == n) {
                StringBuilder sb = new StringBuilder(list.get(0));
                for (int k = 1; k < list.size(); k++) {
                    sb.append(" ").append(list.get(k));
                }
                while (sb.length() < maxWidth) sb.append(" ");
                ans.add(sb.toString());
                break;
            }
 
            // 如果当前行只有一个 word，特殊处理为左对齐
            int cnt = list.size();
            if (cnt == 1) {
                String str = list.get(0);
                while (str.length() != maxWidth) str += " ";
                ans.add(str);
                continue;
            }
 
            /**
            * 其余为一般情况
            * wordWidth : 当前行单词总长度;
            * spaceWidth : 当前行空格总长度;
            * spaceItem : 往下取整后的单位空格长度
            */
            int wordWidth = cur - (cnt - 1);
            int spaceWidth = maxWidth - wordWidth;
            int spaceItemWidth = spaceWidth / (cnt - 1);
            String spaceItem = "";
            for (int k = 0; k < spaceItemWidth; k++) spaceItem += " ";
            StringBuilder sb = new StringBuilder();
            for (int k = 0, sum = 0; k < cnt; k++) {
                String item = list.get(k);
                sb.append(item);
                if (k == cnt - 1) break;
                sb.append(spaceItem);
                sum += spaceItemWidth;
                // 剩余的间隙数量（可填入空格的次数）
                int remain = cnt - k - 1 - 1;
                // 剩余间隙数量 * 最小单位空格长度 + 当前空格长度 < 单词总长度，则在当前间隙多补充一个空格
                if (remain * spaceItemWidth + sum < spaceWidth) {
                    sb.append(" ");
                    sum++;
                }
            }
            ans.add(sb.toString());
        }
        return ans;
    }
}

---

第四题：69. x 的平方根 - 力扣（LeetCode）

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int left = 1;
        int right = x;
        int ans = 0;
        //二分法
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

---

 第五题：70. 爬楼梯 - 力扣（LeetCode）

class Solution {
    public int climbStairs(int n) {
        //两个方向换过来
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

---