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

利用最小二乘法找圆心和半径

#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; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

CMake 从 GitHub 下载第三方库并使用

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

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Linux --进程控制

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

DingDing机器人群消息推送

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

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...