LeetCode //C - 71. Simplify Path

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 71. Simplify Path。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

71. Simplify Path

Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘…’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.

The canonical path should have the following format:

  • The path starts with a single slash ‘/’.
  • Any two directories are separated by a single slash ‘/’.
  • The path does not end with a trailing ‘/’.
  • The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘…’)

Return the simplified canonical path.
 

Example 1:

Input: path = “/home/”
Output: “/home”
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: path = “/…/”
Output: “/”
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: path = “/home//foo/”
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Constraints:
  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period ‘.’, slash ‘/’ or ‘_’.
  • path is a valid absolute Unix path.

From: LeetCode
Link: 71. Simplify Path


Solution:

Ideas:

To simplify the path, we can use a stack-like approach to process each directory and file in the path. Here’s the approach:文章来源地址https://www.toymoban.com/news/detail-664492.html

  1. Split the path into tokens using the slash (‘/’) as a delimiter.
  2. For each token:
  • If it’s “…”, pop a directory from the stack (if any).
  • If it’s “.” or an empty string, continue to the next token.
  • Otherwise, push the token onto the stack.
  1. Construct the simplified path by joining the stack contents with slashes.
  2. If the resulting path is empty, return the root (“/”).
Code:
char * simplifyPath(char * path) {
    char *tokens[3000];   // max path length is 3000
    int top = -1;

    char *token = strtok(path, "/");
    while (token != NULL) {
        if (strcmp(token, "..") == 0) {
            // Move one directory up if possible
            if (top >= 0) top--;
        } else if (strcmp(token, ".") != 0 && strcmp(token, "") != 0) {
            // A valid directory or file name
            tokens[++top] = token;
        }
        token = strtok(NULL, "/");
    }

    char *result = (char *)malloc(3000 * sizeof(char));
    char *cursor = result;
    for (int i = 0; i <= top; i++) {
        int len = strlen(tokens[i]);
        *cursor++ = '/';
        strncpy(cursor, tokens[i], len);
        cursor += len;
    }
    *cursor = '\0';

    // If the result is empty, return the root
    if (*result == '\0') {
        free(result);
        return strdup("/");
    }
    return result;
}

到了这里,关于LeetCode //C - 71. Simplify Path的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode - 1293. Shortest Path in a Grid with Obstacles Elimination

    You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possib

    2024年02月08日
    浏览(40)
  • 【算法专题--双指针算法】leetcode--283. 移动零、leetcode--1089. 复写零

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月17日
    浏览(42)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(39)
  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(38)
  • 【C语言】【LeetCode】循环队列

    目录  (一)题目描述 (二)数据结构的选择 (三)函数接口的分析实现  正文开始:         题目链接:622. 设计循环队列         设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循

    2024年03月15日
    浏览(46)
  • 6.使用leetcode去练习语言

    目录 1 本章预览 2 简单题举例 2.1 题目描述 2.2 题目解析 2.3 题解 2.4 涉及基础语法 3 中等题举例 3.1 题目描述 3.2 题目解析 3.3 题解 3.4 涉及基础语法 4 本章小结 事实上本章并不会去讲述go语言的基础情况,而是去介绍如何使用Leetcode去帮助我们去学习go语言的基本语法,当然本

    2024年02月08日
    浏览(36)
  • 算法沉淀——贪心算法三(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。 返回 你能获得

    2024年03月24日
    浏览(39)
  • 算法沉淀——贪心算法一(leetcode真题剖析)

    贪心算法(Greedy Algorithm)是一种基于贪心策略的优化算法,它通常用于求解最优化问题,每一步都选择当前状态下的最优解,以期望通过局部最优的选择最终达到全局最优。贪心算法的思想是在每一步都做出在当前状态下局部最优的选择,而不考虑未来可能造成的影响。 在

    2024年03月08日
    浏览(49)
  • 算法沉淀——贪心算法五(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/jump-game-ii/ 给定一个长度为 n 的 0 索引 整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的最小跳跃次

    2024年04月11日
    浏览(49)
  • 算法沉淀——贪心算法二(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 示

    2024年03月19日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包