feat: 每日一题更新

upupming · upupming · commit 77029c84130d · 2024-02-26T13:17:21.000+08:00
diff --git a/.vscode/settings.json b/.vscode/settings.json
@@ -154,7 +154,7 @@
     "editor.tabSize": 2
   },
   "editor.codeActionsOnSave": {
-    "source.fixAll.eslint": true
+    "source.fixAll.eslint": "explicit"
   },
   "eslint.packageManager": "yarn",
   "typescript.tsdk": "node_modules\\typescript\\lib"
diff --git a/leetcode/残酷刷题/2518. Number of Great Partitions.js b/leetcode/残酷刷题/2518. Number of Great Partitions.js
@@ -0,0 +1,31 @@
+/**
+ * @param {number[]} nums
+ * @param {number} k
+ * @return {number}
+ */
+var countPartitions = function(nums, k) {
+  const n = nums.length, s = nums.reduce((p, c) => p+c, 0)
+  const dp = Array(n).fill(0).map(() => Array(k).fill(0))
+  dp[0][0] = 1, dp[0][nums[0]] = 1
+  let P = 1e9+7
+  // s>=2k
+  if (s<2*k) return 0
+  for (let i = 1; i < n; i++) {
+      for (let l = 0; l < k; l++) {
+          // 前 i 个元素，构成和 l 的方案数
+          dp[i][l] = (dp[i-1][l] + ((l-nums[i]>=0) ? dp[i-1][l-nums[i]] : 0))%P
+      }
+  }
+  let qpow = (a, b, p = P) => {
+      let ans = 1%p
+      while (b) {
+          if (b&1) ans = Number(BigInt(ans)*BigInt(a)%BigInt(p))
+          a = Number(BigInt(a)*BigInt(a)%BigInt(p))
+          b>>=1
+      }
+      return ans
+  }
+  let t = 0
+  for (let i = 0; i < k; i++) t += dp[n-1][i], t %= P
+  return ((qpow(2, n) - t - t)%P+P)%P
+};
diff --git a/leetcode/残酷刷题/2518. Number of Great Partitions.md b/leetcode/残酷刷题/2518. Number of Great Partitions.md
@@ -0,0 +1,89 @@
+# 2023.10.23 残酷刷题 | 力扣 2518. 好分区的数目
+
+## 题目
+
+给你一个正整数数组 `nums` 和一个整数 `k` 。
+
+**分区** 的定义是：将数组划分成两个有序的 **组** ，并满足每个元素 **恰好** 存在于 **某一个** 组中。如果分区中每个组的元素和都大于等于 `k` ，则认为分区是一个好分区。
+
+返回 **不同** 的好分区的数目。由于答案可能很大，请返回对 `10<sup>9</sup> + 7` **取余** 后的结果。
+
+如果在两个分区中，存在某个元素 `nums[i]` 被分在不同的组中，则认为这两个分区不同。
+
+**示例 1：**
+
+**输入：**nums = \[1,2,3,4\], k = 4
+**输出：**6
+**解释：**好分区的情况是 (\[1,2,3\], \[4\]), (\[1,3\], \[2,4\]), (\[1,4\], \[2,3\]), (\[2,3\], \[1,4\]), (\[2,4\], \[1,3\]) 和 (\[4\], \[1,2,3\]) 。
+
+**示例 2：**
+
+**输入：**nums = \[3,3,3\], k = 4
+**输出：**0
+**解释：**数组中不存在好分区。
+
+**示例 3：**
+
+**输入：**nums = \[6,6\], k = 2
+**输出：**2
+**解释：**可以将 nums\[0\] 放入第一个分区或第二个分区中。
+好分区的情况是 (\[6\], \[6\]) 和 (\[6\], \[6\]) 。
+
+**提示：**
+
+- `1 <= nums.length, k <= 1000`
+- <code>1 <= nums[i] <= 10<sup>9</sup></code>
+
+## 算法——动态规划
+
+- 算法类型：动态规划
+- 算法解析
+    - 预计算 dp 数组
+        - `dp[i][l]` 表示前 `i` 个元素，构成和 `l` 的方案数
+        - `dp[0][0] = 1`、`dp[0][nums[0]] = 1`
+        - `dp[i][l] = dp[i-1][l] + dp[i-1][l-nums[i]] (l>=nums[i])`，分为第 `i` 个数选择与不选择 2 种情况
+    - 最后数组分为两个区 A 和 B，需要 `sum(A) >= k` 且 `sum(B) >= k`
+    - 需要 `sum(nums) >= 2k`，否则不会有答案，提前返回
+    - 总的划分方案数为 `2^n`，先减去 `sum(A) < k` 的方案数，其大小为 `t = dp[n-1][0] + dp[n-1][1] + ... + dp[n-1][k-1]`
+        - 在 `sum(A) >= k` 的方案种，`sum(B) < k` 的方案数，其大小为 `t`
+            - 因为 `sum(B) < k`，就能保证一定有 `sum(A) >= k`，所以就是 `sum(B) < k` 一个条件，和上面一样也是 t
+    - 综上所述，答案就是 `2^n - 2t`
+- 算法复杂度
+    - 时间复杂度：`O(nk)`
+    - 空间复杂度：`O(nk)`
+
+## JS 代码
+
+```js
+/**
+ * @param {number[]} nums
+ * @param {number} k
+ * @return {number}
+ */
+var countPartitions = function(nums, k) {
+  const n = nums.length, s = nums.reduce((p, c) => p+c, 0)
+  const dp = Array(n).fill(0).map(() => Array(k).fill(0))
+  dp[0][0] = 1, dp[0][nums[0]] = 1
+  let P = 1e9+7
+  // s>=2k
+  if (s<2*k) return 0
+  for (let i = 1; i < n; i++) {
+      for (let l = 0; l < k; l++) {
+          // 前 i 个元素，构成和 l 的方案数
+          dp[i][l] = (dp[i-1][l] + ((l-nums[i]>=0) ? dp[i-1][l-nums[i]] : 0))%P
+      }
+  }
+  let qpow = (a, b, p = P) => {
+      let ans = 1%p
+      while (b) {
+          if (b&1) ans = Number(BigInt(ans)*BigInt(a)%BigInt(p))
+          a = Number(BigInt(a)*BigInt(a)%BigInt(p))
+          b>>=1
+      }
+      return ans
+  }
+  let t = 0
+  for (let i = 0; i < k; i++) t += dp[n-1][i], t %= P
+  return ((qpow(2, n) - t - t)%P+P)%P
+};
+```
diff --git a/leetcode/残酷刷题/518. Coin Change II-1.js b/leetcode/残酷刷题/518. Coin Change II-1.js
@@ -0,0 +1,16 @@
+/**
+ * @param {number} amount
+ * @param {number[]} coins
+ * @return {number}
+ */
+var change = function(amount, coins) {
+  const n = coins.length, dp = Array(amount+1).fill(0)
+  dp[0] = 1
+  if (amount === 0) return 1
+  for (let j = 0; j < n; j++) {
+      for (let i = 1; i <= amount; i++) {
+          if (i >= coins[j]) dp[i] += dp[i-coins[j]]
+      }
+  }
+  return dp[amount]
+};
diff --git a/leetcode/残酷刷题/518. Coin Change II.js b/leetcode/残酷刷题/518. Coin Change II.js
@@ -0,0 +1,23 @@
+/**
+ * @param {number} amount
+ * @param {number[]} coins
+ * @return {number}
+ */
+var change = function(amount, coins) {
+    const n = coins.length, dp = Array(amount+1).fill(0).map(() => Array(n).fill(0))
+    dp[0][0] = 1
+    if (amount === 0) return 1
+    for (let i = 1; i <= amount; i++) {
+        let s = 0
+        for (let j = 0; j < n; j++) {
+            if (i >= coins[j]) {
+                // 硬币递增，避免重复计算
+                for (let k = 0; k <= j; k++) {
+                    dp[i][j] += dp[i-coins[j]][k]
+                }
+            }
+            s += dp[i][j]
+        }
+        if (i === amount) return s
+    }
+  };
diff --git a/leetcode/残酷刷题/518. Coin Change II.md b/leetcode/残酷刷题/518. Coin Change II.md
@@ -0,0 +1,96 @@
+# 残酷刷题 | LeetCode 518. Coin Change II
+
+## 题目
+
+给你一个整数数组 `coins` 表示不同面额的硬币，另给一个整数 `amount` 表示总金额。
+
+请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 `0` 。
+
+假设每一种面额的硬币有无限个。 
+
+题目数据保证结果符合 32 位带符号整数。
+
+**示例 1：**
+
+**输入：**amount = 5, coins = \[1, 2, 5\]
+**输出：**4
+**解释：**有四种方式可以凑成总金额：
+5=5
+5=2+2+1
+5=2+1+1+1
+5=1+1+1+1+1
+
+**示例 2：**
+
+**输入：**amount = 3, coins = \[2\]
+**输出：**0
+**解释：**只用面额 2 的硬币不能凑成总金额 3 。
+
+**示例 3：**
+
+**输入：**amount = 10, coins = \[10\]
+**输出：**1
+
+## 算法
+
+- 算法类型：动态规划
+- 算法解析
+    - `dp[i][j]` 表示组成数量 `i`，最后一个硬币是 `j` 的方案数，为了避免重复计算，我们要求硬币的组成顺序是不降序的
+    - `dp[0][0] = 1`
+    - `dp[i][j] = dp[i-coins[j]][k] (i>=coins[j], 2518. 好分区的数目
+k<=j)`
+- 算法复杂度
+    - 时间复杂度：`O(amount*n^2)`
+    - 空间复杂度：`O(amount*n)`
+    - 可以继续优化：将 amount 和 coins 的循环调换，按照 coins 的顺序，可省去最内层的循环，时间复杂度为 `O(amount*n)`，空间复杂度为 `O(amount)`
+
+## JS 代码
+
+```js
+/**
+ * @param {number} amount
+ * @param {number[]} coins
+ * @return {number}
+ */
+ var change = function(amount, coins) {
+  const n = coins.length, dp = Array(amount+1).fill(0).map(() => Array(n).fill(0))
+  dp[0][0] = 1
+  if (amount === 0) return 1
+  for (let i = 1; i <= amount; i++) {
+      let s = 0
+      for (let j = 0; j < n; j++) {
+          if (i >= coins[j]) {
+              // 硬币递增，避免重复计算
+              for (let k = 0; k <= j; k++) {
+                  dp[i][j] += dp[i-coins[j]][k]
+              }
+          }
+          s += dp[i][j]
+      }
+      if (i === amount) return s
+  }
+};
+
+```
+
+### 优化后
+
+```js
+/**
+ * @param {number} amount
+ * @param {number[]} coins
+ * @return {number}
+ */
+var change = function(amount, coins) {
+  const n = coins.length, dp = Array(amount+1).fill(0)
+  dp[0] = 1
+  if (amount === 0) return 1
+  for (let j = 0; j < n; j++) {
+      for (let i = 1; i <= amount; i++) {
+          if (i >= coins[j]) dp[i] += dp[i-coins[j]]
+      }
+  }
+  return dp[amount]
+};
+
+```
