【LeetCode两题选手】算法类题目（7.29）

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

string reverseWords(string s){
    vector<string> vs; 
    string temp="";
    int i=0;
    while(s[i]!='\0'){               //遍历直到结尾 
        if (s[i]==' '){              //遇到空格
            if (!temp.empty())
                vs.push_back(temp); //单词放入容器中
            ++i;                    // 跳过空格 
            temp="";        }
        else{
            temp.push_back(s[i]);   //将字母加到temp字符串后面
            ++i;
        }
    }
    if (!temp.empty())
        vs.push_back(temp);       //将最后一个单词放入容器中

    int len=vs.size();            //倒序遍历容器
    string res="";
    for(int j=0;j<len;++j){
        res.append(vs[len-j-1]);
        if(j!=len-1)
            res.push_back(' ');
    }
    return res;
}

class Solution {
public:
    string reverseWords(string s) {
        int len = s.size(), blank_num = 0, prune = (int) (s[0]==' ');
        char *tail = &s[len], *start = &s[0], *end = &s[0]-1;
        reverse(start, tail);
        while (true){
            while (++end<tail && *end == ' ')blank_num ++;
            while (++end<tail && *end != ' '){}
            reverse(start, end);
            if (end>=tail)return s.substr(0, len-blank_num-prune);
            start = end - blank_num + 1;
        }
    }
};

示例 1：

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入："/a/./b/../../c/"
输出："/c"

示例 5：

输入："/a/../../b/../c//.//"
输出："/c"

示例 6：

输入："/a//bc/d//././/.."
输出："/a/b/c"

	string simplifyPath(string path) {
        vector<string> str;
        stringstream ss(path);
        string sub;
        while(getline(ss,sub,'/'))
        {
            if(sub=="."||sub=="")
                continue;
            if(sub==".."&&str.size())
                str.pop_back();
            if(sub!="..")
                str.push_back(sub);
        }
        string res;
        for(string s:str)
            res+="/"+s;
        if(res.empty())
            res+="/";
        return res;
    }