# LeetCode Weekly Contest 41解题思路

## 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

• 当有其他任务插入时，停止计时，此时需要保存当前任务的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);
int time = Integer.parseInt(param);

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

## 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.

(ai+ai+1+⋯+aj)/(j−i+1)<=ans

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

(ai+ai+1+⋯+aj)/(j−i+1)>ans

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

(ai−ans)+⋯+(aj−ans)>0

(a_i - ans) + \cdots + (aj - ans) \gt 0 的搜索，这里有了所谓的优化技巧，原本O(n2)O(n^2)的复杂度，在这个问题下，可以简化成O(n)O(n)，为何？

```    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.

```public class AutocompleteSystem {

class TrieNode{
TrieNode[] children = new TrieNode;
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){
}
prefix = "";
}

public List<TrieNode> bfs(TrieNode cur){
List<TrieNode> ans = new ArrayList<>();
if (cur == null) return ans;
queue.offer(cur);
while (!queue.isEmpty()){
TrieNode node = queue.poll();
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 == '#'){
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){
}
return ans;
}

}```

0 条评论

• ### LWC 58：724. Find Pivot Index

LWC 58：724. Find Pivot Index 传送门：724. Find Pivot Index Problem: Given an array ...

• ### 算法细节系列（16）：深度优先搜索

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode Weekly Contest 38解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### hdu 2473 Junk-Mail Filter (并查集之点的删除)

Junk-Mail Filter Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/...

• ### CodeForces 666B World Tour(spfa+枚举)

B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

• ### POJ-1276-Cash Machine（多重背包）

Cash Machine Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

• ### 拓扑排序-HDU2647 Reward

什么是拓扑排序？ 简单来说，在做一件事之前必须先做另一(几)件事都可抽象为图论中的拓扑排序，比如课程学习的先后，安排客人座位等。 一个图能拓扑排序的充要条件...

• ### hdu 4009 Transfer water（最小型树图）

Transfer water Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 65768/657...

• ### POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

• ### ZOJ 3204 Connect them

Connect them ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- You have...

### 活动推荐 