Skip to content

Commit 1109e55

Browse files
DuHouAnDuHouAn
committed
Java
1 parent 49dbf54 commit 1109e55

16 files changed

+2736
-89
lines changed

‎docs/DataBase/4_SQL.md‎

Lines changed: 764 additions & 1 deletion
Large diffs are not rendered by default.

‎docs/DataBase/5_LeetCode_Database题解.md‎

Lines changed: 1012 additions & 0 deletions
Large diffs are not rendered by default.

‎docs/LeetCode/12_算法思想.md‎

Lines changed: 1 addition & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -1001,89 +1001,9 @@ public void test(){
10011001
}
10021002
```
10031003

1004-
## 六、抢红包算法
10051004

1006-
线段切割法：在一条线段上找 (N-1) 个随机点，就可以将该线段随机且公平地切割成 N 段。
10071005

1008-
```java
1009-
//思路：线段切割法
1010-
//在一条线段上找 N-1 个随机点，就可以将该线段随机且公平地切割成 N 段。
1011-
public class RedPocket {
1012-
public List<Integer> generatePacketsByLineCutting(int people, int money) {
1013-
List<Integer> res = new ArrayList<>();
1014-
1015-
//在[0,money] 这条线段上找 （people-1） 个随机点
1016-
Set<Integer> points = new TreeSet<>(); //存储（people-1）个随机点
1017-
//使用 treeset 存储，保证这些点是有序的，方便后面的切分
1018-
1019-
Random random = new Random();
1020-
1021-
while(points.size() < people-1){
1022-
points.add(random.nextInt(money));
1023-
}
1024-
//此时 points.size() == people-1
1025-
points.add(money);
1026-
1027-
int pre=0;
1028-
for(int point:points){
1029-
res.add(point-pre);
1030-
pre = point;
1031-
}
1032-
return res;
1033-
}
1034-
1035-
@Test
1036-
public void test(){
1037-
int people =10;
1038-
int money = 100;
1039-
List<Integer> res= generatePacketsByLineCutting(people,money);
1040-
System.out.println(res);
1041-
int result =0;
1042-
for(Integer d:res){
1043-
result += d;
1044-
}
1045-
System.out.println("reslut:"+result);
1046-
}
1047-
}
1048-
```
1049-
1050-
## 七、洗牌算法
1051-
1052-
```java
1053-
// 算法的基本思想：每次从一组数中随机选出一个数，
1054-
// 然后与最后一个数交换位置，并且不再考虑最后一个数。
1055-
// 时间复杂度：O(N)
1056-
public static void shuffle(int[] nums){
1057-
Random random = new Random();
1058-
for(int i=nums.length-1;i>=0;i--){
1059-
int j = random.nextInt(i+1); //在[0,i]范围内
1060-
if(i==j){ //一个小优化
1061-
continue;
1062-
}
1063-
swap(nums,i,j); // i 指向数组最后一个元素
1064-
}
1065-
}
1066-
1067-
private static void swap(int[] nums,int i,int j){
1068-
int tmp = nums[i];
1069-
nums[i] = nums[j];
1070-
nums[j] = tmp;
1071-
}
1072-
1073-
public static void main(String[] args) {
1074-
int[] nums = {1,2,3,4,5,6,7,8};
1075-
shuffle(nums);
1076-
for(int num:nums){
1077-
System.out.println(num);
1078-
}
1079-
}
1080-
```
1081-
1082-
## 八、海量数据处理
1083-
1084-
1085-
1086-
## 五、DFS
1006+
## 六、DFS
10871007

10881008
### 1、岛屿的个数（200）
10891009

‎docs/LeetCode/5_二叉树.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -652,7 +652,9 @@ public void test(){
652652
}
653653
```
654654

655-
## 二、完全二叉树
655+
656+
657+
## 三、完全二叉树
656658

657659
### 1、判断一棵树是否是完全二叉树
658660

‎docs/LeetCode/6_回溯法.md‎

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -223,8 +223,15 @@ public void test(){
223223

224224
[216. 组合总和 III](https://leetcode-cn.com/problems/combination-sum-iii/)
225225

226-
### 78
226+
### 5、子集（78）
227227

228-
### 90
228+
[78. 子集](https://leetcode-cn.com/problems/subsets/)
229+
230+
### 6、子集II（90）
231+
232+
[90. 子集 II](https://leetcode-cn.com/problems/subsets-ii/)
233+
234+
### 7、二进制手表（401）
235+
236+
[401. 二进制手表](https://leetcode-cn.com/problems/binary-watch/)
229237

230-
### 401

‎docs/MySQL/1_MySQL架构.md‎

Whitespace-only changes.

‎docs/MySQL/1_锁机制.md‎

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
# 锁机制
2+
3+
## 数据库锁的分类
4+
5+
按照锁的**粒度**划分：
6+
7+
- 表级锁
8+
- 行级锁
9+
- 页级锁
10+
11+
按照锁的**级别**划分：
12+
13+
- 共享锁
14+
- 排它锁
15+
16+
按照**使用方式**划分：
17+
18+
- 乐观锁
19+
- 悲观锁
20+
21+
## 行级锁、表级锁、页级锁
22+
23+
### 1. 行级锁
24+
25+
行级锁是 MySQL 中锁定粒度最细的一种锁，表示只针对当前行进行加锁。行级锁分为共享锁和排他锁。
26+
27+
特点：
28+
29+
- 开销大，加锁慢
30+
- 会出现死锁
31+
- 锁定粒度最小，发生锁冲突的概率最低，并发度最高
32+
33+
### 2. 表级锁
34+
35+
表级锁时 MySQL 中锁定粒度最大的一种锁，表示对当前操作的整张表进行加锁。最常用的 MyISAM 和 InnoDB 都支持表级锁。
36+
37+
特点：
38+
39+
- 开销小，加锁快
40+
- 不会出现死锁
41+
- 锁定粒度最大，发生锁冲突的概率最高，并发度最低
42+
43+
### 3. 页级锁
44+
45+
页级锁是 MySQL 中锁定粒度介于表级锁和行级锁之间的一种锁。
46+
47+
特点：
48+
49+
- 开销和加锁时间介于表级锁和行级锁之间
50+
- 会出现死锁
51+
- 锁定粒度介于表锁和行锁之间，并发度一般
52+
53+
<div align="center"><img src="https://gitee.com/duhouan/ImagePro/raw/master/java-notes/database/1a851e90-0d5c-4d4f-ac54-34c20ecfb903.jpg" width="350px"/></div>
54+
55+
56+
57+
## 共享锁和排他锁
58+
59+
### 1. 共享锁（S）
60+
61+
共享锁（Shared）又称读锁，是读取操作创建的锁。
62+
63+
如果事务 T 对数据 A 加上共享锁后，则其他事务只能对 A 再加共享锁，不能加排他锁。获准共享锁的事务只能读数据，不能修改数据。
64+
65+
### 2. 排他锁（X）
66+
67+
排他锁（eXclusive）又称写锁。
68+
69+
如果事务 T 对数据 A 加上排他锁后，则其他事务不能再对 A 加上任何类型的锁。获取排他锁的事务既能读数据，又能修改数据。
70+
71+
共享锁和排他锁的兼容关系如下：
72+
73+
| - | X | S |
74+
| :--: | :--: | :--: |
75+
| X | 冲突 | 冲突 |
76+
| S | 冲突 | 兼容 |
77+
78+
79+
80+
## 意向锁
81+
82+
意向锁是**表级锁**，但表示事务正在读写某一行记录，而不是整个表。所以意向锁之间不会发生冲突，真正的冲突发生在加行锁时检查。
83+
84+
### 1. 意向共享锁（IS）
85+
86+
表示**事务准备给数据行加共享锁**，也就是说事务在一个数据行加共享锁前必须先获取该表的 IS 锁。
87+
88+
### 2. 意向排他锁（IX）
89+
90+
表示事务准备给数据行加排他锁，也就是说事务在一个数据行加排他锁前必须先获取该表的 IX 锁。
91+
92+
93+
94+
## 悲观锁和乐观锁
95+
96+
### 1. 悲观锁
97+
98+
悲观锁机制认为每一步如果不采取同步措施都会出现问题，**依赖于数据库的锁机制**。关系型数据库里边就用到了很多悲观锁机制，比如**行锁、表锁**等，**读锁、写锁**等，都是在做操作之前先上锁。
99+
100+
如果锁定时间过长，用户长时间无法访问，会影响程序的并发访问。
101+
102+
### 2. 乐观锁
103+
104+
先执行，如果存在冲突，则采取一个补偿措施（比如告知用户失败）。一般有 2 种实现方式：
105+
106+
- 使用版本号
107+
- 使用时间戳

0 commit comments

Comments
 (0)