leetcode71-简化路径

原题

以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径

请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能/ 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

示例 6:

输入: "/a//b////c/d//././/.."
输出: "/a/b/c"

解法

思想

使用栈的思想来解决该问题,将给定的字符串使用"/"分割,会得到由空字符串、"."".."、目录名组成的字符串数组,然后根据它们的特点对元素进行入栈出栈等操作。

代码

class Solution {
    public String simplifyPath(String path) {
        StringBuilder sb = new StringBuilder();
        //因为最后要遍历栈,这里用ArrayList来模拟栈
        List<String> stack = new ArrayList<>();
        String[] dirs = path.split("/");
        for(String i:dirs){
            //空字符串和"."都表示当前目录
            if(i.equals("") || i.equals(".")) continue;
            //".."表示上一级目录,出栈一个元素
            if(i.equals("..")){
                if(stack.size()!=0) 
                    stack.remove(stack.size()-1);
            }
            //其他目录名入栈
            else stack.add(i); 
        }
        if(stack.size()==0) return "/";
        //通过"/"连接起来
        for(String i:stack){
            sb.append("/");
            sb.append(i);
        }
        return sb.toString();
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode71-%e7%ae%80%e5%8c%96%e8%b7%af%e5%be%84/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月23日 01:09
下一篇 2020年1月23日 18:22

相关推荐

  • leetcode49-字母异位词分组

    原题 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat",…

    算法 2019年12月25日
    090
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    070
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0240
  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    080
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    060
  • 程序员面试金典01.07-旋转矩阵

    原题(来源Leetcode) 给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。 不占用额外内存空间能否做到? 示例 …

    算法 2020年4月7日
    0410
  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0110
  • leetcode205-同构字符串

    原题 给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺…

    算法 2019年12月21日
    0210
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210

发表回复

登录后才能评论