狗家昂赛特

catinclay · 2016-11-19 00:01:03

fay19 发表于 2016-11-18 12:59
感谢楼主，那这样的话dfs是可以做出来的，我前几天看到别的人的面经有这个题，今天刚写了一个dfs的，test ...

求dfs思路...感谢

zhan1612 · 2016-11-19 13:13:59

发一下第三题的encode，但是感觉不优化，咱们讨论下看看有没有更好的办法

复制代码

zhan1612 · 2016-11-19 13:19:29

刚刚代码没沾上，不知道怎么了。发一下第三题的encode，但是感觉不优化，咱们讨论下看看有没有更好的办法

//这里可以优化一下，用KMP算法提前对string预处理，也就是在string shortestEncodeString(string s)这个函数开始的时候预处理一下
bool checkRepeating(string& s, int l, int r, int start, int end){
if((end-start+1)%(r-l+1) != 0)
return false;
int len = r-l+1;
bool res = true;
for(int i=start; i<=end; i++){
if(s[(i-start)%len+l] != s[i]){
res = false;
break;
}
}
return res;
}
int getLength(int l1, int l2){
return (int)(log10(l2/l1+1)+1);
}
string shortestEncodeString(string s){
int len = s.length();
、、也就是在这个地方用kmp进行一下预处理
vector< vector<int> > res(len, vector<int>(len, 0));
for(int i=0; i<len; i++){
for(int j=0; j<=i; j++){
res[j][i] = i-j+1;
}
}
unordered_map<string, string> record;
for(int i=0; i<len; i++){
for(int j=i; j>=0; j--){
string temp = s.substr(j, i-j+1);
if(record.find(temp) != record.end()){
res[j][i] = record[temp].size();
continue;
}
string ans = temp;
for(int k=j; k<i; k++){
string str1 = s.substr(j, k-j+1);
string str2 = s.substr(k+1, i-k);
if(res[j][i] > res[j][k] + res[k+1][i]){
res[j][i] = res[j][k]+res[k+1][i];
ans = record[str1] + record[str2];
}
if(checkRepeating(s, j, k, k+1, i) == true && res[j][i] > 2+getLength(k-j+1, i-k)+res[j][k]){ //如果有与处理的话可以o(1) 的时间知道要不要进入这个if，现在是用函数比较，o(n).
res[j][i] = 2+getLength(k-j+1, i-k)+res[j][k];
ans = to_string((i-j+1)/(k-j+1)) + '[' + record[str1] +']';
}
}
record[temp] = ans;
}
}
return record[s];
}

复制代码

zhan1612 · 2016-11-19 13:22:23

我也是醉了，这次没空格，不好意思啊。怎么删回复啊····再贴一次吧，不要打我啊····

bool checkRepeating(string& s, int l, int r, int start, int end){
if((end-start+1)%(r-l+1) != 0)
return false;
int len = r-l+1;
bool res = true;
for(int i=start; i<=end; i++){
if(s[(i-start)%len+l] != s[i]){
res = false;
break;
}
}
return res;
}
int getLength(int l1, int l2){
return (int)(log10(l2/l1+1)+1);
}
string shortestEncodeString(string s){
int len = s.length();
vector< vector<int> > res(len, vector<int>(len, 0));
for(int i=0; i<len; i++){
for(int j=0; j<=i; j++){
res[j][i] = i-j+1;
}
}
unordered_map<string, string> record;
for(int i=0; i<len; i++){
for(int j=i; j>=0; j--){
string temp = s.substr(j, i-j+1);
if(record.find(temp) != record.end()){
res[j][i] = record[temp].size();
continue;
}
string ans = temp;
for(int k=j; k<i; k++){
string str1 = s.substr(j, k-j+1);
string str2 = s.substr(k+1, i-k);
if(res[j][i] > res[j][k] + res[k+1][i]){
res[j][i] = res[j][k]+res[k+1][i];
ans = record[str1] + record[str2];
}
if(checkRepeating(s, j, k, k+1, i) == true && res[j][i] > 2+getLength(k-j+1, i-k)+res[j][k]){
res[j][i] = 2+getLength(k-j+1, i-k)+res[j][k];
ans = to_string((i-j+1)/(k-j+1)) + '[' + record[str1] +']';
}
}
record[temp] = ans;
}
}
return record[s];
}

复制代码

linjin · 2016-11-19 13:34:49

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fay19 · 2016-11-20 00:50:06

SidneyFan 发表于 2016-11-18 13:22
dfs加一个memory储存见过的string大概就变成dp了吧

恩恩，层主说的有理，我一会加一个hashmap memory一下试试看，感觉可行，谢谢层主

fay19 · 2016-11-20 00:54:28

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fay19 · 2016-11-20 04:28:55

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fay19 · 2016-11-20 04:29:32

catinclay 发表于 2016-11-19 00:01
求dfs思路...感谢

表达能力不好，不知道解释清楚没，不明白可以再留言交流

sunnyroom · 2016-11-23 10:32:25

chestnut9919 发表于 2016-11-18 04:52
第三轮那个跟我一样，原来只是个warm up啊。。怪不得我HC挂了

第三轮时我的电面题； encode没弄出来，电面加面了