以这样的方式对给定字符串进行分区，即第i个子串是第（i-1）子串和第（i-2）子串的和-yiteyi-C++库

以这样的方式对给定字符串进行分区，即第i个子串是第（i-1）个和第（i-2）个子串的和。

null

例如：

Input : "11235813"
Output : ["1", "1", "2", "3", "5", "8", "13"]

Input : "1111223"
Output : ["1", "11", "12", "23"]

Input : "1111213"
Output : ["11", "1", "12", "13"]

Input : "11121114"
Output : []

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

1.从一个数字开始，一次选取三个数字（第一、第二和第三），遍历给定的字符串。 2.如果first+second=third，则递归调用check（），其中second为first，third为second。第三个是根据下一个可能的位数选择的。（两个数字相加的结果最多可包含第二位和第三位数字+1） 3.否则，首先增加第三个（通过增加更多数字）直到极限（这里极限是第一和第二的总和）。 4.增加三分之一后，出现以下情况。 a）当不匹配时，增加第二个偏移量。 b）当不匹配时，增加第一个偏移量。 c）注意：在增加第三个偏移量后调用check（）后，不要更改第二个或第一个偏移量，因为它们已经完成。 5.当到达字符串末尾且满足条件时，将“second”和“third”添加到空列表中。在回滚递归堆栈时，将“第一个”放在列表的前面，以便保留顺序。

                     // Java program to check if we can partition a                   
                     // string in a way that value of i-th string is                   
                     // sum of (i-1)-th and (i-2)-th substrings.                   
                     import                               java.util.LinkedList;                   
                             
                     public                               class                               SumArray {                   
                             
                                         private                               static                               LinkedList<Integer> resultList =                   
                                         new                               LinkedList<>();                   
                             
                                         private                               static                               boolean                               check(                               char                               [] chars,                               int                               offset1,                   
                                         int                               offset2,                               int                               offset3,                               boolean                               freezeFirstAndSecond) {                   
                             
                                         // Find subarrays according to given offsets                   
                                         int                               first = intOf(subArr(chars,                               0                               , offset1));                   
                                         int                               second = intOf(subArr(chars, offset1, offset2));                   
                                         int                               third = intOf(subArr(chars, offset1 + offset2, offset3));                   
                             
                                         // If condition is satisfied for current subarrays                   
                                         if                               (first + second == third) {                   
                             
                                         // If whole array is covered.                   
                                         if                               (offset1 + offset2 + offset3 >= chars.length) {                   
                                         resultList.add(first);                   
                                         resultList.add(second);                   
                                         resultList.add(third);                   
                                         return                               true                               ;                   
                                         }                   
                             
                                         // Check if remaining array also satisfies the condition                   
                                         boolean                               result = check(subArr(chars, offset1,                   
                                         chars.length - offset1), offset2, offset3,                   
                                         Math.max(offset2, offset3),                               true                               );                   
                                         if                               (result) {                   
                                         resultList.addFirst(first);                   
                                         }                   
                                         return                               result;                   
                                         }                   
                             
                                         // If not satisfied, try incrementing third                   
                                         if                               (isValidOffSet(offset1, offset2,                               1                               + offset3, chars.length)) {                   
                                         if                               (check(chars, offset1, offset2,                               1                               + offset3,                               false                               ))                   
                                         return                               true                               ;                   
                                         }                   
                             
                                         // If first and second have been finalized, do not                   
                                         // alter already computed results                   
                                         if                               (freezeFirstAndSecond)                   
                                         return                               false                               ;                   
                             
                                         // If first and second are not finalized                   
                                         if                               (isValidOffSet(offset1,                               1                               + offset2, Math.max(offset1,                   
                                         1                               + offset2),  chars.length)) {                   
                             
                                         // Try incrementing second                   
                                         if                               (check(chars, offset1,                               1                               + offset2,                   
                                         Math.max(offset1,                               1                               + offset2),                               false                               ))                   
                                         return                               true                               ;                   
                                         }                   
                             
                                         // Try incrementing first                   
                                         if                               (isValidOffSet(                               1                               + offset1, offset2, Math.max(                               1                               + offset1,                   
                                         offset2),  chars.length)) {                   
                                         if                               (check(chars,                               1                               + offset1, offset2, Math.max(                               1                               + offset1,                   
                                         offset2),                               false                               ))                   
                                         return                               true                               ;                   
                                         }                   
                                         return                               false                               ;                   
                                         }                   
                             
                                         // Check if given three offsets are valid (Within array length                   
                                         // and third offset can represent sum of first two)                   
                                         private                               static                               boolean                               isValidOffSet(                               int                               offset1,                               int                               offset2,                   
                                         int                               offset3,                               int                               length) {                   
                                         return                               (offset1 + offset2 + offset3 <= length &&                   
                                         (offset3 == Math.max(offset1, offset2) ||                   
                                         offset3 ==                               1                               + Math.max(offset1, offset2)));                   
                                         }                   
                             
                                         // To get a subarray with starting from given                   
                                         // index and offset                   
                                         private                               static                               char                               [] subArr(                               char                               [] chars,                               int                               index,                               int                               offset) {                   
                                         int                               trueOffset = Math.min(chars.length - index, offset);                   
                                         char                               [] destArr =                               new                               char                               [trueOffset];                   
                                         System.arraycopy(chars, index, destArr,                               0                               , trueOffset);                   
                                         return                               destArr;                   
                                         }                   
                             
                                         private                               static                               int                               intOf(                               char                               ... chars) {                   
                                         return                               Integer.valueOf(                               new                               String(chars));                   
                                         }                   
                             
                                         public                               static                               void                               main(String[] args) {                   
                                         String numStr =                               "11235813"                               ;                   
                                         char                               [] chars = numStr.toCharArray();                   
                                         System.out.println(check(chars,                               1                               ,                               1                               ,                               1                               ,                               false                               ));                   
                                         System.out.println(resultList);                   
                                         }                   
                     }                   

输出：

true
[1, 1, 2, 3, 5, 8, 13]

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章