Leetcode Climbing Stairs

One dimension DP.

public int climbStairs(int n) {
        int[] steps = new int[n+1];
        steps[0] = 1;
        steps[1] = 1;
        for (int i=2; i<=n; i++) {
            steps[i] = steps[i-1] + steps[i-2];
        }
        return steps[n];
    }

Leecode Search Insert Position

O(logn) Binary Search

 public int searchInsert(int[] A, int target) {
        if (A == null) return 0;
        return searchInsert(A,target, 0, A.length-1);
    }
    private int searchInsert(int[] A, int target, int start, int end) {
        int mid = (start+end)/2;
        if (target == A[mid]) {
            return mid;
        } else if (target < A[mid]) {
            return start < mid ? searchInsert(A, target, start, mid-1) : start;
        } else {
            return end > mid ? searchInsert(A, target, mid+1, end) : (end + 1);
        }
       
    }

LeetCode Populating Next Right Pointers I&II in Each Node

Recursive method:

public void connect(TreeLinkNode root) {
        if (root == null) return;
        if (root.left != null) {
            root.left.next = root.right;
        }
        if (root.right != null && root.next != null) {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }

Iterative method:

public void connect(TreeLinkNode root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (root == null)
return;
TreeLinkNode currentNode = root;
TreeLinkNode topNode = root;
TreeLinkNode firstNode = root.left;
currentNode.next = null;

while (topNode != null && topNode.left != null) {
while (topNode != null) {
currentNode = topNode.left;
currentNode.next = topNode.right;
currentNode = currentNode.next;
topNode = topNode.next;
currentNode.next = (topNode == null) ? null : topNode.left;
}
topNode = firstNode;
firstNode = (topNode == null) ? null : topNode.left;
}
    }

For II, still use two variables to contain the prev and nextLevel. The only thing we need to pay attention, sometimes we may meet the null pointer node.

public void connect(TreeLinkNode root) {
        if (root==null) return;
        while (root!=null) {
            TreeLinkNode nextLevel=null;
            TreeLinkNode prev=null;
            while (root!=null) {
                if (nextLevel==null) nextLevel= (root.left != null) ? root.left : root.right;
                if (root.left!=null) {
                    if (prev!=null) {
                        prev.next=root.left;
                    }
                    prev=root.left;
                }
                if (root.right!=null) {
                    if (prev!=null) {
                        prev.next=root.right;
                    }
                    prev=root.right;
                }
                root=root.next;
            }
            root=nextLevel;
        }
    }

LeetCode Binary Tree Preorder Traversal

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
       
        while (!stack.empty()) {
            TreeNode temp = stack.pop();
            list.add(temp.val);
           
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
           
        }
        return list;
    }

LeetCode Binary Tree Inorder Traversal

Using stack to store all the elements on the left

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while (!stack.empty() || p != null) {
            if (p!=null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode temp = stack.pop();
                list.add(temp.val);
                p = temp.right;
            }
        }
        return list;
    }

LeetCode Linked List Cycle II

1. Find the cycle
2. Move the slow to the head

2(a+b) = a+b + b+ c; so a = c;

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //Finding the cycle
        //Slow and fast meet at Z point
        while(true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
           
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
       
    }

LeetCode Linked List Cycle

Using two pointers.


public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return false;
       
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
           
            if (fast == slow) {
                return true;
            }
        }
        return false;
       
    }

LeetCode Unique Binary Search Tree

DP

public int numTrees(int n) {
        int[] numArray = new int[n+1];
        numArray[0] = 1;
        numArray[1] = 1;
        for (int i=2; i<=n; i++) {
            for (int j=0; j<i; j++) {
                numArray[i] += numArray[j]*numArray[i-j-1];
            }
        }
        return numArray[n];
    }

LeetCode Reverse Integer

Reverse Integer is similar with the Palindrome Number

1. negative or positive
2. avoid overflow

public int reverse(int x) {
        //negative and positive
        boolean negative = (x > 0) ? false : true;
        int temp = Math.abs(x);
        long result = 0;
        while (temp > 0) {
            result = result * 10 + temp%10;
            temp /= 10;
        }
        if (result > Integer.MAX_VALUE) {
            return 0;
        }
        if (negative) return 0-(int)result;
        return (int)result;
    }

LeetCode SameTree

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null && q == null) return true;
        if (p==null || q == null) return false;
        if (q.val != p.val) return false;
        else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

LeetCode Maximum Depth of Binary

Recursion:

public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth)+1;
    }

LeetCode SingleNumberII

need a bit vector to store how many times 1 occurs on one bit.

public int singleNumber(int[] A) {
        int[] countsPerBit = new int[32];
        int result = 0;
        for (int i=0; i<32; i++) {
            for (int j=0; j<A.length; j++) {
                if ((A[j]>>i & 1) == 1) {
                    countsPerBit[i] = (countsPerBit[i] + 1)%3;
                }
            }
        result |= (countsPerBit[i] << i);
        }
        return result;
    }

LeetCode SingleNumber

Using the HashMap and Traverse the entire hashmap to find the value is not equal to 2.

public int singleNumber(int[] A) {
        int result = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i=0; i<A.length; i++) {
            if (!map.containsKey(A[i])) {
                map.put(A[i], 1);
            } else {
                map.put(A[i], map.get(A[i]) + 1);
            }
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (entry.getValue() != 2) {
                result = entry.getKey();
                break;
            }
        }
        return result;
    }

Another solution is simple and clear but not easy to get it.

public int singleNumber(int[] A) {
       int result = A[0];
       for (int i=1; i<A.length; i++) {
           result ^= A[i];
       }
       return result;
    }

LeetCode LongestValideParentheses

Similar idea with valid parentheses. Using a stack to store the left perenthese.


public int longestValidParentheses(String s) {
        int maxLen = 0;
int lastIndex = -1;
Stack<Integer> lefts = new Stack<Integer>();
for (int i=0; i<s.length();i++) {
if (s.charAt(i) == '(') {
lefts.push(i);
} else {
if (lefts.empty()) {
lastIndex = i;
} else {
lefts.pop();
if (lefts.empty()) {
                                             
maxLen = Math.max(maxLen, i-lastIndex);
} else {
                                                //Count the current length
maxLen = Math.max(maxLen, i - lefts.peek());
}
}
}
}
return maxLen;
    }

LeetCode PermutationSequence

This problem is similar to number to Integer to Roman

Here we need to be careful about the k.
"k--" makes sure the k is not exactly the time of (n-1)!
for example n = 4, k=6. The start digit should be 1, instead of 2.

public String getPermutation(int n, int k) {
String res = "";
k--;
ArrayList<Integer> array = new ArrayList<Integer>();
for (int i=1; i<=n; i++) array.add(i);
while (n>0) {
res += array.get(k/fact(n-1));
array.remove(array.get(k/fact(n-1)));
k = k%fact(n-1);
n--;
}
return res;
}

public int fact(int i) {
int res = 1;
while (i > 1) {
res *= i;
i--;
}
return res;
}

LeetCode NextPermutation

1. From right to left, find the first num[i] < num[i+1];
2. From right to left, find the smallest element such that num[j] > num[i]
3. Sort the num from i to length

public void nextPermutation(int[] num) {
        if (num == null) return;
        int i = num.length - 2;
        while (i >= 0 && num[i] >= num[i+1]) i--;
        if (i < 0) {
            Arrays.sort(num);
            return;
        } else {
            for (int j = num.length - 1; j>=0; j--) {
                if (num[j] > num[i]) {
                    int temp = num[i];
                    num[i] = num[j];
                    num[j] = temp;
                    Arrays.sort(num, i+1, num.length);
                    return;
                }
            }
        }
    }

LeetCode Substring with Concatenation

Using two hashmap to store all the words. Here we need pay attention to the interator.

方法一 在for-each循环中使用entries来遍历 (General)
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());

}

方法二 在for-each循环中遍历keys或values。

如果只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet。

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

//遍历map中的键

for (Integer key : map.keySet()) {

    System.out.println("Key = " + key);

}

//遍历map中的值

for (Integer value : map.values()) {

    System.out.println("Value = " + value);

}

方法三使用Iterator遍历

使用泛型：

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();

while (entries.hasNext()) {

    Map.Entry<Integer, Integer> entry = entries.next();

    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());

}

 public List<Integer> findSubstring(String S, String[] L) {
       List<Integer> result = new ArrayList<Integer>();
       int length = L.length * L[0].length();
       int tokenLength = L[0].length();
       int tokenCount = L.length;
     
       //put all the words in L into HashMap
       Map<String, Integer> map = new HashMap<String, Integer>();
       for (String str : L) {
           if (!map.containsKey(str)) {
               map.put(str, 1);
           } else {
               map.put(str, str.get(str) + 1);
           }
       }
     
       //Search in S
       for (int i = 0; i < S.length() - length + 1; i++) {
           String str = S.substring(i, i+length);
           boolean flag = true;
           //adding all the worlds in str into the tempHashMap
           HashMap<String, Integer> tempMap = new HashMap<String, Integer>();
           for (int j=0; j<tokenCount; j++) {
               String token = str.substring(j*tokenLength, (j+1)*tokenLength);
               if (!map.containsKey(token)) {
                   flag = false;
                   break
               } else {
                   if (!tempMap.containsKey(token)) {
                       tempMap.put(token, 1);
                   } else {
                       tempMap.put(token, tempMap.get(token) + 1);
                   }
               }
           }
           if (!flag) continue;
           boolean add = true;
           for (Map.Entry<String,Integer> entry : map.entrySet()) {
               if (tempMap.get(entry.getKey()) != entry.getValue()) {
                   add = false;
                   break;
               }
           }
           if (add) result.add(i);
       }
       return result;
    }

LeetCode DivideTwoInteger

1. Avoid overflow (using long instead of int)
2. Determine the negative and positive
3. To make the code clear, using the arraylist to store all the divisors (1, 10, 100, 1000)

Here is the code:

public int divide(int dividend, int divisor) {
if (dividend == 0 || divisor == 1) return dividend;
if (divisor == -1) {
   if (dividend==Integer.MIN_VALUE) return Integer.MAX_VALUE;
   else return 0-dividend;
}

//Avoid overflow
long divid = Math.abs((long)dividend);
long divs = Math.abs((long) divisor);

//Store divisors into the ArrayList
ArrayList<Long> divisors = new ArrayList<Long>();
while(divs<=divid) {
   divisors.add(divs);
   divs = divs<<1;
}

//Calculate the divide
int result = 0;
int curr = divisors.size()-1;
while (divid > 0 && curr >= 0) {
   if (divid >= divisors.get(curr)) {
       divid -= divisors.get(curr);
       result += 1<<curr;
   }
   curr--;
}

//Positive and negative sign
return (dividend > 0) ^ (divisor > 0) ? (-result) : result;

}

LeetCode Permutation II

DFS  {1, 1, 1, 2}  4 Situation before list.remove(list.size()-1)
1, 1 1, 1 1 1, 1 1 1 2;
when we operating 1 1, we can directly put 2 after 1 1.
进入下一层递归前，把和当前位重复的数过Skip.

public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        Arrays.sort(num);
        boolean[] visited = new boolean[num.length];
        permuteUniqueHelper(result, temp, num, visited);
        return result;
    }
   
    private void permuteUniqueHelper(List<List<Integer>> result, ArrayList<Integer> list, int[] num, boolean[] visited) {
        if (list.size() == num.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
       
        for (int i=0; i<num.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                list.add(num[i]);
                permuteUniqueHelper(result, list, num, visited);
                list.remove(list.size()-1);
                visited[i] = false;
                while (i<num.length-1 && num[i+1]==num[i]) {
                    i++;
                }
            }
        }
    }

LeetCode Best Time to Buy and Sell the Stock III&VI

DP. Finding the best situation from 0 - i (Left) and i+1, prices.length-1 (Right).


public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
     
        int maxProfit = 0;
        int len = prices.length;
        int[] left = new int[len];
        int[] right = new int[len];
     
        process(prices, left, right);
     
        for (int i=0; i<len; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        return maxProfit;
    }
 
    private void process(int[] prices, int[] left, int[] right) {
        //Left side
        left[0] = 0;
        int min = prices[0];
        for (int i=1; i<left.length; i++) {
            left[i] = Math.max(left[i-1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
     
        //right side
        right[prices.length-1] = 0;
        int max = prices[prices.length-1];
        for (int i=prices.length-2; i>=0; i--) {
            right[i] = Math.max(right[i+1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
    }

Find a better solution.
Reference
http://blog.csdn.net/linhuanmars/article/details/23236995
public int maxProfit(int[] prices) {
        if (prices==null || prices.length==0) return 0;
        int numTrans = 2;
        int[] local = new int[numTrans+1];
        int[] global = new int[numTrans+1];
        for (int i=0; i<prices.length-1; i++) {
            int diff = prices[i+1]-prices[i];
            for (int j=numTrans; j>0; j--) {
                local[j]=Math.max(global[j-1]+Math.max(diff,0), local[j]+diff);
                global[j]=Math.max(global[j],local[j]);
            }
        }
        return global[numTrans];
    }

LeetCode Best Time to Buy and Sell the Stock II

Adding all the positive value A[i] - A[i-1]


public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i-1];
            if (diff > 0) {
                maxProfit += diff;
            }
        }
        return maxProfit;
    }

LeetCode Best Time to Buy and Sell Stock I

Need a variable to record the min value in the matrix

public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int maxdiff = Integer.MIN_VALUE;
        int min = prices[0];
        for (int i=1; i<prices.length; i++) {
            //updating the max value
            if (prices[i] < min) {
                min = prices[i];
            }
            //updating the maxdiff
            if (maxdiff < prices[i] - min) {
                maxdiff = prices[i] - min;
            }
        }
        return maxdiff;
    }

LeetCode Remove Duplicates from Sorted List

public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode curr = head;
        ListNode next = head.next;
        while (next != null) {
            if (curr.val == next.val) {
                curr.next = next.next;
                next = curr.next;
            } else {
                curr = next;
                next = curr.next;
            }
        }
        return head;
    }

LeetCode Reverse Nodes in K-Group

Key part is reverse method.


  public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        int i = 0;
        while (head != null) {
            i++;
            if (i%k == 0) {
                prev = reverse(prev, head.next);
                head = prev.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode prev, ListNode next) {
        ListNode last = prev.next;
        ListNode curr = last.next;
        while (curr != next) {
            last.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = last.next;
        }
        return last;
    }

LeetCode Reverse Linked List II

The key part is "reverse" method.
Also it can be used in the Reverse K group.

public ListNode reverseBetween(ListNode head, int m, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode temp = dummy;
       int i = 1;
       //Find the prev
       while( temp != null && i < m) {
           temp = temp.next;
           i++;
       }
       ListNode prev = temp;
       //Find the next
       while (temp != null && i <= n) {
           temp = temp.next;
           i++;
       }
       ListNode next = temp.next;
       reverse(prev, next);
       return dummy.next;
    }
    private void reverse(ListNode prev, ListNode next) {
        ListNode last = prev.next;
        ListNode curr = last.next;
        while (curr!=next) {
            last.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = last.next;
        }
    }

LeetCode Letter Combinations of a Phone Number

DFS

 public List<String> letterCombinations(String digits) {
       List<String> result = new ArrayList<String>();
       if (digits == null || digits.length() == 0) {
           result.add("");
           return result;
       }
       String[] map = {"abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
       //DFS
       for (String rest : letterCombinations(digits.substring(1))){
           for (char c : map[digits.charAt(0) - '0' - 2].toCharArray()) {
               result.add(c + rest);
           }
       }
       return result;
    }

LeetCode Remove Nth Node From the End of List

Boundary Conditions:
1. Only one node in the list
2. Remove the first node

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode front = head;
        ListNode behind = head;
        //Only one node in the list
        if (head.next == null) return null;
        //Move the front Node n steps
        while (n > 0) {
            front = front.next;
            n--;
        }
        //Remove the first node
        if (front==null) {
            head = head.next;
            return head;
        }
        //Move front and behind at the same time
        while (front.next != null) {
            front = front.next;
            behind = behind.next;
        }
       
        behind.next = behind.next.next;
        return head;
    }

LeetCode Longest Common Prefix

Here we need check the length of the string in the array.

public String longestCommonPrefix(String[] strs) {
        if (strs== null || strs.length == 0) return "";
        StringBuilder sb = new StringBuilder();
for (int i = 0; i < strs[0].length(); i++) {
char temp = strs[0].charAt(i);
for (int j = 0; j < strs.length; j++) {

if (i >= strs[j].length() || temp != strs[j].charAt(i)) {
return sb.toString();
}
}
sb.append(temp);
}
return sb.toString();
    }

Leetcode Roman to Integer

public int romanToInt(String s) {
        //put all the symbols and numbers in the hashmap
        int[] numbers = {1000, 500, 100, 50, 10, 5, 1};
        char[] symbols = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            map.put(symbols[i], numbers[i]);
        }
       
        //Calculate the integer
        char[] charArr = s.toCharArray();
        int result = map.get(charArr[s.length() - 1]);
        for (int i = 0; i < s.length()-1; i++) {
            result += map.get(charArr[i])
                        *(map.get(charArr[i]) >= map.get(charArr[i+1]) ? 1 : -1);
        }
        return result;
    }

LeetCode Integer to Roman

public String intToRoman(int num) {
        int[] numbers = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
       
        String result = "";
        int index = 0;
        while (num>0) {
            int times = num / numbers[index];
            num -= numbers[index] * times;
            while (times > 0) {
                result += symbols[index];
                times--;
            }
            index++;
        }
        return result;
    }

LeetCode ConainerWithMostWater

Always moving the smaller side.

public int maxArea(int[] height) {
        int start=0;
        int end=height.length-1;
        int area = 0;
       
        while (start < end) {
            area = Math.max(area, (end - start) * Math.min(height[start], height[end]));
            if (height[start] > height[end]) {
                end--;
            } else {
                start++;
            }
        }
        return area;
    }

LeetCode Regular Expression Match

It always to get the time limited exceed.
Skipping some cases can avoid the situation.

public boolean isMatch(String s, String p) {
        //I have the boundary condition
//although it is easy to follow
   if(s.length()==0)
            return p.length()>1 && p.length()%2==0 ? p.charAt(1)== '*'
                && isMatch(s,p.substring(2)) : p.length()==0;
if (p.isEmpty()) return false;

char c1 = s.charAt(0);
char c2 = p.charAt(0);
char c2next = p.length() > 1 ? p.charAt(1) : 'x';
if (c2next == '*') {
if (isSame(c1,c2)) {
return isMatch(s.substring(1), p) || isMatch(s, p.substring(2));
} else {
return isMatch(s,p.substring(2));
}
} else {
if (isSame(c1,c2)) {
return isMatch(s.substring(1),p.substring(1));
} else {
return false;
}
}

}
private static boolean isSame(char c1, char c2) {
return c2 == '.' || c1==c2;
}

LeetCode Palindrome Number

1. negative is not palindrome number
2. use double to avoid the overflow.

public boolean isPalindrome(int x) {
        if (x < 0) return false;
        if (x == 0) return true;
        double rev = 0;
        int y = x; //don't forget to save the original number before you do some operation.
        while (x != 0) {
            rev = rev * 10 + x%10;
            x /= 10;
        }
        if (rev > Integer.MAX_VALUE) {
            return false;
        }
     
        return (int)rev == y ;
    }

Leetcode atoi

5 conditions need to check
1. null or empty string
2. skip all the white spaces
3. negative and positive sign
4. calculate the value
5. handle the overflow : here we used double type to avoid overflow. It make the code much clear.

    public int atoi(String str) {
        //null or empty string
        if (str == null || str.length() == 0) {
            return 0;
        }
        //skip all the white space
        double result = 0;
        boolean isNegative = false;
        int index = 0;
        while (index < str.length() && str.charAt(index) == ' ') {
            index++;
        }
        //negative and positive sign
        if (str.charAt(index) == '+') {
            isNegative = false;
            index++;
        } else if (str.charAt(index) == '-') {
            isNegative = true;
            index++;
        }
        //calculate the value
        while (index < str.length() && str.charAt(index) >= '0' && str.charAt(index) <= '9') {
            result = result*10 + (str.charAt(index) - '0');
            index++;
        }
        if (isNegative) {
            result = result * (-1);
        }
        //handle the overflow
        if (result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (result < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int)result;
    }

LeetCode LongestPalindrome

Time Complexity is O(n^2) Space Complexity is O(1)
Sorry for not Mancher's algorithm, since it is too complicated for me.

public String longestPalindrome(String s) {
       if (s==null || s.length()==0) return null;
       if (s.length()==1) return s;
     
       String longest = s.substring(0,1);
       for (int i=0; i<s.length(); i++) {
           //Get longest palindrome from the center of i
           String temp = helper(s,i,i);
           if (temp.length() > longest.length()) {
               longest = temp;
           }
           //Get longest palindrome from the center of i, i+1
            temp = helper(s,i,i+1);
           if (temp.length() > longest.length()) {
               longest = temp;
           }
       }
       return longest;
    }
    private String helper(String s, int start, int end) {
        while (start>=0 && end<= s.length()-1&& s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        return s.substring(start+1, end);
    }

LeetCode ZigZag Conversion

Implimentation:
index+unitsize - 2*row

public String convert(String s, int nRows) {
        //Boundary condition
        if (s==null || s.length()==0 || nRows <=0) return "";
        if (nRows==1) return s;
        //Traverse the whole string, chopped the string as different unit
        //The unit size should be 2*nRows - 2
        //In each unit, the first column is easy to handle.
        //The second column need to use index + Unitsize - 2 * row
        int unitSize = 2*nRows - 2;
        StringBuilder result = new StringBuilder();
        for (int i=0; i<nRows; i++) {
            for (int j = i; j < s.length(); j+=unitSize) {
                result.append(s.charAt(j));
                if (i!=0 && i!=nRows-1 && j+unitSize-2*i<s.length()) {
                    result.append(s.charAt(j+unitSize-2*i));
                }
            }
        }
        return result.toString();
    }