LeetCode Weekly Contest 41解题思路

LeetCode Weekly Contest 41解题思路详细代码可以fork下Github上leetcode项目，不定期更新。赛题本次周赛主要分为以下4道题：Leetcode 643. Maximum Average Subarray ILeetcode 636. Exclusive Time of FunctionsLeetcode 644. Maximum Average Su

Demon的黑与白

2047人浏览 · 2017-07-17 18:40:51

Demon的黑与白 · 2017-07-17 18:40:51 发布

LeetCode Weekly Contest 41解题思路

详细代码可以fork下Github上leetcode项目，不定期更新。

赛题

本次周赛主要分为以下4道题：

Leetcode 643. Maximum Average Subarray I

Problem:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

求连续和的最大值，两种做法，滑动窗口法，和累加和法。

滑动窗口法：

    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; ++i){
            sum += nums[i];
        }
        double max = sum / (1.0 * k);
        for (int i = 0; i < nums.length - k; ++i){
            sum -= nums[i];
            sum += nums[i + k];
            max = Math.max(max, sum / (1.0 * k));
        }

        return max;
    }

累加和法：

    public double findMaxAverage(int[] nums, int k) {
        int[] sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; ++i){
            sums[i + 1] = sums[i] + nums[i];
        }
        double max = Double.NEGATIVE_INFINITY;
        for (int i = 0; i + k < sums.length; ++i){
            max = Math.max(max, (sums[i + k] - sums[i]) / (1.0 * k));
        }
        return max;
    }

Leetcode 636. Exclusive Time of Functions

Problem:

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, “0:start:0” means function 0 starts from the very beginning of time 0. “0:end:0” means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example:

Input:
n = 2
logs =
[“0:start:0”,
“1:start:2”,
“1:end:5”,
“0:end:6”]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

Input logs will be sorted by timestamp, NOT log id.
Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
Two functions won’t start or end at the same time.
Functions could be called recursively, and will always end.
1 <= n <= 100

思路：
模拟CPU的运行任务思路就来了，很简单，当有任务运行时，开始计数，停止计数只可能出现两种状态：

当有其他任务插入时，停止计时，此时需要保存当前任务的id，以及计数情况。
当前任务end态，停止计时，此时更新计数值，且让系统返回被切换后的前一个状态。

代码如下：

    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        int[] stack = new int[logs.size() + 2];

        int cur = -1;
        int prev = 0;
        for (String log : logs){
            String[] param = log.split(":");
            int id = Integer.parseInt(param[0]);
            int time = Integer.parseInt(param[2]);

            if (cur == -1){
                stack[++cur] = id;
                continue;
            }
            if (param[1].equals("start")){
                ans[stack[cur]] += (time - prev);
                stack[++cur] = id;
            }
            else{
                ans[stack[cur]] += (time - prev + 1);
                time++;
                cur--;
            }
            prev = time;
        }
        return ans;
    }

状态的保留用stack来解决，stack.peek()永远都是当前正在执行的任务，一旦执行完毕的任务，则从stack中pop，比较直观。

Leetcode 644. Maximum Average Subarray II

problem:

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation:
when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.

Note:

1 <= k <= n <= 10,000.
Elements of the given array will be in range [-10,000, 10,000].
The answer with the calculation error less than 10-5 will be accepted.

在第一题做法的基础上，遍历k到nums.length，求出最大，时间复杂度为 $O(n^2)$ ，TLE了，此题技巧性比较强，先用二分搜索解，把问题转换成求符合条件的subArray。什么样的subArray符合条件？

此类问题关键在于求最大的average，所以可以写出公式：

(a i + a i + 1 + \dots + a j) / (j - i + 1) < = a n s

$(a_i + a_{i + 1} + \cdots + a_j) / (j - i + 1) <= ans$

所以，只要找到最大的ans使得对所有的 $a_i 到a_j$ 都符合上述约束即可，这就意味着一旦出现：

(a i + a i + 1 + \dots + a j) / (j - i + 1) > a n s

$(a_i + a_{i + 1} + \cdots + a_j) / (j - i + 1) \gt ans$
即不符合最大average的定义，我们只要在给定ans的情况下，找出这种状态即可，另外一方面，在所有符合状态的ans中，不断扩大ans，即能求出最大的ans。

令 k = j - i + 1，所以问题转变成：

(a i - a n s) + \dots + (a j - a n s) > 0

$(a_i - ans) + \cdots + (aj - ans) \gt 0$
的搜索，这里有了所谓的优化技巧，原本

O(n2) $O(n^2)$ 的复杂度，在这个问题下，可以简化成

O(n) $O(n)$ ，为何？

时间复杂度下降的原因在于，并非需要遍历所有可能的长度，即k从nums.length的每个subArray无需全部遍历。利用滑动窗口可以优化，在窗口增大的过程中，维护一个左侧小于0的subArray，这样得到的sum一定是当前下标下，所有窗口长度的最大sum，代码如下：

    public double findMaxAverage(int[] nums, int k) {
        double lf = -12345, rt = 12345;
        while (rt - lf > 10e-6){
            double mid = (rt + lf) / 2;
            if (check(nums, mid, k)) lf = mid;
            else rt = mid;
        }
        return rt;
    }

    private boolean check(int[] nums, double mid, int k){
        double[] arra = new double[nums.length];
        for (int i = 0; i < nums.length; ++i){
            arra[i] = nums[i] - mid;
        }
        double sum  = 0, pre = 0;
        for (int i = 0; i < k; ++i){
            sum += arra[i];
        }
        if (sum > 0) return true;
        double min = 0.0;
        for (int i = k; i < nums.length; ++i){
            sum += arra[i];
            pre += arra[i - k];
            min = Math.min(min, pre);
            if (sum > min) return true;
        }
        return false;
    }

符合窗口性质的搜索，大大简化了时间复杂度，或者换句话说，这里充分利用了窗口变动之后，累计计算的一些值，实在是高明。

Leetcode 642. Design Search Autocomplete System

Problem:

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character ‘#’). For each character they type except ‘#’, you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
If less than 3 hot sentences exist, then just return as many as you can.
When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
Your job is to implement the following functions:

The constructor function:

AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical data. Sentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.

Now, the user wants to input a new sentence. The following function will provide the next character the user types:

List input(char c): The input c is the next character typed by the user. The character will only be lower-case letters (‘a’ to ‘z’), blank space (’ ‘) or a special character (‘#’). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.

Example:

Operation: AutocompleteSystem([“i love you”, “island”,”ironman”, “i love leetcode”], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
“i love you” : 5 times
“island” : 3 times
“ironman” : 2 times
“i love leetcode” : 2 times
Now, the user begins another search:

Operation: input(‘i’)
Output: [“i love you”, “island”,”i love leetcode”]
Explanation:
There are four sentences that have prefix “i”. Among them, “ironman” and “i love leetcode” have same hot degree. Since ’ ’ has ASCII code 32 and ‘r’ has ASCII code 114, “i love leetcode” should be in front of “ironman”. Also we only need to output top 3 hot sentences, so “ironman” will be ignored.

Operation: input(’ ‘)
Output: [“i love you”,”i love leetcode”]
Explanation:
There are only two sentences that have prefix “i “.

Operation: input(‘a’)
Output: []
Explanation:
There are no sentences that have prefix “i a”.

Operation: input(‘#’)
Output: []
Explanation:
The user finished the input, the sentence “i a” should be saved as a historical sentence in system. And the following input will be counted as a new search.

Note:

The input sentence will always start with a letter and end with ‘#’, and only one blank space will exist between two words.
The number of complete sentences that to be searched won’t exceed 100. The length of each sentence including those in the historical data won’t exceed 100.
Please use double-quote instead of single-quote when you write test cases even for a character input.
Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see here for more details.

思路：trie树，先把字符和频次用Trie树存储，根据prefix找到当前结点，遍历该结点以下的所有可能的字符串，统计top3的频次，代码如下：

public class AutocompleteSystem {

    class TrieNode{
        TrieNode[] children = new TrieNode[32];
        String str;
        int times;
    }

    public TrieNode add(TrieNode root, String str, int times){
        char[] cs = str.toCharArray();
        if (root == null) root = new TrieNode();
        TrieNode cur = root;
        for (char c : cs){
            int pos = 0;
            if (c == ' ') pos = 27;
            else pos = c - 'a';
            if (cur.children[pos] == null) cur.children[pos] = new TrieNode();
            cur = cur.children[pos];
        }
        if (cur.str != null) cur.times += times;
        else cur.times = times;
        cur.str = str;
        return root;
    }

    public TrieNode search(TrieNode root, String prefix){
        TrieNode cur = root;
        for (char c : prefix.toCharArray()){
            int pos = 0;
            if (c == ' ') pos = 27;
            else pos = c - 'a';
            if (cur.children[pos] != null) cur = cur.children[pos];
            else return null;
        }
        return cur;
    }

    TrieNode root;
    String prefix;
    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; ++i){
            root = add(root, sentences[i], times[i]);
        }
        prefix = "";
    }

    public List<TrieNode> bfs(TrieNode cur){
        List<TrieNode> ans = new ArrayList<>();
        if (cur == null) return ans;
        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(cur);
        while (!queue.isEmpty()){
            TrieNode node = queue.poll();
            if (node.str != null) ans.add(node);
            for (int i = 0; i < 32; ++i){
                if (node.children[i] != null) queue.offer(node.children[i]);
            }
        }
        return ans;
    }

    public List<String> input(char c) {
        if (c == '#'){
            root = add(root, prefix, 1);
            prefix = "";
            return new ArrayList<>();
        }
        prefix += c;
        List<TrieNode> candicates = bfs(search(root, prefix));
        Collections.sort(candicates, new Comparator<TrieNode>() {
            @Override
            public int compare(TrieNode o1, TrieNode o2) {
                return o2.times != o1.times ? o2.times - o1.times : o1.str.compareTo(o2.str);
            }
        });
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < Math.min(candicates.size(), 3); ++i){
            ans.add(candicates.get(i).str);
        }
        return ans;
    }

}