LeetCode #7

What I’ve Learned

First, We can append length of array by digits = new int[digits.length + 1]; Second, To return in String and for appending, we can use StringBuilder.

Disclaimer

My LeetCode is free plan. I am posting just the free algorithms for now on. Also, I am using JAVA to code.

1. Two Sum Review

My Solution

I thought I could solve this problem with two pointers. But the key of using two pointers is Arrays.sort(nums);. When sorted, it’s harder to find the key in correct order. That is my problem so, the best answer will be finding using just hashcode. When saving keys and values reversed to find, the problem happens with hash.get(). It searches the value so if there is same value, it retrieves the same. For example, as input of {3,3} and target of 6, output should be {0,1} but actually it gives {1,1} back.

class Solution {
    public int[] twoSum(int[] nums, int target) {
    	HashMap<Integer, Integer> hash = new HashMap<>();
    	for(int i =0; i<nums.length; i++) {
    		hash.put(nums[i], i);
    	}
        int r = 0;
        int l = nums.length -1;
        Arrays.sort(nums);
        

        while(r != l){
            if(nums[r] + nums[l] == target){
                break;
            } else if(nums[r] + nums[l] > target){
                l--;
            } else{
                r++;
            }
        }
        return new int[]{r,l};
    }
}

67. Add Binary

Solution

I’ve never heard of StringBuilder. StringBuilder in Java is literally for building string. String is static variable but, String builder is mutable. This solution is not simple. I’ve thought of ‘XOR’ to solve this but the problem was handling the carry. This solution handles carry with sum. With sb.append(sum % 2), answer is added in the StringBuilder. Final sb.reverse().toString() is for reversing.

class Solution {
    public String addBinary(String a, String b) {
    	StringBuilder sb = new StringBuilder();
    	int i = a.length() - 1;
    	int j = b.length() - 1;    	
    	int carry =0;
    	
    	while(i >= 0 || j >= 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;
    		
    		i--;
    		j--;
    	}
    	if(carry != 0) sb.append(carry);
    	return sb.reverse().toString();
    }
}

69. Sqrt(x)

My Solution

I’ve thought of using log but, log doesn’t work. Actually, my approach was totally wrong.

class Solution {
    public int sqrt(int x) {
    	int k = (int) baseLog(x, 2);
    	System.out.println(k);
    return k;	
    }
    
    static double baseLog(double x, double base) {
    	return Math.log10(x) / Math.log10(base);
    }
}

Solution

For my surprise, it was binary search. Checking the medium and cutting in half. And reducing one from last and adding one from start. I need to review it again.

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int first = 1, last = x;
        while (first <= last) {
            int mid = first + (last - first) / 2;
            if (mid == x / mid) {
                return mid;
            } else if (mid > x / mid) {
                last = mid - 1;
            } else {
                first = mid + 1;
            }
        }
        return last;
    }
}