日記

のみろぐ

主に競プロ日記です

LeetCode110

A問題「Reorder Log Files

問題概要

  • ログが与えられます
  • ログの形式は2つあります
  • 1つ目は「識別子より後が全部小文字」で、それをletter-logsと呼びます
  • 2つ目は「識別子より後が全部数字」で、それをdigit-logsと呼びます
  • そこで、letter-logs→digit-logになるように並べ替えて下さい。
  • letter-logsは識別子を無視して辞書順になるように並び替えて下さい
  • ditgit-logsは与えられたままの順序でOK

考察

  • ログがletter-logsかdigit-logsかは、ログの最後の文字を見て数字かどうか判定すれば良さそう。
  • letter-logsの並び替えがちょっとだるそう。連想配列でえい!!ってできそう。keyは識別子以下の文字列とする。valueはログ全体の文字列とする。
  • 最後にletter-logsの連想配列と、digit-logsの配列を繋げた配列を返せばよさげ

解法

  • 考察通りの実装する

コード

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        // letter-logsとdigit-logsを別々に並べ替えた配列を作る
        map<string, string> letterLogs;
        vector<string> digitLogs;
        for (string log : logs) {
            char lastChar = log.back();
            if (lastChar >= '0' && lastChar <= '9') {
                // digit-logsの処理
                digitLogs.push_back(log);
            } else {
                // letter-logsの処理
                int idx = 0; // 識別子後の空白index
                for (int i = 0; i < log.size(); i++) {
                    if (log[i] == ' ') {
                        idx = i;
                        break;
                    }
                }
                string key = log.substr(idx+1, log.size());
                letterLogs[key] = log;
            }
        }
        
        // 最後にletter-logsとdigit-logsを組み合わせた配列を作る
        vector<string> ans;
        for (auto x : letterLogs) {
            ans.push_back(x.second);
        }
        for (string s : digitLogs) {
            ans.push_back(s);
        }
        
        return ans;
    }
};

感想

  • lexicographicallyって英単語、呪文か???ってなった。レキシコグラフィカリー!!(あんまかっこよくないな)。コンテスト中は調べなかったけど辞書順って意味らしい。
  • 識別子後の空白indexを求めるやつ、breakし忘れてはまった。人の製にするのは良くないんですが、これデバッグがだるい。コードをローカルにコピペしてmain関数からクラスをインスタンス化してメソッドを呼び出してデバッグした。だるくないかこれ。もっと良い方法あるのかもだけど
  • 英語呼んで思うんだけど、一度呼んだだけじゃ何言ってるかよく分からない。3回くらいかみ砕きつつ読まないと読めない。にゃーん

B問題「Range Sum of BST

問題概要

  • 2分探索木が与えられます。
  • ノードの値の総和を求めて下さい。

考察

  • やるだけっぽいけど、ノードのたどり方覚えてねぇ...
  • ググったら->っていうアロー演算子使うっぽい。100億年振りに見た
  • ということで、再帰書いて終了。

コード

/**
 * 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 {
public:
   int sum = 0;
   int rangeSumBST(TreeNode* root, int L, int R) {
      if (root->val >= L && root->val <= R) {
         sum += root->val;
      }

      if (root->left != NULL) {
         rangeSumBST(root->left, L, R);
      }
      if (root->right != NULL) {
         rangeSumBST(root->right, L, R);
      }

      return sum;
   }
};

改善

  • ホントは再帰関数だけで完結するコード書きたかったけど、書き方分かんなかったので外部にint sumを作った。
  • 他の人のコード見た感じ、以下の用の書けるみたい。URL
  • よくわからん。おなか空いたから後で見る
class Solution {
public:
   int rangeSumBST(TreeNode* root, int L, int R) {
      int sum = 0;

      if (root->val >= L && root->val <= R) {
         sum += root->val;
      }

      if (root->left != NULL) {
         sum += rangeSumBST(root->left, L, R);
      }
      if (root->right != NULL) {
         sum += rangeSumBST(root->right, L, R);
      }

      return sum;
   }
};

知見

  • 構造体のポインタ型の要素にアクセスするにはアロー演算子を使う。->こんなやつ。コンテスト中はドットでアクセス出来ずに詰んでた(入門書レベルだぞこの内容)

C問題「Minimum Area Rectangle

問題概要

  • 点が(x, y)座標が与えられます。
  • x, y座標と平行になるような辺で構成された最小の長方形を求めて下さい

考察

コンテスト中の考察

  • 4つの点を全探索すると$O(N4)$なので間に合わない。他の方法を考える必要がある
  • 問題を整理すると、以下のような状況になる。そして、点Pと点Oを決め打って上手いこと処理しようと考える。だが、ここでどうやっても無理だなーと思いコンテスト終了

f:id:nomikura:20181112081728p:plain

理想の考察

  • 全探索は $O(N4)$ で間に合わないので、他の方法を考える必要がある
  • 状況を整理すると以下のようになる。そこで、点を2つ決め打つ。すると、(a, b)と(d, c)が確定する。あとは、(a, c)と(d, b)が存在するかを確認すればいいだけとなる。これはsetを使うと楽に書ける
  • 計算量は $O(N^{2}log_N)$ となる

f:id:nomikura:20181112081748p:plain

コード

class Solution {
public:
   int minAreaRect(vector<vector<int>>& points) {
      // 全座標をsetに入れる
      set<pair<int, int>> pts;
      for (vector<int> p : points) {
         pts.insert({p[0], p[1]});
      }

      int ans = 1600000001;
      // 長方形の対角となる点p, qを決め打つ
      for (auto p : pts) {
         for (auto q : pts) {
            int a = p.first, b = p.second, c = q.second, d = q.first;
            // x, y座標がかぶってたら処理を飛ばす
            if (a == d || b == c) continue;
            if (pts.count({a, c}) && pts.count({d, b})) {
               ans = min(ans, abs((a - d) * (b - c)));
            }
         }
      }

      if (ans == 1600000001) return 0;
      return ans;
   }
};

要点

情報の重複を避ける

  • 画像にすると以下の通り。P, Oを決め打った場合、(a, b)と(a, c)を確定させるためdが明らかにならない。しかし、P, Qを決め打つ場合、(a, b)と(d, c)を確定させるため、全ての座標が明らかとなる。
  • 今回は、2つの要素の情報が重複したため計算が間に合わなかった。なので、確定させる要素に重複がないようにすれば良かったのかなーと思う。

f:id:nomikura:20181112081809p:plain

setの話

  • setのメソッドであるcountの計算量は$O(logN)$
  • いつもfind使ってるけどcountの方が良さげ

D問題「Distinct Subsequences II

  • わかりません
  • 典型らしいです