Skip to content

Commit dab2d64

Browse files
DreamCatsDreamCats
committed
📝 update alg
1 parent d8d7119 commit dab2d64

6 files changed

Lines changed: 356 additions & 1 deletion

File tree

‎Java/alg/.DS_Store‎

0 Bytes
Binary file not shown.

‎Java/alg/README.md‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -69,4 +69,8 @@
6969
- [434.字符串中的单词数](lc/434.字符串中的单词数.md)
7070
- [455.分发饼干](lc/455.分发饼干.md)
7171
- [461.汉明距离](lc/461.汉明距离.md)
72-
- [485.最大连续1的个数](lc/485.最大连续1的个数.md)
72+
- [485.最大连续1的个数](lc/485.最大连续1的个数.md)
73+
- [509.斐波那契数](lc/509.斐波那契数.md)
74+
- [543.二叉树的直径](lc/543.二叉树的直径.md)
75+
- [566.重塑矩阵](lc/566.重塑矩阵.md)
76+
- [572.另一个树的子树](lc/572.另一个树的子树.md)

‎Java/alg/lc/509.斐波那契数.md‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
# 509. 斐波那契数
2+
3+
4+
[url](https://leetcode-cn.com/problems/fibonacci-number/)
5+
6+
7+
## 题目
8+
斐波那契数，通常用 `F(n)` 表示，形成的序列称为 斐波那契数列 。该数列由 `0` 和 `1` 开始，后面的每一项数字都是前面两项数字的和。也就是：
9+
10+
```
11+
F(0) = 0，F(1) = 1
12+
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
13+
```
14+
15+
```
16+
输入：2
17+
输出：1
18+
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
19+
输入：3
20+
输出：2
21+
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
22+
输入：4
23+
输出：3
24+
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
25+
```
26+
27+
## 方法
28+
从下往上的思想
29+
30+
## code
31+
32+
### js
33+
34+
```js
35+
let fib = n => {
36+
if (n <= 1)
37+
return n;
38+
let pre2 = 0, pre1 = 1;
39+
for (let i = 2; i <= n; i++) {
40+
let sum = pre2 + pre1;
41+
pre2 = pre1;
42+
pre1 = sum;
43+
}
44+
return pre1;
45+
};
46+
console.log(fib(2));
47+
console.log(fib(3));
48+
console.log(fib(4));
49+
```
50+
51+
### go
52+
53+
```go
54+
func fib(n int) int {
55+
if n <= 1 {
56+
return n
57+
}
58+
pre2, pre1 := 0, 1
59+
for i := 2; i <= n; i++ {
60+
sum := pre2 + pre1
61+
pre2 = pre1
62+
pre1 = sum
63+
}
64+
return pre1
65+
}
66+
```
67+
68+
### java
69+
70+
```java
71+
class Solution {
72+
public int fib(int N) {
73+
if (N <= 1) return N;
74+
int pre2 = 0, pre1 = 1;
75+
for (int i = 2; i <= N; i++) {
76+
int sum = pre2 + pre1;
77+
pre2 = pre1;
78+
pre1 = sum;
79+
}
80+
return pre1;
81+
}
82+
}
83+
```
84+

‎Java/alg/lc/543.二叉树的直径.md‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
# 543. 二叉树的直径
2+
3+
4+
[url](https://leetcode-cn.com/problems/diameter-of-binary-tree/)
5+
6+
7+
## 题目
8+
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
9+
10+
11+
```
12+
1
13+
/ \
14+
2 3
15+
/ \
16+
4 5
17+
```
18+
返回 3, 它的长度是路径 `[4,2,1,3]` 或者 `[5,2,1,3]`。
19+
20+
## 方法
21+
从下往上的思想
22+
23+
## code
24+
25+
### js
26+
27+
```js
28+
let max = 0;
29+
let diameterOfBinaryTree = root => {
30+
depth(root);
31+
return max;
32+
};
33+
let depth = node => {
34+
if (node === null)
35+
return 0;
36+
let l = depth(node.left);
37+
let r = depth(node.right);
38+
max = Math.max(max, (l + r));
39+
return Math.max(l, r) + 1;
40+
};
41+
```
42+
43+
### go
44+
45+
```go
46+
var max = 0
47+
func diameterOfBinaryTree(root *TreeNode) int {
48+
depth2(root)
49+
return max
50+
}
51+
func depth2(node *TreeNode) int {
52+
if node == nil {
53+
return 0
54+
}
55+
l := depth2(node.Left)
56+
r := depth2(node.Right)
57+
max = Max3(max , l + r)
58+
return Max3(l, r) + 1
59+
}
60+
func Max3(a int , b int) int {
61+
if a < b {
62+
return b
63+
} else {
64+
return a
65+
}
66+
}
67+
```
68+
69+
### java
70+
71+
```java
72+
class Solution {
73+
int max = 0;
74+
public int diameterOfBinaryTree(TreeNode root) {
75+
depth(root);
76+
return max;
77+
}
78+
public int depth(TreeNode node) {
79+
if (node == null)
80+
return 0;
81+
int l = depth(node.left);
82+
int r = depth(node.right);
83+
max = Math.max(max, (l + r));
84+
return Math.max(l, r) + 1;
85+
}
86+
}
87+
```
88+

‎Java/alg/lc/566.重塑矩阵.md‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
# 566. 重塑矩阵
2+
3+
4+
[url](https://leetcode-cn.com/problems/reshape-the-matrix/)
5+
6+
7+
## 题目
8+
在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
9+
10+
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
11+
12+
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
13+
14+
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
15+
16+
17+
18+
```
19+
输入:
20+
nums =
21+
[[1,2],
22+
[3,4]]
23+
r = 1, c = 4
24+
输出:
25+
[[1,2,3,4]]
26+
解释:
27+
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
28+
输入:
29+
nums =
30+
[[1,2],
31+
[3,4]]
32+
r = 2, c = 4
33+
输出:
34+
[[1,2],
35+
[3,4]]
36+
解释:
37+
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
38+
```
39+
40+
## 方法
41+
从下往上的思想
42+
43+
## code
44+
45+
### js
46+
47+
```js
48+
```
49+
50+
### go
51+
52+
```go
53+
func matrixReshape(nums [][]int, r int, c int) [][]int {
54+
m, n := len(nums), len(nums[0])
55+
if m*n != r*c {
56+
return nums
57+
}
58+
reshapednums := make([][]int, 0)
59+
idx := 0
60+
for i := 0; i < r; i++ {
61+
for j := 0; j < c; j++ {
62+
reshapednums[i][j] = nums[idx / n][idx % n]
63+
idx++
64+
}
65+
}
66+
return reshapednums
67+
}
68+
```
69+
70+
### java
71+
72+
```java
73+
class Solution {
74+
public int[][] matrixReshape(int[][] nums, int r, int c) {
75+
int m = nums.length, n = nums[0].length;
76+
if (m * n != r * c) return nums;
77+
int[][] reshapedNums = new int[r][c];
78+
int idx = 0;
79+
for (int i = 0; i < r; i++) {
80+
for (int j = 0; j < c; j++) {
81+
reshapedNums[i][j] = nums[idx / n][idx % n];
82+
idx++;
83+
}
84+
}
85+
return reshapedNums;
86+
}
87+
}
88+
```
89+

‎Java/alg/lc/572.另一个树的子树.md‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
# 572. 另一个树的子树
2+
3+
4+
[url](https://leetcode-cn.com/problems/subtree-of-another-tree/)
5+
6+
7+
## 题目
8+
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
9+
10+
11+
```
12+
s:
13+
3
14+
/ \
15+
4 5
16+
/ \
17+
1 2
18+
t:
19+
4
20+
/ \
21+
1 2
22+
```
23+
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
24+
25+
## 方法
26+
从下往上的思想
27+
28+
## code
29+
30+
### js
31+
32+
```js
33+
let isSubtree = (s, t) => {
34+
if (s === null)
35+
return false;
36+
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
37+
};
38+
let isSubtreeWithRoot = (s, t) => {
39+
if (t === null && s === null)
40+
return true;
41+
if (t === null || s === null)
42+
return false;
43+
if (t.val !== s.val)
44+
return false;
45+
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
46+
};
47+
```
48+
49+
### go
50+
51+
```go
52+
func isSubtree(s *TreeNode, t *TreeNode) bool {
53+
if s == nil {
54+
return false
55+
}
56+
return isSubtreeWithRoot(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
57+
}
58+
func isSubtreeWithRoot(s *TreeNode, t*TreeNode) bool {
59+
if t == nil && s == nil {
60+
return true
61+
}
62+
if t == nil || s == nil {
63+
return false
64+
}
65+
if t.Val != s.Val {
66+
return false
67+
}
68+
return isSubtreeWithRoot(s.Left, t.Left) && isSubtreeWithRoot(s.Right, t.Right)
69+
}
70+
71+
```
72+
73+
### java
74+
75+
```java
76+
class Solution {
77+
public boolean isSubtree(TreeNode s, TreeNode t) {
78+
if (s == null) return false;
79+
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
80+
}
81+
82+
private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
83+
if (t == null && s == null) return true;
84+
if (t == null || s == null) return false;
85+
if (t.val != s.val) return false;
86+
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
87+
}
88+
}
89+
```
90+

0 commit comments

Comments
 (0)