版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434648
详细代码可以fork下Github上leetcode项目,不定期更新。
本次周赛主要分为以下4道题:
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:
求连续和的最大值,两种做法,滑动窗口法,和累加和法。
滑动窗口法:
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;
}
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 =undefined “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.undefined 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.undefined So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.
Note:
思路:
模拟CPU的运行任务思路就来了,很简单,当有任务运行时,开始计数,停止计数只可能出现两种状态:
代码如下:
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,比较直观。
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:
在第一题做法的基础上,遍历k到nums.length,求出最大,时间复杂度为O(n2)O(n^2),TLE了,此题技巧性比较强,先用二分搜索解,把问题转换成求符合条件的subArray。什么样的subArray符合条件?
此类问题关键在于求最大的average,所以可以写出公式:
(ai+ai+1+⋯+aj)/(j−i+1)<=ans
(a_i + a_{i + 1} + \cdots + a_j) / (j - i + 1) <= ans
所以,只要找到最大的ans使得对所有的ai到aja_i 到a_j都符合上述约束即可,这就意味着一旦出现:
(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。
令 k = j - i + 1,所以问题转变成:
(ai−ans)+⋯+(aj−ans)>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;
}
符合窗口性质的搜索,大大简化了时间复杂度,或者换句话说,这里充分利用了窗口变动之后,累计计算的一些值,实在是高明。
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)undefined The system have already tracked down the following sentences and their corresponding times:undefined “i love you” : 5 timesundefined “island” : 3 timesundefined “ironman” : 2 timesundefined “i love leetcode” : 2 timesundefined Now, the user begins another search: Operation: input(‘i’)undefined Output: “i love you”, “island”,”i love leetcode”undefined Explanation:undefined 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(’ ‘)undefined Output: “i love you”,”i love leetcode”undefined Explanation:undefined There are only two sentences that have prefix “i “. Operation: input(‘a’)undefined Output: []undefined Explanation:undefined There are no sentences that have prefix “i a”. Operation: input(‘#’)undefined Output: []undefined Explanation:undefined 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:
思路: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;
}
}