完成度最高的周賽了，主要是這周的周賽題目偏水~ 正常應(yīng)該是會卡一題。剛開始的時候被同事拉去對接口了，導致時間沒有把握住热鞍。正常開賽的時候應(yīng)該就超時了。
這次還有一個區(qū)別是衔彻，首次嘗試直接在面板上code薇宠。不使用編譯器調(diào)試，感覺快了很多艰额。
屏幕快照 2018-11-19 下午7.14.20.png
前三題就不說了澄港，水題~
Valid Mountain Array
直接枚舉最高點，遍歷驗證即可
Delete Columns to Make Sorted
直接遍歷行柄沮，發(fā)現(xiàn)是非法數(shù)據(jù)累加即可回梧。 Medium通過率比Easy還高，難度標簽不太準確~
DI String Match
簡單貪心祖搓，每次I插入當前最小值狱意，每次D插入當前最大值
Delete Columns to Make Sorted
這題展開講一下：
題目大意：給定一個字符串列表，求一個最小字符串拯欧。使列表中所有的字符串都是它的子串
注意數(shù)據(jù)規(guī)模：
1 <= A.length <= 12
1 <= A[i].length <= 20
這里因為數(shù)據(jù)規(guī)模較小详囤，我直接采用暴力廣度優(yōu)先搜索。
以string - index 狀態(tài)表示當前搜索狀態(tài)镐作，index為 (1<<A.length)-1最終狀態(tài)藏姐，表示A列表中所有字符串都為當前string的子串。
注意每加入一個字符串该贾，先查找一下是否是當前子串羔杨。再進行首尾合并，優(yōu)先壓入合并最短的字符串杨蛋。
因為廣度優(yōu)先搜索兜材，先到最終狀態(tài)的string未必是最優(yōu)解理澎。所以我一開始等隊列全部出完(感覺應(yīng)該不會超時)。护姆。矾端。結(jié)果TL了掏击。
后面卵皂，將隊列改為優(yōu)先隊列 就過了。
class Solution {
public:
string mergeAB(const string a,const string b){
if(a.length() < 1) return b;
if(b.length() < 1) return a;
string ab = a + b;
string mn = a;
string mx = b;
for(auto npos = mn.length(); npos > 0 ; --npos){
if(npos <= mx.length() && mn.substr(mn.length() - npos, npos) == mx.substr(0, npos)){
ab = mn + mx.substr(npos, mx.length() - npos);
break;
}
}
return ab;
}
string mergeStr(const string a, const string b){
if(a.find(b) != string::npos) return a;
if(b.find(a) != string::npos) return b;
string ab = mergeAB(a,b);
string ba = mergeAB(b,a);
return ab.length() < ba.length() ? ab : ba;
}
string shortestSuperstring(vector<string>& A) {
typedef pair<string, int> state;
int n = A.size();
auto cmp = [](const state a,const state b){
return a.first.length() > b.first.length();
};
priority_queue<state, vector<state>, decltype(cmp)> Q(cmp);
vector<int> vis(1<<n, INT_MAX);
string ans;
for(auto i=0;i<A.size();++i){
Q.push(make_pair(A[i], 1<<i));
vis[1<<i] = true;
ans += A[i];
}
while(!Q.empty()){
state now = Q.top();
Q.pop();
if(now.second == (1<<n) -1) {
return now.first;
}
for(int i=0;i<A.size();++i){
state nxt = now;
nxt.second = now.second | (1<<i);
nxt.first = mergeStr(now.first, A[i]);
if(nxt.first.length() < vis[nxt.second]){
vis[nxt.second] = nxt.first.length();
Q.push(nxt);
}
}
}
return ans;
}
};
