力扣第 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项目实战、毕设定制/协助 📢主要服务内容:选题定题、开题报告、任务书、程序开发、项目定制、论文辅导 💖精彩专栏…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
