-加強版- 大數加減乘除,一文徹底搞定
前言
大家好,我是 bigsai!(上次發佈的忘加原創並且今天的把內容擴充了一下) 最近,大數加減頻頻登上筆試的舞臺,小夥伴們在羣裏也分享自己遇到面試官碰到大數運算的題目,想着這麼重要而簡單的知識點我還沒寫過,那得好好和大家一起總結一下。
羣內情況
各位有過分類刷題的小夥伴,可能看到很多人分類 字符串、貪心、動態規劃、bfs、dfs、大數、數論等,初聽大數,你可能會差異:大數是個啥?聽起來怪高大上的。
大數,其實就是很大很大數字 (可能遠超 32、64 位,基礎類型無法表示) 的加減法,在 Java 中我們可以使用一個大數類 (BigInteger 等) 很容易解決大數的各種運算,但如果遇到面試官他肯定會讓你手寫的。
這個數字一般用字符串、鏈表等形式表示、返回,大數運算的核心就是:模擬,模擬我們日常用紙筆算數字的加減乘除流程,然後再根據計算機、編程語言等特性適當存儲計算即可,不過,大數除法運算稍微特殊一點,和我們直接模擬的思維方式稍有不同,它就是轉換了一下成特殊的加減法運算,後面會細談。
大數加法
大數加法是最簡單的,簡單模擬即可。首先,我們想一下兩個數加法的流程:從右向左計算求和、進位,一直到最後。
在編程語言中同樣也是模擬從右向左逐位相加的過程,不過在具體實現上需要注意一些細節。
1、枚舉字符串將其轉換成char[]
提高效率
2、從右往左進行計算,可以將結果放到一個數組中最後組成字符串,也可以使用 StringBuider 拼接,拼接的時候最後要逆置一下順序。
3、餘數每次疊加過需要清零,兩數相加如果大於等於 10 即有餘數,添加到結果中該位置的數也應該是該數 %10 的結果。
4、計算完最後還要看看餘數是否爲 1,如果爲 1 需要將其添加到結果,例如 "991"+"11"
算三個位置爲002
但還有一個餘數需要添加,所以應該是1002
。
一個加法流程
當然在具體實現上方法較多,你可以首先就將字符串逆置然後從前往後就可以計算了。當然我這裏實現的是字符串從後向前各個位對應計算,然後將結果順序添加到 StringBuilder 上。
這題在力扣【415 兩數相加】可以檢驗自己代碼,實現代碼爲:
public String addStrings(String num1, String num2) {
// 公衆號:bigsai 歡迎你的關注
int len1=num1.length()-1,len2=num2.length()-1;
char ch1[]=num1.toCharArray();
char ch2[]=num2.toCharArray();
StringBuilder sb=new StringBuilder();
int remainder =0;//計算餘數
while (len1>=0||len2>=0)
{
int n1=len1>=0?(ch1[len1--]-'0'):0;
int n2=len2>=0?(ch2[len2--]-'0'):0;
int num=n1+n2+remainder;//求和對應數字
remainder=num/10;//是否進位
sb.append(num%10);// 添加到結果字符串中
}
if(remainder>0)//是否還需要進位
{
sb.append(remainder);
}
//反裝即爲結果
return sb.reverse().toString();
}
大數減法
加法對應的就是減法,有了上面大數加法的實現思路,那麼我想你在大數減法也應該有點想法,但是減法和加法不同的是減法有位置的區別,加法需要進位而減法需要借位。並且大整正數減法可能產生正負也不一定。
兩個正數,如果大數減去小數,那麼一切正常,結果是一個正數;但如果小數減去大數,那麼結果將是一個負數,並且結果處理起來比較麻煩。所以在這裏全部轉成大 - 小處理 (大 - 小不存在不能借位的情況)。
減法轉成大 - 小
1、執行計算前首先比較減數 (num1
) 和被減數 (num2
) 的大小,如果num1>num2
, 那麼就模擬num1-num2
的過程,如果num1<num2
,那麼結果就爲-(num2-num1)
。當然可以爲了穩定模擬時候一個大一個小,可將num1
始終指向較大的那個數,少寫一個 if/else.
一個減法大概流程
public static boolean compare(String num1,String num2)
{
if(num1.length()<num2.length())
return false;
else if(num1.length()>num2.length())
return true;
else
return num1.compareTo(num2)>0;
}
public static String subtractString(String num1,String num2) {
char sign='+';//正負號
//讓num1>num2 如果num1<num2 那麼結果就是—(num2-num1)
//可以先將num1和num2交換和前面情況統一
if(!compare(num1,num2))
{
sign='-';
String team = num2;
num2 = num1;
num1 = team;
}
int len1=num1.length()-1;
int len2=num2.length()-1;
char ch1[] = num1.toCharArray();
char ch2[] = num2.toCharArray();
StringBuilder sb=new StringBuilder();
int borrow=0;//借位
while (len1>=0||len2>=0)
{
int n1=len1>=0?(ch1[len1--]-'0'):0;
int n2=len2>=0?(ch2[len2--]-'0'):0;
int num=n1-n2-borrow;
borrow=0;
if(num<0)//需要向前借位
{
borrow=1;
num+=10;
}
sb.append(num);
}
sb=sb.reverse();//需要先翻轉
int index = 0;//去掉前面沒用的’0‘
while (index<sb.length()&&sb.charAt(index) == '0')
{
index++;
}
//如果兩個數相同 直接返回"0"
if(index==sb.length())
return "0";
if(sign=='+')//如果正數
return sb.substring(index);
else return sign+sb.substring(index);//負數需要返回
}
大數乘法
先計算後進位
而多*多
也是這個道理,將不同位乘積先疊加到對應位置上,然後從右向左進位,一直到不需要進位爲止。
一個乘法流程
你可能會疑問,如果兩個數組的長度分別爲 a 和 b 這個數組到底該開多大呢?
- a+b 大小就夠了,怎麼分析呢?其中一個 a 不變。另一個 b 變成最小 b+1 數字即十的倍數,那麼這樣在相乘的時候也不過是 a+b 長度,所以這裏 a+b 長度就夠了。
這題有力扣對應題可以去試試【43 字符串相乘】,具體代碼爲:
public String multiply(String num1, String num2) {
if("0".equals(num1)||"0".equals(num2))return "0";
char a[]=num1.toCharArray();
char b[]=num2.toCharArray();
int value[]=new int[a.length+b.length];
for(int i=a.length-1;i>=0;i--)
{
for(int j=b.length-1;j>=0;j--)
{
int index=a.length-1-i+b.length-1-j;
value[index]+=(a[i]-'0')*(b[j]-'0');
}
}
for(int i=0;i<value.length-1;i++)
{
value[i+1]+=value[i]/10;
value[i]=value[i]%10;
}
int index=value.length-1;
while(value[index]==0)
{index--;}
StringBuilder sBuilder=new StringBuilder();
while (index>=0) {
sBuilder.append(value[index--]);
}
return sBuilder.toString();
}
大數除法
大數加減乘都搞定了,通過模擬來實現,但是大數除法也通過模擬來實現?
並不是,對於大數 a/b,一般最多要求求到其整數解或者餘數,即 a/b=c……d(a,b,c,d 均爲整); 也就是 a 裏面有 c 個 b,並且還剩下 d。核心是先求 c 是多少,對於程序來說,可以通過枚舉啊,將除法變成減法,從 a 中不斷減 d,一直到不能減爲止。
除法轉成減法運算
但是有個問題,如果被除數 a 很大很大,可能有居多個 b,那麼這樣時間複雜度太高了,不可能執行那麼多次,那麼需要怎麼樣去優化這個方法呢?
那就要加速尋找次數,減少這個減法的次數了,減法次數減小的一個最好方案就是能不能擴大除數 b。如果 b 後面加個'0'
,那麼算出來的結果就乘以 10,減法的次數變成原來十分之一。根據這個思想我們可以一直每次找到 b 的最大 10 的倍數 (小於 a) 計算減的次數再換算成減 b 的總詞數,將結果要以字符串方式保留,後面一直迭代到最後爲止, 這雖然是一道除法運算的題,但是也蘊含減法和加法 (次數疊加到結果中)。
計算思想
當然,也有一些人使用二分法來壓縮尋找可以被減的次數也是可以的 (加法可以迭代數字實現二分倍數),具體實現的話也不是很困難,但是代碼量可能比較多所以一般的面試筆試不會讓你現場寫的,所以好好掌握前面的減法、減法、乘法的代碼即可。
這部分代碼我也簡單給一下 (其他函數上面貼過就不重複貼啦):
//假設 num1>num2
public static String divideString(String num1,String num2)
{
String value="0";//結果
while (compare(num1,num2))
{
StringBuilder sbTeam=new StringBuilder(num2);//用這個往後面不斷加0 和num做減法
StringBuilder sbCount=new StringBuilder("1");//次數 可能很大
int subLen=num1.length()-num2.length();//統計大概要加幾個零
for(int i=0;i<subLen;i++)
{
sbTeam.append('0');
sbCount.append('0');
}
//如果0 加多了 那麼要刪一個 類似"12300" / "23" "12300"比"23000"小
//所以要 "2300" 對應比"23"擴大 "100"倍數,每減一次"2300" 則結果加"100"
if(!compare(num1,sbTeam.toString()))
{
sbTeam=sbTeam.deleteCharAt(sbTeam.length()-1);
sbCount=sbCount.deleteCharAt(sbCount.length()-1);
}
// 一直能減的時候
while (compare(num1,sbTeam.toString()))
{
num1=subtractString(num1,sbTeam.toString());
value=addStrings(sbCount.toString(),value);
}
}
return value;
}
簡單測試了下,正確性還是 ok 的:
除法測試
番外篇
除了上面直接的大數加減乘除,還有一些變形的題目需要我們特殊處理一下,比如可能會使用鏈表等存儲處理,下面分享兩道題。
兩數相加 (力扣 02)
題目描述:
給你兩個 非空 的鏈表,表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的,並且每個節點只能存儲 一位 數字。請你將兩個數相加,並以相同形式返回一個表示和的鏈表
你可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。
img
提示:
-
每個鏈表中的節點數在範圍
[1, 100]
內 -
0 <= Node.val <= 9
-
題目數據保證列表表示的數字不含前導零
本題其實就是用一個鏈表存儲一個數字 (逆序存儲),你需要給它計算出結果後在 逆序 存儲到一個鏈表中返回。
所謂加法的運算規則:從兩個數的最低位進行計算,進行到下一位的時候需要考慮進位問題。一直到最後,而本題所給的鏈表剛好可以用來直接計算,因爲鏈表頭都是數字最低位可以直接相加,然後一直遍歷到結束。可以用一個常數表示進位。
運算邏輯
在具體實現 (鏈表) 的時候:
-
創建新的鏈表,每次將計算的數值插入到鏈表尾部即可。
-
需要準確表示進位,並且最後要考慮以下進位
-
妥善返回正確節點,可以用一個頭節點用來使得所有節點都正常操作,而不需要特殊判斷。
通過代碼第一次比較囉嗦的寫法:
當然,如果你遍歷鏈表把各個數字取出來,使用字符串、數字轉換然後相加得到一個數字,最後在轉成字符串、鏈表的理論可以,可以自行實現。
優化後的代碼爲:
//更簡潔的寫法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node=new ListNode(0);
ListNode team=node;
int jin=0;//進位
while(l1!=null||l2!=null)
{
int num=jin;
if(l1!=null)
{
num+=l1.val;l1=l1.next;
}
if(l2!=null)
{
num+=l2.val;l2=l2.next;
}
jin=num/10;
num%=10;
team.next=new ListNode(num);
team=team.next;
}
if(jin!=0)team.next=new ListNode(jin);
return node.next;
}
兩數相加 2(力扣 445)
題目描述:
給你兩個 非空 鏈表來代表兩個非負整數。數字最高位位於鏈表開始位置。它們的每個節點只存儲一位數字。將這兩數相加會返回一個新的鏈表。
你可以假設除了數字 0 之外,這兩個數字都不會以零開頭。
進階:如果輸入鏈表不能修改該如何處理?換句話說,你不能對列表中的節點進行翻轉。
示例:
輸入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出:7 -> 8 -> 0 -> 7
本題的話和上面不一樣鏈表不是逆置的,但是加法運算其實需要從最後面對齊開始,也就是理論上應該從鏈表尾部開始向前,但是這是個單鏈表,這樣運算的話時間複雜度太高,所以我們要用空間換時間:用棧來解決。
將鏈表的節點依次放到兩個棧中,然後兩個棧同時取數計算。但是待返回的是個鏈表,所以採取頭插法即可 (如果不頭插最後反轉也可),具體流程可以參考如下圖:
邏輯
實現代碼爲:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer>stack1=new Stack<>();
Stack<Integer>stack2=new Stack<>();
while (l1!=null)
{
stack1.add(l1.val);
l1=l1.next;
}
while (l2!=null)
{
stack2.add(l2.val);
l2=l2.next;
}
ListNode val=new ListNode(0);//帶頭結點
int moreadd=0;//餘數
while (!stack1.isEmpty()||!stack2.isEmpty()||moreadd!=0)
{
int num=moreadd;//num=餘數+鏈表1+鏈表2
if(!stack1.isEmpty())
num+=stack1.pop();
if(!stack2.isEmpty())
num+=stack2.pop();
moreadd=num/10;
num=num%10;
//鏈表頭插
ListNode node=new ListNode(num);
node.next=val.next;
val.next=node;
}
return val.next;
}
}
結語
到這裏,大數的加減乘除基本都講解完啦,不知道你有沒有收穫,因爲這裏的大數都是用字符串的方式存儲和處理,遇到的最多,但是也可能遇到一些鏈表、數組等其他形式存儲的需要處理,但是整體的思想都是一樣的。
光看沒有還要多多練習對應的題目,當然本人水平有限上面理解可能有誤或者不到位還請指正!
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/0QAC-5YNKvU6viY30Q5Azg