[Leetcode] Dungeon Game

Dp problem. dp[i][j] records if we want to reach the goal from (i, j), the minimum amount of health points we need. dp[i][j] could be obtained from dp[i+1][j] and dp[i][j+1], we get the smaller one from this two arguments (this will be a positive number) and compare it with the value of dungeon and determine the health point we need.

/*
 * Author: Yang Pei
 * Problem: Dungeon Game
 * Source: https://oj.leetcode.com/problems/dungeon-game/
 * 
 * Note:
 * 
 * Soltuion:
 * Dp, dp[i][j] record the minimum health needed to go from (i, j) to reach the goal.
 * dp[i][j] = (dungeon[i][j] - Math.min(dp[i+1][j], dp[i][j+1]) >= 0) ? 1 : (dungeon[i][j] - Math.min(dp[i+1][j], dp[i][j+1]))
 */
public class DungeonGame {
    public static int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        if(m == 0)
            return 0;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j>= 0; j--) {
                int min;
                if(i == m-1 && j == n-1)
                    min = 1;
                else if(i == m-1)
                    min = dp[i][j+1];
                else if(j == n-1)
                    min = dp[i+1][j];
                else 
                    min = Math.min(dp[i][j+1], dp[i+1][j]);
                dp[i][j] = (dungeon[i][j] - min >= 0) ? 1 : (min - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
    
    public static void main(String[] args) {
        int[][] dungeon = new int[][] {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
        System.out.println(calculateMinimumHP(dungeon));
    }
}

[Leetcode] Binary Search Tree Iterator

The solution is also available here:https://gist.github.com/pyemma/bbe39014f436f2a5aa5b

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        if(root != null)
            pushleft(root);
    }
    private void pushleft(TreeNode root) {
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode temp = stack.pop();
        if(temp.right != null)
            pushleft(temp.right);
        return temp.val;
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

[Leetcode] Excel Sheet Column Title

The solution is also available here:https://gist.github.com/pyemma/93a32e641b90288867ae

/*
 * Author: Yang Pei
 * Problem: Excel Sheet Column Title
 * Source: https://oj.leetcode.com/problems/excel-sheet-column-title/
 * 
 * Note:
 * Given a positive integer, return its corresponding column title as appear in an Excel sheet.
 * For example:
 *     1 -> A
 *     2 -> B
 *     3 -> C
 *     ...
 *     26 -> Z
 *     27 -> AA
 *     28 -> AB
 * Solution:
 * Recursive method or iterative method. 
 */
public class ExcelSheetColumnTitle {
 public String convertToTitle(int n) {
  if(n == 0)
   return "";
  return convertToTitle((n-1)/26) + (char)((n-1)%26 + 'A');
 }
 
 public String convertToTitle1(int n) {
  StringBuilder sb = new StringBuilder();
  while(n > 0) {
   sb.append((char)((n - 1) % 26 + 'A'));
   n = (n - 1) / 26;
  }
  sb = sb.reverse();
  return sb.toString();
 }
}

[Leetcode] Compare Version Numbers

The solution is also available here:https://gist.github.com/pyemma/0d6f6368fdcfcb73451d

/*
 * Author: Yang Pei
 * Problem: Compare Version Numbers
 * Source: https://oj.leetcode.com/problems/compare-version-numbers/
 * 
 * Note:
 * Compare two version numbers version1 and version1.
 * If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
 * 
 * You may assume that the version strings are non-empty and contain only digits and the . character.
 * The . character does not represent a decimal point and is used to separate number sequences.
 * For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
 * 
 * Here is an example of version numbers ordering:
 * 0.1 < 1.1 < 1.2 < 13.37
 * 
 * Solution:
 * Split the version according to the ".", then compare each number. Pay attention to
 * leading zeros. If each version number is within the Integer, we could use Integer.paresInt
 * instead of writing a function to compare.
 * 
 * Corner case: 1.0 and 1, 1.0.1 and 1. In this case, we need to check the array with
 * more split to see if each number is 0 or not. 
 */
public class CompareVersionNumbers {
 public static int compareVersion(String version1, String version2) {
  String[] strs1 = version1.split("\\.");
  String[] strs2 = version2.split("\\.");
  for(int i = 0; i < Math.min(strs1.length, strs2.length); i++) {
   if(compare(strs1[i], strs2[i]) != 0)
    return compare(strs1[i], strs2[i]);
  }
  if(strs1.length < strs2.length) {
   for(int i = strs1.length; i < strs2.length; i++) {
    if(compare("0", strs2[i]) < 0)
     return -1;
   }
   return 0;
  } 
  else if(strs1.length > strs2.length) {
   for(int i = strs2.length; i < strs1.length; i++) {
    if(compare(strs1[i], "0") > 0)
     return 1;
   }
   return 0;
  }
  else
   return 0;
 }
 private static int compare(String num1, String num2) {
  int ind1 = 0;
  while(ind1 < num1.length() && num1.charAt(ind1) == '0')
   ind1++;
  int ind2 = 0;
  while(ind2 < num2.length() && num2.charAt(ind2) == '0')
   ind2++;
  num1 = num1.substring(ind1);
  num2 = num2.substring(ind2);
  if(num1.length() < num2.length())
   return -1;
  else if(num1.length() > num2.length())
   return 1;
  else {
   for(int i = 0; i < num1.length(); i++) {
    if(num1.charAt(i) < num2.charAt(i))
     return -1;
    else if(num1.charAt(i) > num2.charAt(i))
     return 1;
   }
   return 0;
  }
 }
 
 public static void main(String[] args) {
  String version1 = "1.0.1";
  String version2 = "1";
  System.out.println(compareVersion(version1, version2));
 }
}

[Leetcode] Majority Element

The solution is also available here:https://gist.github.com/pyemma/81269253375b3f9714e2

/*
 * Author: Yang Pei
 * Problem: Majority Element
 * Source: https://oj.leetcode.com/problems/majority-element/
 * 
 * Note:
 * Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
 * You may assume that the array is non-empty and the majority element always exist in the array.
 * 
 * Solution:
 * Naive method: Use additional space to hold each element's appearances ---> O(n) space complexity
 * Greed method: Use a box to hold the majority candidate and count its number ---> O(1) space complexity
 * 
 * Follow up:
 * What if the array does not contain a major?
 *   Final check the candidate to see if its count
 */
public class MajorityElement {
 public int majorityElement(int[] num) {
  int n = num.length;
  int major = 0, count = 0;
  for(int i = 0; i < n; i++) {
   if(count == 0) {
    major = num[i];
    count++;
   }
   else {
    if(major == num[i])
     count++;
    else
     count--;
   }
  }
  return major;
 }
}

[Leetcode] Find Peak Element

The code is also available here https://gist.github.com/pyemma/31c930a838b40c847d8a

/*
 * Author: Yang Pei
 * Problem: Find Peak Element
 * Source: https://oj.leetcode.com/problems/find-peak-element/
 * 
 * Note:
 * A peak element is an element that is greater than its neighbors.
 * Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
 * The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
 * You may imagine that num[-1] = num[n] = -∞.
 * 
 * For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
 * 
 * Solution:
 * Naive method: sweep the entire array and find the peak element --> take O(n) time
 * 
 * Binary search method: key idea is to drop as much as portion of array as possible.
 *   We need to check the condition of num[mid] with num[mid+1] to determine
 *   how we drop the array.
 *    If num[mid] < num[mid+1], we know mid would not be the answer
 *    and there must exist a peak from mid+1 to r, we set l <-- mid+1.
 *    Otherwise we have num[mid] > num[mid+1], we know mid could be the answer
 *    and there must exist a peak from l to mid, we set r <-- mid.
 *    When mid == num.length - 1, this indicate that the last element is a peak,
 *    we just l <-- l+1 to break out the loop.
 *    When l == r, according to our operation, we know this would be a peak, we
 *    could break out the loop, so in the outer loop, we set the condition to
 *    "l < r" instead of "l <= r".
 * 
 * Attention:
 * Pay attention to the condition in the outer while loop, if "l <= r" setted, it would
 * involve in infinite loop.
 */
public class FindPeakElement {
 public int findPeakElement(int[] num) {
  int l = 0, r = num.length - 1;
  while(l < r) {
   int mid = l + (r - l) / 2;
   if(mid < num.length - 1) {
    if(num[mid] < num[mid + 1])
     l = mid + 1;
    else
     r = mid;
   }
   else
    l = mid + 1;
  }
  return r;
 }
}

[Leetcode] Text Justification

The code is also available here https://gist.github.com/pyemma/b8b0f771085823ec4b87

/*
 * Author: Yang Pei
 * Problem: Text Justification
 * Source: https://oj.leetcode.com/problems/text-justification/
 * 
 * Note:
 * Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
 * You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
 * Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
 * For the last line of text, it should be left justified and no extra space is inserted between words.
 * 
 * For example,
 * words: ["This", "is", "an", "example", "of", "text", "justification."]
 * L: 16.
 * 
 * Return the formatted lines as:
 * [
 * "This    is    an",
 * "example  of text",
 * "justification.  
 * ]
 * Note: Each word is guaranteed not to exceed L in length.
 * 
 * Solution:
 * Use one function to determine the words, use one function to make the line.
 * 
 * Corner case:
 * The last line and the line with only one words, we should left-justified.
 */
import java.util.*;

public class TextJustification {
 private int wordCount(String[] words, int beg, int L) {
  // return the first of next line's word's index
  int count = 0;
  int i = beg;
  for(i = beg; i < words.length; i++) {
   count = count + words[i].length();
   if(count > L)
    break;
   count = count + 1;
  }
  return i;
 }
 
 private String newLine(String[] words, int beg, int end, int L) {
  int count = 0;
  for(int i = beg; i < end; i++)
   count = count + words[i].length();
  int number = end - beg;
  int blank = number == 1 ? ((L - count) / (number - 1)) : L - count;
  int extra = number == 1 ? ((L - count) % (number - 1)) : 0;
  String bl = "";
  for(int i = 0; i < blank; i++)
   bl = bl + " ";
  StringBuffer line = new StringBuffer();
  for(int i = beg; i < end; i++) {
   line.append(words[i]);
   if(beg != i && i == end - 1)
    break;
   line.append(bl);
   if(extra > 0) {
    line.append(" ");
    extra--;
   }
  }
  return line.toString();
 }
 
 private String lastLine(String[] words, int beg, int L) {
  StringBuffer line = new StringBuffer();
  for(int i = beg; i < words.length; i++) {
   line.append(words[i]);
   if(i != words.length - 1)
    line.append(" ");
  }
  int blank = L - line.length();
  for(int i = 0; i < blank; i++)
   line.append(" ");
  return line.toString();
 }
 
 public List<String> fullJustify(String[] words, int L) {
  int ind = 0;
  List<String> result = new ArrayList<String>();
  while(ind < words.length) {
   int beg = ind;
   ind = wordCount(words, beg, L);
   if(ind == words.length)
    result.add(lastLine(words, beg, L));
   else
    result.add(newLine(words, beg, ind, L));
  }
  return result;
 }
}

[Leetcode] Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

Brute Force, enumerate each substring and check the word in the substring to see if it satisfy the constriction. I first build a hashmap on the L to record the count for each word, and while checking the substring, we also build such a hashmap, whenever we find a word that is not in the L, we terminate the checking and go to next one, or we find a word that appears more than those in L. Otherwise we have find a valid substring and we add the index to the result set.

    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> res = new ArrayList<Integer>();
        int n = L.length;
        if(n == 0)
            return res;
        int m = L[0].length();
        int len = S.length();
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int i = 0; i < n; i++) {
            if(map.containsKey(L[i]) == false)
                map.put(L[i], 1);
            else
                map.put(L[i], map.get(L[i]) + 1);
        }
        HashMap<String, Integer> count = new HashMap<String, Integer>();
        for(int i = 0; i <= len - n*m; i++) {
            count.clear();
            int j = i;
            for(j = i; j < i + n*m; j += m) {
                String str = S.substring(j, j+m);
                if(map.containsKey(str) == false)
                    break;
                else {
                    if(count.containsKey(str) == false)
                        count.put(str, 1);
                    else {
                        if(count.get(str) >= map.get(str))
                            break;
                        else
                            count.put(str, count.get(str) + 1);
                    }
                }
            }
            if(j == i + n*m)
                res.add(i);
        }
        return res;
    }

[Leetcode] Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Use subtraction to mimic the division. We could continue subtract division from dividend until dividend is smaller than division. On way to speed up is to double the division each time. However, pay attention to some case that might overflow:

1. When double the divisor, it might overflow, so we need some check to prevent this.
2. When change the negative to positive number, if negative is MIN_VALUE, it will overflow, here I use long to avoid this situation.

    public int divide(int dividend, int divisor) {
        boolean sign = true;
        if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
            sign = false;
        long a = dividend, b = divisor;
        a = (a < 0) ? -a : a; // here might overflow
        b = (b < 0) ? -b : b;
        long res = 0;
        while(a >= b) {
            long x = b;
            long cnt = 1;
            while(a - x >= x) {
                x = x << 1;
                cnt = cnt << 1;
            }
            a = a - x;
            res = res + cnt;
        }
        if(sign == false)
            return (int)-res;
        return (int)res;
    }

[Leetcode] Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Using BFS from the 'O' on the boundary and find all 'O' that could be connected, that is the connected component. All 'O' expect these in the connected component would be surrounded by 'X' and mark them as 'X'.

    public void solve(char[][] board) {
        int m = board.length;
        if(m == 0)
            return ;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<Integer> qx = new LinkedList<Integer>();
        Queue<Integer> qy = new LinkedList<Integer>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        for(int i = 0; i < n; i++) {
            if(board[0][i] == 'O') {
                qx.add(0); qy.add(i);
                visited[0][i] = true;
            }
            if(board[m-1][i] == 'O') {
                qx.add(m-1); qy.add(i);
                visited[m-1][i] = true;
            }
        }
        for(int i = 1; i < m-1; i++) {
            if(board[i][0] == 'O') {
                qx.add(i); qy.add(0);
                visited[i][0] = true;
            }
            if(board[i][n-1] == 'O') {
                qx.add(i); qy.add(n-1);
                visited[i][n-1] = true;
            }
        }
        while(qx.size() != 0) {
            int x = qx.remove();
            int y = qy.remove();
            for(int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if(xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'O' && visited[xx][yy] == false) {
                    qx.add(xx); qy.add(yy);
                    visited[xx][yy] = true;
                }
            }
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'O' && visited[i][j] == false)
                    board[i][j] = 'X';
            }
        }
    }

[Leetcode] Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints: Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.

Be careful with potential overflow !

    public boolean isPalindrome(int x) {
        if(x < 0)
            return false;
        int base = 1;
        while((x / 10) / base > 0) // remember here might overflow!
            base = base * 10;
        while(base > 1) {
            int a = x / base;
            int b = x % 10;
            if(a != b)
                return false;
            x = x % base;
            x = x / 10;
            base = base / 100;
        }
        return true;
    }

[Leetcode] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Use split to split the path according to "/+". Then swap the entire array and maintain a stack. We do the following:

1. If we encounter a ""(this might happen due to the first character of the path is "/") or a ".", we continue.
2. If we encounter a "..", if there are something in the stack, we pop one out.
3. Otherwise we push the string into the stack.

Finally, we append what in the stack together. Pay attention that when the stack is empty, we should return "/".

    public String simplifyPath(String path) {
        int n = path.length();
        if(n == 0)
            return "/";
        String[] strs = path.split("/+");
        List<String> stack = new ArrayList<String>();
        for(int i = 1; i < strs.length; i++) {
            if(strs[i].equals("."))
                continue;
            else if(strs[i].equals("..")) {
                if(stack.size() != 0)
                    stack.remove(stack.size() - 1);
            }
            else
                stack.add(strs[i]);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < stack.size(); i++) {
            sb.append("/");
            sb.append(stack.get(i));
        }
        if(stack.size() == 0) // corner case, if the stack is empty, should return "/" not ""
            return "/";
        return sb.toString();
     }

[Leetcode] Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Compare words by words to find the longest common prefix.

    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        if(n == 0)
            return ""; // corner case
        String com = strs[0];
        for(int i = 1; i < n; i++) {
            int len = Math.min(com.length(), strs[i].length());
            int p = 0;
            while(p < len && com.charAt(p) == strs[i].charAt(p))
                p++;
            com = com.substring(0, p);
        }
        return com;
    }

Another way is to try to find the first character that differs.

    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        if(n == 0)
            return ""; // corner case
        int len = strs[0].length();
        int i = 0;
        for(i = 0; i < len; i++) {
            for(int j = 0; j < n; j++) {
                if(strs[j].length() <= i || strs[j].charAt(i) != strs[0].charAt(i)) // the first position that differs
                    return strs[0].substring(0, i);
            }
        }
        return strs[0].substring(0, i);
    }

[Leetcode] Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.

    public int lengthOfLastWord(String s) {
        int n = s.length();
        int p1 = n - 1, p2 = n - 1;
        while(p2 >= 0 && s.charAt(p2) == ' ')
            p2--;
        p1 = p2;
        while(p2 >= 0 && s.charAt(p2) != ' ')
            p2--;
        return p1 - p2;
    }

[Leetcode] Longest Substring Without Repeating Characters

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.

Use a window to keep the longest substring without repeating characters. Whenever we find a repeating character, move the left side of the window until we meet this character.

    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n == 0)
            return 0; // corner case
        int p1 = 0, p2 = 0, res = Integer.MIN_VALUE;
        HashSet<Character> set = new HashSet<Character>();
        while(p1 < n) {
            while(p2 < n && set.contains(s.charAt(p2)) == false) {
                set.add(s.charAt(p2));
                p2++;
            }
            res = Math.max(res, p2 - p1);
            if(p2 == n) { // all cases have been examined
                break;
            }
            char ch = s.charAt(p2);
            while(p1 < n && s.charAt(p1) != ch) { // move all characters that is before the duplicate out
                set.remove(s.charAt(p1));
                p1++;
            }
            p1++; p2++; // remember to move p2 forward
        }
        return res;
    }

[Leetcode] Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Use binary search twice. First search on the last column, if we could find the target then return true; otherwise we find the first element that bigger than target. If target exist then it could only exist on this row. So we do binary search on this row and try to find the target.

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0)
            return false;
        int n = matrix[0].length;
        int left = 0, right = m - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(matrix[mid][n-1] == target)
                return true;
            else if(matrix[mid][n-1] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        int i = left;
        if(i >= m) // target is larger than the biggest element in the matrix
            return false;
        left = 0; right = n-1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(matrix[i][mid] == target)
                return true;
            else if(matrix[i][mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }

[Leetcode] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Use stack to hold the numbers and whenever meet a operator, we pop the top two number and calculate the result then push the result back to the stack. The final result would be remained in the stack.

    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        if(n == 0)
            return 0;
        Stack<Integer> nums = new Stack<Integer>();
        for(int i = 0; i < n; i++) {
            if(tokens[i].equals("+")) {
                int num2 = nums.pop();
                int num1 = nums.pop();
                nums.push(num1 + num2);
            }
            else if(tokens[i].equals("-")) {
                int num2 = nums.pop();
                int num1 = nums.pop();
                nums.push(num1 - num2);
            }
            else if(tokens[i].equals("*")) {
                int num2 = nums.pop();
                int num1 = nums.pop();
                nums.push(num1 * num2);
            }
            else if(tokens[i].equals("/")) {
                int num2 = nums.pop();
                int num1 = nums.pop();
                nums.push(num1 / num2);
            }
            else {
                nums.push(Integer.parseInt(tokens[i]));
            }
        }
        return nums.pop();
    }

[Leetcode] Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

We only need to maintain two pointers from left end and right end, calculate the area indicated by this two pointers and then move the lower height. The only chance we could get a larger area is by moving the lower height since when we move left or right inward the length of the "rectangle" is decreasing. In this way, we could guarantee to meet the optimal solution. The prove is as follow:

• Suppose the optimal solution is indicated by index i and j. And at one time, one of the left and right pointer would first meet i or j. We assume that left first meet i. Since we only move the pointer with lower height. If some times we move i before right actually arrived at j. This means there is a higher position k that height[k] >= height[i] and (k - i) > (j - i), meaning we could get an even larger area. This contradict with our assumption. So this could not happend. So we guarantee that we would meet the optimal solution.

    public int maxArea(int[] height) {
        int n = height.length;
        if(n < 2)
            return 0; // corner case
        int left = 0, right = n - 1;
        int ma = Integer.MIN_VALUE;
        while(left < right) {
            int area = (right - left)*Math.min(height[left], height[right]);
            ma = Math.max(ma, area);
            if(height[left] < height[right]) // only move the lower height to try to find the larger area
                left++;
            else
                right--;
        }
        return ma;
    }

[Leetcode] Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.
Note: The sequence of integers will be represented as a string.

Simple string manipulation problem, mainly about finding repeating characters sequences. I used two pointers to find the continuous characters.

    public String countAndSay(int n) {
        String str = "1";
        while(n > 1) {
            int p1 = 0, p2 = 0;
            StringBuffer sb = new StringBuffer();
            while(p1 < str.length()) {
                while(p2 < str.length() && str.charAt(p1) == str.charAt(p2))
                    p2++;
                sb.append(String.valueOf(p2 - p1));
                sb.append(str.charAt(p1));
                p1 = p2;
            }
            str = sb.toString();
            n--;
        }
        return str;
    }

[Leetcode] Reverse Integer

Reverse digits of an integer.

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

Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
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.
Update (2014-11-10):
Test cases had been added to test the overflow behavior.

Pay attention to the case of overflow and the case when x = Integer.MIN_VALUE. In this case, you could not directly let x = -x, since it would overflow again, but we know for sure that the reverse of it would overflow so we could directly return 0.

    public int reverse(int x) {
        boolean sign = true;
        if(x < 0) {
            sign = false;
            if(x == Integer.MIN_VALUE) // overflow
                return 0;
            x = -x;
        }
        int res = 0;
        while(x != 0) {
            int digit = x % 10;
            if((Integer.MAX_VALUE - digit) / 10 < res) { // overflow
                return 0;
            }
            res = res * 10 + digit;
            x = x / 10;
        }
        if(sign == false)
            return -res;
        return res;
    }