Leetcode Contest 111

Leetcode Contest 111

完成度最高的周赛了，主要是这周的周赛题目偏水~ 正常应该是会卡一题。刚开始的时候被同事拉去对接口了，导致时间没有把握住。正常开赛的时候应该就超时了。

这次还有一个区别是，首次尝试直接在面板上code。不使用编译器调试，感觉快了很多。

屏幕快照 2018-11-19 下午7.14.20.png

前三题就不说了，水题~

Valid Mountain Array

直接枚举最高点，遍历验证即可

Delete Columns to Make Sorted

直接遍历行，发现是非法数据累加即可。 Medium通过率比Easy还高，难度标签不太准确~

DI String Match

简单贪心，每次I插入当前最小值，每次D插入当前最大值

Delete Columns to Make Sorted

这题展开讲一下：

题目大意：给定一个字符串列表，求一个最小字符串。使列表中所有的字符串都是它的子串

注意数据规模：

1 <= A.length <= 12
1 <= A[i].length <= 20

这里因为数据规模较小，我直接采用暴力广度优先搜索。
以string - index 状态表示当前搜索状态，index为 (1<<A.length)-1最终状态，表示A列表中所有字符串都为当前string的子串。

注意每加入一个字符串，先查找一下是否是当前子串。再进行首尾合并，优先压入合并最短的字符串。

因为广度优先搜索，先到最终状态的string未必是最优解。所以我一开始等队列全部出完(感觉应该不会超时)。。。结果TL了。

后面，将队列改为优先队列 就过了。

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;
    }
};