首页 > 其他分享 >Leetcode 71. 简化路径

Leetcode 71. 简化路径

时间:2023-12-20 16:59:29浏览次数:37  
标签:斜杠 .. 路径 目录名 简化 71 path Leetcode size

https://leetcode.cn/problems/simplify-path/description/

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);
两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' 。 对于此问题,任何其他格式的点(例如,'...')均被视为文件/目录名称。

请注意,返回的 规范路径 必须遵循下述格式:

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名(如果存在)不能 以 '/' 结尾。
此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.' 或 '..')。
返回简化后得到的 规范路径 。

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

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

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

示例 4:
输入:path = "/a/./b/../../c/"
输出:"/c"
 

提示:
1 <= path.length <= 3000
path 由英文字母,数字,'.','/' 或 '_' 组成。
path 是一个有效的 Unix 风格绝对路径。

解答
首先我们需要自行切分字符串的路径 拆分出 空字符"" 上一级路径".." 当前路径"." 目录名"home".
然后由于遇到上一级路径的指示符 我们需要将之前的目录弹出路径,所以感觉需要栈 数据结构
实际上也确实需要栈 由于后面需要路径翻转,所以我们使用vector模拟栈
以示例4 为例子
1 我们先拆分路径记录
vector dir = {a,.,b,,..,..,c"};
当前路径"." 不作任何处理
上一级路径".." 弹出之前记录的目录名
目录名"home" 记录这一次的目录名

2 然后我们拼接路径名,之前弹出从尾部弹出,拼接却是从头部开始拼接。起始路径时一个'/',每个目录间使用一个'/'隔开

代码如下

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stk;
        int l = 0; int  r = 0;
        while (l < path.size() && r < path.size()) {
            while (l < path.size() && '/' != path[l]) l++;
            if (l >= path.size()) break;
            r = l + 1;
            while (r < path.size() && '/' != path[r]) r++;
            if (r > path.size()) break;
            string curr = path.substr(l+1, r - l - 1);
            if (curr == ".."&& !stk.empty()) {
                stk.pop_back();
            }else if( curr != ".." && curr !="." && curr !="") {
                stk.push_back(curr);
            }
            l = r ;
        }

        string ans ="/";
        for (int i = 0; i < stk.size(); ) {
            ans += stk[i]; 
            i++;
            if(i != stk.size() )ans += "/";
        }
        return ans;
    }
};

我的视频题解

标签:斜杠,..,路径,目录名,简化,71,path,Leetcode,size
From: https://www.cnblogs.com/itdef/p/17916934.html

相关文章

  • [LeetCode22-中等-DFS] 括号生成
    这道题考使用回溯(递归的一种)进行深度优先算法,题目是这样的数字n代表生产括号的对数,写一个算法,返回所有有效的括号组合比如 n=1代表生成1对括号,显然答案就是“()"n=2,代表生成2对括号, 答案就是"()()","(())"n=3代表生成3对括号,答案就是"((()))","()()()","(()())......
  • BOSHIDA DC电源模块如何简化电路设计
    BOSHIDADC电源模块如何简化电路设计DC电源模块是一种集成了直流电源电路的模块,可以提供稳定的直流电源输出。使用DC电源模块可以简化电路设计,具体步骤如下: 1.选择合适的DC电源模块:根据电路所需的电压和电流要求,选择合适的DC电源模块。通常,DC电源模块有不同的输出电压和电流......
  • [LeetCode] LeetCode81. 搜索旋转排序数组II
    题目描述思路:是lc33.搜索旋转排序数组的延伸,允许包含重复元素起初:当nums[left]<=nums[mid]时,区间[left,mid]有序当nums[left]>nums[mid]时,区间[mid,right]有序但是这个题目当nums[left]==nums[mid]时,无法判断哪个区间是有序的,无法判断target位于左侧还是右侧,此时无......
  • [LeetCode Hot 100] LeetCode153. 寻找旋转排序数组中的最小值
    题目描述思路如果数组翻转后又回到升序的情况,即nums[left]<=nums[right],则nums[left]就是最小值,直接返回。如果数组翻转,需要找到数组中第二部分的第一个元素:若nums[left]<=nums[mid],说明区间[left,mid]连续递增,则最小元素一定不在这个区间里,可以直接排除,最小值在[......
  • Leetcode 044. 通配符匹配
    https://leetcode.cn/problems/wildcard-matching/description/给你一个输入字符串(s)和一个字符模式(p),请你实现一个支持'?'和'*'匹配规则的通配符匹配:'?'可以匹配任何单个字符。'*'可以匹配任意字符序列(包括空字符序列)。判定匹配成功的充要条件是:字符模式必须能够......
  • macOS Sonoma 14.2.1 (23C71) 正式版发布,ISO、IPSW、PKG 下载 (安全更新)
    macOSSonoma14.2.1(23C71)正式版发布,ISO、IPSW、PKG下载本站下载的macOS软件包,既可以拖拽到Applications(应用程序)下直接安装,也可以制作启动U盘安装,或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。请访问原文链接:https://sysin.org/blog/ma......
  • macOS Sonoma 14.2.1 (23C71) 正式版 Boot ISO 原版可引导镜像下载 (安全更新)
    macOSSonoma14.2.1(23C71)正式版BootISO原版可引导镜像下载(安全更新)本站下载的macOS软件包,既可以拖拽到Applications(应用程序)下直接安装,也可以制作启动U盘安装,或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。请访问原文链接:https://s......
  • [LeetCode] LeetCode704. 二分查找
    题目描述思路基础二分查找模板的考察。方法一:classSolution{publicintsearch(int[]nums,inttarget){if(nums==null||nums.length==0)return-1;intleft=0,right=nums.length-1;while(left<=right){......
  • [LeetCode Hot 100] LeetCode33. 搜索旋转排序数组
    题目描述思路如果nums[left]<=nums[mid],则[left,mid]有序如果nums[left]>nums[mid],则[mid,right]有序方法一:classSolution{publicintsearch(int[]nums,inttarget){if(nums==null||nums.length==0)return-1;intleft=0,ri......
  • [LeetCode Hot 100] LeetCode35. 搜索插入位置
    题目描述思路基础二分搜索模板本质:找到第一个大于等于target的元素的下标注意:该题目不存在重复元素存在一种特殊情况:target>nums的最大值,此时插入的位置正好是left的位置方法一:classSolution{publicintsearchInsert(int[]nums,inttarget){if......