视频点播网站建设,360 网站优化,营销网络建设,wordpress组件题目链接 Leetcode.2522 将字符串分割成值不超过 K 的子字符串 rating : 1605 题目描述
给你一个字符串 s s s #xff0c;它每一位都是 1 1 1 到 9 9 9 之间的数字组成#xff0c;同时给你一个整数 k k k 。
如果一个字符串 s s s 的分割满足以下条件#xff0c;我们…题目链接 Leetcode.2522 将字符串分割成值不超过 K 的子字符串 rating : 1605 题目描述
给你一个字符串 s s s 它每一位都是 1 1 1 到 9 9 9 之间的数字组成同时给你一个整数 k k k 。
如果一个字符串 s s s 的分割满足以下条件我们称它是一个 好 分割 s s s 中每个数位 恰好 属于一个子字符串。每个子字符串的值都小于等于 k k k 。
请你返回 s s s 所有的 好 分割中子字符串的 最少 数目。如果不存在 s s s 的 好 分割返回 − 1 -1 −1 。
注意
一个字符串的 值 是这个字符串对应的整数。比方说123 的值为 $1234 1 的值是 1 1 1 。子字符串 是字符串中一段连续的字符序列。
示例 1 输入s “165462”, k 60 输出4 解释我们将字符串分割成子字符串 “16” “54” “6” 和 “2” 。每个子字符串的值都小于等于 k 60 。 不存在小于 4 个子字符串的好分割。 示例 2 输入s “238182”, k 5 输出-1 解释这个字符串不存在好分割。 提示 1 ≤ s . l e n g t h ≤ 1 0 5 1 \leq s.length \leq 10^5 1≤s.length≤105 s [ i ] s[i] s[i] 是 1 到 9 之间的数字。 1 ≤ k ≤ 1 0 9 1 \leq k \leq 10^9 1≤k≤109
解法一 动态规划
我们定义 f ( i ) f(i) f(i) 为 s s s 的前 i i i 个字符中好分割的最少个数。按照定义最终我们返回的答案就是 f ( n ) f(n) f(n)。
那么我们很容易就能得出状态转移方程: f [ j ] m a x ( f [ j ] , f [ i ] 1 ) ( s [ i 1 , j ] ≤ k , i j ) f[j] max(f[j] , f[i] 1) \qquad (s[i 1,j] \leq k , i j) f[j]max(f[j],f[i]1)(s[i1,j]≤k,ij)
由于 k ≤ 1 0 9 k \leq 10^9 k≤109所以 j − i j - i j−i 最大就是 9 9 9。
时间复杂度 O ( n × 9 ) O(n \times 9) O(n×9)
C代码
class Solution {
public:int minimumPartition(string s, int k) {int n s.size();vectorint 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) coutf[i] ;return f[n] 1e9 ? -1 : f[n];}
};解法二贪心
我们每次分割的时候让 好分割 尽可能的大剩下的子串就更少所能得到的 好分割 也就越少。
所以贪心策略就是每次分割的时候让 好分割 尽可能地大这样最终的答案就是最少的。
时间复杂度 O ( n ) O(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 longLL 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;}
};
