class Solution {
public:
int minimumPartition(string s, int k) {
}
};
2522. 将字符串分割成值不超过 K 的子字符串
给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。
如果一个字符串 s 的分割满足以下条件，我们称它是一个 好 分割：
s 中每个数位 恰好 属于一个子字符串。k 。请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。
注意：
"123" 的值为 123 ，"1" 的值是 1 。
示例 1：
输入：s = "165462", k = 60 输出：4 解释：我们将字符串分割成子字符串 "16" ，"54" ，"6" 和 "2" 。每个子字符串的值都小于等于 k = 60 。 不存在小于 4 个子字符串的好分割。
示例 2：
输入：s = "238182", k = 5 输出：-1 解释：这个字符串不存在好分割。
提示：
1 <= s.length <= 105s[i] 是 '1' 到 '9' 之间的数字。1 <= k <= 109原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.8 MB, 提交时间: 2023-01-03 11:30:46
// https://www.bilibili.com/video/BV1H8411E7hn
func minimumPartition(s string, k int) int {
ans, x := 1, 0
for _, c := range s {
v := int(c - '0')
if v > k {
return -1
}
x = x*10 + v
if x > k {
ans++
x = v
}
}
return ans
}
python3 解法, 执行用时: 124 ms, 内存消耗: 15.4 MB, 提交时间: 2023-01-03 11:30:11
class Solution:
def minimumPartition(self, s: str, k: int) -> int:
ans, x = 1, 0
for v in map(int, s):
if v > k: return -1
x = x * 10 + v
if x > k:
ans += 1
x = v
return ans