侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【贪心】将字符串分割成值不超过 K 的子字符串

GabrielxD
2023-01-02 / 0 评论 / 0 点赞 / 394 阅读 / 508 字
温馨提示:
本文最后更新于 2023-01-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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 <= 10^5
  • s[i] 是 '1' 到 '9' 之间的数字。
  • 1 <= k <= 10^9

解题

方法一:贪心

思路

贪心思想:为使分割出的子字符串尽可能小,就应该让每个子字符串尽可能长:遍历字符串,每次把当前字符(c)拼入子字符串表示的数字(sub),如果 subk 大说明必须进行分割,增加分割计数(cnt)并只保留 sub 个位数字。

代码

class Solution {
    public int minimumPartition(String s, int k) {
        int cnt = 1;
        long sub = 0;
        for (char c : s.toCharArray()) {
            int x = c - '0';
            if (x > k) return -1;
            sub = sub * 10 + x;
            if (sub > k) {
                sub %= 10;
                ++cnt;
            }
        }
        return cnt;
    }
}
0

评论区