[C++]LeetCode:117 Simplify Path(Unixパスリストの双方向チェーンテーブルの簡略化)

タイトル:
Given an absolute path for a file (Unix-style), simplify it.
For example, path =  "/home/" , =>  "/home" path =  "/a/./b/../../c/" , =>  "/c"
click to show corner cases.
Corner Cases:
Did you consider the case where path =  "/../" ? In this case, you should return  "/" .
Another corner case is the path might contain multiple slashes  '/'  together, such as  "/home//foo/" . In this case, you should ignore redundant slashes and return  "/home/foo" .
構想:これはLinuxカーネルでよく見られる操作であり、入力されたファイルパスを簡略化することです.まず、これらの記号がUnixパスで表す意味について説明します.

“/.” このレベルのディレクトリを表します.

は無視できます.

“/..” 前のレベルのディレクトリに戻ることを示します.つまり、前のレベルのディレクトリが存在する場合は、/....一緒に削除します.そうでない場合は「/.」のみ削除します.

冗長を除去するパスが空の場合、"/"

に戻る.

複数の連続"/"を含む場合、余分な"/"

を削除する.
私たちが行うべき操作を理解した後、スタックを維持し、各ブロック(「/」を区切り記号として使用)について分析したいと考えています.「../」が前のレイヤに戻ることを示す場合は、スタックを出ます(スタックが空でない場合は)、「./」が現在のレイヤにある場合は、直接スキップし、操作せず、他のファイルのパスは直接スタックに入ります.スタックの末尾に置く.最後にスタックの内容に基づいてパスに変換すればよいので、list双方向チェーンテーブルの特性を使用することに注意してください.java LinkedListと同様に、listにもスタックとキューの実装が含まれています.これにより、パスを復元する際に、パスの順序の問題を解決するためにスタックを維持する必要がなくなり、スタックの先頭から直接スタックを出ればよい.
Attention:
1.C++list双方向チェーンテーブル.
要素関数の取得:front();back();
出入りスタック/キュー関数:push_back(); pop_back(); push_front(); pop_front();
私たちは自分のニーズに応じて、適切な関数を選択して操作することができます.
2.String compare関数

int compare (const string& str) const;

等しい場合は0を返します.

if(tmp.compare(".") == 0)

3.冗長性を除去したパスが空の場合は、"/"を返します.

if(ret.size() == 0)
            return "/";

4. 区切り記号「/」の間の要素を取得し、操作する方法に注意してpathを繰り返します.

 while(i < path.size())
        {
            int index = i;
            //  ‘/’      
            string tmp;
            while(i < path.size() && path[i] != '/')
            {
                tmp += path[i];
                i++;
            }

5. キューヘッダの要素を取得してからpop_front()は、通常のパスに変換されます.

while(!stk.empty())
        {
            ret += "/" + stk.front();
            stk.pop_front();
        }

複雑度:O(N)空間もO(N)、スタックの大きさ
AC Code:

class Solution {
public:
    string simplifyPath(string path) {
        if(path.size() == 0) return "";
        list<string> stk;
        string ret;
        
        int i = 0;
        while(i < path.size())
        {
            int index = i;
            //  ‘/’      
            string tmp;
            while(i < path.size() && path[i] != '/')
            {
                tmp += path[i];
                i++;
            }
            
            if(index != i)
            {
                if(tmp.compare(".") == 0)
                {
                   continue;
                }
                else if(tmp.compare("..") == 0)
                {
                    if(!stk.empty())
                    {
                        stk.pop_back();
                    }
                }
                else
                {
                    stk.push_back(tmp);
                }
            }
            
            i++;
        }
        
        while(!stk.empty())
        {
            ret += "/" + stk.front();
            stk.pop_front();
        }
        
        if(ret.size() == 0)
            return "/";
            
        return ret; 
    }
};

この問題では、セパレータ間の要素を配列で格納することもでき、要素を直接下付きで操作することができます.配列もpush_backとpop_back関数.このブログをご覧ください:Simplify Path
しかし,この問題を通して,C++listデータ構造の強さと使い勝手が分かった.これからはよく利用しなければなりません.