Skip to content

Commit 0345f2d

Browse files
DreamCatsDreamCats
committed
📝 update alg lc
1 parent d35b1bf commit 0345f2d

18 files changed

Lines changed: 1517 additions & 1 deletion

‎Java/alg/.DS_Store‎

0 Bytes
Binary file not shown.

‎Java/alg/README.md‎

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -79,4 +79,20 @@
7979
- [617.合并二叉树](lc/617.合并二叉树.md)
8080
- [628.三个数的最大乘积](lc/628.三个数的最大乘积.md)
8181
- [637.二叉树的层平均值](lc/637.二叉树的层平均值.md)
82-
- [645.错误的集合](lc/645.错误的集合.md)
82+
- [645.错误的集合](lc/645.错误的集合.md)
83+
- [665.非递减数列](lc/665.非递减数列.md)
84+
- [671.二叉树中第二小的节点](lc/671.二叉树中第二小的节点.md)
85+
- [674.最长连续递增序列](lc/674.最长连续递增序列.md)
86+
- [680.验证回文字符串2](lc/680.验证回文字符串2.md)
87+
- [693.交替位二进制数](lc/693.交替位二进制数.md)
88+
- [696.计数二进制子串](lc/696.计数二进制子串.md)
89+
- [704.二分查找](lc/704.二分查找.md)
90+
- [724.寻找数组的中心下标](lc/724.寻找数组的中心下标.md)
91+
- [724.寻找数组的中心下标](lc/724.寻找数组的中心下标.md)
92+
- [747.至少是其他数字两倍的最大数](lc/747.至少是其他数字两倍的最大数.md)
93+
- [836.矩形重叠](lc/836.矩形重叠.md)
94+
- [876.链表的中间结点](lc/876.链表的中间结点.md)
95+
- [914.卡牌分组](lc/914.卡牌分组.md)
96+
- [1013.将数组分成和相等的三个部分](lc/1013.将数组分成和相等的三个部分.md)
97+
- [1071.字符串的最大公因子](lc/1071.字符串的最大公因子.md)
98+
- [1103.分糖果2](lc/1103.分糖果2.md)

‎Java/alg/lc/1013.将数组分成和相等的三个部分.md‎

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
# 1013. 将数组分成和相等的三个部分
2+
3+
4+
5+
[url](https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/)
6+
7+
8+
## 题目
9+
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
10+
11+
形式上，如果可以找出索引 `i+1 < j` 且满足 `A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]` 就可以将数组三等分。
12+
13+
14+
```
15+
输入：[0,2,1,-6,6,-7,9,1,2,0,1]
16+
输出：true
17+
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
18+
输入：[0,2,1,-6,6,7,9,-1,2,0,1]
19+
输出：false
20+
输入：[3,3,6,5,-2,2,5,1,-9,4]
21+
输出：true
22+
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
23+
```
24+
25+
26+
## 方法
27+
28+
29+
## code
30+
31+
### js
32+
33+
```js
34+
let canThreePartsEqualSum = A => {
35+
let sum = 0;
36+
// 遍历数组求和
37+
A.forEach(num => sum += num);
38+
// 数组A的和如果不能被3整除直接返回false
39+
if (sum % 3 !== 0)
40+
return false;
41+
// 遍历数组累加，每累加到目标值cnt加1， 表示又找到了1段
42+
sum = Math.floor(sum / 3);
43+
let curSum = 0, cnt = 0;
44+
for (let val of A) {
45+
curSum += val;
46+
if (curSum === sum) {
47+
cnt++;
48+
curSum = 0;
49+
}
50+
}
51+
return cnt === 3 || (cnt > 3 && sum === 0);
52+
};
53+
console.log(canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1]));
54+
console.log(canThreePartsEqualSum([0,2,1,-6,6,7,9,-1,2,0,1]));
55+
console.log(canThreePartsEqualSum([3,3,6,5,-2,2,5,1,-9,4]));
56+
```
57+
58+
### go
59+
60+
```go
61+
func canThreePartsEqualSum(A []int) bool {
62+
sum := 0
63+
// 遍历数组求总和
64+
for _, v := range A {
65+
sum += v
66+
}
67+
// 数组A的和如果不能被3整除直接返回false
68+
if sum%3 != 0 {
69+
return false
70+
}
71+
// 遍历数组累加，每累加到目标值cnt加1，表示又找到1段
72+
sum /= 3
73+
curSum, cnt := 0, 0
74+
for _, v := range A {
75+
curSum += v
76+
if curSum == sum {
77+
cnt++
78+
curSum = 0
79+
}
80+
}
81+
// 最后判断是否找到了3段（注意如果目标值是0的话可以大于3段）
82+
return cnt == 3 || (cnt > 3 && sum == 0)
83+
}
84+
```
85+
86+
### java
87+
88+
```java
89+
class Solution {
90+
public boolean canThreePartsEqualSum(int[] A) {
91+
int sum = 0;
92+
// 遍历数组求总和
93+
for (int num : A) {
94+
sum += num;
95+
}
96+
// 数组A的和如果不能被3整除直接返回false
97+
if (sum % 3 != 0) {
98+
return false;
99+
}
100+
// 遍历数组累加，每累加到目标值cnt加1，表示又找到1段
101+
sum /= 3;
102+
int curSum = 0, cnt = 0;
103+
for (int i = 0; i < A.length; i++) {
104+
curSum += A[i];
105+
if (curSum == sum) {
106+
cnt++;
107+
curSum = 0;
108+
}
109+
}
110+
// 最后判断是否找到了3段（注意如果目标值是0的话可以大于3段）
111+
return cnt == 3 || (cnt > 3 && sum == 0);
112+
}
113+
}
114+
```
115+

‎Java/alg/lc/1071.字符串的最大公因子.md‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
# 1071. 字符串的最大公因子
2+
3+
4+
5+
[url](https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/)
6+
7+
8+
## 题目
9+
对于字符串 `S` 和 `T`，只有在 `S = T + ... + T`（T 自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
10+
11+
返回最长字符串 `X`，要求满足 `X` 能除尽 `str1` 且 `X` 能除尽 `str2`。
12+
13+
14+
15+
```
16+
输入：str1 = "ABCABC", str2 = "ABC"
17+
输出："ABC"
18+
输入：str1 = "ABABAB", str2 = "ABAB"
19+
输出："AB"
20+
输入：str1 = "LEET", str2 = "CODE"
21+
输出：""
22+
```
23+
24+
25+
## 方法
26+
27+
28+
## code
29+
30+
### js
31+
32+
```js
33+
let gcdOfStrings = (str1, str2) => {
34+
if ((str1 + str2) !== (str2 + str1))
35+
return "";
36+
return str2.substring(0, gcd(str1.length, str2.length));
37+
};
38+
39+
let gcd = (a, b) => {
40+
return b === 0 ? a : gcd(b, a % b);
41+
};
42+
console.log(gcdOfStrings("ABCABC", "ABC"));
43+
console.log(gcdOfStrings("ABABAB", "ABAB"));
44+
console.log(gcdOfStrings("LEET", "CODE"));
45+
```
46+
47+
### go
48+
49+
```go
50+
func gcdOfStrings(str1 string, str2 string) string {
51+
if str1+str2 != str2+str1 {
52+
return ""
53+
}
54+
return str2[0:gcd2(len(str1), len(str2))]
55+
}
56+
func gcd2(a int, b int) int {
57+
if b == 0 {
58+
return a
59+
} else {
60+
return gcd2(b, a % b)
61+
}
62+
}
63+
```
64+
65+
### java
66+
67+
```java
68+
class Solution {
69+
public String gcdOfStrings(String str1, String str2) {
70+
if (!(str1 + str2).equals(str2 + str1)) {
71+
return "";
72+
}
73+
return str2.substring(0, gcd(str1.length(), str2.length()));
74+
}
75+
76+
private int gcd(int a, int b) {
77+
return b == 0 ? a : gcd(b, a % b);
78+
}
79+
}
80+
```
81+

‎Java/alg/lc/1103.分糖果2.md‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
# 1103. 分糖果 II
2+
3+
4+
5+
[url](https://leetcode-cn.com/problems/distribute-candies-to-people/)
6+
7+
8+
## 题目
9+
排排坐，分糖果。
10+
11+
我们买了一些糖果 `candies`，打算把它们分给排好队的 `n = num_people` 个小朋友。
12+
13+
给第一个小朋友 `1` 颗糖果，第二个小朋友 `2` 颗，依此类推，直到给最后一个小朋友 `n` 颗糖果。
14+
15+
然后，我们再回到队伍的起点，给第一个小朋友 `n + 1` 颗糖果，第二个小朋友 `n + 2` 颗，依此类推，直到给最后一个小朋友 `2 * n` 颗糖果。
16+
17+
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
18+
19+
返回一个长度为 `num_people`、元素之和为 `candies` 的数组，以表示糖果的最终分发情况（即 `ans[i]` 表示第 `i` 个小朋友分到的糖果数）。
20+
21+
22+
```
23+
输入：candies = 7, num_people = 4
24+
输出：[1,2,3,1]
25+
解释：
26+
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
27+
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
28+
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
29+
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
30+
输入：candies = 10, num_people = 3
31+
输出：[5,2,3]
32+
解释：
33+
第一次，ans[0] += 1，数组变为 [1,0,0]。
34+
第二次，ans[1] += 2，数组变为 [1,2,0]。
35+
第三次，ans[2] += 3，数组变为 [1,2,3]。
36+
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
37+
```
38+
39+
40+
## 方法
41+
42+
43+
## code
44+
45+
### js
46+
47+
```js
48+
let distributeCandies = (candies, num_people) => {
49+
let ans = Array(num_people).fill(0);
50+
let i;
51+
for (i = 0; candies > 0; i++) {
52+
ans[i % num_people] += i + 1;
53+
candies -= i + 1;
54+
}
55+
ans[(i - 1) % num_people] += candies;
56+
return ans;
57+
};
58+
console.log(distributeCandies(7, 4))
59+
```
60+
61+
### go
62+
63+
```go
64+
func distributeCandies(candies int, num_people int) []int {
65+
ans := make([]int, num_people)
66+
i := 0
67+
for i = 0; candies > 0; i++ {
68+
ans[i % num_people] += i + 1
69+
candies -= i + 1
70+
}
71+
ans[(i - 1) % num_people] += candies
72+
return ans
73+
}
74+
```
75+
76+
### java
77+
78+
```java
79+
class Solution {
80+
public int[] distributeCandies(int candies, int num_people) {
81+
int[] ans = new int[num_people];
82+
int i;
83+
for (i = 0; candies > 0; i++) {
84+
ans[i % num_people] += i + 1;
85+
candies -= i + 1;
86+
}
87+
ans[(i - 1) % num_people] += candies;
88+
return ans;
89+
}
90+
}
91+
```
92+

0 commit comments

Comments
 (0)