当前位置: 首页 > news >正文

专门做游戏的网站自助快速建站

专门做游戏的网站,自助快速建站,食品网站建设规划书,网络公司做网站后期注意题目链接 Leetcode.2522 将字符串分割成值不超过 K 的子字符串 rating : 1605 题目描述 给你一个字符串 s s s ,它每一位都是 1 1 1 到 9 9 9 之间的数字组成,同时给你一个整数 k k k 。 如果一个字符串 s s s 的分割满足以下条件,我们…

题目链接

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 1s.length105
  • s [ i ] s[i] s[i]'1''9' 之间的数字。
  • 1 ≤ k ≤ 1 0 9 1 \leq k \leq 10^9 1k109

解法一 : 动态规划

我们定义 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[i+1,j]k,i<j)

由于 k ≤ 1 0 9 k \leq 10^9 k109,所以 j − i j - i ji 最大就是 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();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 ) 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;}
};
http://www.khdw.cn/news/58127.html

相关文章:

  • 十大免费建站程序wordpress专业竞价托管
  • 用闲置的安卓手机做网站中国搜索引擎
  • 网站背景音乐丁的老头seo博客
  • wordpress ajax 提交排名优化网站
  • 网站所有分类中 点击箭头不出现下拉菜单电商运营自学网站
  • 海尔集团网站是怎么做的什么是软文
  • 电脑系统做的好的网站台州网站建设
  • 成都网站制作-中国互联想卖产品怎么推广宣传
  • 网站建设指标佛山疫情最新情况
  • 做的比较好的游戏网站百度搜索排名优化哪家好
  • 网站页面设计内容北京网络推广公司
  • 网站建设业务培训近期的重大新闻
  • 关于互联网的网站软文自助发稿平台
  • 南阳微网站网络舆情监测系统软件
  • listify wordpress西安百度seo排名
  • 苏中建设 官方网站网站推广的途径有哪些
  • 做智能家居网站下载百度
  • 织梦网站安装视频google搜索引擎入口2022
  • 自己做网站步骤重庆网站制作系统
  • 郑州高端网站建设公司销售找客户的方法
  • 百度做玻璃钢的网站线上销售渠道有哪几种
  • 网站建设会议验收常见的网络营销模式
  • 淘宝做链接有哪些网站可以做百度seo多少钱一个月
  • 广西住房建设厅网站首页微信社群营销怎么做
  • 搜狐焦点石家庄房产网轻松seo优化排名
  • 门户网站建设意义域名注册网站
  • 风铃网站代做seo公司推荐推广平台
  • seo推广公司招商开鲁网站seo转接
  • 国内做设计的网站有哪些广告的六种广告形式
  • 代运营怎么做武汉网络seo公司