Sqrt(x)

Method 1:
Binary Search

Code:

public class Solution {
    public int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        
        long low = 1;
        long high = x/2+1;
        
        while (low <= high){
            long mid = (low+high)/2;
            if (mid * mid == x) return (int) mid;
            else if (mid * mid < x){
                low = mid + 1;
            }else{
                high = mid -1;
            }
        }
    
        return (int)high;
        
    }
}

Another Method:

Newton method.

[LeetCode Java Solution] – Two Pointers / Math – Add Binary

Problem:

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

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

Method:

1. How to add binary number?

From the right to left. If two digits add up to 1 or 0, just put it as 1 or 0. If the two digits add up to 2, make the digit 0, and carry 1. If the two digits add up to 3, make the digit 1, and carry 1.

2. Please pay attention to the while condition.

3. Don’t forget to check carry at last.

Code:

public class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1 ;
        int j = b.length() - 1 ;
        int c = 0;//
        String s = "";
        
        while (i >= 0 || j >= 0){
            int digit = 0;
            if (i >= 0){
                digit += a.charAt(i) - '0';
                i--;
            }
            if (j >= 0){
                digit += b.charAt(j) - '0';
                j--;
            }
            if (c != 0){
                digit += c;
            }
            
            if (digit == 0){
                s = "0" + s;
                c = 0;
            }else if (digit == 1 ){
                s = 1 + s;
                c = 0;
            }else if (digit == 2){
                s = "0" + s;
                c = 1;
            }else if (digit == 3){
                s = "1" + s;
                c = 1;
            }
        }
        
        if (c != 0){
            s = "1" + s;
        }
        
        return s;
    }
}

Method 2:

We could also use the StringBuilder to store the result. The related methods are the following:

1.

StringBuilder

append(char c) Appends the string representation of the char argument to this sequence.

2.

StringBuilder

insert(int offset, char c) Inserts the string representation of the char argument into this sequence.

3.

StringBuilder

reverse() Causes this character sequence to be replaced by the reverse of the sequence.

[LeetCode Java Solution] – Math/String – Roman to Integer

Problem:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Method:

1. This problem has to use HashMap, since we need to quickly look up what does each character mean.

2. Thoughts: if the current char has greater or equal value than the next char, add it; else, minus it.

Code:

public class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
        dict.put('I',1);
        dict.put('V',5);
        dict.put('X',10);
        dict.put('L',50);
        dict.put('C',100);
        dict.put('D',500);
        dict.put('M',1000);
        
        int res = 0;
        
        int i = 0;
        
        for (i = 0; i < s.length()-1; i++){
            if (dict.get(s.charAt(i)) >= dict.get(s.charAt(i+1))){
                res += dict.get(s.charAt(i));
            }else{
                res -= dict.get(s.charAt(i));
            }
        }
        
       res += dict.get(s.charAt(i));
       return res;
        
    }
}

[LeetCode] – Math/String – Integer to Roman

Problem:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Related Knowledge:

Roman Numbers:

I (1)

V (5)

X (10)

L (50)

C (100)

D (500)

M (1000)

Method:

The tricky is how to prepare the array. Consider there are totally 13 characters in roman number.

String[] str = {“M”,”CM”,”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”};
int[] digit = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

Code:

public class Solution {
    public String intToRoman(int num) {
        String[] str = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] n = {1000,900,500,400,100,90,50,40,10,9,5,4,1 };
        StringBuilder s = new StringBuilder();
        
        for (int i = 0; i < str.length; i++){
            int repeat = num/n[i];
            
            for (; repeat >0; repeat--){
                s.append(str[i]);
            }
            num = num % n[i];
        }
        
        return new String(s);
    }
}

Method 2:

Get all digits into an ArrayList (Only 4 digits, since all < 3999). And then get one digit, append several strings.

1-3: use ‘one’

4: one + five

5: five

6-8: five +one

9: one + ten

The above rules apply for all 4 digits.

Code for method 2:

public class Solution {
    public String intToRoman(int num) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int digit = 1000;
        while (digit > 0){
            res.add(num/digit);
            num = num % digit;
            digit = digit / 10;
        }
        StringBuilder s = new StringBuilder();
        
        s.append(convert(res.get(0),"M","",""));
        s.append(convert(res.get(1),"C","D","M"));
        s.append(convert(res.get(2),"X","L","C"));
        s.append(convert(res.get(3),"I","V","X"));
        
        return s.toString();
    }
    
    public String convert(int digit, String one, String five, String ten){
        switch (digit){
            case 0: break;
            case 1: return one;
            case 2: return one.concat(one);
            case 3: return one.concat(one).concat(one);
            case 4: return one.concat(five);
            case 5: return five;
            case 6: return five.concat(one);
            case 7: return five.concat(one).concat(one);
            case 8: return five.concat(one).concat(one).concat(one);
            case 9: return one.concat(ten);
        }
        return "";
    }
}

[LeetCode] – LinkedList/Math – Add Two Numbers

Problems:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Methods:

Add from the front to the end.

Details:

• While condition better to be || instead of &&
• Last step is to check for flag!!!

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode c = dummy;
        int flag = 0;
        int digit = 0;
        while (c1 != null || c2 != null){
            if (c1 != null){
                digit += c1.val;
                c1 = c1.next;
            }
            if (c2 != null){
                digit += c2.val;
                c2 = c2.next;
            }
            if (flag != 0){
                digit += flag;
                flag = 0;
            }
            
            if (digit < 10){
                ListNode nNode = new ListNode(digit);
                c.next = nNode;
                c = c.next;
            }else{
                ListNode nNode = new ListNode(digit-10);
                c.next = nNode;
                c = c.next;
                flag = 1;
            }
            digit = 0;
        }
        if (flag == 1){
            ListNode nNode = new ListNode(1);
            c.next = nNode;
        }
        return dummy.next;
    }
}

[LeetCode] – Binary Search / Math – Pow(x, n)

Problem:

Implement pow(x, n).

Method 1: 

Divide and Conquer. (Dividing n by 2)

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (x == 0.0) return 0.0;
        
        if (n < 0){
            n = -n;
            x = 1/x;
        }
        
        double temp = myPow(x, n/2);
        
        return n%2==0 ? temp*temp: temp*temp*x; 
    }
}

Method 2:

Shifting n to the right.

Code:

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if (x == 0.0) return 0.0;
        if (n < 0){
            n = -n;
            x = 1/x;
        }
        double res = 1.0;
        while (n > 0){
            if (n%2 == 1){
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

[LeetCode] – Math – Valid Number

Problem:

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Method 1:

Using regular expression is the simplest way to approach this problem.

Method 2:

Use direct method.

Rules:

1. If ‘e’ , there should not be an e before it. there have to be any digit after it.

2. If ‘.’, there should not be an . before it. There should not be an e before it.

3. If ‘+-‘, it must be the first one , or must after an e

Flags:

1. num: is it  numeric up to this point?

2. exp: is there ‘e’ before?

3. . : is there ‘.’ before?

Code 

总体思路， 边走边查，记录当前之前的字符串是否符合规定，一旦不符合，马上退出。

public class Solution {
    public boolean isNumber(String s) {
        // corner case
        if (s == null) return false;
        
        // remove white spaces
        String sCut = s.trim();
        
        int len = sCut.length();
        
        boolean num = false; // is it numeric up to this point?
        boolean exp = false; // is there any 'e' before?
        boolean dot = false; // is there any '.' before?
        
        for (int i = 0; i < len; i ++){
            char c = sCut.charAt(i);
            
            if (c == 'e'){
                // no e before, there should be digit before, and also there should be digit after it.
                if (exp || !num) return false;
                num = false;
                exp = true;
            }else if ( Character.isDigit(c)){
                num = true;
            }else if (c == '.'){
                // there should be no '.' before. there should be no e before. 
                if ( dot || exp) return false;
                dot = true;
            }else if (c == '+' || c == '-') {
                if ( i == 0 || sCut.charAt(i-1) == 'e') continue;
                else return false;
            }else{
                return false;
            }
        }
        
        return num;
    }
}

[LeetCode] – String / Math – String to Integer (atoi)

Problem:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Preparation of knowledge:

• atoi: ASCII to Integer
• Basic Idea: str.charAt(i) – ‘0’

Method 1:

1. Consider corner cases:

• Remove white spaces in the beginning: str = str.trim();
• Check if str == null or str.length== 0 (Be careful that these two are different!!!!)
• Check if there is ‘-‘ or ‘+’ sign in the very beginning
• Check if the final result exceed the integer range.

2. We could use a double variable to store the final result and check at the very end to see if it falls into the integer range or not.

Code for method 1: 

// 
public class Solution {
    public int myAtoi(String str) {
        
        
        // remove all empty space at teh beginning
        str = str.trim(); // This method returns a copy of the string, with leading and trailing whitespace omitted.
        if (str == null || str.length() == 0 ) return 0;
        // check the '-' or '+' sign
        boolean isneg = false;
        int i = 0;
        if (str.charAt(0) == '+' || str.charAt(0) == '-'){
            i++;
            if (str.charAt(0) == '-') isneg = true;
        }
        // use double to store result;
        
        double res = 0;
        
        for (; i < str.length(); i++){
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                int digit = (int)(str.charAt(i) - '0');
                res = 10*res + digit;
            }else{
                break;
            }
        }
        if (isneg) res = -res;
        
        if (res > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }else if (res < Integer.MIN_VALUE){
            return Integer.MIN_VALUE;
        }else{
            return (int)res;
        }
    }
}

Method 2:

Supposing that we are not able to use a double variable (final result is a long type), then how do we check if it the result exceeds the integer range?

Add a clause in the beginning of for loop to check :

• If ‘+’: result * 10 + digit > max
• If ‘-‘ : -(result * 10 + digit) < min

However, be very careful about the edge!!!

Code for method 2:

// 
public class Solution {
    public int myAtoi(String str) {
        
        
        // remove all empty space at teh beginning
        str = str.trim(); // This method returns a copy of the string, with leading and trailing whitespace omitted.
        if (str == null || str.length() == 0 ) return 0;
        // check the '-' or '+' sign
        boolean isneg = false;
        int i = 0;
        if (str.charAt(0) == '+' || str.charAt(0) == '-'){
            i++;
            if (str.charAt(0) == '-') isneg = true;
        }
        // use double to store result;
        
       int  res = 0;
        
        for (; i < str.length(); i++){
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                int digit = (int)(str.charAt(i) - '0');
            
                if (!isneg && res > (Integer.MAX_VALUE - digit)/10){
                    // be careful of how it is written, we can't try the other way
                   return Integer.MAX_VALUE;
              
                } 
                if (isneg && res > -((Integer.MIN_VALUE + digit)/10)  )
                    // be careful about the edge
                    return Integer.MIN_VALUE;
                }
                res = 10*res + digit;
            }else{
                break;
            }
        }
        
        return isneg == true? -res : res;
        
    }
}