Skip to content

Commit 2bb0318

Browse files
JstarfishJstarfish
committed
📚stack
1 parent cfc2ee2 commit 2bb0318

File tree

100 files changed

+7773
-7133
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

100 files changed

+7773
-7133
lines changed

‎docs/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/.obsidian/workspace.json‎

Lines changed: 17 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -25,8 +25,8 @@
2525
"state": {
2626
"type": "markdown",
2727
"state": {
28-
"file": "data-structure-algorithms/Dynamic-Programming.md",
29-
"mode": "preview",
28+
"file": "data-structure-algorithms/Double-Pointer.md",
29+
"mode": "source",
3030
"source": false
3131
}
3232
}
@@ -98,7 +98,7 @@
9898
"state": {
9999
"type": "backlink",
100100
"state": {
101-
"file": "data-structure-algorithms/Dynamic-Programming.md",
101+
"file": "data-structure-algorithms/Double-Pointer.md",
102102
"collapseAll": false,
103103
"extraContext": false,
104104
"sortOrder": "alphabetical",
@@ -115,7 +115,7 @@
115115
"state": {
116116
"type": "outgoing-link",
117117
"state": {
118-
"file": "data-structure-algorithms/Dynamic-Programming.md",
118+
"file": "data-structure-algorithms/Double-Pointer.md",
119119
"linksCollapsed": false,
120120
"unlinkedCollapsed": true
121121
}
@@ -138,7 +138,7 @@
138138
"state": {
139139
"type": "outline",
140140
"state": {
141-
"file": "data-structure-algorithms/Dynamic-Programming.md"
141+
"file": "data-structure-algorithms/Double-Pointer.md"
142142
}
143143
}
144144
}
@@ -161,16 +161,26 @@
161161
},
162162
"active": "264bec0c6c3126ab",
163163
"lastOpenFiles": [
164+
"data-structure-algorithms/algorithm/Backtracking.md",
165+
"data-structure-algorithms/algorithm/未命名.md",
166+
"data-structure-algorithms/Leetcode-dynamic-programming.md",
167+
"data-structure-algorithms/complexity.md",
168+
"data-structure-algorithms/README.md",
169+
"data-structure-algorithms/Linked-List.md",
170+
"data-structure-algorithms/Array.md",
171+
"data-structure-algorithms/algorithm",
172+
"data-structure-algorithms/未命名文件夹",
173+
"data-structure-algorithms/Back-Track.md",
174+
"data-structure-algorithms/Double-Pointer.md",
175+
"data-structure-algorithms/Dynamic-Programming.md",
164176
"data-structure-algorithms/soultion/String-Solution.md",
165177
"data-structure-algorithms/soultion/LinkedList-Soultion.md",
166178
"data-structure-algorithms/soultion/stock-problems.md",
167179
"data-structure-algorithms/soultion/Math-Solution.md",
168180
"data-structure-algorithms/soultion/Array-Solution.md",
169181
"data-structure-algorithms/soultion/DP-Solution.md",
170-
"data-structure-algorithms/Linked-List.md",
171182
"interview/Kafka-FAQ.md",
172183
"work/DPA.md",
173-
"data-structure-algorithms/Array.md",
174184
"data-structure-algorithms/Recursion.md",
175185
"data-management/Big-Data/Bloom-Filter.md"
176186
]

‎docs/.vuepress/config.js‎

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -150,9 +150,16 @@ function genDSASidebar() {
150150
return [
151151
{
152152
title: "数据结构",
153-
collapsable: false,
154-
sidebarDepth: 2, // 可选的, 默认值是 1
155-
children: ["Array","Linked-List","Stack","Queue","Binary-Tree","Skip-List"]
153+
collapsable: true,
154+
//sidebarDepth: 2, // 可选的, 默认值是 1
155+
children: [
156+
['data-structure/Array','数组'],
157+
['data-structure/Linked-List','链表'],
158+
['data-structure/Stack','栈'],
159+
['data-structure/Queue','队列'],
160+
['data-structure/Binary-Tree','二叉树'],
161+
['data-structure/Skip-List','跳表']
162+
]
156163
},
157164
{
158165
title: "算法",

‎docs/data-structure-algorithms/.DS_Store‎

2 KB
Binary file not shown.

‎docs/data-structure-algorithms/algorithm/Backtracking.md‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
---
2+
title: 回溯算法
3+
date: 2023-05-09
4+
tags:
5+
- back tracking
6+
categories: Algorithm
7+
---
8+
9+
![](https://img.starfish.ink/leetcode/backtracking-banner.png)
10+
11+
> 回溯算法」是解决很多算法问题的常见思想，它也是传统的人工智能的方法，其本质是 **在树形问题中寻找解** 。
12+
>
13+
> 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
14+
15+
# 回溯算法
16+
17+
> **回溯法** 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
18+
>
19+
> - 找到一个可能存在的正确的答案；
20+
> - 在尝试了所有可能的分步方法后宣告该问题没有答案。
21+
22+
> **深度优先搜索** 算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会 **尽可能深** 的搜索树的分支。当结点 `v` 的所在边都己被探寻过，搜索将 **回溯** 到发现结点 `v` 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
23+
24+
我刚开始学习「回溯算法」的时候觉得很抽象，一直不能理解为什么 **递归之后需要做和递归之前相同的逆向操作**，在做了很多相关的问题以后，我发现其实「回溯算法」与「 **深度优先遍历** 」有着千丝万缕的联系。
25+
26+
27+
28+
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
29+
30+
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
31+
32+
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
33+
34+
35+
36+
## 基本思想
37+
38+
> **回溯法** 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
39+
>
40+
> - 找到一个可能存在的正确的答案；
41+
> - 在尝试了所有可能的分步方法后宣告该问题没有答案。
42+
43+
> **深度优先搜索** 算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会 **尽可能深** 的搜索树的分支。当结点 `v` 的所在边都己被探寻过，搜索将 **回溯** 到发现结点 `v` 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
44+
45+
我刚开始学习「回溯算法」的时候觉得很抽象，一直不能理解为什么 **递归之后需要做和递归之前相同的逆向操作**，在做了很多相关的问题以后，我发现其实「回溯算法」与「 **深度优先遍历** 」有着千丝万缕的联系。
46+
47+
48+
49+
50+
51+
## 示例
52+
53+
### [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)
54+
55+
> 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
56+
>
57+
> 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
58+
>
59+
> ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png)
60+
>
61+
> ```
62+
> 输入：digits = "23"
63+
> 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
64+
> ```
65+
66+
思路：
67+
68+
![17. 电话号码的字母组合](https://code-thinking-1253855093.file.myqcloud.com/pics/20201123200304469.png)
69+
70+
图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
71+
72+
73+
74+
![](https://pic.leetcode-cn.com/02b0ec926e3da5f12a0a118293b8ac10dc236741ccb04414ded44a30f7fc70af-1573829897(1).jpg)

docs/data-structure-algorithms/Array.md renamed to docs/data-structure-algorithms/data-structure/Array.md

File renamed without changes.

docs/data-structure-algorithms/Binary-Tree.md renamed to docs/data-structure-algorithms/data-structure/Binary-Tree.md

File renamed without changes.

docs/data-structure-algorithms/Linked-List.md renamed to docs/data-structure-algorithms/data-structure/Linked-List.md

File renamed without changes.

docs/data-structure-algorithms/Queue.md renamed to docs/data-structure-algorithms/data-structure/Queue.md

File renamed without changes.

docs/data-structure-algorithms/Skip-List.md renamed to docs/data-structure-algorithms/data-structure/Skip-List.md

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,10 @@
1-
# 跳表
1+
---
2+
title: 跳表
3+
date: 2023-05-09
4+
tags:
5+
- Skip List
6+
categories: data-structure
7+
---
28

39
![](https://img.starfish.ink/data-structure/skiplist-banner.png)
410

0 commit comments

Comments
 (0)