8 LeetCode Java: String to Integer (atoi) – Easy

Problem:
Implement atoi to convert a string to an integer.

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.
Thoughts:
The tricky part for this problem is how to handle overflow.
The annoying thing here is the special cases. “010” -> 10 “+-2″ -> 0 ” 010″ -> 10 “-012ab1234” -> -12 “2147483648” -> “2147483647” “-2147483648” -> – 2147483648 Although I would think for some of these special cases we should throw Exceptions instead of returning things.
Solutions:

public class Solution {
    public int myAtoi(String str) {
        str = str.trim();
        int result = 0;
        int flag = 1;
        int start = 0;
        if (str == null || str.length() == 0){
            return 0;
        }
        if (str.charAt(0) == '-'){
            flag = -1;
            start = 1;
        }
        else if (str.charAt(0) == '+'){
            start = 1;
        }
        for (int i = start; i < str.length(); i ++){
            if (str.charAt(i) != '0'){
                start = i;
                break;
            }
        }
        for (int i = start; i < str.length(); i ++){
            char c = str.charAt(i);
            if (c < 48 || c > 57){
                break;
            }
            int digit = c - 48;
            int tmp = result * 10 + digit;
            if (tmp == Integer.MIN_VALUE && i == (str.length() -1) && str.charAt(0) == '-'){
                return Integer.MIN_VALUE;
            }
            else if ((tmp - digit) / 10 != result || (result > 0 && tmp < 0)){
                //overflow
                if (str.charAt(0) == '-'){
                    return Integer.MIN_VALUE;
                }
                else{
                    return Integer.MAX_VALUE;
                }
            }
            else{
                result = tmp;
            }
        }
        return result * flag;
    }
}

7 LeetCode Java: Reverse Integer – Easy

Problem:
Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Things not provided by the problem itself:
If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Thoughts:
The tricky part is how to handle overflow case. How to determine overflow.
There is no one perfect way to determine overflow during integer calculation. It varies depending on what the specific calculation is.

Say int a = 964632435. a * 10 overflows. but the result is 1056389759 still a positive not a negative. So cannot use result < 0 to determine overflow. The formula to calculate next Integer is b = a * 10 + 1. Because is always a valid integer. So could use ( b – 1) / 10 == a to determine overflow. Also remember Java Integer Range is from -2xxxxxx8 to 2xxxxxx7. Not balanced. Condition result != (newresult – digit) / 10 is not safe enough, say if x * 10 + digit = Integer.MAX + 1. It overflows but reverse is still right. But this problem is never facing this special case because if reverse if Integer.MAX + 1 then the original number is not a valid Integer.

Solutions:

public class Solution {
    // -8 ~  7
    public int reverse(int x) {
        if (x == Integer.MIN_VALUE){
            // will overflow
            return 0;
        }
        else{
            int flag = 1;
            if (x < 0){
                flag = -1;
                x = -x;
            }
            int result = 0;
            while(x > 0){
                int digit = x % 10;
                int newresult = result * 10 + digit; 
                if (result != (newresult - digit) / 10){
                    result = 0;
                    break;
                }
                result = newresult;
                x = x / 10;
            }
            result = result * flag;
            return result;
        }//else
        
    }//public int 
}

6 LeetCode Java: ZigZag Conversion – Easy

Problem:
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

Thoughts:

Use a delta flag to indicate whether next move should go up or go down.
Solutions:

public class Solution {
    public String convert(String s, int nRows) {
        String[] helper = new String[nRows];
        for (int i = 0; i < nRows; i ++){
            helper[i] = "";
        }
        int row = 0;
        int delta = 1;
        for (int i = 0; i < s.length(); i ++){
            char c = s.charAt(i);
            helper[row] += c;
            if (row == nRows - 1){
                delta = -1;
            }
            else if (row == 0){
                delta = 1;
            }
            row = row + delta;
            row = Math.max(0, row);
        }//for
        String result = "";
        for (int i = 0; i < nRows && s.length() > 0; i ++){
            result += helper[i];
        }
        return result;
    }
}v

5 LeetCode Java: Longest Palindromic Substring

Problem:
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Thoughts:
Trivial way is to calculate each substring is palindrome, using O(n^2) time and space.
Could be optimized using only O(1) space.
Idea is to return the longest palindromic substring that is center by (i,i) or (i, i + 1).

Solution:
Trivial way:

public class Solution {
    public String longestPalindrome(String s) {
        boolean[][] isPa = new boolean[s.length()][s.length()];
        calIsPa(isPa, s);
        String longest = "";
        int max = 0;
        for (int i = 0; i < s.length(); i ++){
            for (int j = i; j < s.length(); j ++){
                if (isPa[i][j] == true && (j - i + 1) > max){
                    max = j - i + 1;
                    longest = s.substring(i, j + 1);
                }
            }
        }
        return longest;
    }
    private void calIsPa(boolean[][] isPa, String s){
        for (int i = 0; i < s.length(); i ++){
            isPa[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i ++){
            if (s.charAt(i) == s.charAt(i+1)){
                isPa[i][i+1] = true;
            }
        }
        for (int l = 3; l <= s.length(); l ++ ){
            for (int i = 0; i < s.length() - l + 1; i ++){
                if (s.charAt(i) == s.charAt(i + l - 1) && isPa[i+1][i + l -2]){
                    isPa[i][i+ l - 1] = true;
                }
            }
        }
    }
    
}

The better way:

public class Solution {
    public String longestPalindrome(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i ++){
            String tmp = "";
            tmp = paCenterBy(s, i, i);
            if (tmp.length() > longest.length()){
                longest = tmp;
            }
            tmp = paCenterBy(s, i, i + 1);
            if (tmp.length() > longest.length()){
                longest = tmp;
            }
        }  
        return longest;
    }
    private String paCenterBy(String s, int cleft, int cright){
        String result = "";
        while (cleft >=0 && cright < s.length() && s.charAt(cleft) == s.charAt(cright)){
            cleft --;
            cright ++;
        }
        return s.substring(cleft + 1, cright);
    }
}

3 LeetCode Java: Longest Substring Without Repeating Characters

Problem:
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Thoughts:
Keep a set of flags to indicate what character has appeared.
We could use a HashSet<Character. Whenever we meet a character, we put it into the set. We there are duplicate character, we remove all the characters before the first appearance of the duplicate character and itself.

There could be a optimization about the HashSet. Instead to use a set of character, use a boolean array of 256 elements saves more space when n becomes larger (n is the number of elements in the given array). Because a Character takes 16-bit and a boolean only takes 1 bit. So no matter what n is, using boolean array only takes 256 bit at most.

Solutions:
This is the optimized version using boolean array.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
    	boolean[] flag = new boolean[256];
     
    	int result = 0;
    	int start = 0;
    	char[] arr = s.toCharArray();
    	for (int i = 0; i < arr.length; i++) {
    		char current = arr[i];
    		if (flag[current]) {
    			result = Math.max(result, i - start);
    			for (int k = start; k < i; k++) {
    				if (arr[k] == current) {
    					start = k + 1; 
    					break;
    				}
    				flag[arr[k]] = false;
    			}
    		} else {
    			flag[current] = true;
    		}
    	}
    	result = Math.max(arr.length - start, result);
     
    	return result;
    }
}

2 LeetCode Java: Add Two Numbers – Medium

Problem:
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

Thoughts:
This problem is given by an easy way. The numbers are stored reversely so that we could add from the left to right. The thing to keep in mind is that the two numbers might not have the same length.

The most clear way to handle this is to iterate over the two numbers list, iteration continues until reaches the end of the longer list. When the shorter list reaches the end already, consider the digit to be zero.

Solutions:

/**
 * 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 n1 = l1;
        ListNode n2 = l2;
        ListNode fakeHead = new ListNode(-1);
        ListNode result = fakeHead;
        int toAdd = 0;
        while(!(n1 == null && n2 == null)){
            int v1 = 0;
            int v2 = 0;
            if (n1 != null){
                v1 = n1.val;
                n1 = n1.next;
            }
            if (n2 != null){
                v2 = n2.val;
                n2 = n2.next;
            }
            int tmp = v1 + v2 + toAdd;
            result.next = new ListNode(tmp % 10);
            result = result.next;
            toAdd = tmp / 10;
            
        }
        if (toAdd > 0){
            result.next = new ListNode(toAdd);
        }
        return fakeHead.next;
    }
}

One thing to notice about the above solution is that it have operation that is not quite necessary, line 27 – 30. Especially for test case, 0->1, 1->2->3->4->5->6->7->8->9. If one number is significantly longer, then there is no need to do the addition, module, and maybe not necessary the new node (if toAdd is 0 which means no more addition is needed). But if we stop looping when we meet the end of shorter list and re-point the tail to be the same position at the longer list, now we are modifying the original number list.

The notes above is just thoughts on the solution and other possibilities, just in case there are different requirements and constraints by the problem.