2014年12月2日星期二

[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;
    }

2014年12月1日星期一

[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 a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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;
    }