[Leet Code] Throne Inheritance

問題が解決するにつれて、三星電子の力がB型の血の味をテストしているようだ.
実はB型にとって時間の複雑さの特徴は、あまり制限がないことです.
本当に久しぶりにCPPを出して使いました
コードが乱れるかもしれないので哀悼・・
住所はこちらです

問題の特定

王国には王がいて、王はまた子供を産んだ...子供たちは子供を産み続け、
例えば、最初の王がA、B、C、Dの子供を産んだら.
王、A、B、C、Dの順番、
AがAAAB ACを生んだら.
王,A,AA,AB,AC,B,C,Dの順に進む.
出生時に親と子の情報をリンクリストで入力すると、問題は解決します.
Hash
まずbirth,init,deathなどから入力される入力値はすべて名前であり,名前の文字数は最大15文字で,小文字のみである.
ハッシュ・テーブルの作成も試してみることができますが、CPPでlong longを宣言して含めることを想像しました.

long long Hash(string name) {
	long long ret = 0;
    int i = 0;
    while(name[i]) {
    	ret = (ret << 5) + (name[i] - 'a' + 1);
	}
    return ret;
}

使用する場合、最大65ビットが使用されます.オーバーフローが発生するため、ハッシュテーブルを作成しないことにします.(面倒だから!)
Undered mapで解決しました.

トラブルシューティングプロセス

関数によってそれぞれを破壊します.

構造体宣言

struct Node {
    string name;
    int n = 0;
    bool death;
    Node *prev, *next;
    Node *child, *parent;

}buf[100010];
int idx = 0;

名前、そして子供がいるかどうかを確認するnは、死ぬかどうかを判断するdeathからなる.
普通はあまり使わないn...retコードの空のノードをチェックするとnullptrエラーが発生し、区別に使用されます.
そのような方法でbufを発表するのは理由がある.
通常、チェーンテーブルを直接使用してNewまたはmalloc、callocキーワードを1つ1つ使用して宣言しますが、アルゴリズムの問題を解く際にメモリ要因の制限が大きくない場合は、静的宣言の配列から1つずつ使用するとより速く、管理が容易になります.
bufのインデックス管理はidxを採用している.

ThroneInheritanceの作成者

unordered_map<string, Node*> map;
string king = "";
ThroneInheritance(string kingName) {
	buf[idx] = {kingName, 0, 0,0, 0, 0, 0};
	map[kingName] = &buf[idx++];
	king = kingName;
}

最初の作成時にbuf[idx]を使用してマッピングされたKingName Keyに入れます.
そして、最初の王の名前はキングのstring変数と呼ばれています.

birth

void birth(string parentName, string childName) {
	Node *p = map[parentName];

        buf[idx] = {childName, 0,0, 0,0, map[parentName]};
        map[childName] = &buf[idx];
        if(p->n != 0){
            p->child->prev = &buf[idx];
            buf[idx].next = p->child;
        }
        p->child = &buf[idx];
        p->n = 1;
        idx+= 1;
}

Birth関数の核心はparentNameとchildNameであり,それらの関係である.
まず、まだ生成されていないchildNameに対応する要素を生成します.
親ノードをparentNameが所有するItemとしてbufで宣言し、childName Key値に対応するItemに配置します.
親ノードの子ノードが存在する場合.
1.現在の親ノードの子ノードのprevをchildNameのプロジェクト方向に移動します.
2.childName内のアイテムのnext方向は、現在の親によって子を指します.
3.parentの子供をchildNameの道具にする.
一連のプロセスを図に示す.

old childはすでに親のchildノードを占めている.
これを和弦にかえる

まず、新しいold childのprevノードを追加するnew Childノードを見てみましょう.

次に、new child nodeでold child nodeを表示します.

最後に,親ノードの子ノードをnew子ノードに向けるようにすればよい.
そうすると、転がってきた石を取り出すような感じになります.
この方法の最終目標は

このような形態です.
いずれにしても、このように積み上げると、入ってくる順番に解放されることを知っておく必要があります.

death

void death(string name) {
        Node *p = map[name];
        p->death = true;
}

一番簡単な関数かも?彼が死んだことをチェックすればいい.

getInheritanceOrder

void getID(Node *name, vector<string> &ans) {
        if(!name){ return ;}
        Node *sibling = name;
        for(; sibling->next; sibling = sibling->next){
        }
        for(; sibling; sibling = sibling->prev) {
            if(!sibling->death)
                ans.push_back(sibling->name);
            if(sibling->n)
                getID(sibling->child, ans);
        }    
}

vector<string> getInheritanceOrder() {
        vector<string> ans;
        if(!map[king]->death)
            ans.push_back(king);
        if(map[king]->n)
            getID(map[king]->child, ans);
        return ans;
}

今はツアー中にすべての王族の情報をansに入れて返信します.
いつものようにdfsに乗ればいいです.
最初に10回呼び出された関数を考えると,最悪のNは10*2であり,これは理不尽な解答である.
getIDでIDの順番を決めます.
サブノードが現れると逆さまになり,最初の点から巡回しansに値出力を入力する.
完全なコードはここにあります.

ポスト

パワーテストB型を考えるのは久しぶりです.
もし本当にB型だったら、getInheritanceOrderを完全に探索させない問題を提起すると思います.
これは得がたい資料構造でいろいろな面白い問題です.