0042.路径简化.md

路径简化

题目链接

C++

#include <iostream>
#include <string>
#include <list>
#include <sstream>

using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        // 去除字符串开头的 "cd "
        s = s.substr(3, s.size() - 3);	
        stringstream is(s);
        // 用 list 模拟 stack
        list<string> stk; 	
        string cur = "";
        // 字符串流 is 按照 '/' 分隔符进行分割，并将每个分割后的字符串存储在 cur 中
        while (getline(is, cur, '/')) {
            // 若 cur 为空字符串或 "." 则跳过
            if (cur == "" || cur == ".") continue; 
            // 若 cur 为 ".." 且 stk 非空，弹出栈顶文件夹
            else if (cur == ".." && !stk.empty()) stk.pop_back(); 
            // 若 cur 不为 ".."，则将文件夹压入栈中
            else if (cur != "..") stk.emplace_back(cur);    
        }
        string res = "";
        for (const auto& str : stk) res += "/" + str; 
        // 若 res 为空，输出根目录 "/"
        if (res.empty()) cout << "/" << endl;     
        else cout << res << endl;                 
    }
    return 0;
}

Java

/**
 * 思路：使用栈进行模拟
 * 
 * 具体做法：
 * 以 "/" 为分隔符，将 Unix 命令字符串划分为一个字符串数组
 * 
 * 遍历字符串
 *   如果是 "." 则忽略
 *   如果是 ".."
 *     如果栈不为空：将栈顶的文件夹弹出
 *   如果是文件夹名，则将文件夹压入栈中
 * 
 * 最终如果栈为空，则输出根目录 "/"
 * 将栈强转为数组，然后按照顺序打印数组中的文件夹名
*/
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String unixCommand = scanner.nextLine();
            // "/+" 是正则表达式，可匹配多个连续的 "/"，replaceAll("/+", "/") 可将多个连续的 "/" 替换为单个"/"
            String[] dirs = unixCommand.substring(3, unixCommand.length())
            .replaceAll("/+", "/").split("/");
            pwd(dirs);
        }
        scanner.close();
    }

    public static void pwd(String[] dirs) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < dirs.length; i++) {
            if (dirs[i].equals(".") || dirs[i].equals("")) {
                continue;
            } else if (dirs[i].equals("..")) {
                if (!stack.empty()) {
                    stack.pop();
                }
            } else {
                stack.push(dirs[i]);
            }
        }
        Object[] array = stack.toArray();
        if (array.length == 0) {
            System.out.printf("/");
        }
        for (int i = 0; i < array.length; i++) {
            System.out.printf("/%s", array[i]);
        }
        System.out.println();
    }
}

Python

# 周赛第一题，路径打印
# 字符串处理问题，可以使用堆栈进行处理，栈顶我们定义为tmp[-1]，通过判断不同的元路径执行不同的操作，这道题要注意如果最终返回根路径要打印"/"，这个卡了一会,还是要注意边界处理的
def go_back(s):
    k = 0
    res = ""
    for i in range(len(s)-1, -1, -1):
        if k > 0:
            res = s[i]+res
        else:
            if s[i] == '/':
                k += 1
    return res

def get_path(s):
    res = ""
    tmp = ""
    for i in s:
        if i == '/':
            if tmp == "" or tmp[-1] == '/':
                tmp = "/"
            else:
                if tmp == "/.":
                    tmp = "/"
                elif tmp == "/..":
                    res = go_back(s=res)
                    tmp = "/"
                else:
                    res = res + tmp
                    tmp = "/"
        else:
            tmp += i
    if res == "":
        return "./"
    return res  

Go

##用栈模拟一遍，用‘/’做分隔符，分割原始路径得到string切片，遍历切片，如果是“.”或者“”不压入栈，是“..”如果栈长度大于0弹出一个元素，其他的字符串压入栈中，遍历完后格式化打印栈，如果栈的大小是0，输出‘/’

注：卡玛网使用的go环境版本比较低，有些库函数不能使用。
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	var unixCommand string
	scan := bufio.NewScanner(os.Stdin)
	for scan.Scan() {
		unixCommand = scan.Text()
		dirs := strings.Split(replice(unixCommand[3:]), "/")
		pwd(dirs)
	}
}

func pwd(dirs []string) {
	stack := make([]string, 0)
	for _, dir := range dirs {
		if dir == "." || dir == "" {
			continue
		} else if dir == ".." {
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		} else {
			stack = append(stack, dir)
		}
	}
	if len(stack) == 0 {
		fmt.Print("/")
	}
	for _, dir := range stack {
		fmt.Printf("/%s", dir)
	}
	fmt.Println()
}

func replice(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		res += string(s[i])
		if s[i] == '/' {
			for j := i + 1; j < len(s) && s[j] == '/'; j++ {
				i++
			}
		}
	}
	return res
}

JS

C