Skip to content

Commit ade3a1e

Browse files
JstarfishJstarfish
committed
dfs
1 parent 2e7e0d8 commit ade3a1e

File tree

8 files changed

+180
-168
lines changed

8 files changed

+180
-168
lines changed

‎docs/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/data-management/MySQL/MySQL-Segmentation.md‎

Lines changed: 64 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -36,48 +36,77 @@ subtopic
3636

3737

3838

39-
### 分区类型及操作
40-
41-
#### RANGE分区
42-
43-
mysql将会根据指定的拆分策略，,把数据放在不同的表文件上。相当于在文件上,被拆成了小块.但是,对外给客户的感觉还是一张表，透明的。
44-
45-
按照 range 来分，就是每个库一段连续的数据，这个一般是按比如**时间范围**来的，但是这种一般较少用，因为很容易产生热点问题，大量的流量都打在最新的数据上了。
46-
47-
range 来分，好处在于说，扩容的时候很简单
48-
49-
#### List分区
50-
51-
MySQL中的LIST分区在很多方面类似于RANGE分区。和按照RANGE分区一样，每个分区必须明确定义。它们的主要区别在于，LIST分区中每个分区的定义和选择是基于某列的值从属于一个值列表集中的一个值，而RANGE分区是从属于一个连续区间值的集合。
52-
53-
#### 其它
54-
55-
- Hash分区: hash 分发，好处在于说，可以平均分配每个库的数据量和请求压力；坏处在于说扩容起来比较麻烦，会有一个数据迁移的过程，之前的数据需要重新计算 hash 值重新分配到不同的库或表
56-
57-
- Key分区
58-
59-
- 子分区
60-
61-
#### 对NULL值的处理
62-
63-
64-
MySQL中的分区在禁止空值NULL上没有进行处理，无论它是一个列值还是一个用户定义表达式的值，一般而言，在这种情况下MySQL把NULL当做零。如果你不希望出现类似情况，建议在设计表时声明该列“NOT NULL”
65-
39+
- **RANGE分区**：基于属于一个给定连续区间的列值，把多行分配给分区。mysql将会根据指定的拆分策略，把数据放在不同的表文件上。相当于在文件上,被拆成了小块.但是,对外给客户的感觉还是一张表，透明的。
40+
41+
按照 range 来分，就是每个库一段连续的数据，这个一般是按比如**时间范围**来的，比如交易表啊，销售表啊等，可以根据年月来存放数据。可能会产生热点问题，大量的流量都打在最新的数据上了。
42+
43+
range 来分，好处在于说，扩容的时候很简单。
44+
45+
```mysql
46+
CREATE TABLE sales (
47+
id INT,
48+
amount DECIMAL(10,2),
49+
sale_date DATE
50+
)
51+
PARTITION BY RANGE (YEAR(sale_date)) (
52+
PARTITION p0 VALUES LESS THAN (2000),
53+
PARTITION p1 VALUES LESS THAN (2005),
54+
PARTITION p2 VALUES LESS THAN (2010),
55+
PARTITION p3 VALUES LESS THAN MAXVALUE
56+
);
57+
```
58+
59+
- **LIST分区**：按列表划分，类似于RANGE分区，但使用的是明确的值列表。
60+
61+
它们的主要区别在于，LIST分区中每个分区的定义和选择是基于某列的值从属于一个值列表集中的一个值，而RANGE分区是从属于一个连续区间值的集合。
62+
63+
```mysql
64+
CREATE TABLE customers (
65+
id INT,
66+
name VARCHAR(50),
67+
country VARCHAR(50)
68+
)
69+
PARTITION BY LIST (country) (
70+
PARTITION p0 VALUES IN ('USA', 'Canada'),
71+
PARTITION p1 VALUES IN ('UK', 'France'),
72+
PARTITION p2 VALUES IN ('Germany', 'Italy')
73+
);
74+
```
75+
76+
- **HASH分区**：按哈希算法划分，将数据根据某个列的哈希值均匀分布到不同的分区中。
77+
78+
hash 分发，好处在于说，可以平均分配每个库的数据量和请求压力；坏处在于说扩容起来比较麻烦，会有一个数据迁移的过程，之前的数据需要重新计算 hash 值重新分配到不同的库或表
79+
80+
```mysql
81+
CREATE TABLE orders (
82+
id INT,
83+
order_date DATE,
84+
customer_id INT
85+
)
86+
PARTITION BY HASH(id) PARTITIONS 4;
87+
```
88+
89+
- **KEY分区**：类似于HASH分区，但使用MySQL内部的哈希函数。
90+
91+
```mysql
92+
CREATE TABLE logs (
93+
id INT,
94+
log_date DATE
95+
)
96+
PARTITION BY KEY(id) PARTITIONS 4;
97+
```
6698

99+
67100

68101
**看上去分区表很帅气，为什么大部分互联网还是更多的选择自己分库分表来水平扩展咧？**
69102

70-
回答：
103+
- 分区表，分区键设计不太灵活，如果不走分区键，很容易出现全表锁
71104

72-
1）分区表，分区键设计不太灵活，如果不走分区键，很容易出现全表锁
73-
74-
2）一旦数据量并发量上来，如果在分区表实施关联，就是一个灾难
75-
76-
3）自己分库分表，自己掌控业务场景与访问模式，可控。分区表，研发写了一个sql，都不确定mysql是怎么玩的，不太可控
77-
78-
4）运维的坑，嘿嘿
105+
- 一旦数据并发量上来，如果在分区表实施关联，就是一个灾难
79106

107+
- 自己分库分表，自己掌控业务场景与访问模式，可控。分区表，研发写了一个sql，都不确定mysql是怎么玩的，不太可控
80108

109+
81110

82111
## Mysql分库
83112

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

0 Bytes
Binary file not shown.

‎docs/data-structure-algorithms/soultion/Binary-Tree-Solution.md‎

Lines changed: 13 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -829,28 +829,27 @@ public boolean isSameTree(TreeNode p, TreeNode q) {
829829
830830
```java
831831
public void flatten(TreeNode root) {
832-
if (root == null) return;
833-
834-
// 递归处理左右子树，确保所有子树都已展开为链表
835-
flatten(root.left);
836-
flatten(root.right);
832+
if (root == null) {
833+
return; // 如果根节点为空，则直接返回
834+
}
837835
838-
// 保存已展开的左右子树
839-
TreeNode left = root.left;
840-
TreeNode right = root.right;
836+
flatten(root.left); // 递归展开左子树
837+
flatten(root.right); // 递归展开右子树
841838
842-
// 将左子树移动到右子树位置，左指针置空
839+
// 将左子树移到右子树的位置
840+
TreeNode temp = root.right;
841+
root.right = root.left;
843842
root.left = null;
844-
root.right = left;
845843
846-
// 找到新右子树的末尾节点（从根节点开始遍历）
847-
TreeNode curr = root;
844+
// 找到当前右子树的末尾节点
845+
TreeNode curr = root.right;
848846
while (curr.right != null) {
849847
curr = curr.right;
850848
}
851849
852-
// 将原右子树连接到新右子树的末尾
853-
curr.right = right;
850+
// 将原来的右子树接到当前右子树的末尾
851+
curr.right = temp;
852+
}
854853
}
855854
```
856855

‎docs/data-structure-algorithms/soultion/DFS-Solution.md‎

Lines changed: 63 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -153,60 +153,62 @@ categories: leetcode
153153
> 输出：true
154154
> ```
155155
156-
- **DFS 思路**：从每个起点出发，四方向搜索匹配字符，回溯恢复现场。
156+
思路：本问题是典型的回溯问题，需要使用**深度优先搜索（DFS）+ 剪枝**解决。
157157
158-
- 代码实现：
158+
**DFS 思路**：从每个起点出发，四方向搜索匹配字符，回溯恢复现场。
159159
160-
```java
161-
public boolean exist(char[][] board, String word) {
162-
// 遍历网格中的每一个单元格作为起始点
163-
for (int i = 0; i < board.length; i++) {
164-
for (int j = 0; j < board[0].length; j++) {
165-
// 注意：此处缺少首字符过滤，会进入不必要的递归，但最终结果正确
166-
if (dfs(board, word, 0, i, j))
167-
return true; // 找到路径立即返回
168-
}
169-
}
170-
return false; // 全部遍历后仍未找到
171-
}
172-
173-
/**
174-
* 深度优先搜索核心方法
175-
* @param board 二维字符网格
176-
* @param word 目标单词
177-
* @param idx 当前需要匹配的字符索引
178-
* @param r 当前行坐标
179-
* @param c 当前列坐标
180-
* @return 是否找到有效路径
181-
*/
182-
private boolean dfs(char[][] board, String word, int idx, int r, int c) {
183-
// 成功条件：已匹配完所有字符
184-
if (idx == word.length()) return true;
185-
186-
// 边界检查 + 剪枝（当前字符不匹配）
187-
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length
188-
|| board[r][c] != word.charAt(idx))
189-
return false;
190-
191-
// 标记已访问（防止重复使用）
192-
char tmp = board[r][c];
193-
board[r][c] = '#';
194-
195-
// 向四个方向递归搜索（顺序：下、上、右、左）
196-
boolean res = dfs(board, word, idx + 1, r + 1, c) // 向下
197-
|| dfs(board, word, idx + 1, r - 1, c) // 向上
198-
|| dfs(board, word, idx + 1, r, c + 1) // 向右
199-
|| dfs(board, word, idx + 1, r, c - 1); // 向左
200-
201-
// 回溯：恢复现场，让其他路径能重新访问该节点
202-
board[r][c] = tmp;
203-
204-
return res;
205-
}
206-
```
160+
```java
161+
public boolean exist(char[][] board, String word) {
162+
// 遍历网格中的每一个单元格作为起始点
163+
for (int i = 0; i < board.length; i++) {
164+
for (int j = 0; j < board[0].length; j++) {
165+
// 注意：此处缺少首字符过滤，会进入不必要的递归，但最终结果正确
166+
if (dfs(board, word, 0, i, j))
167+
return true; // 找到路径立即返回
168+
}
169+
}
170+
return false; // 全部遍历后仍未找到
171+
}
172+
173+
/**
174+
* 深度优先搜索核心方法
175+
* @param board 二维字符网格
176+
* @param word 目标单词
177+
* @param idx 当前需要匹配的字符索引
178+
* @param r 当前行坐标
179+
* @param c 当前列坐标
180+
* @return 是否找到有效路径
181+
*/
182+
private boolean dfs(char[][] board, String word, int idx, int r, int c) {
183+
// 成功条件：已匹配完所有字符
184+
if (idx == word.length()) return true;
185+
186+
// 边界检查 + 剪枝（当前字符不匹配）
187+
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length
188+
|| board[r][c] != word.charAt(idx))
189+
return false;
190+
191+
// 标记已访问（防止重复使用）
192+
char tmp = board[r][c];
193+
board[r][c] = '#';
194+
195+
// 向四个方向递归搜索（顺序：下、上、右、左）
196+
boolean res = dfs(board, word, idx + 1, r + 1, c) // 向下
197+
|| dfs(board, word, idx + 1, r - 1, c) // 向上
198+
|| dfs(board, word, idx + 1, r, c + 1) // 向右
199+
|| dfs(board, word, idx + 1, r, c - 1); // 向左
200+
201+
// 回溯：恢复现场，让其他路径能重新访问该节点
202+
board[r][c] = tmp;
203+
204+
return res;
205+
}
206+
```
207207
208208
- **复杂度**：时间 $O(mn × 3ᴸ)$，空间 $O(L)$（L 为单词长度）。
209209

210+
211+
210212
### 4.2 树相关 DFS 问题
211213

212214
#### [二叉树的最大深度『104』](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
@@ -230,7 +232,7 @@ categories: leetcode
230232
思路：深度优先搜索
231233
232234
```java
233-
public static int maxDepth(TreeNode root) {
235+
public int maxDepth(TreeNode root) {
234236
if (root == null) {
235237
return 0;
236238
}
@@ -283,7 +285,7 @@ public boolean isSymmetric(TreeNode root){
283285
}
284286

285287
public boolean check(TreeNode left,TreeNode right){
286-
//递归的终止条件是两个节点都为空
288+
//递归的终止条件是两个节点都为空,必须先判断这个，确保都为null
287289
//或者两个节点中有一个为空
288290
//或者两个节点的值不相等
289291
if(left==null && right==null){
@@ -300,9 +302,15 @@ public boolean check(TreeNode left,TreeNode right){
300302

301303
#### [验证二叉搜索树『98』](https://leetcode.cn/problems/validate-binary-search-tree/)
302304

303-
- **问题描述**：判断二叉树是否满足 BST 性质。
305+
> **问题描述**：判断二叉树是否满足 BST 性质。
306+
>
307+
> **有效** 二叉搜索树定义如下：
308+
>
309+
> - 节点的左子树只包含 **小于** 当前节点的数。
310+
> - 节点的右子树只包含 **大于** 当前节点的数。
311+
> - 所有左子树和右子树自身必须也是二叉搜索树。
304312
305-
- **DFS 思路**：传递当前节点的值范围 [min, max]。
313+
思路：**DFS 思路**：我们可以在遍历的过程中维护一个范围（最大值到最小值），并检查每个节点的值是否落在这个范围内。
306314

307315
- 代码实现：
308316

@@ -312,10 +320,11 @@ public boolean check(TreeNode left,TreeNode right){
312320
}
313321

314322
private boolean validate(TreeNode node, long min, long max) {
323+
//叶子结点为空，说明不违反BST性质，true
315324
if (node == null) return true;
316325
//当前节点小于等于最小值或大于等于最大值，不满足
317326
if (node.val <= min || node.val >= max) return false;
318-
//递归左右子树，左子树的话，传递当前值为最大值
327+
//递归左右子树，左子树的话，传递当前值为最大值，这里要用 && 且
319328
return validate(node.left, min, node.val)
320329
&& validate(node.right, node.val, max);
321330
}

‎docs/interview/JVM-FAQ.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -486,6 +486,8 @@ OOM 如果通俗点儿说，就是 JVM 内存不够用了，javadoc 中对[OutOf
486486

487487
memory leak 最终会导致 out of memory！
488488

489+
内存泄漏是内存溢出的常见诱因，但内存溢出也可能由非泄漏因素（如数据量过大）直接引发
490+
489491

490492

491493
### 内存泄漏时，如何定位问题代码?

‎docs/interview/Java-Basics-FAQ.md‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -602,6 +602,19 @@ hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重
602602

603603

604604

605+
### 实例方法和静态方法有什么不一样?
606+
607+
| **对比维度** | **实例方法** | **静态方法** |
608+
| ---------------- | ------------------------------------------------ | -------------------------------------------- |
609+
| **归属** | 属于对象，需实例化后调用（`new Obj().method()`） | 属于类，直接通过类名调用（`Class.method()`） |
610+
| **内存分配** | 堆内存（对象创建时） | 方法区（类加载时） |
611+
| **调用方式** | `对象.方法名()` | `类名.方法名()` |
612+
| **访问实例成员** | 允许 | 禁止 |
613+
| **多态支持** | 支持重写（Override），运行时绑定 | 不支持重写，可隐藏父类同名静态方法（Hide） |
614+
| **适用场景** | 对象状态操作、工厂模式 | 工具类、单例模式、无状态计算 |
615+
616+
617+
605618
## 反射
606619

607620
### 什么是反射机制？

0 commit comments

Comments
 (0)