naoya_t@hatenablog

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

LeetCode Weekly Contest 110

agwたんの勧めでLeetCodeのコンテスト初挑戦

leetcode.com
11/11(日) 11:30-13:00 JST

早起きしたけど二度寝してて次に起きたら11時過ぎてたけど
開始時間が1時間遅れたお陰(10:30→11:30)で参加できた回

4完 151/3720位
初レーティングは2000
f:id:n4_t:20181115105616p:plain:w640

Q1 - Reorder Log Files (4)

なるほどSRMみたいにクラスのメソッドとして書く方式か
これサンプルデータからテストコードを自動生成する的なやつがほしいな…
(main関数を自分で書いてassert自分で書いたけど面倒い)

アルファベットのやつと数字のやつに分けて、アルファベットのやつはソートもする
splitするの面倒い...(SRM用ライブラリからのコピペだけど)
自動的にC++だったけどこれpython選べる?
→AC 14:19

class Solution {
    vector<string> split(string str, int delim = ' ') {
        vector<string> result;

        const char *s = str.c_str();
        if (delim == ' ') {
            for (const char *p = s; *p; p++) {
                if (*p == delim)
                    s++;
                else
                    break;
            }
            if (!*s) return result;

            for (const char *p = s; *p; p++) {
                if (*p == delim) {
                    if (s < p) {
                        string a(s, p - s);
                        result.push_back(a);
                    }
                    s = p + 1;
                }
            }
            if (*s) result.push_back(s);
        } else {
            for (const char *p = s; *p; p++) {
                if (*p == delim) {
                    string a(s, p - s);
                    result.push_back(a);
                    s = p + 1;
                    if (*s == '\0') result.push_back("");
                }
            }
            if (*s) result.push_back(s);
        }

        return result;
    }

   public:
    vector<string> reorderLogFiles(vector<string> &logs) {
        int n = logs.size();
        vector<string> post;
        vector<pair<string, string>> pre;
        for (int i = 0;  i<n; ++i) {
            vector<string> fs = split(logs[i]);
            char ch = fs[1][0];
            if ('0' <= ch && ch <= '9') {
                post.push_back(logs[i]);
                continue;
            } else {
                pre.push_back(
                    make_pair(logs[i].substr(1 + fs[0].size()), fs[0]));
            }
        }

        vector<string> ans;
        sort(pre.begin(), pre.end());
        for (auto p : pre) {
            ans.push_back(p.second + " " + p.first);
        }
        for (string s : post) {
            ans.push_back(s);
        }
        return ans;
    }
};

Q2 - Range Sum of BST (4)

サンプル用BSTを構築するのを自分で書いてから
実装
なんだ、単にBSTをtraverseできるかって話か(順番は関係ないな)
→AC 28:58

class Solution {
   public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        queue<TreeNode*> q;
        q.push(root);
        int sum = 0;
        while (!q.empty()) {
            TreeNode* n = q.front();
            q.pop();
            // if (n == NULL) continue;
            int nv = n->val;
            if (L <= nv && nv <= R) sum += nv;
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }

        return sum;
    }
};

Q3 - Minimum Area Rectangle (5)

長方形の (x0,x1), (y0,y1) を全部試すとO(N^4) だし当然死亡するよな
x,y座標それぞれについてとりうるyの集合を…ああん
あれ?2つの点を選んで、その2点が対角になるような長方形が存在するか調べる作戦で行けるのでは?多分O(N^2logN)
→AC 47:17

class Solution {
   public:
    int minAreaRect(vector<vector<int>>& points) {
        int n = points.size();
        set<pair<int, int>> s;
        for (int i = 0; i < n; ++i) {
            s.insert(make_pair(points[i][0], points[i][1]));
        }

        int best = 0x7fffffff;

        for (int i = 0; i < n - 1; ++i) {
            int x0 = points[i][0], y0 = points[i][1];

            for (int j = i + 1; j < n; ++j) {
                int x1 = points[j][0], y1 = points[j][1];
                int area = abs(x1 - x0) * abs(y1 - y0);
                if (area == 0) continue;

                pair<int, int> q(x0, y1), r(x1, y0);
                if (s.find(q) == s.end()) continue;
                if (s.find(r) == s.end()) continue;

                best = min(best, area);
            }
        }

        if (best == 0x7fffffff) best = 0;
        return best;
    }
};

Q4 - Distinct Subsequences II (7)

うーん
DPで解けるってことだよなきっと

a,bまで来て次にaが来たとき
・空文字列の末尾にaを追加 → {a}
・最初のaまでで作れた文字列 {a} に aを追加 → {aa}
・次のbまでで作れた文字 {b} にaを追加 → {ba}
で、ここから {a} を排除しないといけない

{なんかてきとう} + 最後のa で作れる文字列が既出なのはどういう時?
・最後のa も含めて {なんかてきとう} + aa が作れる時
というか単に
・{なんかてきとう} + 1つ手前のa
はすべて既出なので、DPしてて1つ前に a だった時点の個数を引けばいい
いや
それだとaaaのとき困る
DPしててaだったすべての時点の個数を引かないといけない

でもまあそれって、キャラクタごとに個数を累計しておけばよさげ。

→AC 1:11:24

class Solution {
   public:
    int distinctSubseqII(string S) {
        const long long MOD = 1000000007LL;

        int L = S.size();
        vector<long long> cacc(26, 0);

        long long accum = 1;

        for (int i = 0; i < L; ++i) {
            char ch = S[i] - 'a';
            long long here = accum;
            here = (here + MOD - cacc[ch]) % MOD;

            accum = (accum + here) % MOD;
            cacc[ch] = (cacc[ch] + here) % MOD;
        }

        accum = (accum + MOD - 1) % MOD;

        return (int)accum;
    }
};