讨论/《零起步学算法》 - 例题:简化路径/
《零起步学算法》 - 例题:简化路径
共 8 个回复

解题思路

Golang,标准库,1行

使用标准库的同时,别忘了看看源码

Snipaste_2021-02-09_09-53-34.png

代码

import (
	path2 "path"
)

func simplifyPath(path string) string {
	return path2.Clean(path)
}
3

Java

class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<String>();
        //用"/"分割开
        String mebs[] = path.split("/");
        for(String meb:mebs){
            //如果为空也就是"///"这种连续情况
            //或者"."表示当前目录本身,不做任何操作
            if(meb.equals("")||meb.equals(".")){
                continue;
            }
            //".."表示返回上一级,则弹出一项
            if(meb.equals("..")){
                if(!stack.isEmpty()){
                    stack.pop();
                }
                continue;
            }
            stack.push(meb);
        }
        StringBuilder sb = new StringBuilder();
        if(stack.isEmpty()){
            sb.append("/");
        }
        //先入栈的是父目录,因此从头插入
        while(!stack.isEmpty()){
            sb.insert(0,stack.pop());
            sb.insert(0,"/");
        }
        return sb.toString();
    }
}
2
class Solution {
    public String simplifyPath(String path) {
        String[] arr = path.split("/");
        Deque<String> stack = new ArrayDeque<>();
        for (String s : arr) {
            if ("".equals(s) || ".".equals(s)) {
                continue;
            }
            if ("..".equals(s)) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(s);
            }
        }
        if (stack.isEmpty()) {
            return "/";
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop()).insert(0, "/");
        }
        return res.toString();
    }
}
1

Java

class Solution {
    public String simplifyPath(String path) {
        String[] paths = path.split("/");
        if (paths.length==1) return "/";

        Deque<String> stack = new ArrayDeque<>();
        for (String p : paths){
            if (p.equals("") || p.equals(".")) {
                continue;
            } else if (p.equals("..")) {
                if(!stack.isEmpty()) stack.pop();
            } else {
                stack.push(p);
            }
        }
        if(stack.isEmpty())return "/";

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop());
            sb.insert(0, "/");
        }

        return sb.toString();
    }
}
1
class Solution {

    /**
     * @param String $path
     * @return String
     */
    function simplifyPath($path) {
        if (!$path) { return '/'; }
        $arr = explode('/', $path);
        $stack = [];
        foreach ($arr as $char) {
            if ('' == $char || '.' == $char) { continue; }
            if ('..' == $char) { 
                if ($stack) { array_pop($stack); }
                continue; 
            }
            $stack[] = $char;
        }
        if (!$stack) { return '/'; }
        $str = '';
        while ($stack) { $str = '/' . array_pop($stack) . $str; }
        return $str;
    }
}

本来我还有些好奇问什么不用包名path,结果定睛一看入参变量名就是path,所以要做区分

C++ split函数随便抄了一个改了改

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> st;
        string ans;
        for(const auto &s:split(path,'/')){
            if(s==".."){
                if(!st.empty()){
                    st.pop();
                }
            }
            else if(!s.empty() && s!="."){
                st.push(s);
            }
        }
        while(!st.empty()){
            ans = "/" + st.top() + ans;
            st.pop();
        }
        return ans.empty()? "/" : ans;
    }
private:
    vector<string> split(const string& s,const char flag = ' ') {
        vector<string> sv;
        istringstream iss(s);
        string temp;

        while (getline(iss, temp, flag)) {
            sv.push_back(temp);
        }
        return sv;
    }
};

java代码,栈用Stack实现。

class Solution {
    public String simplifyPath(String path) {
        String []dirs = path.split("/");
        if(dirs.length==0){
            return "/";
        }

        Stack <String> st = new Stack <String>();
        for(String dir: dirs){
            if("".equals(dir)||".".equals(dir)){
                continue;
            }
            if(dir.equals("..")){
                if(!st.isEmpty()){
                    st.pop();
                }
                continue;
            }
            st.push(dir);
        }
        StringBuilder str = new StringBuilder();
        if(st.isEmpty()){
            str.insert(0,"/");
        }else{
            while(!st.isEmpty()){
                str.insert(0,st.pop());
                str.insert(0,"/");
            }
        }
        return str.toString();


    }
}