服装设计师的个人网站,wordpress优化速度,西安网评论,网站安全管理机制建设链接简化路径题序号71题型字符串解法栈难度中等熟练度✅✅✅
题目 给你一个字符串 path #xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 #xff08;以 ‘/’ 开头#xff09;#xff0c;请你将其转化为 更加简洁的规范路径。 在 Unix 风格的文件系统中规则如下…链接简化路径题序号71题型字符串解法栈难度中等熟练度✅✅✅
题目 给你一个字符串 path 表示指向某一文件或目录的 Unix 风格 绝对路径 以 ‘/’ 开头请你将其转化为 更加简洁的规范路径。 在 Unix 风格的文件系统中规则如下 一个点 ‘.’ 表示当前目录本身。 此外两个点 ‘…’ 表示将目录切换到上一级指向父目录。 任意多个连续的斜杠即‘//’ 或 ‘///’都被视为单个斜杠 ‘/’。 任何其他格式的点例如‘…’ 或 ‘…’均被视为有效的文件/目录名称。 返回的 简化路径 必须遵循下述格式 始终以斜杠 ‘/’ 开头。 两个目录名之间必须只有一个斜杠 ‘/’ 。 最后一个目录名如果存在不能 以 ‘/’ 结尾。 此外路径仅包含从根目录到目标文件或目录的路径上的目录即不含 ‘.’ 或 ‘…’。 返回简化后得到的 规范路径 。 示例 1 输入path “/home/” 输出“/home” 解释 应删除尾随斜杠。 示例 2 输入path “/home//foo/” 输出“/home/foo” 解释 多个连续的斜杠被单个斜杠替换。 示例 3 输入path “/home/user/Documents/…/Pictures” 输出“/home/user/Pictures” 解释 两个点 “…” 表示上一级目录父目录。 示例 4 输入path “/…/” 输出“/” 解释 不可能从根目录上升一级目录。 示例 5 输入path “/…/a/…/b/c/…/d/./” 输出“/…/b/d” 解释 “…” 在这个问题中是一个合法的目录名。 提示 1 path.length 3000 path 由英文字母数字‘.’‘/’ 或 ‘_’ 组成。 path 是一个有效的 Unix 风格绝对路径。
题型
核心思想该题使用栈Stack这种数据结构来模拟路径的遍历和回退过程。复杂度时间复杂度是 O(n)其中 n 是路径字符串的长度因为我们需要遍历整个字符串。空间复杂度也是 O(n)因为我们需要存储路径的有效部分。c 实现算法
class Solution {
public:std::string simplifyPath(std::string path) {std::vectorstd::string stack;//定义一个栈//创建了一个 std::stringstream 对象 ss并将字符串 path 作为其初始内容。//这样做的目的是为了方便地对路径字符串进行分割和读取操作。std::stringstream ss(path);//dir 用于存储从 stringstream 中读取的每个目录std::string dir;//使用 getline 函数从 stringstream 中按 / 分割读取路径的每个部分直到没有更多内容可读。while (getline(ss, dir, /)) {//如果目录为空字符串或为 .表示当前目录不做任何操作继续下一次循环。if (dir.empty() || dir .) {continue;}//如果目录为 ..表示返回上一级目录。如果栈不为空则弹出栈顶元素即移除上一级目录。else if (dir ..) {if (!stack.empty()) {stack.pop_back();}}//否则将该目录压入栈中。 else {stack.push_back(dir);}}//初始化一个空字符串 simplified用于存储简化后的路径。然后遍历栈中的每个目录//将其添加到 simplified 字符串中并在每个目录前加上 /。std::string simplified;for (const std::string d : stack) {simplified / d;}//simplified 为空字符串说明路径简化后是一个根目录返回 /。否则返回 simplified。return simplified.empty() ? / : simplified;}
};算法推演 初始化 stack[] ss/a/./b/…/…/c/ 遍历路径 读取第一个部分“” 空字符串忽略。 stack[] 读取第二个部分“a” 将 “a” 压入栈。 stack[“a”] 读取第三个部分“.” 当前目录忽略。 stack[“a”] 读取第四个部分“b” 将 “b” 压入栈。 stack[“a”, “b”] 读取第五个部分“…” 返回上一级目录弹出栈顶元素 “b”。 stack[“a”] 读取第六个部分“…” 返回上一级目录弹出栈顶元素 “a”。 stack[] 读取第七个部分“c” 将 “c” 压入栈。 stack[“c”] 构建简化后的路径 初始化 simplified“” 遍历栈中的每个目录将其添加到 simplified 字符串中并在每个目录前加上 /。 simplified“/c” 返回结果 simplified 不为空返回 “/c” 最终结果 简化后的路径为“/c” c 完整demo
#include iostream
#include vector
#include string
#include sstreamclass Solution {
public:std::string simplifyPath(std::string path) {std::vectorstd::string stack;//定义一个栈//创建了一个 std::stringstream 对象 ss并将字符串 path 作为其初始内容。//这样做的目的是为了方便地对路径字符串进行分割和读取操作。std::stringstream ss(path);//dir 用于存储从 stringstream 中读取的每个目录std::string dir;//使用 getline 函数从 stringstream 中按 / 分割读取路径的每个部分直到没有更多内容可读。while (getline(ss, dir, /)) {//如果目录为空字符串或为 .表示当前目录不做任何操作继续下一次循环。if (dir.empty() || dir .) {continue;}//如果目录为 ..表示返回上一级目录。如果栈不为空则弹出栈顶元素即移除上一级目录。else if (dir ..) {if (!stack.empty()) {stack.pop_back();}}//否则将该目录压入栈中。 else {stack.push_back(dir);}}//初始化一个空字符串 simplified用于存储简化后的路径。然后遍历栈中的每个目录//将其添加到 simplified 字符串中并在每个目录前加上 /。std::string simplified;for (const std::string d : stack) {simplified / d;}//simplified 为空字符串说明路径简化后是一个根目录返回 /。否则返回 simplified。return simplified.empty() ? / : simplified;}
};int main() {Solution solution;std::string path /home//foo/;std::string simplifiedPath solution.simplifyPath(path);std::cout Simplified Path: simplifiedPath std::endl;return 0;
}
