GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — 71. 简化路径 · SinceraXY/Algorithm_code@137cf2c

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • leetcode/medium/71_简化路径
    • 71_简化路径.cpp
    • 71_简化路径.go
    • 71_简化路径.py
    • README.md
  • notes
    • README.md
    • topics
      • 栈与队列算法专题.md
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎leetcode/medium/71_简化路径/71_简化路径.cpp‎

Copy file name to clipboard
+43Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
class Solution {
2+
public:
3+
string simplifyPath(string path) {
4+
auto split = [](const string& s, char delim) -> vector<string> {
5+
vector<string> ans;
6+
string cur;
7+
for(char ch: s) {
8+
if(ch==delim){
9+
ans.push_back(move(cur));
10+
cur.clear();
11+
}
12+
else {
13+
cur += ch;
14+
}
15+
}
16+
ans.push_back(move(cur));
17+
return ans;
18+
};
19+
20+
vector<string> names = split(path, '/');
21+
vector<string> stack;
22+
for(string& name: names) {
23+
if(name=="..") {
24+
if(!stack.empty()) {
25+
stack.pop_back();
26+
}
27+
}
28+
else if(!name.empty()&&name!=".") {
29+
stack.push_back(move(name));
30+
}
31+
}
32+
string ans;
33+
if(stack.empty()) {
34+
ans="/";
35+
}
36+
else {
37+
for(string& name:stack) {
38+
ans += "/" + move(name);
39+
}
40+
}
41+
return ans;
42+
}
43+
};
Collapse file

‎leetcode/medium/71_简化路径/71_简化路径.go‎

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
func simplifyPath(path string) string {
2+
stack := []string{}
3+
for _, name := range strings.Split(path, "/") {
4+
if name == ".." {
5+
if len(stack) > 0 {
6+
stack = stack[:len(stack)-1]
7+
}
8+
} else if name != "" && name != "." {
9+
stack = append(stack, name)
10+
}
11+
}
12+
return "/" + strings.Join(stack, "/")
13+
}
Collapse file

‎leetcode/medium/71_简化路径/71_简化路径.py‎

Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution:
2+
def simplifyPath(self, path: str) -> str:
3+
names=path.split("/")
4+
stack=list()
5+
for name in names:
6+
if name == "..":
7+
if stack:
8+
stack.pop()
9+
elif name and name != ".":
10+
stack.append(name)
11+
return "/"+"/".join(stack)
12+
13+
14+
15+
#不建议
16+
class Solution:
17+
def simplifyPath(self, path: str) -> str:
18+
return os.path.realpath(path)
Collapse file

‎leetcode/medium/71_简化路径/README.md‎

Copy file name to clipboard
+127Lines changed: 127 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
# 71. 简化路径
2+
3+
- **平台**：LeetCode
4+
- **链接**：https://leetcode.cn/problems/simplify-path/description/
5+
- **难度**：Medium
6+
- **标签**：栈、字符串
7+
8+
## 题目描述
9+
10+
给你一个字符串 `path` ，表示指向某个文件或目录的 Unix 风格绝对路径。
11+
12+
请你将其转化为更加简洁的规范路径。
13+
14+
**规则：**
15+
1. `.` 表示当前目录，忽略。
16+
2. `..` 表示上一级目录（如果已经在根目录 `/`，则继续保持在根目录）。
17+
3. 多个连续的 `/` 视为一个 `/`。
18+
4. 规范路径必须以 `/` 开头，且不能以 `/` 结尾（根目录 `/` 除外）。
19+
20+
返回规范化后的路径。
21+
22+
## 示例
23+
24+
**示例 1：**
25+
```
26+
输入：path = "/home/"
27+
输出："/home"
28+
```
29+
30+
**示例 2：**
31+
```
32+
输入：path = "/../"
33+
输出："/"
34+
```
35+
36+
**示例 3：**
37+
```
38+
输入：path = "/home//foo/"
39+
输出："/home/foo"
40+
```
41+
42+
## 解题思路
43+
44+
### 方法：栈（模拟目录层级）
45+
46+
**核心思路：**
47+
- 以 `/` 为分隔符，把路径切分成若干段（目录名）。
48+
- 用一个“栈”（可用数组 / `vector` / `list`）维护当前已经确认的目录层级：
49+
- 遇到空串 `""` 或 `.`：跳过。
50+
- 遇到 `..`：如果栈非空则弹出栈顶；如果栈为空说明已经在根目录，忽略。
51+
- 其他普通目录名：入栈。
52+
- 最后把栈中目录用 `/` 拼接回去：
53+
- 栈空则答案为 `/`。
54+
- 否则答案为 `"/" + join(stack, "/")`。
55+
56+
**为什么要用栈：**
57+
- `..` 的语义是“回到上一级目录”，天然符合 LIFO（后进先出）的回退行为。
58+
59+
## 代码实现
60+
61+
### C++
62+
```cpp
63+
class Solution {
64+
public:
65+
string simplifyPath(string path) {
66+
auto split = [](const string& s, char delim) -> vector<string> {
67+
vector<string> ans;
68+
string cur;
69+
for(char ch: s) {
70+
if(ch==delim){
71+
ans.push_back(move(cur));
72+
cur.clear();
73+
}
74+
else {
75+
cur += ch;
76+
}
77+
}
78+
ans.push_back(move(cur));
79+
return ans;
80+
};
81+
82+
vector<string> names = split(path, '/');
83+
vector<string> stack;
84+
for(string& name: names) {
85+
if(name=="..") {
86+
if(!stack.empty()) {
87+
stack.pop_back();
88+
}
89+
}
90+
else if(!name.empty()&&name!=".") {
91+
stack.push_back(move(name));
92+
}
93+
}
94+
string ans;
95+
if(stack.empty()) {
96+
ans="/";
97+
}
98+
else {
99+
for(string& name:stack) {
100+
ans += "/" + move(name);
101+
}
102+
}
103+
return ans;
104+
}
105+
};
106+
```
107+
108+
本题提供了三种语言的实现（思路一致）：
109+
110+
- [C++ 实现](./71_简化路径.cpp)
111+
- [Python 实现](./71_简化路径.py)
112+
- [Go 实现](./71_简化路径.go)
113+
114+
## 复杂度分析
115+
116+
设 `n` 为字符串 `path` 的长度。
117+
118+
- **时间复杂度**：O(n)。切分 + 扫描每个字符/片段一次，最终拼接同阶。
119+
- **空间复杂度**：O(n)。栈在最坏情况下存下所有目录名（不考虑返回字符串本身也同阶）。
120+
121+
## 关键点
122+
123+
1. 分割后会出现空串（例如前导 `/`、尾部 `/`、以及 `//`），需要跳过。
124+
2. `..` 只有在栈非空时才弹栈，否则代表已经在根目录。
125+
3. 最终结果：
126+
- 栈为空返回 `/`。
127+
- 栈非空用 `/` 连接，并确保不以 `/` 结尾。
Collapse file

‎notes/README.md‎

Copy file name to clipboardExpand all lines: notes/README.md
+52-2Lines changed: 52 additions & 2 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,7 @@
7575
| 专题 | 难度 | 核心技巧 | 关键要点 | 文档链接 |
7676
|------|------|----------|----------|----------|
7777
| 📊 数组算法 | ⭐⭐ | 二分查找、双指针、滑动窗口、前缀和 | 有序性质、区间操作、原地修改 | [查看详情](./topics/数组算法专题.md) |
78-
| 🔗 链表算法 | ⭐⭐ | 虚拟头节点、快慢指针、反转技巧 | 统一边界处理、空间O(1) | [查看详情](./topics/链表算法专题.md) |
78+
| 🔗 链表算法 | ⭐⭐ | 虚拟头节点、快慢指针、反转技巧 | 统一边界处理、空间 O(1) | [查看详情](./topics/链表算法专题.md) |
7979
| 🔢 哈希表算法 | ⭐⭐ | 数组计数、映射关系、去重集合 | 空间换时间、容器选择、范围判断 | [查看详情](./topics/哈希表算法专题.md) |
8080
| 🔤 字符串算法 | ⭐⭐⭐ | KMP匹配、滑动窗口、回文检测 | 模式识别、字符统计、原地操作 | [查看详情](./topics/字符串算法专题.md) |
8181
| 📚 栈队列算法 | ⭐⭐ | 单调栈、容器适配器、双栈实现 | LIFO/FIFO、不提供迭代器、STL原理 | [查看详情](./topics/栈与队列算法专题.md) |
@@ -91,6 +91,7 @@
9191
| 🪟 | **滑动窗口** - 固定窗口、可变窗口、时间优化 | [查看 ↓](#-滑动窗口) |
9292
| 🎭 | **虚拟头节点** - 链表操作统一处理技巧 | [查看 ↓](#-虚拟头节点技巧) |
9393
| 🔢 | **哈希表** - 数组/set/map选择、容器对比 | [查看 ↓](#-哈希表) |
94+
| 📚 | **栈队列要点速记** - 单调队列、deque、堆/priority_queue | [查看 ↓](#-栈队列专题要点速记) |
9495
| 📊 | **复杂度分析** - 时间空间复杂度速查表 | [查看 ↓](#-复杂度分析) |
9596
| 🛠️ | **解题技巧** - 问题识别、优化策略、思维模式 | [查看 ↓](#️-解题技巧) |
9697

@@ -252,7 +253,6 @@ bool isPalindrome(string s) {
252253
253254
</div>
254255
255-
256256
## 🪟 滑动窗口
257257
258258
### 💡 核心思想
@@ -622,6 +622,56 @@ bool isAnagram(string s, string t) {
622622
- **优化哈希函数**：自定义类型需实现高质量哈希函数
623623
- **控制负载因子**：及时扩容保持查询效率
624624

625+
## 📚 栈队列专题要点速记
626+
627+
<div style="background-color: #FFF9E6; border-left: 4px solid #FFB900; padding: 12px; margin: 16px 0;">
628+
629+
### 📈 单调队列（Monotonic Queue）
630+
631+
> 「单调队列不是一成不变的，而是不同场景不同写法」，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。
632+
>
633+
> 「不要以为某题中的单调队列实现就是固定的写法。」
634+
635+
**常见写法差异**：
636+
- **存下标**：便于判断窗口边界
637+
- **存数值**：自定义 `push/pop/front` 接口
638+
639+
</div>
640+
641+
<div style="background-color: #E8F5E9; border-left: 4px solid #4CAF50; padding: 12px; margin: 16px 0;">
642+
643+
### 🧱 deque 与单调队列
644+
645+
单调队列通常用 `deque` 作为底层数据结构。
646+
647+
在 C++ 中，`deque` 是 `stack` 和 `queue` 默认的底层实现容器：
648+
- 支持两端扩展
649+
- `deque` 的元素并不是严格连续分布
650+
651+
</div>
652+
653+
<div style="background-color: #E1F5FE; border-left: 4px solid #03A9F4; padding: 12px; margin: 16px 0;">
654+
655+
### 🏔️ 优先级队列（priority_queue）与堆（heap）
656+
657+
**什么是优先级队列？**
658+
659+
其实「就是一个披着队列外衣的堆」，因为优先级队列对外接口只是从队头取元素、从队尾添加元素。
660+
661+
**缺省实现：**
662+
663+
缺省情况下 `priority_queue` 利用 max-heap（大顶堆）完成对元素的排序，这个大顶堆是以 `vector` 为表现形式的 complete binary tree（完全二叉树）。
664+
665+
**什么是堆？**
666+
667+
「堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。」如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
668+
669+
### 🎯 TopK 的复杂度直觉（部分排序）
670+
671+
很多 TopK 问题的关键是「使用优先级队列来对部分频率进行排序」，只维护大小为 `k` 的小顶堆即可，因此堆操作是 `O(logk)`，整体常见为 `O(nlogk)`。
672+
673+
</div>
674+
625675
## 📊 复杂度分析
626676

627677
### ⏱️ 时间复杂度对照表
Collapse file

‎notes/topics/栈与队列算法专题.md‎

Copy file name to clipboardExpand all lines: notes/topics/栈与队列算法专题.md
+35Lines changed: 35 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
## 📚 专题目录
44
- [栈与队列基础](#栈与队列基础)
55
- [STL底层实现](#STL底层实现)
6+
- [优先级队列与堆](#优先级队列与堆)
67
- [栈的经典应用](#栈的经典应用)
78
- [队列的经典应用](#队列的经典应用)
89
- [单调栈](#单调栈)
@@ -171,6 +172,8 @@ public:
171172
- ✅ **内存效率**: 比vector更节省内存重分配
172173
- ✅ **随机访问**: 支持O(1)随机访问 (虽然栈队列用不到)
173174

175+
`deque` 可以两边扩展，而且 `deque` 里元素并不是严格的连续分布。
176+
174177
**不同底层容器对比**:
175178
| 容器 | 栈适用性 | 队列适用性 | 原因 |
176179
|------|----------|-----------|------|
@@ -180,6 +183,30 @@ public:
180183

181184
---
182185

186+
## 优先级队列与堆
187+
188+
什么是优先级队列呢？
189+
190+
其实「就是一个披着队列外衣的堆」，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
191+
192+
而且优先级队列内部元素是自动依照元素的权值排列。缺省情况下 `priority_queue` 利用 max-heap（大顶堆）完成对元素的排序，这个大顶堆是以 `vector` 为表现形式的 complete binary tree（完全二叉树）。
193+
194+
什么是堆呢？
195+
196+
「堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。」如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
197+
198+
所以大家经常说的大顶堆（堆头是最大元素）、小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用 `priority_queue`（优先级队列）就可以了，底层实现都是一样的。
199+
200+
### TopK 的复杂度直觉（只对部分数据排序）
201+
202+
很多 TopK 问题并不需要对所有数据排序，而是「使用优先级队列来对部分频率进行排序」。
203+
204+
当我们只维护大小为 `k` 的堆时：
205+
- 每次堆操作是 O(logk)
206+
- 处理 n 个元素时，总体常见为 O(nlogk)
207+
208+
---
209+
183210
## 📚 栈的经典应用
184211

185212
### 1. 括号匹配
@@ -352,6 +379,14 @@ int largestRectangleArea(vector<int>& heights) {
352379

353380
**定义**: 队列内元素保持单调性的队列结构 (通常用双端队列实现)
354381

382+
> 「单调队列不是一成不变的，而是不同场景不同写法」，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。
383+
>
384+
> 「不要以为某题中的单调队列实现就是固定的写法。」
385+
386+
常见写法差异：
387+
- 存下标（便于判断窗口边界）
388+
- 存数值（自定义 `push/pop/front` 接口）
389+
355390
### 滑动窗口最大值
356391
```cpp
357392
class MonotonicQueue {

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.