Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 77029c8

Browse files
committed
feat: 每日一题更新
1 parent f955951 commit 77029c8

File tree

6 files changed

+256
-1
lines changed

6 files changed

+256
-1
lines changed

‎.vscode/settings.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -154,7 +154,7 @@
154154
"editor.tabSize": 2
155155
},
156156
"editor.codeActionsOnSave": {
157-
"source.fixAll.eslint": true
157+
"source.fixAll.eslint": "explicit"
158158
},
159159
"eslint.packageManager": "yarn",
160160
"typescript.tsdk": "node_modules\\typescript\\lib"
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/**
2+
* @param {number[]} nums
3+
* @param {number} k
4+
* @return {number}
5+
*/
6+
var countPartitions = function(nums, k) {
7+
const n = nums.length, s = nums.reduce((p, c) => p+c, 0)
8+
const dp = Array(n).fill(0).map(() => Array(k).fill(0))
9+
dp[0][0] = 1, dp[0][nums[0]] = 1
10+
let P = 1e9+7
11+
// s>=2k
12+
if (s<2*k) return 0
13+
for (let i = 1; i < n; i++) {
14+
for (let l = 0; l < k; l++) {
15+
// 前 i 个元素,构成和 l 的方案数
16+
dp[i][l] = (dp[i-1][l] + ((l-nums[i]>=0) ? dp[i-1][l-nums[i]] : 0))%P
17+
}
18+
}
19+
let qpow = (a, b, p = P) => {
20+
let ans = 1%p
21+
while (b) {
22+
if (b&1) ans = Number(BigInt(ans)*BigInt(a)%BigInt(p))
23+
a = Number(BigInt(a)*BigInt(a)%BigInt(p))
24+
b>>=1
25+
}
26+
return ans
27+
}
28+
let t = 0
29+
for (let i = 0; i < k; i++) t += dp[n-1][i], t %= P
30+
return ((qpow(2, n) - t - t)%P+P)%P
31+
};
Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
# 2023年10月23日 残酷刷题 | 力扣 2518. 好分区的数目
2+
3+
## 题目
4+
5+
给你一个正整数数组 `nums` 和一个整数 `k` 。
6+
7+
**分区** 的定义是:将数组划分成两个有序的 **组** ,并满足每个元素 **恰好** 存在于 **某一个** 组中。如果分区中每个组的元素和都大于等于 `k` ,则认为分区是一个好分区。
8+
9+
返回 **不同** 的好分区的数目。由于答案可能很大,请返回对 `10<sup>9</sup> + 7` **取余** 后的结果。
10+
11+
如果在两个分区中,存在某个元素 `nums[i]` 被分在不同的组中,则认为这两个分区不同。
12+
13+
**示例 1:**
14+
15+
**输入:**nums = \[1,2,3,4\], k = 4
16+
**输出:**6
17+
**解释:**好分区的情况是 (\[1,2,3\], \[4\]), (\[1,3\], \[2,4\]), (\[1,4\], \[2,3\]), (\[2,3\], \[1,4\]), (\[2,4\], \[1,3\]) 和 (\[4\], \[1,2,3\]) 。
18+
19+
**示例 2:**
20+
21+
**输入:**nums = \[3,3,3\], k = 4
22+
**输出:**0
23+
**解释:**数组中不存在好分区。
24+
25+
**示例 3:**
26+
27+
**输入:**nums = \[6,6\], k = 2
28+
**输出:**2
29+
**解释:**可以将 nums\[0\] 放入第一个分区或第二个分区中。
30+
好分区的情况是 (\[6\], \[6\]) 和 (\[6\], \[6\]) 。
31+
32+
**提示:**
33+
34+
- `1 <= nums.length, k <= 1000`
35+
- <code>1 <= nums[i] <= 10<sup>9</sup></code>
36+
37+
## 算法——动态规划
38+
39+
- 算法类型:动态规划
40+
- 算法解析
41+
- 预计算 dp 数组
42+
- `dp[i][l]` 表示前 `i` 个元素,构成和 `l` 的方案数
43+
- `dp[0][0] = 1`、`dp[0][nums[0]] = 1`
44+
- `dp[i][l] = dp[i-1][l] + dp[i-1][l-nums[i]] (l>=nums[i])`,分为第 `i` 个数选择与不选择 2 种情况
45+
- 最后数组分为两个区 A 和 B,需要 `sum(A) >= k` 且 `sum(B) >= k`
46+
- 需要 `sum(nums) >= 2k`,否则不会有答案,提前返回
47+
- 总的划分方案数为 `2^n`,先减去 `sum(A) < k` 的方案数,其大小为 `t = dp[n-1][0] + dp[n-1][1] + ... + dp[n-1][k-1]`
48+
- 在 `sum(A) >= k` 的方案种,`sum(B) < k` 的方案数,其大小为 `t`
49+
- 因为 `sum(B) < k`,就能保证一定有 `sum(A) >= k`,所以就是 `sum(B) < k` 一个条件,和上面一样也是 t
50+
- 综上所述,答案就是 `2^n - 2t`
51+
- 算法复杂度
52+
- 时间复杂度:`O(nk)`
53+
- 空间复杂度:`O(nk)`
54+
55+
## JS 代码
56+
57+
```js
58+
/**
59+
* @param {number[]} nums
60+
* @param {number} k
61+
* @return {number}
62+
*/
63+
var countPartitions = function(nums, k) {
64+
const n = nums.length, s = nums.reduce((p, c) => p+c, 0)
65+
const dp = Array(n).fill(0).map(() => Array(k).fill(0))
66+
dp[0][0] = 1, dp[0][nums[0]] = 1
67+
let P = 1e9+7
68+
// s>=2k
69+
if (s<2*k) return 0
70+
for (let i = 1; i < n; i++) {
71+
for (let l = 0; l < k; l++) {
72+
// 前 i 个元素,构成和 l 的方案数
73+
dp[i][l] = (dp[i-1][l] + ((l-nums[i]>=0) ? dp[i-1][l-nums[i]] : 0))%P
74+
}
75+
}
76+
let qpow = (a, b, p = P) => {
77+
let ans = 1%p
78+
while (b) {
79+
if (b&1) ans = Number(BigInt(ans)*BigInt(a)%BigInt(p))
80+
a = Number(BigInt(a)*BigInt(a)%BigInt(p))
81+
b>>=1
82+
}
83+
return ans
84+
}
85+
let t = 0
86+
for (let i = 0; i < k; i++) t += dp[n-1][i], t %= P
87+
return ((qpow(2, n) - t - t)%P+P)%P
88+
};
89+
```
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/**
2+
* @param {number} amount
3+
* @param {number[]} coins
4+
* @return {number}
5+
*/
6+
var change = function(amount, coins) {
7+
const n = coins.length, dp = Array(amount+1).fill(0)
8+
dp[0] = 1
9+
if (amount === 0) return 1
10+
for (let j = 0; j < n; j++) {
11+
for (let i = 1; i <= amount; i++) {
12+
if (i >= coins[j]) dp[i] += dp[i-coins[j]]
13+
}
14+
}
15+
return dp[amount]
16+
};
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/**
2+
* @param {number} amount
3+
* @param {number[]} coins
4+
* @return {number}
5+
*/
6+
var change = function(amount, coins) {
7+
const n = coins.length, dp = Array(amount+1).fill(0).map(() => Array(n).fill(0))
8+
dp[0][0] = 1
9+
if (amount === 0) return 1
10+
for (let i = 1; i <= amount; i++) {
11+
let s = 0
12+
for (let j = 0; j < n; j++) {
13+
if (i >= coins[j]) {
14+
// 硬币递增,避免重复计算
15+
for (let k = 0; k <= j; k++) {
16+
dp[i][j] += dp[i-coins[j]][k]
17+
}
18+
}
19+
s += dp[i][j]
20+
}
21+
if (i === amount) return s
22+
}
23+
};
Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
# 残酷刷题 | LeetCode 518. Coin Change II
2+
3+
## 题目
4+
5+
给你一个整数数组 `coins` 表示不同面额的硬币,另给一个整数 `amount` 表示总金额。
6+
7+
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 `0` 。
8+
9+
假设每一种面额的硬币有无限个。
10+
11+
题目数据保证结果符合 32 位带符号整数。
12+
13+
**示例 1:**
14+
15+
**输入:**amount = 5, coins = \[1, 2, 5\]
16+
**输出:**4
17+
**解释:**有四种方式可以凑成总金额:
18+
5=5
19+
5=2+2+1
20+
5=2+1+1+1
21+
5=1+1+1+1+1
22+
23+
**示例 2:**
24+
25+
**输入:**amount = 3, coins = \[2\]
26+
**输出:**0
27+
**解释:**只用面额 2 的硬币不能凑成总金额 3 。
28+
29+
**示例 3:**
30+
31+
**输入:**amount = 10, coins = \[10\]
32+
**输出:**1
33+
34+
## 算法
35+
36+
- 算法类型:动态规划
37+
- 算法解析
38+
- `dp[i][j]` 表示组成数量 `i`,最后一个硬币是 `j` 的方案数,为了避免重复计算,我们要求硬币的组成顺序是不降序的
39+
- `dp[0][0] = 1`
40+
- `dp[i][j] = dp[i-coins[j]][k] (i>=coins[j], 2518. 好分区的数目
41+
k<=j)`
42+
- 算法复杂度
43+
- 时间复杂度:`O(amount*n^2)`
44+
- 空间复杂度:`O(amount*n)`
45+
- 可以继续优化:将 amount 和 coins 的循环调换,按照 coins 的顺序,可省去最内层的循环,时间复杂度为 `O(amount*n)`,空间复杂度为 `O(amount)`
46+
47+
## JS 代码
48+
49+
```js
50+
/**
51+
* @param {number} amount
52+
* @param {number[]} coins
53+
* @return {number}
54+
*/
55+
var change = function(amount, coins) {
56+
const n = coins.length, dp = Array(amount+1).fill(0).map(() => Array(n).fill(0))
57+
dp[0][0] = 1
58+
if (amount === 0) return 1
59+
for (let i = 1; i <= amount; i++) {
60+
let s = 0
61+
for (let j = 0; j < n; j++) {
62+
if (i >= coins[j]) {
63+
// 硬币递增,避免重复计算
64+
for (let k = 0; k <= j; k++) {
65+
dp[i][j] += dp[i-coins[j]][k]
66+
}
67+
}
68+
s += dp[i][j]
69+
}
70+
if (i === amount) return s
71+
}
72+
};
73+
74+
```
75+
76+
### 优化后
77+
78+
```js
79+
/**
80+
* @param {number} amount
81+
* @param {number[]} coins
82+
* @return {number}
83+
*/
84+
var change = function(amount, coins) {
85+
const n = coins.length, dp = Array(amount+1).fill(0)
86+
dp[0] = 1
87+
if (amount === 0) return 1
88+
for (let j = 0; j < n; j++) {
89+
for (let i = 1; i <= amount; i++) {
90+
if (i >= coins[j]) dp[i] += dp[i-coins[j]]
91+
}
92+
}
93+
return dp[amount]
94+
};
95+
96+
```

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /