Skip to content

Latest commit

 

History

History
 
 

1849.Splitting-a-String-Into-Descending-Consecutive-Values

1849.Splitting-a-String-Into-Descending-Consecutive-Values

我们只要确定了第一段区间,也就确定了第一个数字num。那么我们就要寻找第二个区间的范围能够表达数字num-1. 如果找到的话,就递归寻找下一个区间范围使得能够表达数字num-2 .... 直到最后一个区间结束时恰好是字符串的终点。

注意可以探索的区间很长,比如你尝试第一个区间长度达到19时,极有可能长整形也会溢出,C++的stoll会报错。我们注意到,尝试的第一个数字不可能非常大,假设它的数值大于1e10,即有11位数字,那么第二个数字必然也至少有10位数字,总的长度就会超过原始字符串20的限制。所以我们用逐位累加的方法来计算num(而不是用stoll),当发现num>1e10时就可以终止更大的区间尝试了。