fenghaolw

http://www.itint5.com/oj/#26 Evaluate an arithmetic expression. For simplicity, the following assumptions are made: There are only positive integers. There is no overflow.  Only plus, minus, and multiply operations are supported. No parenthesis, divide, and modulo. All inputs are valid arithmetic expressions. Example: Input: 1+4*3-5 Output: 8 Input: 2-3-5*2 Output: -11 Note that multiplication has higher priority than plus and minus. Every time we meet a '*' , we will calculate the number. If we meet a '+' or '-' , we will call the recursion, or push the number into a data structure. Recursive version: Note that for minus operations, instead of using prevNum - calc(expr, currNum, pos) , we need to convert it to negative number (i.e., prevNum + calc(expr, -currNum, pos) ). Otherwise the result will be incorrect. For example, 5-4+2 , if we use the first approach, the result will be 5-(4+2)=-1 . However, it should be 5+(-4+2)=3 . Iterative v...

http://www.itint5.com/oj/#4 In a complete binary tree every level, except possibly the last, is completely filled, and all nodes are as far left as possible. How can we count the total number of nodes in a complete binary tree? A straightforward method is to traverse the tree, which takes O(n) in time, where n is the number of nodes. However, this method does not utilize the property of complete binary tree. Since we know the tree is complete, it is very easy to find the height of the tree; the tricky part is how can we find the number of nodes in the last level. We can utilize a binary search method to figure out how many nodes are in the last level. For each node, we check the "left height" of its left subtree and its right subtree, respectively. "Left height" means the depth of the leftmost leaf node. If the "left heights" are the same, we know that the left subtree is full; if the "left heights" are not the same, we know that the r...

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this. ...

http://www.itint5.com/oj/#23 The row and column indices in Excel are denoted by: A, B, C, ..., Z, AA, AB, ... AZ, BA, ... The corresponding decimal numbers are: 1, 2, 3, ..., 26, 27, 28, ... Implement two functions to transform decimal numbers to Excel numbers and vice versa. Excel number is a numeral system based 26.