38 外观数列
简单粗暴,效果也不太好
time: 18.22%, memory: 5.05%
class Solution {
public:
string countAndSay(int n) {
string cur_array = "1";
while(--n){
string tmp = "";
char c = cur_array[0];
int cnt = 1;
for(int i = 1; i < cur_array.size(); i++){
if(cur_array[i] == c){
cnt++;
}
else{
tmp = tmp + to_string(cnt);
tmp = tmp + c;
c = cur_array[i];
cnt = 1;
}
}
tmp = tmp + to_string(cnt);
tmp = tmp + c;
cur_array = tmp;
}
return cur_array;
}
};
14 最长公共子前缀
还是最简单的做法,以第一个字符串作为初始前缀,逐个比较得到公共子前缀。做了一步优化,先选出最短的字符串作为初始前缀,然后再比较,能从20ms优化到16ms。如果能先根据字符串长度做一下排序,可能会更快。
代码:
time: 7.31%, memory: 5.02%
class Solution {
public:
string get_prefix(string s1, string s2){
int i = 0, j = 0;
string prefix = "";
while(i < s1.size() && j < s2.size() && s1[i] == s2[j]){
prefix = prefix + s1[i];
i++;
j++;
}
return prefix;
}
string longestCommonPrefix(vector<string>& strs) {
if(strs.size() == 0) return "";
int min_len = strs[0].size(), idx = 0;
for(int i = 1; i < strs.size(); i++){
if(strs[i].size() < min_len) {
min_len = strs[i].size();
idx = i;
}
}
string pre = strs[idx];
for(int i = 0; i < strs.size(); i++){
if(i == idx) continue;
pre = get_prefix(pre, strs[i]);
if(pre == "") break;
}
return pre;
}
};
网友评论