Skip to content

Latest commit

 

History

History
356 lines (344 loc) · 10.3 KB

9.5.2017(Q126-Q135).md

File metadata and controls

356 lines (344 loc) · 10.3 KB

Questions 125 ~ 135

126, Word Ladder II

This one is pretty difficult. Initially, I used bfs to compute the minimum path length, then use dfs to find all the possible paths. However, this approach runs into TLE.
The successful method is to expand a tree from the beginWord, until at a certain level, endWord appears. During the expansion procedure, every node records its parents, and finally we can use back track to find all the paths from beginWord to endWord.
It took me plenty of time.
typedef unordered_set<string> us;
typedef vector<string> vs;
typedef pair<string,int> si;
class Solution {
    unordered_map<string, vs> dic, par;
    void dfs(vector<vs> &ans, vs cur, string bw){
        string tail = cur[(int)cur.size()-1];
        if(tail == bw){
            reverse(cur.begin(),cur.end());
            ans.push_back(cur);
            return;
        }
        for(auto s:par[tail]){
            cur.push_back(s);
            dfs(ans,cur,bw);
            cur.pop_back();
        }
    }
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vs> ans;
        for(auto w:wordList) dic[w] = vs();
        if(!dic.count(endWord)) return ans;
        dic[beginWord] = vs();
        par[beginWord] = vs();
        for(auto w:dic){
            auto key = w.first;
            for(int i=0;i<(int)key.size();++i){
                string tmp = key;
                for(char c='a';c<='z';++c) if(c!=key[i]){
                    tmp[i]=c;
                    if(dic.count(tmp)) dic[key].push_back(tmp);
                }
            }
        }
        queue<si> que;
        que.push(si(beginWord,0));
        int L = 0;
        bool ok = true;
        while(!que.empty() && ok){
            unordered_map<string,vs> tmpmap;
            while(!que.empty() && que.front().second == L){
                auto sc = que.front();
                que.pop();
                string parent = sc.first;
                for(auto s:dic[parent]) if(!par.count(s)){
                    if(!tmpmap.count(s)) {
                        tmpmap[s] = vs{parent};
                        que.push(si(s,L+1));
                    }
                    else tmpmap[s].push_back(parent);
                    if(s == endWord) ok = false;
                }
            }
            for(auto p:tmpmap) par[p.first] = p.second;
            ++L;
        }
        if(ok) return ans;
        dfs(ans,vs{endWord},beginWord);
        return ans;
    }
};

127, Word Ladder

This one is much easier than the other: just simply use bfs.
typedef unordered_set<string> us;
typedef vector<string> vs;
typedef pair<string,int> si;
class Solution {
    unordered_map<string, vs> dic;
    int minLength(string bw, string ew){
        us used;
        queue<si> que;
        que.push(si(bw,1));
        used.insert(bw);
        while(!que.empty()){
            string current = que.front().first;
            int curl = que.front().second;
            que.pop();
            for(auto s:dic[current]) if(!used.count(s)){
                if(s == ew) return curl+1;
                used.insert(s);
                que.push(si(s,curl+1));
            }
        }
        return 0;
    }
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for(auto s:wordList) dic[s] = vs();
        if(!dic.count(endWord)) return 0;
        dic[beginWord] = vs();
        for(auto p:dic){
            auto key = p.first;
            for(int i=0;i<(int)key.size();++i){
                char c = key[i];
                string dup = key;
                for(char ch='a';ch<='z';++ch) if(ch!=c){
                    dup[i] = ch;
                    if(dic.count(dup)) dic[key].push_back(dup);
                }
            }
        }
        return minLength(beginWord,endWord);
        
    }
};

128, Longest Consecutive Sequence

I am curious, why this is hard. 1, put numbers into a unordered_set; 2, pick a number, and search along both directions.
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> U(nums.begin(),nums.end());
        int ans = 0;
        while(!U.empty()){
            int pivat = *U.begin();
            U.erase(pivat);
            int l = 0, r = 0;
            while(pivat+r<INT_MAX && U.count(pivat+r+1)){
                U.erase(pivat+r+1);
                ++r;
            }
            while(pivat-l>INT_MIN && U.count(pivat-l-1)){
                U.erase(pivat-l-1);
                ++l;
            }
            ans = max(ans,1+r+l);
        }
        return ans;
    }
};

129, Sum Root to Leaf Numbers

Simple dfs, nothing special to say
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    inline bool isLeaf(TreeNode *r){ return r && !r->left && !r->right; }
    void dfs(int &sum,int tmp, TreeNode *r){
        tmp = tmp*10 + r->val;
        if(isLeaf(r)){
            sum += tmp;
            return;
        }
        if(r->left) dfs(sum,tmp,r->left);
        if(r->right) dfs(sum,tmp,r->right);
        return;
    }
public:
    int sumNumbers(TreeNode* root) {
        if(!root) return 0;
        int ans = 0;
        dfs(ans,0,root);
        return ans;
    }
};

130, Surrounded Regions

You can use dfs or bfs, whatever you like. I used BFS in this question.
class Solution {
    int di[4] = {1,-1,0,0};
    int dj[4] = {0,0,1,-1};
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty() || board[0].empty()) return;
        int n = (int)board.size(), m = (int)board[0].size();
        unordered_set<int> out;
        queue<int> que;
        for(int i=0;i<n;++i) for(int j=0;j<m;j+=max(1,m-1)) if(board[i][j]=='O'){
            que.push(i*m+j);
            out.insert(i*m+j);
        }
        for(int j=1;j<m-1;++j) for(int i=0;i<n;i+=max(1,n-1)) if(board[i][j]=='O'){
            que.push(i*m+j);
            out.insert(i*m+j);
        }
        while(!que.empty()){
            int i = que.front()/m, j = que.front()%m;
            que.pop();
            for(int k=0;k<4;++k){
                int ii = i+di[k], jj = j+dj[k];
                if(ii>=0 && ii<n && jj>=0 && jj<m && !out.count(ii*m+jj) && board[ii][jj]=='O'){
                    out.insert(ii*m+jj);
                    que.push(ii*m+jj);
                }
            }
        }
        for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(board[i][j]=='O' && !out.count(i*m+j)) board[i][j] = 'X';
        return;
    }
};

131, Palindrome Partitioning

Nothing special, just using a simple dfs
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<int> vi;
class Solution {
    int n;
    vector<vi> dic;
    void dfs(vector<vs> &ans,string &s, vs &cur, int i){
        if(i>=n){
            ans.push_back(cur);
            return;
        }
        for(auto j:dic[i]){
            cur.push_back(s.substr(i,j-i+1));
            dfs(ans,s,cur,j+1);
            cur.pop_back();
        }
        return;
    }
public:
    vector<vector<string>> partition(string s) {
        n = (int)s.size();
        vector<vb> dp(n,vb(n,true));
        for(int l=1;l<n;++l) for(int i=0;i+l<n;++i){
            dp[i][i+l] = dp[i+1][i+l-1] && (s[i]==s[i+l]);
        }
        dic.resize(n);
        for(int i=0;i<n;++i) for(int j=i;j<n;++j) if(dp[i][j]) dic[i].push_back(j);
        vector<vs> ans;
        vs cur;
        dfs(ans,s,cur,0);
        return ans;
    }
};

132. Palindrome Partitioning II

using bfs to find the shortest path from the beginning to the end. Every step of the move has to span a palindrome
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int,int> ii;
class Solution {
public:
    int minCut(string s) {
        int n = (int)s.size();
        vector<vi > opt(n);
        opt[n-1]={n-1,n};
        for(int j=n-2;j>=0;--j){
            opt[j]={j,j+1};
            for(auto k:opt[j+1]) if(k<n && s[j]==s[k]) opt[j].push_back(k+1);
        }
        queue<ii> que;
        vb used(n,false);
        used[0] = true;
        que.push(ii(0,0));
        while(!que.empty()){
            int i = que.front().first, cut = que.front().second;
            que.pop();
            for(auto j: opt[i]) if(!used[j]){
                if(j>=n) return cut;
                que.push(ii(j,cut+1));
                used[j]=true;
            }
        }
        return n;
    }
};

133. Clone Graph

Using map
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
    unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> dp;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        if(dp.count(node)) return dp[node];
        dp[node] = new UndirectedGraphNode(node->label);
        for(auto p:node->neighbors) dp[node]->neighbors.push_back(cloneGraph(p));
        return dp[node];
    }
};

134. Gas Station

Find the minimum of the subtraction array
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = (int)gas.size(), ans = 0, sum = gas[0]-cost[0];
        for(int i=1,mSum = 0;i<n;sum += gas[i] - cost[i], ++i) if(sum<mSum) {mSum = sum, ans = i;}
        return sum>=0? ans:-1;
    }
};

135. Candy

Count valley and peaks
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size(), sum = 0;
        for(int i=0,peak = 0;i<n;++i){
            if((i==0 || ratings[i]<=ratings[i-1]) && (i==n-1 || ratings[i]<=ratings[i+1])){
                sum += 1;
                int j = i-1, lvl = 2;
                while(j>=0 && ratings[j]>ratings[j+1]){
                    if(j && ratings[j]>ratings[j-1]) sum += max(peak,lvl++) - peak;
                    else sum += lvl++;
                    --j;
                }
                j = i+1;
                lvl = 1;
                while(j<n && ratings[j]>ratings[j-1]){
                    sum += 1+lvl++;
                    ++j;
                }
                peak = lvl;
                i = j-1;
            }
        }
        return sum;
    }
};