当前位置: 首页 > 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;精彩专栏…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...