Carry bit

Multiply Strings

• 这题搞懂了才算真正理解carrry bit！！！多练

• 当前取A[i] 和B[j]相乘，那么结果只有可能影响第i+j和i+j+1位

• 现在把i+j设成高位，high = i +j, i+j+1设成低位，low = i+j+1

• product = nnum1[i] * num2[j]

• tmp = product + res[i+j+1];

• res[i+j+1] = tmp % 10;

• res[i+j] = tmp/10 + res[i+j];

• 最后要找到第一个non-zero number也有点小技巧if(sb.length() == 0 && i == 0)

• 这题还要注意"0" * "0"的 corner case

  public String multiply(String num1, String num2) {
          int m = num1.length(), n = num2.length();
          int[] res = new int[m + n];
          for (int i = m - 1; i>= 0; i--) {
              for (int j = n - 1; j >= 0; j--) {
                  int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                  int tmp = product + res[i+j+1];
                  res[i+j+1] = tmp % 10;
                  res[i+j] = tmp/10 + res[i+j];
              }
          }
          boolean seen = false;
          StringBuilder sb = new StringBuilder();
          for (int num : res) {
              if (num == 0 && !seen) continue;
              sb.append(num);
              seen = true;
          }
          return sb.length() == 0 ? "0" : sb.toString();
  }

Add Binary

Plus One

• 一开始想到的就是最标准的分情况讨论

• 首先是末位< 9的话加完就直接返回

• 然后走一个while loop，只要carry == 0或者i < 0就停止

• 最后判断carry bit == 1的情况

• 写出来代码巨长巨丑，只打败2%

public int[] plusOne(int[] digits) {
        int carry = 0;
        int n = digits.length;
        int i = n - 1;
        int sum = digits[i] + 1;
        if(sum < 10){
            digits[i] = sum;
            return digits;
        }
        digits[i] = sum % 10;
        carry = sum /10;
        i--;
        while(i >= 0 && carry == 1){
            int add = carry + digits[i];
            digits[i] = add % 10;
            carry = add /10;
            i--;
        }
        if(carry == 0){
            return digits;
        }else{
            int[] res = new int[n+1];
            res[0] = 1;

            return res;
        }
    }

• 不用说肯定有优化的方法，于是看到了这个巧妙的方法！

• 直接走一个loop，每次判断当前值digits[i]< 9, 直接digits[i] ++后 return digits

• 如果digits[i]>= 9,那么直接digits[i] = 0,妙处就在这里！仔细想想，如果能走到非最低位，肯定说明前一位有进位，所以其实这种情况下就并不是只有最低位plus one,而是可以想象成每一位都plus one!

• 最后如果是自然跳出了for-loop并且还没return的话只有可能是"999"的情况了，都不需要check if else, 直接看一个新数组int[] res = new int[n+1], res[0] = 1, then return res

public int[] plusOne(int[] digits) {
        int n = digits.length - 1;
        for(int i = n; i >= 0; i--) {
            if(digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] res = new int[n + 2];
        res[0] = 1;
        return res;
    }