力扣–累加數(shù)

文章目錄

• 力扣--累加數(shù)
• • 一、問題描述
  • 二、分析
  • 三、代碼

一、問題描述

二、分析

• 這道題第一眼看可能覺得比較簡單，枚舉前后3個(gè)位置，判斷這3個(gè)位置的數(shù)字是否滿足題目的要求（第三個(gè)數(shù) = 前兩個(gè)數(shù)之和）
• 但是看到后面的用例就會(huì)發(fā)現(xiàn)問題：199100199==》這3個(gè)數(shù)不一定是1位數(shù)，可能是多位數(shù)，所以都需要進(jìn)行枚舉

• 定義i,j,k分別代表第一個(gè)數(shù)字、第二個(gè)數(shù)字和第三個(gè)數(shù)字的起始下標(biāo)，這樣好處在于計(jì)算各個(gè)字符串時(shí)都很方便。
• 第一個(gè)數(shù)字的起始下標(biāo)一定是0，但是第二和第三個(gè)數(shù)字的起始下標(biāo)不固定，需要通過兩層循環(huán)枚舉，在拿到起始數(shù)字之后，就可以dfs一直到最后驗(yàn)證是否整個(gè)字符串符合要求。
• 這道題dfs的遞歸結(jié)束條件和普通稍有不同。這里遞歸成功的標(biāo)志是一直到字符串最后一個(gè)字符都滿足要求，即是累加序列，那么我們需要看是否能夠遞歸到最后一個(gè)位置正好結(jié)束。
• 為了處理大正數(shù)相加應(yīng)該使用兩字符串相加的程序，并且與和的字符串比較，避免轉(zhuǎn)換為int消耗時(shí)間與溢出。

三、代碼

class Solution { public://字符串相加函數(shù)string add(string& a,string& b){int n1 = a.size() - 1;int n2 = b.size() - 1;int carry = 0;string ans;while(n1 >= 0 || n2 >= 0 || carry > 0){int t1 = n1 >= 0 ? a[n1--] - '0' : 0;int t2 = n2 >= 0 ? b[n2--] - '0' : 0;ans += (t1 + t2 + carry) % 10 + '0';carry = (t1 + t2 + carry) >= 10 ? 1 : 0;}reverse(ans.begin(),ans.end());return ans;}bool dfs(string& str,int i,int j,int k){//代表第一個(gè)數(shù)字的下標(biāo)以0開始并且不等于0//代表第二個(gè)數(shù)字的下標(biāo)以0開始并且不等于0//代表第三個(gè)數(shù)字的下標(biāo)以0開始并且不等于0//這三種情況都是false的if((str[i] == '0' && i + 1 < j) || (str[j] == '0' && j + 1 < k) || (str[k] == '0' && k + 1 < str.size() - 1)){return false;}//取出前兩個(gè)數(shù)字string num1 = str.substr(i,j - i);string num2 = str.substr(j,k - j);//計(jì)算前臉個(gè)數(shù)字的和，避免大數(shù)溢出采用字符串相加的方式string add_num = add(num1,num2);int n = add_num.size();//代表如果第三個(gè)數(shù)字的起始位置k到字符結(jié)束的位置字符的數(shù)量小于n//就代表一定不滿足條件(長度都不夠肯定不想等)if(n > str.size() - k){return false;}//獲取第三個(gè)數(shù)字string num3 = str.substr(k,n);//現(xiàn)在長度相等但是值不相等直接返回falseif(num3 != add_num){return false;}//按照題目要求，只有整個(gè)str都滿足時(shí)才算疊加序列//即第三個(gè)數(shù)字剛好是k到str的末尾if(k + n == str.size()){return true;}//反之代表當(dāng)前沒走到str的末尾，繼續(xù)遞歸return dfs(str,j,k,k + n);}bool isAdditiveNumber(string num) {//直接排除特殊情況if(num.size() < 3){return false;}//i代表第一個(gè)數(shù)字的起始下標(biāo)//j代表第二個(gè)數(shù)字的起始下標(biāo)//k代表第三個(gè)數(shù)字的起始下標(biāo)//第一個(gè)數(shù)字一定是從0位置開始的int i = 0;//枚舉第二個(gè)數(shù)字的起始下標(biāo)jfor(int j = i + 1;j < num.size();j++){//枚舉第三個(gè)數(shù)字的起始下標(biāo)kfor(int k = j + 1;k < num.size();k++){if(dfs(num,i,j,k)){return true;}}}return false;} };

總結(jié)

以上是生活随笔為你收集整理的力扣--累加数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。