力扣题:高精度运算-1.4

力扣题-1.4

[力扣刷题攻略] Re：从零开始的力扣刷题生活

力扣题1：306. 累加数

解题思想：首先先通过secondStart和secondEnd可以确定num1 = num[0:secondStart],num2 = num[secondStart:secondEnd]，然后遍历secondStart和secondEnd进行第二个数字的提取，然后通过check函数进行判断是否合法。

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        n = len(num)
        ## 遍历secondStart和secondEnd即可，因为num1 = num[0:secondStart],num2 = num[secondStart:secondEnd]
        ## secondStart从1开始，secondEnd从secondStart+1开始
        for secondStart in range(1,n-1):
            ## 判断特殊条件num1=0
            if num[0] == '0' and secondStart!=1:
                break
            for secondEnd in range(secondStart,n-1):
                ## 判断特殊条件num2=0
                if num[secondStart] == '0' and secondStart != secondEnd:
                    break
                num1 = num[0:secondStart]
                num2 = num[secondStart:secondEnd+1]
                num3 = num
                if self.check(num1,num2,num3):
                    return True
        return False
    
    def add(self,num1,num2):
        ## 进行字符串的加法操作，从低位开始相加
        i, j = len(num1) - 1, len(num2) - 1
        add = 0
        ans = list()
        while i >= 0 or j >= 0 or add != 0:
            x = int(num1[i]) if i >= 0 else 0
            y = int(num2[j]) if j >= 0 else 0
            result = x + y + add
            ans.append(str(result % 10))
            add = result // 10
            i -= 1
            j -= 1
        ## 最后需要进行翻转
        return "".join(ans[::-1])

    def check(self,num1,num2,num3):
        n = len(num3)
        num3 = num3[len(num1)+len(num2):]
        flag = 1
        while num3 != "" and flag == 1:
            temp = self.add(num1,num2)
            temp_len = len(temp)
            curr_num = num3[:temp_len]
            if curr_num == temp:
                num1 = num2
                num2 = temp
                num3 = num3[temp_len:]
            else:
                flag = 0
        if flag == 0:
            return False
        return True

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.length();
        
        for (int secondStart = 1; secondStart < n - 1; ++secondStart) {
            if (num[0] == '0' && secondStart != 1) {
                break;
            }
            
            for (int secondEnd = secondStart; secondEnd < n - 1; ++secondEnd) {
                if (num[secondStart] == '0' && secondStart != secondEnd) {
                    break;
                }
                
                string num1 = num.substr(0, secondStart);
                string num2 = num.substr(secondStart, secondEnd - secondStart + 1);
                string num3 = num;
                
                if (check(num1, num2, num3)) {
                    return true;
                }
            }
        }
        
        return false;
    }

    string add(string num1, string num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int add = 0;
        string result = "";

        while (i >= 0 || j >= 0 || add != 0) {
            int x = (i >= 0) ? (num1[i] - '0') : 0;
            int y = (j >= 0) ? (num2[j] - '0') : 0;
            int sum = x + y + add;

            result = char(sum % 10 + '0') + result;
            add = sum / 10;

            i -= 1;
            j -= 1;
        }

        return result;
    }

    bool check(string num1, string num2, string num3) {
        int n = num3.length();
        num3 = num3.substr(num1.length() + num2.length());

        int flag = 1;
        while (!num3.empty() && flag == 1) {
            string temp = add(num1, num2);
            int tempLen = temp.length();
            string currNum = num3.substr(0, tempLen);

            if (currNum == temp) {
                num1 = num2;
                num2 = temp;
                num3 = num3.substr(tempLen);
            } else {
                flag = 0;
            }
        }

        return (flag == 1);
    }
};