Happy Coding

Saturday, June 27, 2015

[LeetCode] Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution: Since here we do not have parentheses, a stack is not necessary.

One can directly make one pass to derive the result, by maintaining preMulDiv, preAddSub, preNum, and curNum.

The logic:

Each time we see '+' or '-', we know '*' or '/' before it must have been processed. If we have unprocessed '+' or '-' before, process the old one.

Each time we see a number, if we have unprocessed '*' or '/', process it immediately. Otherwise, update preNum and curNum.

In the end, we need to check whether we need to process '+' or '-' once.
Remarks. In order to deal with the special test case "0-2147483648", I added a little more code. Did not aim to take care of all large number operations.

public class Solution {
    private boolean isOverflow(String s) {
        return s.equals("2147483648");
    }

    private int evalOp(int a, int b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            default: return a / b;
        }
    }
    
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Character preAddSub = null;
        Character preMulDiv = null;
        Integer preNum = null;
        Integer curNum = null;
        int i = 0;
        while (i < s.length()) {
            if (Character.isWhitespace(s.charAt(i))) {
                i++;
            } else if (Character.isDigit(s.charAt(i))) {
                int j = i + 1;
                while (
                    j < s.length() && 
                    Character.isDigit(s.charAt(j))
                ) {
                    j++;    
                }
                if (isOverflow(s.substring(i, j))) {
                    return Integer.MIN_VALUE;
                }
                int nextNum = Integer.valueOf(s.substring(i, j));
                if (preMulDiv != null) {
                    curNum = evalOp(curNum, nextNum, preMulDiv);
                    preMulDiv = null;
                } else {
                    preNum = curNum;
                    curNum = nextNum;
                }
                i = j;
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-') {
                if (preAddSub != null) {
                    curNum = evalOp(preNum, curNum, preAddSub);
                } 
                preAddSub = s.charAt(i);
                i++;
            } else {
                preMulDiv = s.charAt(i);
                i++;
            }
        }
        if (preAddSub != null) {
            curNum = evalOp(preNum, curNum, preAddSub);
        } 
        return curNum;
    }
}

Friday, June 26, 2015

[LeetCode] Longest Substring Without Repeating Characters

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.
Solution 1: HashSet. This requires two iterations.
Sadly, Time Limit Exceeded.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashSet<Character> set = new HashSet<Character>();
        int i = 0; 
        int j = 0;
        int maxLen = 0;
        while (j < s.length()) {
            if (set.contains(s.charAt(j))) {
                while (set.contains(s.charAt(j))) {
                    set.remove(s.charAt(i));
                    i++;
                }
            } 
            maxLen = Math.max(maxLen, j - i + 1);
            set.add(s.charAt(j));
            j++;
        }
        return maxLen;
    }
}

Solution 2: HashMap. Now this is only one iteration.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int i = 0; 
        int j = 0;
        int maxLen = 0;
        while (j < s.length()) {
            if (
                map.containsKey(s.charAt(j)) && 
                map.get(s.charAt(j)) >= i
            ) {
                i = map.get(s.charAt(j)) + 1;
            } 
            maxLen = Math.max(maxLen, j - i + 1);
            map.put(s.charAt(j), j); 
            j++;
        }
        return maxLen;
    }
}

[LeetCode] First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:

O(n) running time, O(n) extra space.

public class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int num = 1;
        while (set.contains(num)) { 
            num++;
        }
        return num;
    }
}

O(n) running time, O(1) extra space.
This utilizes a smart trick by modifying the array to act as a HashSet. See a detailed discussion here.

public class Solution {
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private int partition(int[] nums) {
        int storeIdx = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] > 0) {
                swap(nums, storeIdx, j);
                storeIdx++;
            }
        }
        return storeIdx;
    }
    
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        int numPos = partition(nums);
        for (int i = 0; i < numPos; i++) {
            if (Math.abs(nums[i]) - 1 < numPos) {
                if (nums[Math.abs(nums[i]) - 1] > 0) {
                    nums[Math.abs(nums[i]) - 1] *= -1;
                }
            }
        }
        for (int i = 0; i < numPos; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return numPos + 1;
    }
}

Friday, June 12, 2015

[LeetCode] Decode Ways

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution: Dynamic Programming.

Note that if a message starts with 0, there is no feasible way to decode it.

public class Solution {
    private int[] ways;
    
    private int numDecodings(String s, int i) {
        if (i >= s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        if (ways[i] > -1) {
            return ways[i];
        }
        ways[i] = numDecodings(s, i + 1);
        if (
            i + 2 <= s.length() &&
            Integer.valueOf(s.substring(i, i + 2)) <= 26
        ) {
            ways[i] += numDecodings(s, i + 2);
        }
        return ways[i];
    }
    
    public int numDecodings(String s) {
        if (s.length() == 0) {
            return 0;
        }
        ways = new int[s.length()];
        Arrays.fill(ways, -1);
        return numDecodings(s, 0);
    }
}

[LeetCode] Basic Calculator

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Solution: Stack.

If we encounter +, - or (, we push them in the stack.

If we encounter ), we know the expression inside () has been evaluated. Pop the result for that expression, and pop (. And perform one operation if necessary.

if we encounter a number, perform one operation if necessary.

Remarks. One may solve this recursively by working from the end of the string.

public class Solution {
    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }
    
    private void pushOrAddOrMinus(
        String str, 
        Stack<String> stack
    ) {
        if (stack.empty() || stack.peek().equals("(")) {
            stack.push(str);
            return;
        }
        int val = Integer.valueOf(str);
        if (stack.peek().equals("+")) {
            stack.pop();
            int val_o = Integer.valueOf(stack.pop());
            stack.push(String.valueOf(val_o + val));
        } else if (stack.peek().equals("-")) {
            stack.pop();
            int val_o = Integer.valueOf(stack.pop());
            stack.push(String.valueOf(val_o - val));
        }
    }
    
    public int calculate(String s) {
        if (s.length() == 0) {
            return 0;
        }
        Stack<String> stack = new Stack<String>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '+') {
                stack.push("+");
                i++;
            } else if (s.charAt(i) == '-') {
                stack.push("-");
                i++;
            } else if (s.charAt(i) == '(') {
                stack.push("(");
                i++;
            } else if (s.charAt(i) == ')') {
                String str = stack.pop();
                stack.pop();
                i++;
                pushOrAddOrMinus(str, stack);
            } else if (s.charAt(i) == ' ') {
                i++;  
            } else {
                int j = i + 1;
                while (j < s.length() && isDigit(s.charAt(j))) {
                    j++;
                }
                String str = s.substring(i, j);
                i = j;
                pushOrAddOrMinus(str, stack);
            }
        }
        return Integer.valueOf(stack.pop());
    }
}

Tuesday, June 9, 2015

[LeetCode] Generate Parentheses

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Solution: Backtracking.

public class Solution {
    private ArrayList<String> result;
    private char[] chars;
    
    private void genParen(int leftRem, int rightRem, int i) {
        if (leftRem > rightRem || leftRem < 0) {
            return;
        }
        if (leftRem == 0 && rightRem == 0) {
            result.add(String.valueOf(chars));
            return;
        }
        chars[i] = '(';
        genParen(leftRem - 1, rightRem, i + 1);
        chars[i] = ')';
        genParen(leftRem, rightRem - 1, i + 1);
    }
    
    public List<String> generateParenthesis(int n) {
        result = new ArrayList<String>();
        chars = new char[2 * n];
        genParen(n, n, 0);
        return result;
    }
}

[LeetCode] Rectangle Area

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Credits:
Special thanks to @mithmatt for adding this problem, creating the above image and all test cases.

Solution:
The main observation is that the vertices of the common rectangle (if it exists) must be formed by x coordinates and y coordinates of the vertices of the given two rectangles.
There are 16 possible such vertices. For any of them, if it lies in both rectangles, then it is a vertex of the common rectangle. When the two rectangles are the same, all 16 of them belong to the common rectangle (each vertex is duplicated four times).

public class Solution {
   class Point {
       int x;
       int y;
       
       Point() { }
       
       Point(int _x, int _y) {
           x = _x;
           y = _y;
       }
   }
   
   class Rect {
       int left;
       int right;
       int top;
       int bottom;
       
       Rect() {}
       
       Rect(int l, int b, int r, int t) {
           left = l;
           bottom = b;
           right = r;
           top = t;
       }
       
       Rect(Point a, Point b, Point c, Point d) {
           left = min(a.x, b.x, c.x, d.x);
           bottom = min(a.y, b.y, c.y, d.y);
           right = max(a.x, b.x, c.x, d.x);
           top = max(a.y, b.y, c.y, d.y);
       }
       
       private int min(int v1, int v2, int v3, int v4) {
           int min12 = Math.min(v1, v2);
           int min34 = Math.min(v3, v4);
           return Math.min(min12, min34);
       }
       
       private int max(int v1, int v2, int v3, int v4) {
           int max12 = Math.max(v1, v2);
           int max34 = Math.max(v3, v4);
           return Math.max(max12, max34);
       }
       
       public boolean contains(Point pt) {
           return pt.x >= left && 
                  pt.x <= right && 
                  pt.y >= bottom && 
                  pt.y <= top;
       }
       
       public int area() {
           return (right - left) * (top - bottom);
       }
   }
   
   public int computeArea(
       int A, int B, int C, int D, 
       int E, int F, int G, int H
   ) {
       Rect rect1 = new Rect(A, B, C, D);
       Rect rect2 = new Rect(E, F, G, H);
       int[] x = new int[]{A, C, E, G};
       int[] y = new int[]{B, D, F, H};
       ArrayList<Point> vertices = new ArrayList<Point>();
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               Point p = new Point(x[i], y[j]);
               if (rect1.contains(p) && rect2.contains(p)) {
                   vertices.add(p);
               }
           }
       }
       if (vertices.size() == 0 || vertices.size() == 1) {
           return rect1.area() + rect2.area();
       }
       if (vertices.size() == 16) {
           return rect1.area();
       }
       Rect rect_common = new Rect(
           vertices.get(0),
           vertices.get(1),
           vertices.get(2),
           vertices.get(3)
       );
       return rect1.area() - rect_common.area() + rect2.area();
   }
}