题目链接

Leetcode.2522 将字符串分割成值不超过 K 的子字符串 rating : 1605

题目描述

给你一个字符串 $s$ ，它每一位都是 $1$ 到 $9$ 之间的数字组成，同时给你一个整数 $k$ 。

如果一个字符串 $s$ 的分割满足以下条件，我们称它是一个 好 分割：

• $s$ 中每个数位 恰好 属于一个子字符串。
• 每个子字符串的值都小于等于 $k$ 。

请你返回 $s$ 所有的 好 分割中，子字符串的 最少 数目。如果不存在 $s$ 的 好 分割，返回 $-1$ 。

注意：

• 一个字符串的 值 是这个字符串对应的整数。比方说，"123" 的值为 $1234 ，"1" 的值是 $1$ 。
• 子字符串 是字符串中一段连续的字符序列。

示例 1：

输入：s = “165462”, k = 60
输出：4
解释：我们将字符串分割成子字符串 “16” ，“54” ，“6” 和 “2” 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。

示例 2：

输入：s = “238182”, k = 5
输出：-1
解释：这个字符串不存在好分割。

提示：

• $1\le s.length\le 10^5$
• $s[i]$ 是 '1' 到 '9' 之间的数字。
• $1\le k\le 10^9$

解法一 ： 动态规划

我们定义 $f(i)$ 为 $s$ 的前 $i$ 个字符中，好分割的最少个数。按照定义，最终我们返回的答案就是 $f(n)$。

那么我们很容易就能得出状态转移方程:

$$f[j]=max(f[j],f[i]+1)(s[i+1,j]\le k,i<j)$$

由于 $k\le 10^9$，所以 $j-i$ 最大就是 $9$。

时间复杂度：$O(n\times 9)$

C++代码：

class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.size();
        vector<int> f(n + 1,1e9);
        f[0] = 0;

        for(int i = 0;i <= n;i++){
            int len = min(n , i + 9) , sum = 0;

            for(int j = i + 1;j <= len;j++){
                sum = sum * 10 + (s[j - 1] - '0');
                if(sum > k) break;
                f[j] = min(f[i] + 1 , f[j]);
            }
        }

        //for(int i = 1;i <= n;i++) cout<<f[i]<<" ";

        return f[n] == 1e9 ? -1 : f[n];
    }
};

解法二：贪心

我们每次分割的时候，让 好分割 尽可能的大，剩下的子串就更少，所能得到的 好分割 也就越少。

所以贪心策略就是，每次分割的时候让 好分割 尽可能地大，这样最终的答案就是最少的。

时间复杂度： $O(n)$

C++代码：

using LL = long long;

class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.size() , ans = 0;
        for(int i = 0;i < n;i++){
            //可能会溢出 所以要用 long long
            LL sum = 0;
            int j = i;
            for(;j < n;j++){
                if((s[j] - '0') > k) return -1;
                sum = sum * 10 + (s[j] - '0');
                if(sum > k) break;
            }
            ans++;
            i = j - 1;
        }

        return ans;
    }
};