首页 > 代码库 > (每日算法)Leetcode--Simplify Path (简单路径)

(每日算法)Leetcode--Simplify Path (简单路径)

给定一个Unix风格的路径,简化之。使其不改变路径的结果,但是去掉中间无用的字符。

因为系统执行的时候也是逐段查看的,因此最直观的做法就是使用栈来简化,当是/..时,出栈;当是/.时,忽视;当时其他时才进栈。

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

不难写出代码如下:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> result;
        for(auto i = path.begin(); i != path.end(); )
        {
            ++i;
            auto j = find(i, path.end(), '/');//查找
            string dir = string(i, j);  //通过两个迭代器构造字符串
            if(!dir.empty() && dir != ".")//当是///时dir为空
            {
                if(dir == ".."){
                    if(!result.empty())
                        result.pop_back();
                }
                    else
                        result.push_back(dir);
            }
            i = j;
        }
        stringstream out;
        if(result.empty())
            out<<"/";
        else
            for(auto item : result)
                out<<"/"<<item;
        return out.str();
    }
    
};


有三个知识点,写出来,大家一起学习:

1)find函数的使用

 算法并不直接操纵容器,而是遍历两个迭代器指定的一个元素范围

 find(vec.begin(), vec.end(), val)
  在[vec.begin(), vec.end())范围内(左闭右开区间)查找元素val。
  如果查找得到,然回该元素的迭代器;查找不到,返回第二个参数。

2)通过迭代器构造string

string dir = string(i, j)

将dir初始化为迭代器i和j之间元素的拷贝(左闭右开区间)。

类通过=运算符的初始化和dir(string(i, j))相同。

3)stringstream的知识点

允许向string流中读写数据,out.str()--返回out所保存的string 拷贝;out.str(s)--将string s拷贝到out中,返回void

#include<sstream>
#include<iostream>
using namespace std;
int main()
{
        string line,word;
        while(getline(cin,line))
        {
                stringstream stream(line);
                cout<<stream.str()<<endl;
                while(stream>>word){cout<<word<<endl;}
        }
        return 0;
}

输入:shanghai no1 school 19

输出:shanghai no1 school 19

      shanghai

    no1

    school

    19

#include<sstream>
#include<iostream>
using namespace std;
int main()
{
        int val1 = 512,val2 =1024;
        stringstream ss;
        ss<<"val1: "<<val1<<endl<<"val2: "<<val2<<endl;
    //“val1: "此处有空格,字符串流是通过空格判断一个字符串的结束</span></span>
    cout<<ss.str(); 
    string dump; 
    int a,b; 
    ss>>dump>>a>>dump>>b; 
    cout<<a<<" "<<b<<endl; 
    return 0;
}


注意从stringstream中解析对象的时候,是以空格和回车键为分隔符的

输出为:val1: 512

    val2: 1024

    512 1024

第一处黑体字部分:将int类型读入ss,变为string类型

第二处黑体字部分:提取512,1024保存为int类型。当然,如果a,b声明为string类型,那么这两个字面值常量相应保存为string类型


stringstream不会主动释放内存(或许是为了提高效率),但如果你要在程序中用同一个流,反复读写大量的数据,将会造成大量的内存消 耗,因些这时候,需要适时地清除一下缓冲 (用 stream.str("") )







(每日算法)Leetcode--Simplify Path (简单路径)