当前位置: 首页 > news >正文

力扣第 71 题 简化路径

一、题目描述

给定一个字符串 path,表示一个由目录名和斜杠 "/" 组成的绝对路径,请简化该路径,使其变为规范路径。

在 Unix 风格的文件系统中:

  • 一个点 "." 表示当前目录本身;
  • 两个点 ".." 表示将目录移动到上一级;
  • 多个连续的斜杠视为单个斜杠 "//" 等同于 "/"
  • 规范路径必须以单个斜杠 "/" 开头,并且两个目录之间必须只有一个斜杠 "/"
  • 规范路径不能以斜杠 "/" 结尾(除非它是根目录 "/")。

输入:一个字符串 path,表示文件系统中的绝对路径。

输出:返回简化后的规范路径。


二、解题思路

核心思想

  1. 使用 来存储路径中的有效目录名。
  2. 遍历路径,根据不同的字符处理:
    • 遇到 "..":如果栈非空,则弹出栈顶目录(回退到上一级)。
    • 遇到 "." 或空字符:跳过,表示当前目录或无意义路径。
    • 遇到有效目录名:将其压入栈中。
  3. 最后,将栈中的目录名按照斜杠拼接成最终的简化路径。

三、具体实现

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&#xff0c;表示一个由目录名和斜杠 "/" 组成的绝对路径&#xff0c;请简化该路径&#xff0c;使其变为规范路径。 在 Unix 风格的文件系统中&#xff1a; 一个点 "." 表示当前目录本身&#xff1b;两个点 "..&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

分布式下怎么优化处理数据&#xff0c;怎么代替Join 简单来说&#xff0c; 可以采用 数据冗余&#xff0c;有意地存储一些重复的数据&#xff0c;以此减少关联查询的需求 数据拆分与多次查询&#xff0c;将一次获取的多表数据&#xff0c;拆分多个单独的查询 使用数据仓库…...

51单片机快速入门之中断的应用 2024/11/23 串口中断

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

[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简化处理错误策略&#xff0c;本文解释eyre错误处理库&#xff0c;并通过多个实际示例进行说明&#xff0c;最后于anyhow库进行对比&#xff0c;让你更好理解其应用场景。 eyre是一个用于 Rust 的错误处理库&#x…...

面试小札:JVM虚拟机

1. 定义与基本概念 - JVM&#xff08;Java Virtual Machine&#xff09;即Java虚拟机&#xff0c;是Java程序的运行核心。它是一个虚构出来的计算机&#xff0c;通过在实际的计算机上仿真模拟各种计算机功能来运行Java字节码。字节码是一种中间格式&#xff0c;它使得Java程序能…...

Docker扩容操作(docker总是空间不足)

Docker扩容操作(docker总是空间不足) 1、df二连&#xff0c;一共也就70g&#xff0c;总是占满93%以上。所以需要移动到其他目录上 查看docker镜像和容器存储目录的空间大小 du -sh /var/lib/docker/2、停止docker服务 systemctl stop docker3、首先创建目录并迁移 # 首先创…...

数字图像处理(4):FPGA中的定点数、浮点数

&#xff08;1&#xff09;定点数&#xff1a;小数点固定在数据的某一位置的数&#xff0c;可以分为定点整数和定点小数和普通定点数。定点数广泛应用于数字图像处理&#xff08;图像滤波、图像缩放&#xff09;和数字信号处理&#xff08;如FFT、定点卷积&#xff09;中。 定…...

毕昇入门学习

schemas.py 概述 这段代码主要定义了一系列基于 Pydantic 的数据模型&#xff08;BaseModel&#xff09;&#xff0c;用于数据验证和序列化&#xff0c;通常用于构建 API&#xff08;如使用 FastAPI&#xff09;。这些模型涵盖了用户认证、聊天消息、知识库管理、模型配置等多…...

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 中的看门狗&#xff08;Watchdog Timer&#xff0c;简称 WDG&#xff09;有两种主要类型&#xff1a;独立看门狗&#xff08;IWDG&#xff09; 和 窗口看门狗&#xff08;WWDG&#xff09;。它们的喂狗机制各有特点&#xff0c;主要区别如下&#xff1a; 1. 独立看门狗&a…...

【赵渝强老师】PostgreSQL的数据库

PostgreSQL的逻辑存储结构主要是指数据库中的各种数据库对象&#xff0c;包括&#xff1a;数据库集群、数据库、表、索引、视图等等。所有数据库对象都有各自的对象标识符oid&#xff08;object identifiers&#xff09;,它是一个无符号的四字节整数&#xff0c;相关对象的oid都…...

linux安全管理-会话安全

文章目录 1 设置命令行界面超时退出2 配置终端登录失败策略3 配置 SSH 登录失败策略 1 设置命令行界面超时退出 1、检查内容 检查操作系统是否设置命令行界面超时退出。 2、配置要求 操作系统设置命令行界面超时退出。 3、配置方法 配置命令行界面超时时间&#xff0c;编辑/et…...

Ubuntu监视显卡占用情况

在终端中运行 watch -n 0.5 nvidia-smi【以下内容由大模型生成】 watch -n 0.5 nvidia-smi 是一个组合命令&#xff0c;用于在 Linux 终端中定期执行 nvidia-smi 命令并显示其输出。让我们分解一下这个命令的各个部分&#xff1a; watch: watch 是一个用于定期执行其他命令并显…...

学成在线day06

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

Mac安装及合规无限使用Beyond Compare

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

【青牛科技】2K02 电动工具专用调速电路芯片描述

概述&#xff1a; 2K02 是电动工具专用调速电路。内置稳压电路&#xff0c;温度系数好&#xff0c;可以调节输出频率以及占空比的振荡输出&#xff0c;广泛的应用于小型电钻&#xff0c;割草机等工具。 主要特点&#xff1a; ● 电源电压范围宽 ● 占空比可调 ● 温度系数好 …...

基于SpringBoot实现的民宿管理系统(代码+论文)

&#x1f389;博主介绍&#xff1a;Java领域优质创作者&#xff0c;阿里云博客专家&#xff0c;计算机毕设实战导师。专注Java项目实战、毕设定制/协助 &#x1f4e2;主要服务内容&#xff1a;选题定题、开题报告、任务书、程序开发、项目定制、论文辅导 &#x1f496;精彩专栏…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...