naoya_t@hatenablog

いわゆるチラシノウラであります

LeetCode Weekly Contest 117

12/30(日) 11:30-13:00
3-5-6-8
4完3ペナで111/3425位
レート微増 (2252→2263)
f:id:n4_t:20190102175542p:plain

Q1 - Univalued Binary Tree (3)

はい
Run Codeがぐるぐる回って帰ってこなかったけど2問目解いてた
→AC 05:26

class Solution {
    bool same(TreeNode* node, int v) {
        if (!node) return true;
        if (node->val != v) return false;
        return (same(node->left, v) && same(node->right, v));
    }
public:
    bool isUnivalTree(TreeNode* root) {
        int v = root->val;
        return (same(root->left, v) && same(root->right, v));
    }
};

Q2 - Numbers With Same Consecutive Differences (5)

  • 1桁なのに0がなくてWA
  • Kが0のときに同じやつが重複して入っててWA

→AC 18:33 (+p2)

// 略
class Solution {
public:
    vector<int> numsSameConsecDiff(int N, int K) {
        vector<vi> q, q2;
        for(int i=0;i<=9;++i) q.pb(vi{i});
        rep(i,N-1){
            q2.clear();
            for(vi& x:q) {
                int l = x.back();
                x.pb(-1);
                if (IN(l-K, 0, 9)){
                    x.back() = l-K;
                    q2.pb(x);
                }
                if (IN(l+K, 0, 9)){
                    x.back() = l+K;
                    q2.pb(x);
                }
            }
            swap(q, q2);
        }

        sort(ALL(q));

        set<int> tmp;
        for(vi& x:q){
            int y = 0;
            int leading_zeros = 0;
            rep(k,N){
                if (x[k]==0) {
                    if (k==0) leading_zeros = 1;
                    else if (x[k-1]==0) ++leading_zeros;
                }
                y = y*10 + x[k];
            }
            if (N!=1 && leading_zeros!=0) continue;
            tmp.insert(y);
        }
        vector<int> ans(ALL(tmp));
        return ans;
    }
};

Q3 (6)

  • wordlistの単語をそのまま放り込んだsetにクエリ文字列qがそのまま入ってればそのまま
  • wordlistの各単語をtolowerしたやつ→元のやつの対応をmapに放り込んだ中にqをtolowerしたやつが入ってれば元のやつを
  • wordlistの各単語をtolowerした上で母音を伏せ字にしたやつ→元のやつの対応をmapに放り込んだ中にqをtolowerした上で母音を伏せ字にしたやつが入っていれば元のやつを
  • さもなければ空文字列

文字列処理実装めどいpythonで書けばよかった)
→AC 40:15

// 略
string lower(string& s) {
    int L = s.size();
    vector<char> tmp(L);
    rep(i,L) tmp[i] = tolower(s[i]);
    return string(ALL(tmp));
}
inline bool isvowel(char c) {
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
string lowerxx(string& s) {
    int L = s.size();
    vector<char> tmp(L);
    rep(i,L) {
        tmp[i] = tolower(s[i]);
        if (isvowel(tmp[i])) tmp[i] = '%';
    }
    return string(ALL(tmp));
}

class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        int W = wordlist.size();
        int Q = queries.size();
        vs ans(Q, "");
        vi ad(Q, 0);

        set<string> exact(ALL(wordlist));
        rep(q,Q) {
            if (found(exact, queries[q])) {
                ans[q] = queries[q];
                ad[q]++;
            }
        }

        map<string, string> caps;
        rep(w,W) {
            string lw = lower(wordlist[w]);
            if (found(caps, lw)) continue;
            caps[lw] = wordlist[w];
        }
        rep(q,Q) {
            if (ad[q]) continue;
            string lw = lower(queries[q]);
            if (found(caps, lw)) {
                ans[q] = caps[lw];
                ad[q]++;
            }
        }

        map<string, string> vows;
        rep(w,W) {
            string lw = lowerxx(wordlist[w]);
            if (found(vows, lw)) continue;
            vows[lw] = wordlist[w];
        }
        rep(q,Q) {
            if (ad[q]) continue;
            string lw = lowerxx(queries[q]);
            if (found(vows, lw)) {
                ans[q] = vows[lw];
                ad[q]++;
            }
        }

        return ans;
    }
};

Q4 - Binary Tree Cameras (8)

木DPするだけなんだけど
・あるノードにカメラを設置している場合
・設置していないけど子がいて、少なくとも子のどちらかにカメラが設置されているのでOKな場合
・設置していなくて、子がいたとしても子のどちらにもカメラが設置されていない(が子は孫にカバーされている)場合
の3つの値をかき集める感じで
子(左右)の有無の条件が最初に書いたやつではカバーされていなくてWA
直してAC 1:15:29(+p1)

// 略
#define INFTY 9999

class Solution {
    vi sub(TreeNode* root) {
        // int l_have=INFTY, l_ok=INFTY, l_needed=INFTY;
        // int r_have=INFTY, r_ok=INFTY, r_needed=INFTY;
        if (!root->left && !root->right) {
            return vi{ 1, INFTY, 0 };
        }

        vi left;
        if (root->left) {
            left = sub(root->left);
        } else {
            left = vi { INFTY, 0, INFTY };
        }
        vi right;
        if (root->right) {
            right = sub(root->right);
        } else {
            right = vi { INFTY, 0, INFTY };
        }

        int lmin = *min_element(ALL(left));
        int rmin = *min_element(ALL(right));

        vi res(3, INFTY);

        res[0] = 1 + lmin + rmin;

        if (left[0] < INFTY && right[0] < INFTY) {
            res[1] = min(res[1], 0 + left[0] + min(right[0],right[1]));
            res[1] = min(res[1], 0 + min(left[0],left[1]) + right[0]);
        }
        else if (left[0] < INFTY && !root->right) {
            res[1] = min(res[1], 0 + left[0]);
        }
        else if (!root->left && right[0] < INFTY) {
            res[1] = min(res[1], 0 + right[0]);
        }

        if (left[1] < INFTY && right[1] < INFTY) {
            res[2] = 0 + left[1] + right[1];
        }
        else if (left[1] < INFTY && !root->right) {
            res[2] = min(res[2], 0 + left[1]);
        }
        else if (!root->left && right[1] < INFTY) {
            res[2] = min(res[2], 0 + right[1]);
        }
        return res;
    }
public:
    int minCameraCover(TreeNode* root) {
        vi res = sub(root);
        return min(res[0], res[1]);
    }
};