Lintcode 617. Maximum Average Subarray II

Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.

Example

Example 1:

Input:
[1,12,-5,-6,50,3]
3
Output:
15.667
Explanation:
 (-6 + 50 + 3) / 3 = 15.667

Example 2:

Input:
[5]
1
Output:
5.000

Notice

It's guaranteed that the size of the array is greater or equal to k.

Analysis:
Binary search for the result. Given a target average T, can we find out 
A[left] + ... A[right] / (right - left + 1) >= T. If we can find out this T, meaning the T we tried might be too small. We should try a bigger T. 

For  A[left] + ... A[right] / (right - left + 1) >= T, we can transform to 
(A[left] - T) + ... + (A[right] - T) >= 0
That is, For B[i] = A[i - 1], can we find out B[i] + ... + B[j] >= 0? This can be done by prefix sum. 


Code (Java):

public class Solution {
    /**
     * @param nums: an array with positive and negative numbers
     * @param k: an integer
     * @return: the maximum average
     */
    public double maxAverage(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return 0;
        }
        
        double lo = nums[0];
        double hi = nums[0];
        for (int i = 0; i < nums.length; i++) {
            lo = Math.min(lo, nums[i]);
            hi = Math.max(hi, nums[i]);
        }
        
        while (lo + 1e-5 < hi) {
            double mid = lo + (hi - lo) / 2;
            if (canFind(nums, k, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        
        return lo;
    }
    
    private boolean canFind(int[] nums, int k, double target) {
        double leftSum = 0;
        double rightSum = 0;
        double minLeftSum = 0;
        
        for (int i = 1; i <= nums.length; i++) {
            rightSum += nums[i - 1] - target;
            
            if (i >= k) {
                leftSum += i > k ? nums[i - k - 1] - target : 0;
                
                minLeftSum = Math.min(leftSum, minLeftSum);
            
                if (rightSum - minLeftSum >= 0) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Lintcode 437. Copy Books

Given n books and the ith book has A[i] pages. You are given k people to copy the nbooks.

n books list in a row and each person can claim a continous range of the n books. For example one copier can copy the books from ith to jth continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).

They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?

Example

Given array A = [3,2,4], k = 2.

Return 5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

Solution:
Binary search for results. Given a max time T, find out the minimum number of people to finish the job. The number of people > k, means the time T we found was too small, so we should try out a bigger time.

Code (Java):

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages == null || pages.length == 0 || k <= 0) {
            return 0;
        }

        int sum = 0;
        for (int page : pages) {
            sum += page;
        }

        int lo = sum / k;
        int hi = sum;

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canFinish(pages, k, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        if (canFinish(pages, k, lo)) {
            return lo;
        } else if (canFinish(pages, k, hi)){
            return hi;
        } else {
            return 0;
        }
    }

    private boolean canFinish(int[] pages, int k, int maxTime) {
        int count = 1;
        int currTime = 0;

        for (int i = 0; i < pages.length; i++) {
            if (pages[i] > maxTime) {
                return false;
            }

            currTime += pages[i];
            if (currTime > maxTime) {
                count++;
                currTime = pages[i];
            }
        }

        return count <= k;
    }
}

Lintcode 183. Wood Cut

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

Example

For L=[232, 124, 456], k=7, return 114.

Challenge

O(n log Len), where Len is the longest length of the wood.

Notice

You couldn't cut wood into float length.

If you couldn't get >= k pieces, return 0.

Analysis:
Binary search for the result. The min length is 1, and the max length is the Max(L[i]). So we can try every possible length and calculate how many pieces can we cut? If the number is greater than k, means the the number we tried might be too small. Otherwise, the number is too large. So we can do it via binary search. The total time complexity would be O(nlogAns)

Code (Java):

public class Solution {
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    public int woodCut(int[] L, int k) {
        if (L == null || L.length == 0 || k <= 0) {
            return 0;
        }

        int lo = 1;
        int hi = 0;
        for (int i = 0; i < L.length; i++) {
            hi = Math.max(hi, L[i]);
        }

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            int pieces = getPieces(mid, L);
            if (pieces < k) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        if (getPieces(hi, L) >= k) {
            return hi;
        } else if (getPieces(lo, L) >= k){
            return lo;
        } else {
            return 0;
        }
    }

    private int getPieces(int len, int[] L) {
        int ans = 0;
        for (int l : L) {
            ans += l / len;
        }

        return ans;
    }
}

Lintcode 391. Number of Airplanes in the Sky

Given an list interval, which are taking off and landing time of the flight. How many airplanes are there at most at the same time in the sky?

Example

Example 1:

Input: [(1, 10), (2, 3), (5, 8), (4, 7)]
Output: 3
Explanation:
The first airplane takes off at 1 and lands at 10.
The second ariplane takes off at 2 and lands at 3.
The third ariplane takes off at 5 and lands at 8.
The forth ariplane takes off at 4 and lands at 7.
During 5 to 6, there are three airplanes in the sky.

Example 2:

Input: [(1, 2), (2, 3), (3, 4)]
Output: 1
Explanation: Landing happen before taking off.

Notice

If landing and taking off of different planes happen at the same time, we consider landing should happen at first.

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        if (airplanes == null || airplanes.size() == 0) {
            return 0;
        }
        
        int max = 0;
        List<Event> events = new ArrayList<>();
        for (Interval airplane : airplanes) {
            events.add(new Event(airplane.start, 0));
            events.add(new Event(airplane.end, 1));
        }
        
        Collections.sort(events, new MyEventComparator());
        
        int count = 0;
        for (Event e : events) {
            if (e.flag == 0) {
                count++;
            } else {
                count--;
            }
            
            max = Math.max(max, count);
        }
        
        return max;
    }
}

class Event {
    int time;
    int flag; // 0 start 1 end
    
    public Event(int time, int flag) {
        this.time = time;
        this.flag = flag;
    }
}

class MyEventComparator implements Comparator<Event> {
    @Override
    public int compare(Event a, Event b) {
        if (a.time != b.time) {
            return a.time - b.time;
        }
        
        return b.flag - a.flag;
    }
}

Lintcode 367. Expression Tree Build

The structure of Expression Tree is a binary tree to evaluate certain expressions.
All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.

Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.

Example

For the expression (2*6-(23+7)/(1+2)) (which can be represented by ["2" "*" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]).
The expression tree will be like

                 [ - ]
             /          \
        [ * ]              [ / ]
      /     \           /         \
    [ 2 ]  [ 6 ]      [ + ]        [ + ]
                     /    \       /      \
                   [ 23 ][ 7 ] [ 1 ]   [ 2 ] .

After building the tree, you just need to return root node [-].

Code (Java)

/**
 * Definition of ExpressionTreeNode:
 * public class ExpressionTreeNode {
 *     public String symbol;
 *     public ExpressionTreeNode left, right;
 *     public ExpressionTreeNode(String symbol) {
 *         this.symbol = symbol;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param expression: A string array
     * @return: The root of expression tree
     */
    public ExpressionTreeNode build(String[] expression) {
        if (expression == null || expression.length == 0) {
            return null;
        }
        
        Stack<String> opStack = new Stack<>();
        Stack<ExpressionTreeNode> nodeStack = new Stack<>();
        
        int i = 0;
        for (String s : expression) {
            if (isNumeric(s)) {
                ExpressionTreeNode node = new ExpressionTreeNode(s);
                nodeStack.push(node);
            } else if (opStack.isEmpty() || s.equals("(")) {
                opStack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                if (opStack.peek().equals("(")) {
                    opStack.push(s);
                } else {
                    compute(opStack, nodeStack);
                    opStack.push(s);
                }
            } else if (s.equals("*") || s.equals("/")) {
                String top = opStack.peek();
                if (top.equals("(")) {
                    opStack.push(s);
                } else if (top.equals("*") || top.equals("/")) {
                    compute(opStack, nodeStack);
                    opStack.push(s);
                } else {
                    opStack.push(s);
                }
            } else {
                while (!opStack.isEmpty() && !opStack.peek().equals("(")) {
                    compute(opStack, nodeStack);
                }
                opStack.pop(); // pop out the '('
            }
        }
        
        while (!opStack.isEmpty()) {
            compute(opStack, nodeStack);
        }
        
        return nodeStack.isEmpty() ? null : nodeStack.pop();
    }
    
    private void compute(Stack<String> opStack, Stack<ExpressionTreeNode> nodeStack) {
        ExpressionTreeNode node2 = nodeStack.pop();
        ExpressionTreeNode node1 = nodeStack.pop();
        
        String op = opStack.pop();
        
        ExpressionTreeNode root = new ExpressionTreeNode(op);
        root.left = node1;
        root.right = node2;
        
        nodeStack.push(root);
    }
    
    private boolean isNumeric(String s) {
        for (char c : s.toCharArray()) {
            if (!Character.isDigit(c)) {
                return false;
            }
        }
        
        return true;
    }
}

Lintcode 623. K Edit Distance

Given a set of strings which just has lower case letters and a target string, output all the strings for each the edit distance with the target no greater than k.

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example

Given words = ["abc", "abd", "abcd", "adc"] and target = "ac", k = 1
Return ["abc", "adc"]




Code (Java):

public class Solution {
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */
    public List<String> kDistance(String[] words, String target, int k) {
        List<String> ans = new ArrayList<>();
        if (words == null || words.length == 0 || k < 0) {
            return ans;
        }
        
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        TrieNode p = trie.root;
        
        int[] dp = new int[target.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i;
        }
        
        kDistanceHelper(p, dp, target, k, ans);
        
        return ans;
    }
    
    private void kDistanceHelper(TrieNode p, int[] dp, String target, int k, List<String> ans) {
        if (p == null) {
            return;
        }
        
        if (p.leaf && dp[target.length()] <= k) {
            ans.add(p.word);
        }
        
        int[] curr = new int[target.length() + 1];
        curr[0] = dp[0] + 1;
        
        for (char c = 'a'; c <= 'z'; c++) {
            if (p.children[c - 'a'] != null) {
                for (int j = 1; j <= target.length(); j++) {
                    if (c == target.charAt(j - 1)) {
                        curr[j] = dp[j - 1];
                    } else {
                        curr[j] = Math.min(dp[j - 1], Math.min(dp[j], curr[j - 1])) + 1;
                    }
                }
                kDistanceHelper(p.children[c - 'a'], curr, target, k, ans);
            }
        }
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            p = p.children[c - 'a'];
        }
        
        p.leaf = true;
        p.word = word;
    }
}

class TrieNode {
    TrieNode[] children;
    boolean leaf;
    String word;
    
    public TrieNode() {
        children = new TrieNode[26];
        leaf = false;
        word = "";
    }
}

Lintcode 130. Heapify

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Clarification

What is heap?

• Heap is a data structure, which usually have three methods: push, pop and top. where "push" add a new element the heap, "pop" delete the minimum/maximum element in the heap, "top" return the minimum/maximum element.

What is heapify?

• Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].

What if there is a lot of solutions?

• Return any of them.

完整参考代码

基于 Siftup 的版本 $O(nlogn)$

Java版本：

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftup(int[] A, int k) {
        while (k != 0) {
            int father = (k - 1) / 2;
            if (A[k] > A[father]) {
                break;
            }
            int temp = A[k];
            A[k] = A[father];
            A[father] = temp;
            
            k = father;
        }
    }
    
    public void heapify(int[] A) {
        for (int i = 0; i < A.length; i++) {
            siftup(A, i);
        }
    }
}

Python版本：

import sys
import collections
class Solution:
    # @param A: Given an integer array
    # @return: void
    def  siftup(self, A, k):
        while k != 0:
            father = (k - 1) // 2
            if A[k] > A[father]:
                break
            temp = A[k]
            A[k] = A[father]
            A[father] = temp
            
            k = father
    def heapify(self, A):
        for i in range(len(A)):
            self.siftup(A, i)

算法思路：

1. 对于每个元素A[i]，比较A[i]和它的父亲结点的大小，如果小于父亲结点，则与父亲结点交换。
2. 交换后再和新的父亲比较，重复上述操作，直至该点的值大于父亲。

时间复杂度分析

1. 对于每个元素都要遍历一遍，这部分是 $O(n)$。
2. 每处理一个元素时，最多需要向根部方向交换 $logn$ 次。

因此总的时间复杂度是 $O(nlogn)$

基于 Siftdown 的版本 $O(n)$

Java版本：

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    private void siftdown(int[] A, int k) {
        while (k * 2 + 1 < A.length) {
            int son = k * 2 + 1;   // A[i] 的左儿子下标。
            if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])
                son = k * 2 + 2;     // 选择两个儿子中较小的。
            if (A[son] >= A[k])      
                break;
            
            int temp = A[son];
            A[son] = A[k];
            A[k] = temp;
            k = son;
        }
    }
    
    public void heapify(int[] A) {
        for (int i = (A.length - 1) / 2; i >= 0; i--) {
            siftdown(A, i);
        }
    }
}

Python版本：

import sys
import collections
class Solution:
    # @param A: Given an integer array
    # @return: void
    def siftdown(self, A, k):
        while k * 2 + 1 < len(A):
            son = k * 2 + 1    #A[i]左儿子的下标
            if k * 2 + 2 < len(A) and A[son] > A[k * 2 + 2]:
                son = k * 2 + 2    #选择两个儿子中较小的一个
            if A[son] >= A[k]:
                break
                
            temp = A[son]
            A[son] = A[k]
            A[k] = temp
            k = son
    
    def heapify(self, A):
        for i in range(len(A) - 1, -1, -1):
            self.siftdown(A, i)

算法思路：

1. 初始选择最接近叶子的一个父结点，与其两个儿子中较小的一个比较，若大于儿子，则与儿子交换。
2. 交换后再与新的儿子比较并交换，直至没有儿子。
3. 再选择较浅深度的父亲结点，重复上述步骤。

时间复杂度分析

这个版本的算法，乍一看也是 $O(nlogn)$， 但是我们仔细分析一下，算法从第 n/2 个数开始，倒过来进行 siftdown。也就是说，相当于从 heap 的倒数第二层开始进行 siftdown 操作，倒数第二层的节点大约有 n/4 个， 这 n/4 个数，最多 siftdown 1次就到底了，所以这一层的时间复杂度耗费是 $O(n/4)$，然后倒数第三层差不多 n/8 个点，最多 siftdown 2次就到底了。所以这里的耗费是 O(n/8 * 2), 倒数第4层是 O(n/16 * 3)，倒数第5层是 O(n/32 * 4) ... 因此累加所有的时间复杂度耗费为：

T(n) = O(n/4) + O(n/8 * 2) + O(n/16 * 3) ...

然后我们用 2T - T 得到：

2 * T(n) = O(n/2) + O(n/4 * 2) + O(n/8 * 3) + O(n/16 * 4) ... 
T(n)     =          O(n/4)     + O(n/8 * 2) + O(n/16 * 3) ...

2 * T(n) - T(n) = O(n/2) +O (n/4) + O(n/8) + ...
                = O(n/2 + n/4 + n/8 + ... )
                = O(n)

因此得到 T(n) = 2 * T(n) - T(n) = O(n)

Lintcode 126. Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

• The root is the maximum number in the array
• The left subtree and right subtree are the max trees of the subarray divided by the root number.

Construct the max tree by the given array.

Example

Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

    6
   / \
  5   3
 /   / \
2   0   1

Challenge

O(n) time and memory.

Solution:
For any node x of the array, its parent must be the first number greater than it. 
– ….., L, <X, …,<X, X, <X, …, <X, R,…
– 如果L<R，[L, R]里一定R先做根。然后[L, R)里L先做根，然后就是X
– 如果L>R， [L, R]里一定L先做根。然后(L, R]里R先做根，然后就是X
• 如何找到每个值左右第一个比它大的值？
– 单调递减栈

Code (Java)

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(new TreeNode(A[0]));

        for (int i = 1; i < A.length; i++) {
            TreeNode curr = new TreeNode(A[i]);
            while (!stack.isEmpty() && curr.val > stack.peek().val) {
                TreeNode top = stack.pop();
                if (stack.isEmpty() || curr.val < stack.peek().val)  {
                    curr.left = top;
                } else {
                    stack.peek().right = top;
                }
            }
            stack.push(curr);
        }

        // now the stack is a mono descreasing stack
        //
        while (stack.size() > 1) {
            TreeNode top = stack.pop();
            stack.peek().right = top;
        }

        return stack.pop();
    }
}

Lintcode 364. Trapping Rain Water II

Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.

Example

Given 5*4 matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]

return 14.

Code (Java)

public class Solution {
    /**
     * @param heights: a matrix of integers
     * @return: an integer
     */
    public int trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int m = heights.length;
        int n = heights[0].length;

        PriorityQueue<Pair> pq = new PriorityQueue<>(new MyPairComparator());
        boolean[][] visited = new boolean[m][n];

        // step 1: put borders into the pq
        //
        for (int i = 0; i < n; i++) {
            pq.offer(new Pair(0, i, heights[0][i]));
            visited[0][i] = true;

            pq.offer(new Pair(m - 1, i, heights[m - 1][i]));
            visited[m - 1][i] = true;
        }

        for (int i = 1; i < m - 1; i++) {
            pq.offer(new Pair(i, 0, heights[i][0]));
            visited[i][0] = true;

            pq.offer(new Pair(i, n - 1, heights[i][n - 1]));
            visited[i][n - 1] = true;
        }
        
        int ans = 0;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!pq.isEmpty()) {
            Pair top = pq.poll();

            for (int i = 0; i < 4; i++) {
                int nx = top.x + dirs[i][0];
                int ny = top.y + dirs[i][1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    ans += Math.max(0, top.val - heights[nx][ny]);
                    pq.offer(new Pair(nx, ny, Math.max(top.val, heights[nx][ny])));
                }
            }
        }

        return ans;
    }
}

class Pair {
    int x;
    int y;
    int val;

    public Pair(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

class MyPairComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair a, Pair b) {
        return a.val - b.val;
    }
}