題目

https://leetcode.com/problems/additive-number/

題解

看來不只有我想噴這道題。。

思路很樸素，代碼寫的太矬了，注釋寫在代碼里了。

真的想看過程的話，可以看：評論區題解，思路一致，實現比較優雅。

class Solution {public boolean isAdditiveNumber(String num) {if (num.equals("000")) return true;int p0 = 0; // n1 begin pointerint p1 = 1; // n1 end pointer(n2 begin pointer)int p2 = 2; // n2 end pointerlong n1, n2, sum;if (num.startsWith("0")) { // 若以0開頭 必須固定n1=0for (; 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());}} }

總結

以上是生活随笔為你收集整理的leetcode 306. Additive Number | 306. 累加数（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。