Leetcode.1849 将字符串拆分为递减的连续值
题目链接
Leetcode.1849 将字符串拆分为递减的连续值 Rating : 1747
题目描述
给你一个仅由数字组成的字符串 s
。
请你判断能否将 s
拆分成 两个或者多个 非空子字符串 ,使子字符串的 数值 按 降序 排列,且每两个 相邻子字符串 的数值之 差 等于 1 。
- 例如,字符串
s = "0090089"
可以拆分成["0090", "089"]
,数值为[90,89]
。这些数值满足按降序排列,且相邻值相差 1 ,这种拆分方法可行。 - 另一个例子中,字符串
s = "001"
可以拆分成["0", "01"]
、["00", "1"]
或["0", "0", "1"]
。然而,所有这些拆分方法都不可行,因为对应数值分别是[0,1]、[0,1]
和[0,0,1]
,都不满足按降序排列的要求。
如果可以按要求拆分 s
,返回 true ;否则,返回 false 。
子字符串 是字符串中的一个连续字符序列。
示例 1:
输入:s = “1234”
输出:false
解释:不存在拆分 s 的可行方法。
示例 2:
输入:s = “050043”
输出:true
解释:s 可以拆分为 [“05”, “004”, “3”] ,对应数值为 [5,4,3] 。
满足按降序排列,且相邻值相差 1 。
示例 3:
输入:s = “9080701”
输出:false
解释:不存在拆分 s 的可行方法。
示例 4:
输入:s = “10009998”
输出:true
解释:s 可以拆分为 [“100”, “099”, “98”] ,对应数值为 [100,99,98] 。
满足按降序排列,且相邻值相差 1 。
提示:
- 1 < = s . l e n g t h < = 20 1 <= s.length <= 20 1<=s.length<=20
s
仅由数字组成
解法:模拟
提示1:题目要求相邻字符串数值之差为1,说明当确定第一个字符串时,后续字符串的数值也就确定了。
提示2:题目要求最少分成两个串,s.size()
最大才是 20
,一个子串的值不能超过
1
0
10
10^{10}
1010,超过就无解了。
用 pre
表示第一段子串的值,用 cur
表示接下来每一段子串 实际的值,用 next
表示接下来每一段子串 正确的值。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
C++代码:
using LL = long long;
class Solution {
public:
bool splitString(string s) {
int n = s.size();
//第一段子串的值 和 子串最大的值
LL pre = 0,mx = 1e10;
for(int i = 0;i < n;i++){
pre = pre * 10 + (s[i] - '0');
//如果有子串的值 > mx 后面也不会有解了
if(pre > mx) break;
//cur 表示接下来每一段 实际的值
//next 表示接下来每一段 符合条件的值
LL cur = 0;
LL next = pre - 1;
for(int j = i + 1;j < n && next >= 0;j++){
cur = cur * 10 + (s[j] - '0');
//这一段子串的值符合要求,更新 next 和 cur 开始寻找下一段
//只有当 cur 的这一段是最后一段时,并且 cur == next , cur 才允许为0
、 if((cur == next && cur != 0) || (cur == next && cur == 0 && j == n - 1)){
cur = 0;
next--;
//当前已经是最后一段,说明s 可以分解为题目要求的非空子串,直接返回 true
if(j == n - 1) return true;
}
//cur > next 说明该段不符合要求,直接退出循环
else if(cur > next) break;
}
}
return false;
}
};
相关文章
- 求一个字符串中子串连续出现的最大次数
- Python 字符串内置方法笔记
- 在Shell里面判断字符串是否为空
- 771. 字符串中最长的连续出现的字符
- LeetCode-1694. 重新格式化电话号码【字符串,分块】
- C# 字符串中多个连续空格转为一个空格
- C# XML本地文件转换成XML字符串
- 报错"ORA-01861: 文字与格式字符串不匹配"
- C# 字符串中多个连续空格转为一个空格
- 7-2 字符串字母大小写转换 (15 分)
- ZZNUOJ_用C语言编写程序实现1160:字符串长度(指针专题)(附完整源码)
- python 删除字符串中的连续空格只保留一个
- 【华为机试真题 Python实现】在字符串中找出连续最长的数字串(含“±”号)
- 习题 6.16 输入一个字符串,内有数字和非数字字符,如。。。将其中连续的数字作为一个整数,依次存放到一数组a中。例如,123放在a[0],456放在a[1]。。。统计共有多少个整数,并输出这些数。
- 习题 8.19(1) 编写一个函数new,对n个字符开辟连续的存储空间,此函数应返回一个指针(地址),指向字符串开始的空间。new(n)表示分配n个字节的内存空间。
- c语言之hex字符串转hex数组(“123456”->“0x12,0x34,0x56“)亲测可用
- 在OpenCV里用getTextSize计算文本字符串的宽度和高度
- 剑指 Offer 38. 字符串的排列
- python处理带有‘x‘的字符串,拆分,解码,重组