本系列将探讨算法的优化。
时间复杂度对算法的选择
时间优化
思维的改进
LCP08.剧情触发时间
最开始的想法同时考虑三个属性，每到新的一天就遍历requirements数组，看能否有剧情出发，果不其然超时了，最后两个样例没通过
之后进行改进。
首先如果只考虑一种属性，显然我们只需要计算每一天的属性情况，最后对于所有的requirements 都在属性列表中进行二分查找（现在只有一种属性了)，就能知道他是在哪一天完成的了。
但这道题实际上，每一种属性的满足是互相独立的。
简单来说，对于一个剧情要求 (C, R, H) 来说，假设 C 要求是在第 x 天满足的，R要求是在第 y 天满足的，H 要求是在第 z 天满足的。那么该剧情的满足时间为：
t=max(x,y,z)
原始代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
int res[3]={0};
int day=increase.size();
vector<int>end(requirements.size(),-1);
for(int i=0;i<day;i++){
for(int j=0;j<3;j++){
res[j]+=increase[i][j];
}
for(int m=0;m<requirements.size();m++){
if(end[m]!=-1)continue;
int count=0;
int count1=0;
for(int n=0;n<3;n++){
if(res[n]>=requirements[m][n])
count++;
if(requirements[m][n]==0)
count1++;
}
if(count1==3){
end[m]=0;
continue;
}
if(count==3)
end[m]=i+1;
}
}
return end;
}
};
|
改进代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
vector<int> C(increase.size() + 1, 0);
vector<int> R(increase.size() + 1, 0);
vector<int> H(increase.size() + 1, 0);
for (int i = 0; i < increase.size(); ++i)
{
C[i + 1] = C[i] + increase[i][0];
R[i + 1] = R[i] + increase[i][1];
H[i + 1] = H[i] + increase[i][2];
}
vector<int> ret;
int maxlen = C.size();
for (int i = 0; i < requirements.size(); i++)
{
int lbc = lower_bound(C.begin(), C.end(), requirements[i][0]) - C.begin();
int lbr = lower_bound(R.begin(), R.end(), requirements[i][1]) - R.begin();
int lbh = lower_bound(H.begin(), H.end(), requirements[i][2]) - H.begin();
if (lbc == maxlen || lbr == maxlen || lbh == maxlen)
{
ret.emplace_back(-1);
}
else
{
ret.emplace_back(max(max(lbc, lbr), lbh));
}
}
return ret;
}
};
|
代码简洁优化
- 检查单词是否为句中其他单词的前缀
使用字符串流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| ```
```c++
class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
stringstream ssin(sentence);
string word;
for(int i =1;ssin>>word;i++){
if(word.substr(0,searchWord.size())==searchWord)
return i;
}
return -1;
}
};
|
判断是否包括元音字母？
最原始思路
1
2
3
4
5
6
7
8
9
| int de(char c){
if(c=='a')return 1;
if(c=='e')return 1;
if(c=='i')return 1;
if(c=='o')return 1;
if(c=='u')return 1;
return 0;
}
de(c)
|
哈希表:
1
2
3
| unordered_set<char>S({'a','e','i','o','u'});
S.count(c);
|
参考资料：
https://www.acwing.com/blog/content/32/
