c++-c++编程基础之leetcode题解第71题简化路径.zip资源-CSDN下载

共1个文件

md：1个

需积分: 1 19 浏览量 2024-04-16 08:26:58 上传评论收藏 2KB ZIP 举报

在本压缩包中，主题聚焦于C++编程基础与LeetCode算法题目的解法，特别是针对LeetCode第71题“简化路径”（Simplify Path）的探讨。这道题目旨在检验开发者的路径解析能力，涉及到字符串处理和栈的数据结构应用。让我们深入探讨这个问题以及如何用C++解决它。我们需要理解“简化路径”问题的背景。在计算机系统中，文件和目录的路径通常由一系列斜线（/）分隔的目录名组成，例如"/home/user/documents/file.txt"。简化路径的任务是去掉路径中的"."和"..”，并返回规范化的路径。"."表示当前目录，"..”表示上级目录，如果遇到..且前面没有目录时，则应忽略。解题思路通常会采用栈这一数据结构。在C++中，我们可以使用标准库中的`std::stack`来实现。以下是一种可能的解决方案： 1. 创建一个空栈，用于存储路径中的目录。 2. 遍历输入路径字符串，将每个路径分隔符（/）之后的目录名处理。 - 如果目录名为"."，则忽略它，因为当前目录没有实际作用。 - 如果目录名为"..”，检查栈是否为空或者栈顶元素不是"..”。如果不是，表示可以向上级目录回退，因此将栈顶元素弹出。 - 否则，将新的目录名压入栈中。 3. 当遍历完所有字符后，栈中剩下的元素就是规范化路径的组成部分。将它们按顺序连接起来，前缀加上"/"，即为最终的简化路径。在C++代码实现中，我们可以使用`std::string`来存储路径，`std::stringstream`来处理字符串，`std::stack`来管理目录，以及`std::getline`来读取路径中的每个部分。这里是一个简单的伪代码示例： ```cpp #include <stack> #include <sstream> #include <string> std::string simplifyPath(const std::string& path) { std::stack<std::string> dirs; std::stringstream ss(path); std::string token; while (std::getline(ss, token, '/')) { if (token == "..") { if (!dirs.empty() && dirs.top() != "..") { dirs.pop(); } } else if (token != ".") { dirs.push(token); } } std::string result; while (!dirs.empty()) { result = "/" + dirs.top() + result; dirs.pop(); } return result.empty() ? "/" : result; } ``` 这个函数首先将输入的路径字符串按照斜线分割成各个部分，然后逐一处理这些部分。当处理完成后，从栈中取出规范化后的路径。注意，最后可能需要在结果前添加一个"/"，以符合规范路径的格式。学习这个解法，不仅可以提升对C++编程的理解，还能加深对字符串处理、栈操作以及算法应用的认识。通过解决LeetCode这样的实际问题，开发者可以提高自己的编程技能，并为面试和实际工作中的问题解决做好准备。同时，了解和掌握C++标准库中的各种容器（如`std::stack`）及其操作，对于提升编程效率至关重要。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第71题简化路径.zip （1个子文件）

c++_c++编程基础之leetcode题解第71题简化路径

README.md 3KB

# [71. Simplify Path (Medium)](https://leetcode.com/problems/simplify-path/) Given a string <code>path</code>, which is an absolute path (starting with a slash <code>'/'</code>) 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 <code>'.'</code> refers to the current directory, a double period <code>'..'</code> refers to the directory up a level, and any multiple consecutive slashes (i.e. <code>'//'</code>) are treated as a single slash <code>'/'</code>. For this problem, any other format of periods such as <code>'...'</code> are treated as file/directory names. The canonical path should have the following format: <ul> <li>The path starts with a single slash <code>'/'</code>.</li> <li>Any two directories are separated by a single slash <code>'/'</code>.</li> <li>The path does not end with a trailing <code>'/'</code>.</li> <li>The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period <code>'.'</code> or double period <code>'..'</code>)</li> </ul> Return the simplified canonical path.   Example 1: <pre>Input: path = "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name. </pre> Example 2: <pre>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. </pre> Example 3: <pre>Input: path = "/home//foo/" Output: "/home/foo" Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one. </pre>   Constraints: <ul> <li><code>1 <= path.length <= 3000</code></li> <li><code>path</code> consists of English letters, digits, period <code>'.'</code>, slash <code>'/'</code> or <code>'_'</code>.</li> <li><code>path</code> is a valid absolute Unix path.</li> </ul> **Companies**: [Facebook](https://leetcode.com/company/facebook), [Google](https://leetcode.com/company/google), [Amazon](https://leetcode.com/company/amazon), [VMware](https://leetcode.com/company/vmware) **Related Topics**: [String](https://leetcode.com/tag/string/), [Stack](https://leetcode.com/tag/stack/) ## Solution 1. ```cpp // OJ: https://leetcode.com/problems/simplify-path/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(N) class Solution { public: string simplifyPath(string path) { vector<string> v; istringstream ss(path); string s, ans; while (getline(ss, s, '/')) { if (s == "..") { if (v.size()) v.pop_back(); } else if (s.size() && s != ".") v.push_back(s); } for (auto &p : v) ans += '/' + p; return ans.size() ? ans : "/"; } }; ```

评论收藏

内容反馈