力扣第 71 题 简化路径
一、题目描述
给定一个字符串 path
,表示一个由目录名和斜杠 "/"
组成的绝对路径,请简化该路径,使其变为规范路径。
在 Unix 风格的文件系统中:
- 一个点
"."
表示当前目录本身; - 两个点
".."
表示将目录移动到上一级; - 多个连续的斜杠视为单个斜杠
"//"
等同于"/"
; - 规范路径必须以单个斜杠
"/"
开头,并且两个目录之间必须只有一个斜杠"/"
; - 规范路径不能以斜杠
"/"
结尾(除非它是根目录"/"
)。
输入:一个字符串 path
,表示文件系统中的绝对路径。
输出:返回简化后的规范路径。
二、解题思路
核心思想
- 使用 栈 来存储路径中的有效目录名。
- 遍历路径,根据不同的字符处理:
- 遇到
".."
:如果栈非空,则弹出栈顶目录(回退到上一级)。 - 遇到
"."
或空字符:跳过,表示当前目录或无意义路径。 - 遇到有效目录名:将其压入栈中。
- 遇到
- 最后,将栈中的目录名按照斜杠拼接成最终的简化路径。
三、具体实现
1. 算法流程
- 初始化一个空栈,用于存储目录名。
- 以斜杠
"/"
为分隔符,将路径字符串拆分为多个部分。 - 遍历每个部分,按以下规则处理:
- 如果是
".."
且栈非空:弹出栈顶元素。 - 如果是
"."
或空字符串:跳过。 - 否则,将有效目录名压入栈。
- 如果是
- 将栈中所有元素用斜杠拼接,前面加上
"/"
,即为结果。
2. C 语言代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>char* simplifyPath(char* path) {// 创建一个栈char* stack[3000]; // 假设路径中最多有 3000 个目录int top = -1; // 栈顶指针char* token = strtok(path, "/"); // 按 "/" 分割路径while (token != NULL) {if (strcmp(token, "..") == 0) {// 如果是 "..",弹出栈顶目录if (top >= 0) {top--;}} else if (strcmp(token, ".") != 0 && strlen(token) > 0) {// 如果是有效目录名,压入栈stack[++top] = token;}token = strtok(NULL, "/"); // 继续分割下一个部分}// 拼接简化路径char* result = (char*)malloc(3000 * sizeof(char));result[0] = '\0';if (top == -1) {strcpy(result, "/");} else {for (int i = 0; i <= top; i++) {strcat(result, "/");strcat(result, stack[i]);}}return result;
}int main() {char path[3000];printf("请输入路径:");scanf("%s", path);char* result = simplifyPath(path);printf("简化后的路径为:%s\n", result);free(result);return 0;
}
四、代码说明
核心函数
1. strtok
strtok(path, "/")
将路径字符串按"/"
分割。- 每次调用返回一个路径部分,直到返回
NULL
。
2. 栈操作
- 栈用数组实现,
top
记录栈顶位置。 - 根据路径部分的内容执行以下操作:
".."
:回退到上一级,top--
。"."
或空字符串:跳过。- 其他:压入栈,
stack[++top] = token
。
3. 拼接路径
- 如果栈为空,返回
"/"
。 - 否则,将栈中的目录名用
"/"
拼接成简化路径。
五、运行示例
示例 1
输入:
/home/
输出:
/home
示例 2
输入:
/../
输出:
/
示例 3
输入:
/home//foo/
输出:
/home/foo
六、复杂度分析
时间复杂度
- 路径分割操作和遍历每部分的时间复杂度为 O ( n ) O(n) O(n),其中 n n n 是路径字符串的长度。
空间复杂度
- 栈中最多存储路径中的目录部分,最坏情况占用 O ( n ) O(n) O(n) 空间。
七、总结
这道题目考察了字符串操作和栈的基本应用。在实现中,strtok
和数组栈的结合使代码简单易懂。如果你对 C++ 或其他语言感兴趣,也可以尝试用 STL 或其他高级工具实现!
如果你有任何问题,欢迎在评论区留言交流! 😊
相关文章:
力扣第 71 题 简化路径
一、题目描述 给定一个字符串 path,表示一个由目录名和斜杠 "/" 组成的绝对路径,请简化该路径,使其变为规范路径。 在 Unix 风格的文件系统中: 一个点 "." 表示当前目录本身;两个点 "..&q…...

使用ENSP实现OSPF
一、项目拓扑 二、项目实现 1.路由器AR1配置 进入系统试图 sys将路由器命名为R1 sysname R1关闭信息中心 undo info-center enable 进入g0/0/0接口 int g0/0/0将g0/0/0接口IP地址配置为1.1.1.1/24 ip address 1.1.1.1 24进入g0/0/1接口 int g0/0/1将g0/0/1接口IP地址配置为2…...
分布式下怎么优化处理数据,怎么代替Join
分布式下怎么优化处理数据,怎么代替Join 简单来说, 可以采用 数据冗余,有意地存储一些重复的数据,以此减少关联查询的需求 数据拆分与多次查询,将一次获取的多表数据,拆分多个单独的查询 使用数据仓库…...

51单片机快速入门之中断的应用 2024/11/23 串口中断
51单片机快速入门之中断的应用 基本函数: void T0(void) interrupt 1 using 1 { 这里放入中断后需要做的操作 } void T0(void): 这是一个函数声明,表明函数 T0 不接受任何参数,并且不返回任何值。 interrupt 1: 这是关键字和参…...

[Java]微服务配置管理
介绍 代码拆分为微服务后, 每个服务都有自己的配置文件, 而这些配置文件中有很多重复的配置, 并且配置变化后需要重启服务, 才能生效, 这样就会影响开发体验和效率 配置管理服务可以帮助我们集中管理公共的配置, 并且nacos就可以实现配置管理服务 配置共享 我们可以把微服务共…...
c/c++ 用easyx图形库写一个射击游戏
#include <graphics.h> #include <conio.h> #include <stdlib.h> #include <time.h>// 定义游戏窗口的大小 #define WINDOW_WIDTH 800 #define WINDOW_HEIGHT 600// 定义玩家和目标的尺寸 #define PLAYER_SIZE 50 #define TARGET_SIZE 20// 玩家的结构…...

Rust eyre 错误处理实战教程
在《Rust 错误处理库: thiserror 和 anyhow》中我们介绍了Rust简化处理错误策略,本文解释eyre错误处理库,并通过多个实际示例进行说明,最后于anyhow库进行对比,让你更好理解其应用场景。 eyre是一个用于 Rust 的错误处理库&#x…...
面试小札:JVM虚拟机
1. 定义与基本概念 - JVM(Java Virtual Machine)即Java虚拟机,是Java程序的运行核心。它是一个虚构出来的计算机,通过在实际的计算机上仿真模拟各种计算机功能来运行Java字节码。字节码是一种中间格式,它使得Java程序能…...
Docker扩容操作(docker总是空间不足)
Docker扩容操作(docker总是空间不足) 1、df二连,一共也就70g,总是占满93%以上。所以需要移动到其他目录上 查看docker镜像和容器存储目录的空间大小 du -sh /var/lib/docker/2、停止docker服务 systemctl stop docker3、首先创建目录并迁移 # 首先创…...

数字图像处理(4):FPGA中的定点数、浮点数
(1)定点数:小数点固定在数据的某一位置的数,可以分为定点整数和定点小数和普通定点数。定点数广泛应用于数字图像处理(图像滤波、图像缩放)和数字信号处理(如FFT、定点卷积)中。 定…...
毕昇入门学习
schemas.py 概述 这段代码主要定义了一系列基于 Pydantic 的数据模型(BaseModel),用于数据验证和序列化,通常用于构建 API(如使用 FastAPI)。这些模型涵盖了用户认证、聊天消息、知识库管理、模型配置等多…...
2411C++,学习C++提示4
结构绑定 auto [first, ...ts] std::tuple{1, 2 ,3};assert(1 first);浮点作为非类型模板参数 template<double Value> constexpr auto value Value;int main() {std::cout << value<4.2>; // prints 4.2 }template<double... Vl1s, double... Vl2s&g…...
STM32-- 看门狗--介绍、使用场景、失效场景
STM32 中的看门狗(Watchdog Timer,简称 WDG)有两种主要类型:独立看门狗(IWDG) 和 窗口看门狗(WWDG)。它们的喂狗机制各有特点,主要区别如下: 1. 独立看门狗&a…...

【赵渝强老师】PostgreSQL的数据库
PostgreSQL的逻辑存储结构主要是指数据库中的各种数据库对象,包括:数据库集群、数据库、表、索引、视图等等。所有数据库对象都有各自的对象标识符oid(object identifiers),它是一个无符号的四字节整数,相关对象的oid都…...
linux安全管理-会话安全
文章目录 1 设置命令行界面超时退出2 配置终端登录失败策略3 配置 SSH 登录失败策略 1 设置命令行界面超时退出 1、检查内容 检查操作系统是否设置命令行界面超时退出。 2、配置要求 操作系统设置命令行界面超时退出。 3、配置方法 配置命令行界面超时时间,编辑/et…...
Ubuntu监视显卡占用情况
在终端中运行 watch -n 0.5 nvidia-smi【以下内容由大模型生成】 watch -n 0.5 nvidia-smi 是一个组合命令,用于在 Linux 终端中定期执行 nvidia-smi 命令并显示其输出。让我们分解一下这个命令的各个部分: watch: watch 是一个用于定期执行其他命令并显…...

学成在线day06
上传视屏 断点续传 通常视频文件都比较大,所以对于媒资系统上传文件的需求要满足大文件的上传要求。http协议本身对上传文件大小没有限制,但是客户的网络环境质量、电脑硬件环境等参差不齐,如果一个大文件快上传完了网断了没有上传完成&…...

Mac安装及合规无限使用Beyond Compare
文章目录 Beyond CompareBeyond Compare简介Beyond Compare安装Beyond Compare到期后继续免费使用 Beyond Compare Beyond Compare简介 Beyond Compare 是一款由 Scooter Software 开发的文件和文件夹比较工具。它主要用于对比两个文件或文件夹之间的差异,并支持文…...

【青牛科技】2K02 电动工具专用调速电路芯片描述
概述: 2K02 是电动工具专用调速电路。内置稳压电路,温度系数好,可以调节输出频率以及占空比的振荡输出,广泛的应用于小型电钻,割草机等工具。 主要特点: ● 电源电压范围宽 ● 占空比可调 ● 温度系数好 …...

基于SpringBoot实现的民宿管理系统(代码+论文)
🎉博主介绍:Java领域优质创作者,阿里云博客专家,计算机毕设实战导师。专注Java项目实战、毕设定制/协助 📢主要服务内容:选题定题、开题报告、任务书、程序开发、项目定制、论文辅导 💖精彩专栏…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...