西安建设学院网站,南山网站设计电话,产品查询展示型网站,wordpress中文商城题目链接 Leetcode.1849 将字符串拆分为递减的连续值 Rating #xff1a; 1747 题目描述
给你一个仅由数字组成的字符串 s。
请你判断能否将 s拆分成 两个或者多个 非空子字符串 #xff0c;使子字符串的 数值 按 降序 排列#xff0c;且每两个 相邻子字符串 的数值之 差 …题目链接 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 。 提示
1s.length201 s.length 201s.length20s仅由数字组成
解法模拟
提示1题目要求相邻字符串数值之差为1说明当确定第一个字符串时后续字符串的数值也就确定了。
提示2题目要求最少分成两个串s.size()最大才是 20一个子串的值不能超过101010^{10}1010超过就无解了。
用 pre表示第一段子串的值用 cur表示接下来每一段子串 实际的值用 next表示接下来每一段子串 正确的值。
时间复杂度O(n2)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 可以分解为题目要求的非空子串直接返回 trueif(j n - 1) return true;}//cur next 说明该段不符合要求直接退出循环else if(cur next) break;}}return false;}
};
