11.10打卡

1. 加1（66）

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字

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;
    }
}

2. 二进制求和（67）

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和

class Solution {
    public String addBinary(String a, String b) {
         StringBuilder res = new StringBuilder();
        int alen= a.length()-1,blen= b.length()-1;
        if(alen<blen){
            return addBinary(b,a);
        }
        int cnt = 0;
        while (alen>=0){
            int a1 =a.charAt(alen)-'0';
            int b1=(blen<0)?0: b.charAt(blen)-'0';
            int sum = a1+b1+cnt;
            res.append(sum &1);
            cnt = sum>>1;
            alen--;
            blen--;
        }
         if((cnt&1)==1)
            res.append(cnt);
        return res.reverse().toString();
    }
}

3. 文本左右对齐（68）

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

思想：分类讨论

• 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格；
• 当前行不是最后一行，且只有一个单词：该单词左对齐，在行末填充空格；
• 当前行不是最后一行，且不只一个单词：

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
   List<String> res = new ArrayList<>();
        int right =0,n=words.length;
        while (true){
            int left = right; //当前行的第一个单词在word的位置
            int sumLen =0; //统计改行单词长度之和
            //循环确定当前行可以放置多少单词，单词之间至少有一个空格
            while (right<n && sumLen+words[right].length()+right-left<=maxWidth){
                sumLen+=words[right++].length();
            }
            //当前行是最后一行，单词左对齐，且单词之间应只有一个空格，在行末填充空格
            if(right==n){
                StringBuffer sb = join(words,left,n," ");
                sb.append(blank(maxWidth-sb.length()));
                res.add(sb.toString());
                return res;
            }
            int numWord = right-left;
            int numSpace = maxWidth-sumLen;
            //如果当前行只有一个单词，左对齐
            if(numWord==1){
                StringBuffer sb = new StringBuffer(words[left]);
                sb.append(blank(numSpace));
                res.add(sb.toString());
               continue;
            }
            //当前行不止一个单词
            int avgspace = numSpace/(numWord-1);
            int extraspace = numSpace%(numWord-1);
            StringBuffer sb= new StringBuffer();
            sb.append(join(words,left,left+extraspace+1,blank(avgspace+1)));
            sb.append(blank(avgspace));
            sb.append(join(words,left+extraspace+1,right,blank(avgspace)));
            res.add(sb.toString());
        }
    }

    private String blank(int i) {
        //返回长度为i 的空格字符串
        StringBuffer sb = new StringBuffer();
        for (int j = 0; j < i; j++) {
            sb.append(" ");
        }
        return sb.toString();
    }

    private StringBuffer join(String[] words, int left, int right, String space) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left+1; i < right; i++) {
            sb.append(space);
            sb.append(words[i]);
        }
        return sb;
    }
    }

4. x的平方根（69）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 

思想：二分查找

class Solution {
    public int mySqrt(int x) {
     //二分查找
        int l =0, r=x,ans=-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if((long)mid *mid <=x){
                ans=mid;
                l=mid+1;
            }else {
                r=mid-1;
            }
        }
        return ans;
    }
}

5. 爬楼梯（70）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。

class Solution {
    public int climbStairs(int n) {
    int f0=1;int f1 =1;
      int k=2;
      while (k<=n){
          f0 =f0+f1;
          f1=f0-f1;
          k++;
      }
      return f0;
    }
}