GSoC 2022: pgmoneta On Disk Encryption

Posted on 2022-09-10

TL, DR

Issue page.
Code refactoring pull request
All in one squashed pull request

Overview

pgmoneta is a backup / restore solution for PostgreSQL. The existing codebase already contains some encryption code used to encrypt passwords. I enhanced the encryption API, created new encryption workflow, and added cli options so that the encryption can be applied to wal and other data (e.g. config file). The documentation and benchmarking test are also provided for users to reference.

Contribution

Early Stage Investigation and Code Refactoring

At early stage, we discussed what encryption algorithms should be supported. As result, AES CBC mode and AES CTR mode are choosed for following reasons:

Advanced Encryption Standard Instruction Set (AES-NI) is now integrated into many processors. Hardware acceleration made AES outperform other algorithms.
CBC is supported because it is the most commonly used and considered save mode. Its main drawbacks are that encryption is sequential (decryption can be parallelized).
CTR is supported because both encryption and decryption are parallelizable. We offer user a faster encrtypt option.

After determining what algorithms to support, I moved existing aes code from security.h(c) to aes.h(c) before implement the feature.

Feature Implemention

Commits are squashed into one single pull request and you can check it here.

This is the most challenging part of the GSoC event. I spent lots of time understanding how the current event loop and workflow work. Debugging a multi-process program is a painful but fun experience and I learned a lot about gdb and addresssanitizer. Another challenge is handling complicated git workflow. I was always afraid to accidentally lose my changes when dealing with git. Participating GSoC and interacting with other people made me have a better understanding of git workflow.

Documentation and Benchmarking

The encryption feature is well documented. The configuration file parameter and its available options are listed in doc/CONFIGURATION.md. The comparison and choose of AES modes are described ENCRYPTION.md. The tutorial of perform a benchmarking test and test result also documented in ENCRYPTION.md.

Further Work

Track the issue page for details.

Acknowledgement

I am grateful to my mentor Jesper Pedersen, for his invaluable patience and feedback. I could not have undertaken this journey without his help.

研究計画書

Posted on 2021-04-24 Edited on 2021-05-25 In distributed system

Background

分散システムについての研究は計算科学の早期からあり、今でも発展しつつあるドメインである。リーダー選出、同期合意などの研究は1970年代から始まっている。よく知られているのは1986年に、Fisher氏らにより証明されたFLP定理で、非同期システム内の合意達成は不可能であることについて述べた[1]。しかし当時はムーアの法則（ゴードンムーアが1965年に自らの論文上に示した集積回路上のトランジスタ数は2年ごとに倍になるという経験則）の存在により、並行計算に関する研究は注目されていない。
1990年代から半導体製造の物理的な限界に迫って、ムーアの法則の失効がみられる。同時に、コンピュータネットワークが発展し、2000年前後で全世界が繋がるインターネットとなった。
さらに、移動端末の普及により、ビッグデータ、クラウドコンピューティング、機械学習、暗号通貨などのアプリケーションが流行っている。Google、Facebook、Amazonなどの大手会社に限らず、ほとんどのネットサービス会社のコアアーキテクチャが、分散式のインフラストラクチャーを土台にして、信頼性もパフォーマンスも高いシステムである。Paxos[2]、Raft[3]合意アルゴリズム、Gossipプロトコル[4]、一貫性のあるハッシュ[5]などの分散システムの研究成果、幅広く応用されている。さらにビザンチンフォールトトレラントについての理論まで適用したシステムもある。近く将来で、IoTの時代が来て、より多くの端末がネットにつながり、協同稼働することがみられる。一言でいうと、これから長い間は、分散システムが頼られる時代であると考える。

Literature Review

背景で述べたように、インターネットの発展と共に、膨大な数の情報が生産された。IDCのホワイトペーパーにより、2007年時点で、デジタル形式で保存されているデータは約281EB（1EB=1000 petabytes (PB) ）あり、年平均成長率は57%である。政府、会社などの組織はより早くスピードでデータ量が増加している[6]。2003年で行われた「情報爆発」との研究により、構造化データに比べて、非構造化データがデータ全体の約95%に占めている[7]。検索、分析、マイニング、可視化など要件では、大量なデータに対する保存、管理、アクセス、処理に大きなチャレンジをもたらす[8]。これらの難題を挑むため、数多くの分散システムに基づいたソフトウェアが開発された。本レビューは分散ストレージシステムに注目し、影響が大きい事例を整理する。

The Google Cluster

この論文[9]の内容によって、Googleは安価の一般PCで構成されたクラスターで、メインフレームアーキテクチャを入れ替わった。そして、ハードウェア信頼性の低下及び台数の増加に踏まえ、ソフトウェアで信頼性を確保することを考えた（fault tolerance）。Googleは実際の例で安価PCクラスターのフィジビリティを世に示した。

GFS

GFS[10]は「効率的に大量のデータを保存、検索できるかつ大規模なスケールアウト可能」を目標にして、Googleが開発された分散式ファイルシステムである。強い一貫性を求めず、シンプルなデザインで高いパフォーマンスを実現した。安価PCクラスターにデプロイし、信頼性と可用性を確保しながら、大幅にコストを抑えた。これからGFSの仕組について簡単に述べる。

システム構成

Master Server
シングルノードのマスター機を使い、Chunkのメタデータ（namespace、アクセス制御データ、位置マップ）すべてをメモリ内に保存することより、スピードアップにしました。同時に、leaseの配布、garbage collection、周期的にChunkサーバーの点検、ファイル移行などのオペレーションも担当する。マスター機はWAL（write-ahead logging）と非同期のMaster-Slave Replication　でデータを永続化し、災害後の復活ができる。また、B+Tree式のスナップショットをとることにより、再起後のリペアを加速する。使用時、クライアントは一度マスター機からChunkの情報をもらい、その後の書き読みリクエストはすべてChunkサーバーが処理される。これでマスター機の負担を軽減することができる。
Chunk Server
Chunkサイズを64Mにすることにより、メタデータのサイズを抑える。GFSは標準POSIXを提供しなく、追加書き（Append）がメインのWrite方式である。追加書きに最適化したチェックサムアルゴリズムでファイルチェックとダメージデータのリペアを加速する。Chunkサーバーの間にLeaseでMaster-Slaveの関係を分ける。レプリカを違うハードウェアに指定することにより、RackレベルのFault toleranceを実現する。書き込みの際にMaster Chunkを持つサーバーがリクエストを受け、Slave Chunkはシリアル化でデータレプリケーションをし、ネットの負荷を軽減する。

この論文はGoogleが早期発表したものであり、今でも分散システムの入門教材としてよく討論される。これをベースにした開発されたオープンソース分散式ファイルシステムはHDFS、KFSなどがある。また、伝統のRDBより弱い一貫性のシステムでも現実的に応用できることを世に示した。現在、GFSは次世代のColossusに進化したが、Colossusについての論文はまだ発表していない。

Big Table

BigTable[11]はGoogleがGFSを基盤にして開発された構造化データを保存するためのシステムである。Googleの自社サービスで生産されたデータをBigTableで管理するを目標にして、設計上大量データを対応できる同時に、アクセスのリアルタイム性も要求する。プラスに、高い適用性、fault tolerance、スケーラビリティも考慮した。特徴としては：

データモデル

(row:string, column:string, time:int64)→string
BigTable は多次元のハッシュテーブルである。テーブル内のデータは、行キーワード、列キーワード、タイムスタンプ、3レベルのインデックスでアクセスされる。

Row Key：64KBに越えない任意文字列であり、辞書順でソートされ、関連性あるデータは連続で保存され、圧縮、パーティションなどの操作に効率高いである。一行内の読み書き操作はACIDのトランザクション処理を保証する。
Col Key：同じタイプのデータを一つのセット（Column Family）にまとめて管理する。アクセス制御の基本単位でもある。
Timestamp：同じデータの違うバージョンをTimestampで管理する。2種類のGC方式がある、1つは一定時間ないのデータをもつ、1つは最新バージョンのN個を持つ。

システム構成

シングルノードのマスター機があり、Tabletサーバークラスタを管理する。マスター機はChubby（Paxosに基づいた分散式ロックサービス）[12]でTabletサーバーの加入と撤去を監視し、ロードバランシングやGCなどのオペレーションを行う。
テーブル内のすべての行がダイナミックでパーティション可能で、そのパーティションは“Tablet”という。1つのTabletは複数のGFS Chunkサーバー上にあるSST（Sorted String Table）構造のファイル（レプリカ）、Commit Log、メモリ内にあるMemTableで構成される。レプリカ同士の間にChubbyを用いて一貫性を確保しながら、高い可用性も実現した。SSTを使用することにより、大量データの連続書き込みが高速化可能。またBloom Filterを利用し、ハードディスクのアクセス回数を減らす。TabletサーバーはB+Treeに類似のデータ構造で3レイアのインデックスでTabletの位置を記録する。Tabletは指定されたRow Key範囲を関連し、膨大になるとき自動的にパーティションを行う。
この論文が発表後、オープンソースのHBaseが開発され、AmazonのDynamo[25]と一緒に、NoSQLストレージシステムに先端に立った。その後数々のNoSQLシステムが各社に開発され、大幅に応用された。また、1996年で発表したLSM-Tree[13]が改めて世に知られ、BTreeに並べ、ストレージシステムに使われる二大データ構造となる。

Percolator

Percolator[14]はBigTableをベースして、MapReruce[23]モデルで走ってるPageRankアルゴリズム[24]の実行時間を減らすために差分データだけを処理したいを目標にして、開発されたストレージシステムである。行間ACIDトランザクションを実現した。システムの特徴としては：

システム構成

oracle.timestamp
oracle_tsは厳密に単調増加で、タイムスタンプを配布するサービスである。これによってスナップショット分離を実現する。
クライアント
クライアントは2PC（two-phase commit）のコーディネーターとなる。
BigTable
BigTableは行内ACIDトランザクションを保証する。

/* Pseudocode for Percolator transaction protocol. */
class Transaction {
    struct Write {
        Row row;
        Column col;
        string value;
    };
    vector < Write > writes;
    int start ts;

    Transaction(): start ts(oracle.GetTimestamp()) {}
    void Set(Write w) {
        writes.push back(w);
    }
    bool Get(Row row, Column c, string * value) {
        while (true) {
            bigtable::Txn T = bigtable::StartRowTransaction(row);
            // Check for locks that signal concurrent writes.
            if (T.Read(row, c + "lock", [0, start ts])) {
                // There is a pending lock; try to clean it and wait
                BackoffAndMaybeCleanupLock(row, c);
                continue;
            }

            // Find the latest write below our start timestamp.
            latest write = T.Read(row, c + "write", [0, start ts]);
            if (!latest write.found()) return false; // no data
            int data ts = latest write.start timestamp();
            * value = T.Read(row, c + "data", [data ts, data ts]);
            return true;
        }
    }
    // Prewrite tries to lock cell w, returning false in case of conflict.
    bool Prewrite(Write w, Write primary) {
        Column c = w.col;
        bigtable::Txn T = bigtable::StartRowTransaction(w.row);

        // Abort on writes after our start timestamp . . .
        if (T.Read(w.row, c + "write", [start ts, ∞])) return false;
        // . . . or locks at any timestamp.
        if (T.Read(w.row, c + "lock", [0, ∞])) return false;

        T.Write(w.row, c + "data", start ts, w.value);
        T.Write(w.row, c + "lock", start ts, {
            primary.row,
            primary.col
        }); // The primary’s location.
        return T.Commit();
    }
    bool Commit() {
        Write primary = writes[0];
        vector < Write > secondaries(writes.begin() + 1, writes.end());
        if (!Prewrite(primary, primary)) return false;
        for (Write w: secondaries)
            if (!Prewrite(w, primary)) return false;

        int commit ts = oracle.GetTimestamp();

        // Commit primary first.
        Write p = primary;
        bigtable::Txn T = bigtable::StartRowTransaction(p.row);
        if (!T.Read(p.row, p.col + "lock", [start ts, start ts]))
            return false; // aborted while working
        T.Write(p.row, p.col + "write", commit ts,
            start ts); // Pointer to data written at start ts .
        T.Erase(p.row, p.col + "lock", commit ts);
        if (!T.Commit()) return false; // commit point

        // Second phase: write out write records for secondary cells.
        for (Write w: secondaries) {
            bigtable::Write(w.row, w.col + "write", commit ts, start ts);
            bigtable::Erase(w.row, w.col + "lock", commit ts);
        }
        return true;
    }
} // class Transaction

行間トランザクションの実現

Perwrite
start_tsをとり、複数の書きの中、1つの書きをprimaryにして、他の書きをsecondaryにする。Primary書きはコミットの同期点とする。Write-writeチェックでSnapshot Isolationの“First-commiter-win”との要求を保証し、コンフリクトを検出した場合すなわちトランザクションを放棄（Abort）することにより、デッドロックを防ぐ。
Commit
Perwriteが成功であればコミット段階に入る。commit_tsをとり、ロックに保有をチェックし、他トランザクションでロックを回収された場合は放棄する。commit_tsをとることは必ずPerwriteが成功してからのオペレーションであるため、oracle_tsの単調増加性と合わせて、Snapshot-readを保証する。Primary writeを先にコミットし、成功すればトランザクションのコミット成功と判断し、クライアントにリターンする。Secondary書きは非同期でコミットする。
Failover
ネットの不安定性の原因で、コーディネーターとなったクライアントの状態を特定することが困難である。つまり、Failoverとコミットが同期に実行されている場合がある。同じトランザクション内の複数の書きがすべて成功か放棄かを保証するために、PercolatorはLazy方式でFailoverを行う。次のトランザクションがある行を書くときロックをとり試し、ロックが占有された場合は待ち、タイムアウトの時Failoverが発動し、ロックを回収する。これによってFailoverの安全性を保証する。

PercolatorはBigTable上にカスタマイズしたシステムであり、データを実際のデータをwriteマーク2列に分けて、読み書きのスループットにある程度の影響があると考える。また、コミットが完了まで3回のIOとRPC通信（Prewrite primary、 Prewrite secondary、 Commit primary）が必要、遅延に影響を与えるとも考える。これから述べる次世代システムSpannerが違うデザインを採用し、されにパフォーマンスアップすることを実現した。

Megastore

Megastore[15]はOLTP向けに開発され、RDBとNoSQLの間に位置付け、RDBの便利性とNoSQLのスケーラビリティを両立したストレージシステムである。

低遅延を保証するために、メインのEntityGroupはどのデータセンターにあるかユーザーが指定することが可能である。
1つのEntityGroupのデータが違うテーブルに保存される可能性はある（Entity Root Tableとchild Table）が、違うEntityGroupの同じKeyのデータを1つのEntityGroupにまとめる。
BigTableのようなKVストアが弱構造化データの保存が得意のため、リードヘビの環境で、なるべく非正規化のスキーマ設計を採用し、Join操作のコストを減らす。
BigTableのマルチバージョン特性に基づいたMVCCトランザクション。
読みはcurrent/snapshot/inconsistent三種類あって、MVCCにより読みと書きの同期実行が可能である。Currentはすべての書きが完了を保証し、最新のデータを読み取る。Snapshotはバージョン指定で読み取る。Inconsistentは一貫性を保証せず、直ぐに読み取る。
全てのレプリカは書き込み可能である。書きはPaxosでログ位置を決め、競争で次のログ位置を取ったレプリカが書き込みを実行する。失敗した書きはリトライ。（楽観的並行性制御）
Paxosのコミュニケーションコストを回避するため、Megastoreはcoordinatorサービスを用いて、ローカルにあるレプリカの中、どのEntityGroupのデータが最新であるかを追跡する。最新であるデータはPaxosが行われず、直接ローカルデータを読み取る。Coordinatorの状態は、書き込みの際に更新される。
Coordinatorがダウンの時、書き操作がブロックされる場合がある。それを防ぐために、MegastoreはChubbyで失効検出を実現する。
完備のレプリカサーバの他、2種類の軽量化のレプリカサーバがある。1つはログのみ保存し、Paxosに利用される。1つはデータのみ保存し、リードオンリーリクエストを処理する。
Megastoreはスケーラビリティ、パフォーマンス、低遅延、信頼性を保証した上で、RDBによくあるデータモデル、トランザクションなどの概念を分散式システムに実現し、初めての分散式RDBとも言えるでしょう。

Spanner

Spanner[16] はMegastoreの後継者として、Megastoreから多くの設計理念を継承した。Megastoreにある実用性に欠けた問い合わせ言語（DQL）、パーティションが不便などの問題点を解決し、さらにパフォーマンスアップをした。一言で言うとKVストアで実装したが、SQLに類似するDQLとJoinなどのRDB特性をサポートするシステムである。

データモデル

個々のテーブルは複数のTabletという単位に自動的にパーティションされる。それぞれのTabletは複数のマシンでPaxosを用いて内容をレプリカ同士の間に同期する。すべてのテーブルの主キーはルートノードの主キーをPrefixにする。Spannerはルートノードにある1つの記録とそれをPrefixにした他テーブルのデータすべてをDirectory という1つのセットにまとめる。パーティション時Directoryは隣接する位置に保存され、データアクセスのローカル性を高める。

トランザクション

TrueTime API
クラスター内のマシン同士が完璧に時刻を同期しているではなく、ズレは発生する。そのズレをε以下に抑えるために原子時計を用いて開発されたものはTrueTime APIである。
1つのトランザクションは複数のTabletのデータ扱うかどうかによって処理が異なる。
複数の場合だけ、2PCを行って一貫性を保証する。なお、Megastoreのデザインと違うのは、coordinatorはLeaderとSlaveがあり、互いにPaxosで合意をとる。これによってcoordinatorの信頼性を高める。
また、1つのトランザクションはリードオンリーか読み書きかによって処理が異なる。
リードオンリーんのトランザクションはTrueTime APIを用いて、MVCCによるアイソレーションを実現し、ロックなしでNon-Bolckingにデータを読み込む。
読み書きトランザクションの場合、S2PLプロトコルに従ってロックをとる。その後TrueTime APIから時刻をとって、その時刻を+2εでトランザクションのコミットタイムスタンプとする。（自分がクラスター内に一番遅いマシンと仮定し、クラスター内に一番早いマシンが取れるタイムスタンプ）。トランザクションが書き込み完了後、+2εの時刻が必ず過去になったと言えるまでわざとロックを持ったまま待機する。これがCommit Waitという。これによって、クラスター内のどのマシンから見てもロックが取られている状態になるため、外部一貫性が保証される。

原子時計を用いることにより、分散システムでNon-BolckingのMVCCを実現したことと、短時間のCommit Waitで並列処理性を高めることがSpannerの二大特徴と考える。一方で、「原子時計は必要なくNTPで十分」と宣言したオープンソースのCockroachDBも存在する。CockroachDBとSpannerのベンチマークを比較し、原子時計の必要性を確認するのもやりがいのあることと考える。

Research Aim

これまでGoogle社が開発された分散式ストレージシステムにつにて簡単に述べた。全体的にみると、fault tolerance、高い性能、スケーラビリティ、トランザクションなどの共通的なデザイン目標もある。ただし、それらのデザイン目標はそもそも両立できないと考える。例えば、一貫性を保証するために使われるPaxosが、頻繫にRPCでコミュニケーションが必要のためネットワークの負荷が重くなる。２PCを行う際にcoordinatorが音信不通になるとシステムがブロックになってしまう。読み書きの際にロックをかけるなどのコスト高い操作で性能が落ちる。永続化するためのWALが頻繫にfsync()をするため遅延が高い。これらの事実上のスタンダードとして使われるアルゴリズムやプロトコルをいかにしてパフォーマンスをアップすることができるかは、重大な課題になると考える。

一方で、文献レビューで述べた各種のシステムのうち、ある業務要件に対して特別に開発されたものもある。つまりその業務要件を満たすために取捨選択した設計で、どこでも使える万能薬ではない。私が実際な仕事経験で、あるくじ会社のシステム構築に参加した。そのシステムに使ったパーツは：

スポーツ対戦の進行状況をお客様に提供しているため、大会開催時の単位アクセス回数が多くと想定されて、In　MemoryデータベースRedisをCacheとして利用している。
一定時間（週、月）ごとに、経営に関する統計的なデータを計算するジョブ（OLAP）があり、データ量が膨大であると想定されて、HBaseを利用している。
システムを監視するためのモニタリングシステムがある。リアルタイムでシステムの調子を見るため、ストリーミング形式なデータを処理すると想定する。また問題発生時Debug、問題特定のため、一定時間内の監視データを保存する必要ある。以上の要件に考えて、時系列データベースInfluxDBを利用した。

DDIAにより、「状況によって最適なソフトウェアは違う。すべてのソフトウェア、汎用データベースといったものも、特定した利用シーンで設計されたものである」[17]。私の仕事経験からもそう強く感じている。今よく使われているストレージシステムの仕組みを細かく理解し、使いにくい部分は改善できる点を探るのも課題と考えている。また、5GやIoTが来る近く将来で様々なデータの利用シーンを想定し、ある場面に適用するツールがないと見つかったら、解決策を提案することも課題の1つと考えている。

Reserach Plan

このセクションは主に2年間の学習（研究）計画について述べる。具体的な研究方向ですら決まっていない素人の計画であるが、入学後先生の指導によって随時に更新するつもりはある。

基礎理論をしる

“Edsger W. Dijkstra Prize in Distributed Computing” by PODC
Dijkstra賞は2000から、分散システム分野に物凄く影響ある論文に授与する賞である。よく耳にするLamport Clock[18]、Global Snapshot[19]、FLP Impossibilityから、分散システムの基盤理論となったWait-Free[20]、Lock-Free[21]、Liveness Property[22] まで多く収録されている。これらの論文を読んで、基礎理論を深く理解し、今までどんな研究したか、どんな成果が出たかを知る。これからの研究には不可欠であることと考えている。
CS294-91 Distributed Computing
UC Berkeley大学が主催し、基礎理論に注目したオープン講座である。扱う参考書や論文、授業中のスライドなどのリソースがある。これをガイドラインとして、理論知識の学習を進めると考えている。

論理の実装及び応用をみる

“The Hall of Fame Award” by ACM SIGOPS
HOFはOS分野の賞であるが、分散システムに関する論文も多く授与している。Dijkstra賞は理論的なものがメインで、HOFはエンジニアリング、実際な実装を注目している。例としてDynamoやBigtableなどが収録されている。これらの論文を読んで、ケーススタディーとして、分散システムに関する理論がどういう風に応用されているかを知ることができると考えている。また、実装から妥結した設計や、不満点などを探って、「それをどうやって改善しようか」とのことがこれからの研究方向にもなると考えている。

6.824: Distributed Systems
MIT大学のオープン講座である。レクチャーは生産環境で大規模に応用されるシステムについての論文の読み及び説明を中心とした。レクチャーの録画まであるので、ケーススタディーの理解を深めるやスピードアップに助かるリソースになると思う。

他にも15-440/640, Spring 2014: Distributed Systems、15-712 Advanced and Distributed Operating Systems, Spring 2012、CSE552: Distributed and Parallel Systems、などの有名大学からのオープン講座がある。どれでもリソースをきちんとまとめた講座であり、必要であれば随時に参考できると考える。

細かい研究テーマを決めて研究を進める

以上の2段階を乗り越えると、分散システム分野において、全体的な知識や研究内容について把握できると考える。それから先行研究を把握したうえで研究することを目標にして、
自分に興味があったテーマを選び、よりに範囲を絞って、テーマに関する論文や教科書を洗い出して学習する。先行研究の研究手法や結論などをまとめて、文献レビューを作成する。されに、先行研究から研究不足やまだやってないことを探して、自分の研究を決める。そこから具体的な研究手法を考えて、研究を進めていく段階になるが、今はテーマが決まっていないため詳細な計画を立つことはできない状態である。しかし、その時研究を順調にできるために、あらかじめ研究メソッドについての学習はできると考える。学習材として、COMP516 Research Methods in Computer Science (2007-2008)リバプール大学からのオープン講座があり、これを入学前にオンライン履修して、入学後の研究生活をスムーズにいけると考える。
また、先生が研究テーマを指示した場合は、そちらのテーマで研究を行うと考えている。

Expected Results

細かくまで研究テーマがきまっていないが、2年間の学習及び研究に渡って、先で述べた「分散システムアルゴリズムの性能アップ」、「あるシーンに特化したストレージシステムの開発」、もしくは新たに発見したテーマのどれかに集中し、わずかな貢献が出来れば幸いである。

References

LeetCode 841. Keys and Rooms

Posted on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

就一道很普通的搜索题, bfs, dfs都行.

代码

bfs

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        queue<int> keys;
        keys.push(0);
        unordered_set<int> ok = {0};
        while(!keys.empty()){
            int rn = keys.front();
            keys.pop();
            ok.emplace(rn);
            for(int key : rooms[rn]){
                if(ok.find(key) == ok.end()) keys.push(key);
            }
        }
        return ok.size() == rooms.size();
    }
};

LeetCode 376. Wiggle Subsequence

Posted on 2021-03-18 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

满足一上一下的最长子序列. 一开始想用贪心, 代码如下.

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        int res = 2;
        bool flag = nums[1] < nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            if(!(nums[i] < nums[i - 1] == flag)) {
                flag = !flag;
                res++;
            }
        }
        return res;
    }
};

此方法无法解决nums[i] == nums[i - 1]的情况, 所以分成上下分开统计, 最后返回最大值

nums[i+1] > nums[i]
1. 假设 down[i] 表示的最长摆动序列的最远末尾元素下标正好为 i，遇到新的上升元素后，up[i+1] = down[i] + 1 ，这是因为 up 一定从 down 中产生（初始除外），并且 down[i] 此时最大。
2. 假设 down[i] 表示的最长摆动序列的最远末尾元素下标小于 i，设为 j，那么 nums[j:i] 一定是递增的，因为若完全递减，最远元素下标等于 i，若波动，那么 down[i] > down[j]。由于 nums[j:i] 递增，down[j:i] 一直等于 down[j] ，依然满足 up[i+1] = down[i] + 1 。
nums[i+1] < nums[i]，类似第一种情况
nums[i+1] == nums[i]，新的元素不能用于任何序列，保持不变.

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        int up = 1, down = 1;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] < nums[i - 1]) down = up + 1;
            if(nums[i] > nums[i - 1]) up = down + 1;
        }
        return max(up, down);
    }
};

LeetCode 478. Generate Random Point in a Circle

Posted on 2021-03-17 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

线性的对半径取随机的话, 会导致origin附近的样本点比外围多, 使得样本分布不均匀, 要取sqrt().
延伸阅读

代码

class Solution {
public:
    Solution(double radius, double x_center, double y_center): r{radius}, x{x_center}, y{y_center} {};
    vector<double> randPoint() {
        double theta = 2 * PI * ((double)rand() / RAND_MAX);
        double ran = sqrt(((double)rand() / RAND_MAX));
        double foo = x + ran * r * cos(theta), bar = y + ran * r * sin(theta);
        return {foo, bar};  
    }
    
private:
    double r, x, y;
    const double PI = 3.14159265358979323846;
};
    
    
 
/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */

LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee

Posted on 2021-03-16 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

其实这里有官方的全套解析. 我开始觉得我记录这个东西是无用功了.

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int res = 0, min = prices[0];
        for(int i = 0; i < prices.size(); ++i) {
            if(prices[i] < min) min = prices[i];
            if(prices[i] > min + fee) {
                res += prices[i] - min - fee;
                min = prices[i] - fee;
            }
        }
        return res;
    }
};

LeetCode 535. Encode and Decode TinyURL

Posted on 2021-03-15 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

基本是按照这个实现的.
一个随机字符串生成器加map储存.

代码

#include <iostream>
#include <ctime>
#include <unistd.h>

class Solution {
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        string str = gen_random(6);
        while(mp.find(str) != mp.end())
            str = gen_random(6);
        mp[str] = longUrl;
        return str;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return mp[shortUrl];
    }

private:
    map<string, string> mp;
    
    string gen_random(const int len) {
        string tmp_s;
        static const char alphanum[] =
            "0123456789"
            "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
            "abcdefghijklmnopqrstuvwxyz";

        srand( (unsigned) time(NULL) * getpid());
        tmp_s.reserve(len);
        for (int i = 0; i < len; ++i) 
            tmp_s += alphanum[rand() % (sizeof(alphanum) - 1)];

        return tmp_s;
    }
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

LeetCode 1721. Swapping Nodes in a Linked List

Posted on 2021-03-14 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

这次的题是交换val, 不是交换node, 所以更简单.
两个指针p1, p2, p1先走k步, 然后p1和p2一起走, 当p1走到头的时候, p2就是倒数第k个了

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode holder(0, head);
        ListNode* foo = head, *bar = head;
        for(int i = 0; i < k; i++) {
            foo = foo -> next;
        }
        while(foo){
            foo = foo -> next;
            bar = bar -> next;
        }
        foo = &holder;
        for(int i = 0; i < k; i++) {
            foo = foo -> next;
        }
        swap(foo->val, bar->val);
        return holder.next;
    }
};

LeetCode 823. Binary Trees With Factors

Posted on 2021-03-13 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

$dp[i] = \sum_{j=0}^i \forall{j} \{arr[j] | arr[i] \mod arr[j] == 0\}, dp[arr[i]/arr[j]] * dp[arr[j]]$

代码

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        long res = 0, m = 1e9+7;
        sort(arr.begin(), arr.end());
        unordered_map<int, long> dp;
        for(int i = 0; i < arr.size(); ++i) {
            dp[arr[i]] = 1;
            for(int j = 0; j < i; ++j) {
                if(arr[i] % arr[j] == 0) {
                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] / arr[j]]) % m;
                }
            }
            res = (res + dp[arr[i]]);
        }
        return res % m;
    }
};

LeetCode 1461. Check If a String Contains All Binary Codes of Size K

Posted on 2021-03-12 Edited on 2021-03-19 In LeetCode Notes

题目

原题在此

解析

只要关注最长的子串就好, 如果有最长的子串, 那较短的子串也一定在里面. 将子串放入set中, 最后比对size.

代码

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int d = 0;
        unordered_set<int> hset;
        for (int i = 0; i < s.length(); i++) {
            d = (d << 1) | (s[i] - '0');
            if (i >= k - 1) {
                hset.insert(d);
                d -= (s[i - (k - 1)] - '0') << (k - 1);
            }
        }
        return hset.size() == (1 << k);
    }
};