leetcode 306. Additive Number | 306. 累加数（Java）

╰+哭是因爲堅強的太久メ 2022-10-18 15:00 161阅读 0赞

## 题目 ##

[https://leetcode.com/problems/additive-number/][https_leetcode.com_problems_additive-number]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

看来不只有我想喷这道题。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

思路很朴素，代码写的太矬了，注释写在代码里了。

真的想看过程的话，可以看：[评论区题解][Link 1]，思路一致，实现比较优雅。

class Solution { 
        public boolean isAdditiveNumber(String num) { 
            if (num.equals("000")) return true;
            int p0 = 0; // n1 begin pointer
            int p1 = 1; // n1 end pointer(n2 begin pointer)
            int p2 = 2; // n2 end pointer
            long n1, n2, sum;
            if (num.startsWith("0")) {  // 若以0开头 必须固定n1=0
                for (; p2 < num.length(); p2++) { 
                    n1 = 0;
                    n2 = Long.parseLong(num.substring(p1, p2));
                    if (String.valueOf(n2).length() > num.length() / 2) break;
                    if (checkPrefix(num, p1, p2, n1, n2)) return true;
                }
                return false;
            }
            // 不以0开头的情况 n1,n2都不固定
            p1 = 1;
            p2 = 2;
            for (; p1 < p2; p1++) { 
                for (p2 = p1 + 1; p2 < num.length(); p2++) { 
                    n1 = Long.parseLong(num.substring(p0, p1));
                    n2 = Long.parseLong(num.substring(p1, p2));
                    if (String.valueOf(Math.max(n1, n2)).length() > num.length() / 2) break;
                    if (checkPrefix(num, p1, p2, n1, n2)) return true;
                }
            }
            return false;
        }
        // IDEA 自动抽取出的公共部分
        private boolean checkPrefix(String num, int p1, int p2, long n1, long n2) { 
            long sum = n1 + n2;
            String subStr = num.substring(p1);
            String prefix = String.valueOf(n2) + sum;
            return subStr.equals(prefix) || subStr.startsWith(prefix) && strictWay(subStr, 0, p2 - p1, p2 - p1 + String.valueOf(sum).length());
        }
        // 当确定num1和num2之后，后面的数字就是可以唯一计算的了。此函数验证后面的数字是否正确。
        public boolean strictWay(String num, int p0, int p1, int p2) { 
            long n1 = Long.parseLong(num.substring(p0, p1));
            long n2 = Long.parseLong(num.substring(p1, p2));
            long sum = n1 + n2;
            if (!num.startsWith("" + n1 + n2 + sum)) { 
                return false;
            } else { 
                String subStr = num.substring(p1);
                String prefix = String.valueOf(n2) + sum;
                return subStr.equals(prefix) || strictWay(subStr, 0, p2 - p1, p2 - p1 + String.valueOf(sum).length());
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_additive-number]: https://leetcode.com/problems/additive-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/e3634246ce15420ab3d21d31efaba365.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/ce66bb3dc1304d5d943188298d3af3cd.png
[Link 1]: https://leetcode.com/problems/additive-number/discuss/75567/Java-Recursive-and-Iterative-Solutions
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/c2697c2b8fbf4546a40cbf72a0b25138.png