8000 Merge branch 'master' of github.com:kylesliu/awesome-golang-algorithm… · AlgoBBA/awesome-golang-algorithm@06e3645 · GitHub
[go: up one dir, main page]
Skip to content

Commit 06e3645

Browse files
author
Kyle Liu
committed
Merge branch 'master' of github.com:kylesliu/awesome-golang-algorithm into master
# Conflicts: # SUMMARY.md
2 parents ec1f78e + 792b82e commit 06e3645

File tree

5 files changed

+428
-4
lines changed

5 files changed

+428
-4
lines changed

‎SUMMARY.md

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,12 +3,16 @@
33
* [Introduction](README.md)
44
* [介绍](readme-doc.md)
55

6+
<<<<<<< HEAD
67
## 剑指 Offer
8+
=======
9+
## 剑指 Offer <a id="lcof"></a>
10+
>>>>>>> 792b82e420332e0a6146200d15f9d42b5c5fac4b
711
8-
* [OF3.数组中重复的数字](lcof/of003/README.md)
9-
* [OF37.序列化二叉树](lcof/of037/README.md)
10-
* [OF14-I.剪绳子](lcof/of014-I/README.md)
11-
* [OF14-II.剪绳子](lcof/of014-II/README.md)
12+
* [OF3.数组中重复的数字](lcof/of003.md)
13+
* [OF37.序列化二叉树](lcof/of037.md)
14+
* [OF14-I.剪绳子](lcof/of014-i.md)
15+
* [OF14-II.剪绳子](lcof/of014-ii.md)
1216

1317
## LeetCode
1418

‎lcof/of003.md

Lines changed: 203 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,203 @@
1+
---
2+
description: 剑指 Offer 03. 数组中重复的数字
3+
---
4+
5+
# OF3.数组中重复的数字
6+
7+
## 题目描述
8+
9+
[题目地址](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
10+
11+
找出数组中重复的数字。
12+
13+
在一个长度为 n 的数组 _`nums`_ 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
14+
15+
### **示例 1：**
16+
17+
```go
18+
输入：
19+
[2, 3, 1, 0, 2, 5, 3]
20+
输出：2 或 3
21+
```
22+
23+
### **限制：**
24+
25+
```go
26+
2 <= n <= 100000
27+
```
28+
29+
## 题解
30+
31+
### 思路1 ： **哈希表 / Set**
32+
33+
**算法流程：**
34+
35+
1. 初始化： 新建 HashSet ，记为 dicdic
36+
2. 遍历数组 numsnums 中的每个数字 numnum
37+
1. 当 num 在 dic 中，说明重复，直接返回 num
38+
2. 将 numnum 添加至 dicdic 中
39+
3. 返回 -1−1 。本题中一定有重复数字，因此这里返回多少都可以
40+
41+
**复杂度分析：**
42+
43+
* **时间复杂度**$$O(N)$$**：**遍历数组使用 O\(N\) ，HashSet 添加与查找元素皆为 O\(1\)O\(1\)
44+
* **空间复杂度**$$O(N)$$**：** HashSet 占用 O\(N\) 大小的额外空间
45+
46+
#### 代码
47+
48+
{% tabs %}
49+
{% tab title="Go" %}
50+
```go
51+
func findRepeatNumber2(nums []int) int {
52+
mapTmp := make(map[int]bool)
53+
for _, val := range nums {
54+
if mapTmp[val] {
55+
return val
56+
} else {
57+
mapTmp[val] = true
58+
}
59+
}
60+
return 0
61+
}
62+
```
63+
{% endtab %}
64+
65+
{% tab title="Python" %}
66+
```python
67+
class Solution:
68+
def findRepeatNumber(self, nums: [int]) -> int:
69+
dic = set()
70+
for num in nums:
71+
if num in dic: return num
72+
dic.add(num)
73+
return -1
74+
```
75+
{% endtab %}
76+
77+
{% tab title="C++" %}
78+
```cpp
79+
class Solution {
80+
public:
81+
int findRepeatNumber(vector<int>& nums) {
82+
unordered_map<int, bool> map;
83+
for(int num : nums) {
84+
if(map[num]) return num;
85+
map[num] = true;
86+
}
87+
return -1;
88+
}
89+
};
90+
```
91+
{% endtab %}
92+
93+
{% tab title="Java" %}
94+
```java
95+
class Solution {
96+
public int findRepeatNumber(int[] nums) {
97+
Set<Integer> dic = new HashSet<>();
98+
for(int num : nums) {
99+
if(dic.contains(num)) return num;
100+
dic.add(num);
101+
}
102+
return -1;
103+
}
104+
}
105+
```
106+
{% endtab %}
107+
{% endtabs %}
108+
109+
### 思路2：**原地交换**
110+
111+
#### 算法流程
112+
113+
1. 遍历数组 numsnums ，设索引初始值为 i = 0i=0 :
114+
1. 若 nums\[i\] = inums\[i\]=i ： 说明此数字已在对应索引位置，无需交换，因此跳过
115+
2. 若 nums\[nums\[i\]\] = nums\[i\]nums\[nums\[i\]\]=nums\[i\] ： 代表索引 nums\[i\]nums\[i\] 处和索引 ii 处的元素值都为 nums\[i\]nums\[i\] ，即找到一组重复值，返回此值 nums\[i\]nums\[i\]
116+
3. 否则： 交换索引为 ii 和 nums\[i\]nums\[i\] 的元素值，将此数字交换至对应索引位置
117+
2. 若遍历完毕尚未返回，则返回 -1
118+
119+
#### 复杂度分析
120+
121+
* **时间复杂度**$$O(N)$$**：**遍历数组使用 $$O(N)$$ ，每轮遍历的判断和交换操作使用 $$O(N)$$
122+
* **空间复杂度**$$O(1)$$**：** 使用常数复杂度的额外空间。
123+
124+
{% tabs %}
125+
{% tab title="Go" %}
126+
```go
127+
func findRepeatNumber3(nums []int) int {
128+
for idx, val := range nums {
129+
if idx == val {
130+
continue
131+
}
132+
if nums[val] == val {
133+
return val
134+
}
135+
nums[val], nums[idx] = nums[idx], nums[val]
136+
}
137+
return 0
138+
}
139+
```
140+
{% endtab %}
141+
142+
{% tab title="Python" %}
143+
```python
144+
class Solution:
145+
def findRepeatNumber(self, nums: [int]) -> int:
146+
i = 0
147+
while i < len(nums):
148+
if nums[i] == i:
149+
i += 1
150+
continue
151+
if nums[nums[i]] == nums[i]: return nums[i]
152+
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
153+
return -1
154+
```
155+
{% endtab %}
156+
157+
{% tab title="Java" %}
158+
```java
159+
class Solution {
160+
public int findRepeatNumber(int[] nums) {
161+
int i = 0;
162+
while(i < nums.length) {
163+
if(nums[i] == i) {
164+
i++;
165+
continue;
166+
}
167+
if(nums[nums[i]] == nums[i]) return nums[i];
168+
int tmp = nums[i];
169+
nums[i] = nums[tmp];
170+
nums[tmp] = tmp;
171+
}
172+
return -1;
173+
}
174+
}
175+
```
176+
{% endtab %}
177+
178+
{% tab title="C++" %}
179+
```cpp
180+
class Solution {
181+
public:
182+
int findRepeatNumber(vector<int>& nums) {
183+
int i = 0;
184+
while(i < nums.size()) {
185+
if(nums[i] == i) {
186+
i++;
187+
continue;
188+
}
189+
if(nums[nums[i]] == nums[i])
190+
return nums[i];
191+
swap(nums[i],nums[nums[i]]);
192+
}
193+
return -1;
194+
}
195+
};
196+
```
197+
{% endtab %}
198+
{% endtabs %}
199+
200+
## 总结
201+
202+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：[awesome-golang-algorithm](https://github.com/kylesliu/awesome-golang-algorithm)
203+

‎lcof/of014-i.md

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
---
2+
description: 剑指 Offer 14- I. 剪绳子
3+
---
4+
5+
# OF14-I.剪绳子
6+
7+
## 题目描述
8+
9+
[题目地址](https://leetcode-cn.com/problems/jian-sheng-zi-lcof/)
10+
11+
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n&gt;1并且m&gt;1），每段绳子的长度记为 k\[0\],k\[1\]...k\[m-1\] 。请问 k\[0\]_k\[1\]_...\*k\[m-1\] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
12+
13+
### **示例 ：**
14+
15+
```go
16+
输入: 2
17+
输出: 1
18+
解释: 2 = 1 + 1, 1 × 1 = 1
19+
20+
输入: 10
21+
输出: 36
22+
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
23+
24+
2 <= n <= 58
25+
```
26+
27+
### 标签：
28+
29+
* 动态规划
30+
* 数学
31+
32+
### 相似题目：
33+
34+
\*\*\*\*[**343. 整数拆分**](https://leetcode-cn.com/problems/integer-break/)\*\*\*\*
35+
36+
## 题解
37+
38+
### 思路1 ： 动态规划
39+
40+
1. 对于的正整数 n，当 n≥2 时，可以拆分成至少两个正整数的和。令 k 是拆分出的第一个正整数，则剩下的部分是 n-k，n-k可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
41+
2. 创建数组 dp，其中 dp\[i\] 表示将正整数 ii 拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0 不是正整数，1是最小的正整数，0和1都不能拆分，因此dp\[0\]=dp\[1\]=0。
42+
3. 当 i≥2 时，假设对正整数 ii 拆分出的第一个正整数是j &lt; i , 1≤j&lt;i），则有以下两种方案：
43+
1. 将 ii 拆分成 j 和 i−j 的和，且 i-j不再拆分成多个正整数，此时的乘积是 j×\(i−j\)；
44+
2. 将 i拆分成 jj 和 i-j的和，且 i-j 继续拆分成多个正整数，此时的乘积是 j×dp\[i−j\]。
45+
4. 因此，当 j 固定时，有 dp\[i\] - max\(j\*\(i-j\) j\*dp\[i-j\]\)。由于 jj的取值范围是 1 到i−1，需要遍历所有的 j 得到 dp\[i\] 的最大值，因此可以得到状态转移方程如下：
46+
47+
$$
48+
dp[i] = max( max (j \times (i-j) , j \times dp[i-j]))
49+
$$
50+
51+
1. 最终得到 dp\[n\] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
52+
53+
**复杂度分析：**
54+
55+
* **时间复杂度**$$O(1)$$**：**
56+
* **空间复杂度**$$O(1)$$**：**
57+
58+
#### 代码
59+
60+
{% tabs %}
61+
{% tab title="Go" %}
62+
```go
63+
func cuttingRope(n int) int {
64+
dp := make(map[int]int)
65+
dp[1] = 1 // 首项
66+
for i := 2; i < n+1; i++ {
67+
j, k := 1, i-1
68+
ans := 0
69+
for j <= k {
70+
ans = max(ans, max(j, dp[j])*max(k, dp[k])) // 递推公式
71+
j++
72+
k--
73+
}
74+
dp[i] = ans
75+
}
76+
return dp[n]
77+
}
78+
79+
func max(x int, y int) int {
80+
if x > y {
81+
return x
82+
}
83+
return y
84+
}
85+
```
86+
{% endtab %}
87+
88+
{% tab title="Python" %}
89+
```python
90+
class Solution:
91+
def cuttingRope(self, n: int) -> int:
92+
dp = [0] * (n + 1)
93+
for i in range(2, n + 1):
94+
for j in range(i):
95+
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
96+
return dp[n]
97+
```
98+
{% endtab %}
99+
100+
{% tab title="Java" %}
101+
```java
102+
class Solution {
103+
public int cuttingRope(int n) {
104+
int[] dp = new int[n + 1];
105+
for (int i = 2; i <= n; i++) {
106+
int curMax = 0;
107+
for (int j = 1; j < i; j++) {
108+
curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
109+
}
110+
dp[i] = curMax;
111+
}
112+
return dp[n];
113+
}
114+
}
115+
```
116+
{% endtab %}
117+
{% endtabs %}
118+
119+
## 总结
120+
121+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：[awesome-golang-algorithm](https://github.com/kylesliu/awesome-golang-algorithm)
122+

‎lcof/of014-ii.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# OF14-II.剪绳子
2+
3+
> \[!WARNING\|style:flat\] This problem is temporarily not PR, please submit [Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
4+
5+
## 题目描述
6+
7+
....
8+
9+
**范例 :**
10+
11+
```text
12+
Input: n=1
13+
Output: 1
14+
```
15+
16+
## 题意
17+
18+
> ...
19+
20+
## 题解
21+
22+
### 思路1
23+
24+
> ...
25+
>
26+
> ```go
27+
>
28+
> ```
29+
30+
## 结语
31+
32+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-algorithm](https://github.com/kylesliu/awesome-golang-algorithm)
33+

0 commit comments

Comments
 (0)
0