CONY的世界

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

這題我的寫法太複雜了，因為一直想到要用插入的方式做，所以會想到要move 所有後面的數值，所以就想說與其這樣不如new array 來做

不過這題如果從後面做起，就不用這麼複雜了

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] array = new int[m+n];
        int index = 0, index1 = 0, index2 = 0;
        while(index < m+n) {
            if(index1 > m-1)
                array[index] = nums2[index2++];
            else if(index2 > n-1)
                array[index] = nums1[index1++];
            else{
                if(nums1[index1] >= nums2[index2])    
                    array[index] = nums2[index2++];
                else
                    array[index] = nums1[index1++];
            }
            index++;
        }
        System.arraycopy(array,0,nums1,0,array.length);
//        for(int i=0; i < array.length;i++)
  //          nums1[i] = array[i];  //Notice:nums1 = array   would not copy whole array, Doesn't work !!!
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        while(n>0)
            nums1[n+m-1] = (m == 0 || nums2[n-1] > nums1[m-1])?nums2[--n]:nums1[--m];
    }
}


67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

這題一開始又想到比較難的方向，想用logic gate 概念來解，也是可以

class Solution {
    public String addBinary(String a, String b) {
        boolean carry = false;
        int a_bits = a.length()-1, b_bits = b.length()-1;
        StringBuilder result = new StringBuilder();
        while(a_bits >= 0 || b_bits >= 0 || carry){
            boolean a1 = (a_bits >=0 && a.charAt(a_bits) == '1')?true:false;
            boolean a2 = (b_bits >=0 && b.charAt(b_bits) == '1')?true:false;
            result.append(((a1^a2^carry)?"1":"0"));
            carry = (a1&&a2)||((a1||a2)&&carry);
            a_bits--;   b_bits--;
        }
        return result.reverse().toString();
    }
}

也可以用 /2 方式來做

class Solution {
    public String addBinary(String a, String b) {
        int carry = 0;
        int a_bits = a.length()-1, b_bits = b.length()-1;
        StringBuilder result = new StringBuilder();
        while(a_bits >= 0 || b_bits >= 0 || carry > 0){
            int sum = carry;
            if(a_bits >=0)  sum += a.charAt(a_bits--) - '0';                                
            if(b_bits >=0)  sum += b.charAt(b_bits--) - '0';
            result.append(sum%2);    
            carry = sum/2;
        }
        return result.reverse().toString();
    }
}