偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

大數(shù)加減乘除，一文徹底搞定

作者： bigsai
開(kāi)發(fā) 后端
加法對(duì)應(yīng)的就是減法，有了上面大數(shù)加法的實(shí)現(xiàn)思路，那么我想你在大數(shù)減法也應(yīng)該有點(diǎn)想法，但是減法和加法不同的是減法有位置的區(qū)別，加法需要進(jìn)位而減法需要借位。并且大整正數(shù)減法可能產(chǎn)生正負(fù)也不一定。

[[394151]]

本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」，作者bigsai。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。

前言

大家好，我是bigsai!(上次發(fā)布的忘加原創(chuàng)并且今天的把內(nèi)容擴(kuò)充了一下)最近，大數(shù)加減頻頻登上筆試的舞臺(tái)，小伙伴們?cè)谌豪镆卜窒碜约河龅矫嬖嚬倥龅酱髷?shù)運(yùn)算的題目，想著這么重要而簡(jiǎn)單的知識(shí)點(diǎn)我還沒(méi)寫(xiě)過(guò)，那得好好和大家一起總結(jié)一下。

群內(nèi)情況

各位有過(guò)分類刷題的小伙伴，可能看到很多人分類 字符串、貪心、動(dòng)態(tài)規(guī)劃、bfs、dfs、大數(shù)、數(shù)論等，初聽(tīng)大數(shù)，你可能會(huì)差異：大數(shù)是個(gè)啥?聽(tīng)起來(lái)怪高大上的。

大數(shù)，其實(shí)就是很大很大數(shù)字(可能遠(yuǎn)超32、64位，基礎(chǔ)類型無(wú)法表示)的加減法，在Java中我們可以使用一個(gè)大數(shù)類(BigInteger等)很容易解決大數(shù)的各種運(yùn)算，但如果遇到面試官他肯定會(huì)讓你手寫(xiě)的。

這個(gè)數(shù)字一般用字符串、鏈表等形式表示、返回，大數(shù)運(yùn)算的核心就是：模擬，模擬我們?nèi)粘Ｓ眉埞P算數(shù)字的加減乘除流程，然后再根據(jù)計(jì)算機(jī)、編程語(yǔ)言等特性適當(dāng)存儲(chǔ)計(jì)算即可，不過(guò)，大數(shù)除法運(yùn)算稍微特殊一點(diǎn)，和我們直接模擬的思維方式稍有不同，它就是轉(zhuǎn)換了一下成特殊的加減法運(yùn)算，后面會(huì)細(xì)談。

大數(shù)加法

大數(shù)加法是最簡(jiǎn)單的，簡(jiǎn)單模擬即可。首先，我們想一下兩個(gè)數(shù)加法的流程：從右向左計(jì)算求和、進(jìn)位，一直到最后。

在編程語(yǔ)言中同樣也是模擬從右向左逐位相加的過(guò)程，不過(guò)在具體實(shí)現(xiàn)上需要注意一些細(xì)節(jié)。

1、枚舉字符串將其轉(zhuǎn)換成char[]提高效率

2、從右往左進(jìn)行計(jì)算，可以將結(jié)果放到一個(gè)數(shù)組中最后組成字符串，也可以使用StringBuider拼接，拼接的時(shí)候最后要逆置一下順序。

3、余數(shù)每次疊加過(guò)需要清零，兩數(shù)相加如果大于等于10即有余數(shù)，添加到結(jié)果中該位置的數(shù)也應(yīng)該是該數(shù)%10的結(jié)果。

4、計(jì)算完最后還要看看余數(shù)是否為1，如果為1需要將其添加到結(jié)果，例如 "991"+"11"算三個(gè)位置為002但還有一個(gè)余數(shù)需要添加，所以應(yīng)該是1002。

一個(gè)加法流程

當(dāng)然在具體實(shí)現(xiàn)上方法較多，你可以首先就將字符串逆置然后從前往后就可以計(jì)算了。當(dāng)然我這里實(shí)現(xiàn)的是字符串從后向前各個(gè)位對(duì)應(yīng)計(jì)算，然后將結(jié)果順序添加到StringBuilder上。

這題在力扣【415兩數(shù)相加】可以檢驗(yàn)自己代碼，實(shí)現(xiàn)代碼為：

  1. public String addStrings(String num1, String num2) { 
  2. // 公眾號(hào)：bigsai 歡迎你的關(guān)注 
  3.     int len1=num1.length()-1,len2=num2.length()-1; 
  4.     char ch1[]=num1.toCharArray(); 
  5.     char ch2[]=num2.toCharArray(); 
  6.  
  7.     StringBuilder sb=new StringBuilder(); 
  8.     int remainder =0;//計(jì)算余數(shù) 
  9.     while (len1>=0||len2>=0) 
  10.     { 
  11.         int n1=len1>=0?(ch1[len1--]-'0'):0; 
  12.         int n2=len2>=0?(ch2[len2--]-'0'):0; 
  13.         int num=n1+n2+remainder;//求和對(duì)應(yīng)數(shù)字 
  14.         remainder=num/10;//是否進(jìn)位 
  15.         sb.append(num%10);// 添加到結(jié)果字符串中 
  16.     } 
  17.  
  18.     if(remainder>0)//是否還需要進(jìn)位 
  19.     { 
  20.         sb.append(remainder); 
  21.     } 
  22.     //反裝即為結(jié)果 
  23.     return sb.reverse().toString(); 
  24. } 

大數(shù)減法

加法對(duì)應(yīng)的就是減法，有了上面大數(shù)加法的實(shí)現(xiàn)思路，那么我想你在大數(shù)減法也應(yīng)該有點(diǎn)想法，但是減法和加法不同的是減法有位置的區(qū)別，加法需要進(jìn)位而減法需要借位。并且大整正數(shù)減法可能產(chǎn)生正負(fù)也不一定。

兩個(gè)正數(shù)，如果大數(shù)減去小數(shù)，那么一切正常，結(jié)果是一個(gè)正數(shù);但如果小數(shù)減去大數(shù)，那么結(jié)果將是一個(gè)負(fù)數(shù)，并且結(jié)果處理起來(lái)比較麻煩。所以在這里全部轉(zhuǎn)成大-小處理(大-小不存在不能借位的情況)。

減法轉(zhuǎn)成大-小

1、執(zhí)行計(jì)算前首先比較減數(shù)(num1)和被減數(shù)(num2)的大小，如果num1>num2,那么就模擬num1-num2的過(guò)程，如果num1

2、在比較兩個(gè)數(shù)字大小的時(shí)候，因?yàn)槭亲址问?，首先比較兩個(gè)字符串的長(zhǎng)度，長(zhǎng)的那個(gè)更大短的那個(gè)更小，如果兩個(gè)字符串等大，那么就可以通過(guò)字典序從前往后進(jìn)行比較(Java可直接使用compareTo方法)。

3、和加法不同的是，減法前面可能產(chǎn)生若干前綴0，這些0是需要你去掉的，例如"1100"-"1000"計(jì)算得到的結(jié)果為"0100",你就要把前面的0去掉返回"100"。

4、具體實(shí)現(xiàn)的時(shí)候和加法相似，如果使用StringBuilder存儲(chǔ)，需要逆置順序，如果是個(gè)負(fù)數(shù)，前面還要加上'-'.

5、每個(gè)位置正常進(jìn)行減法運(yùn)算，如果值小于0，那么就需要向上借位(+10),那么處理上一位進(jìn)行減法時(shí)候還要將借位的處理一下。

一個(gè)減法大概流程

這題在力扣上沒(méi)有原題，但是可以在小米OJ【大數(shù)相減】上驗(yàn)證自己代碼的正確性，具體實(shí)現(xiàn)的代碼為：

  1. public static boolean compare(String num1,String num2) 
  2. { 
  3.     if(num1.length()<num2.length()) 
  4.         return  false; 
  5.     else if(num1.length()>num2.length()) 
  6.         return true; 
  7.     else 
  8.         return num1.compareTo(num2)>0; 
  9. } 
  10. public static  String subtractString(String num1,String num2) { 
  11.     char sign='+';//正負(fù)號(hào) 
  12.     //讓num1>num2 如果num1<num2 那么結(jié)果就是—(num2-num1)  
  13.     //可以先將num1和num2交換和前面情況統(tǒng)一 
  14.     if(!compare(num1,num2)) 
  15.     { 
  16.         sign='-'; 
  17.         String team = num2; 
  18.         num2 = num1; 
  19.         num1 = team; 
  20.     } 
  21.     int len1=num1.length()-1; 
  22.     int len2=num2.length()-1; 
  23.  
  24.     char ch1[] = num1.toCharArray(); 
  25.     char ch2[] = num2.toCharArray(); 
  26.     StringBuilder sb=new StringBuilder(); 
  27.     int borrow=0;//借位 
  28.     while (len1>=0||len2>=0) 
  29.     { 
  30.         int n1=len1>=0?(ch1[len1--]-'0'):0; 
  31.         int n2=len2>=0?(ch2[len2--]-'0'):0; 
  32.  
  33.         int num=n1-n2-borrow; 
  34.         borrow=0; 
  35.         if(num<0)//需要向前借位 
  36.         { 
  37.             borrow=1; 
  38.             num+=10; 
  39.         } 
  40.         sb.append(num); 
  41.     } 
  42.  
  43.     sb=sb.reverse();//需要先翻轉(zhuǎn) 
  44.     int index = 0;//去掉前面沒(méi)用的’0‘ 
  45.     while (index<sb.length()&&sb.charAt(index) == '0') 
  46.     { 
  47.         index++; 
  48.     } 
  49.     //如果兩個(gè)數(shù)相同 直接返回"0" 
  50.     if(index==sb.length()) 
  51.         return "0"; 
  52.     if(sign=='+')//如果正數(shù)  
  53.         return  sb.substring(index); 
  54.     else  return sign+sb.substring(index);//負(fù)數(shù)需要返回 
  55. } 

大數(shù)乘法

大數(shù)乘法乍一想可能比較復(fù)雜，因?yàn)槌朔ū绕鸺臃赡苓M(jìn)位不光是1，還有兩個(gè)數(shù)各種位置都需要相乘計(jì)算，這時(shí)候就需要我們化繁為簡(jiǎn)了。

多*多考慮起來(lái)可能有些麻煩，但是如果多*一考慮起來(lái)呢?如果是多位乘以一位數(shù)，那么就拿一位的分別乘以多位數(shù)的個(gè)位、十位、百位，在計(jì)算的同時(shí)考慮一下進(jìn)位的情況。

但是也可以先直接用int類型數(shù)組存儲(chǔ)各位的乘積然后從右向左進(jìn)行進(jìn)位，如下圖所示。

先計(jì)算后進(jìn)位

而多*多 也是這個(gè)道理，將不同位乘積先疊加到對(duì)應(yīng)位置上，然后從右向左進(jìn)位，一直到不需要進(jìn)位為止。

一個(gè)乘法流程

你可能會(huì)疑問(wèn)，如果兩個(gè)數(shù)組的長(zhǎng)度分別為a和b這個(gè)數(shù)組到底該開(kāi)多大呢?

  • a+b大小就夠了，怎么分析呢?其中一個(gè)a不變。另一個(gè)b變成最小b+1數(shù)字即十的倍數(shù)，那么這樣在相乘的時(shí)候也不過(guò)是a+b長(zhǎng)度，所以這里a+b長(zhǎng)度就夠了。

這題有力扣對(duì)應(yīng)題可以去試試【43字符串相乘】，具體代碼為：

  1. public String multiply(String num1, String num2) { 
  2.     if("0".equals(num1)||"0".equals(num2))return "0"; 
  3.     char a[]=num1.toCharArray(); 
  4.     char b[]=num2.toCharArray(); 
  5.  
  6.     int value[]=new int[a.length+b.length]; 
  7.  
  8.     for(int i=a.length-1;i>=0;i--) 
  9.     { 
  10.         for(int j=b.length-1;j>=0;j--) 
  11.         { 
  12.             int index=a.length-1-i+b.length-1-j; 
  13.             value[index]+=(a[i]-'0')*(b[j]-'0'); 
  14.         } 
  15.     } 
  16.     for(int i=0;i<value.length-1;i++) 
  17.     { 
  18.         value[i+1]+=value[i]/10; 
  19.         value[i]=value[i]%10; 
  20.     } 
  21.     int index=value.length-1; 
  22.     while(value[index]==0) 
  23.     {index--;} 
  24.     StringBuilder sBuilder=new StringBuilder(); 
  25.     while (index>=0) { 
  26.         sBuilder.append(value[index--]); 
  27.     } 
  28.     return sBuilder.toString(); 
  29. } 

大數(shù)除法

大數(shù)加減乘都搞定了，通過(guò)模擬來(lái)實(shí)現(xiàn)，但是大數(shù)除法也通過(guò)模擬來(lái)實(shí)現(xiàn)?

并不是，對(duì)于大數(shù)a/b，一般最多要求求到其整數(shù)解或者余數(shù)，即a/b=c……d(a,b,c,d均為整);也就是a里面有c個(gè)b，并且還剩下d。核心是先求c是多少，對(duì)于程序來(lái)說(shuō)，可以通過(guò)枚舉啊，將除法變成減法，從a中不斷減d，一直到不能減為止。

除法轉(zhuǎn)成減法運(yùn)算

但是有個(gè)問(wèn)題，如果被除數(shù)a很大很大，可能有居多個(gè)b，那么這樣時(shí)間復(fù)雜度太高了，不可能執(zhí)行那么多次，那么需要怎么樣去優(yōu)化這個(gè)方法呢?

那就要加速尋找次數(shù)，減少這個(gè)減法的次數(shù)了，減法次數(shù)減小的一個(gè)最好方案就是能不能擴(kuò)大除數(shù)b。如果b后面加個(gè)'0'，那么算出來(lái)的結(jié)果就乘以10，減法的次數(shù)變成原來(lái)十分之一。根據(jù)這個(gè)思想我們可以一直每次找到b的最大10的倍數(shù)(小于a)計(jì)算減的次數(shù)再換算成減b的總詞數(shù)，將結(jié)果要以字符串方式保留，后面一直迭代到最后為止,這雖然是一道除法運(yùn)算的題，但是也蘊(yùn)含減法和加法(次數(shù)疊加到結(jié)果中)。

 

計(jì)算思想

當(dāng)然，也有一些人使用二分法來(lái)壓縮尋找可以被減的次數(shù)也是可以的(加法可以迭代數(shù)字實(shí)現(xiàn)二分倍數(shù))，具體實(shí)現(xiàn)的話也不是很困難，但是代碼量可能比較多所以一般的面試筆試不會(huì)讓你現(xiàn)場(chǎng)寫(xiě)的，所以好好掌握前面的減法、減法、乘法的代碼即可。

這部分代碼我也簡(jiǎn)單給一下(其他函數(shù)上面貼過(guò)就不重復(fù)貼啦)：

  1. //假設(shè) num1>num2 
  2. public static String divideString(String num1,String num2) 
  3. { 
  4.     String value="0";//結(jié)果 
  5.     while (compare(num1,num2)) 
  6.     { 
  7.         StringBuilder sbTeam=new StringBuilder(num2);//用這個(gè)往后面不斷加0 和num做減法 
  8.         StringBuilder sbCount=new StringBuilder("1");//次數(shù) 可能很大 
  9.         int subLen=num1.length()-num2.length();//統(tǒng)計(jì)大概要加幾個(gè)零  
  10.         for(int i=0;i<subLen;i++) 
  11.         { 
  12.             sbTeam.append('0'); 
  13.             sbCount.append('0'); 
  14.         } 
  15.         //如果0 加多了 那么要?jiǎng)h一個(gè) 類似"12300" / "23" "12300"比"23000"小 
  16.         //所以要 "2300" 對(duì)應(yīng)比"23"擴(kuò)大 "100"倍數(shù)，每減一次"2300" 則結(jié)果加"100" 
  17.         if(!compare(num1,sbTeam.toString())) 
  18.         { 
  19.             sbTeam=sbTeam.deleteCharAt(sbTeam.length()-1); 
  20.             sbCount=sbCount.deleteCharAt(sbCount.length()-1); 
  21.         } 
  22.         // 一直能減的時(shí)候 
  23.         while (compare(num1,sbTeam.toString())) 
  24.         { 
  25.             num1=subtractString(num1,sbTeam.toString()); 
  26.             value=addStrings(sbCount.toString(),value); 
  27.         } 
  28.     } 
  29.     return  value; 
  30. } 

簡(jiǎn)單測(cè)試了下，正確性還是ok的：

除法測(cè)試

番外篇

除了上面直接的大數(shù)加減乘除，還有一些變形的題目需要我們特殊處理一下，比如可能會(huì)使用鏈表等存儲(chǔ)處理，下面分享兩道題。

兩數(shù)相加(力扣02)

題目描述：

給你兩個(gè) 非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

提示：

  • 每個(gè)鏈表中的節(jié)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
  • 0 <= Node.val <= 9
  • 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

本題其實(shí)就是用一個(gè)鏈表存儲(chǔ)一個(gè)數(shù)字(逆序存儲(chǔ))，你需要給它計(jì)算出結(jié)果后在 逆序 存儲(chǔ)到一個(gè)鏈表中返回。

所謂加法的運(yùn)算規(guī)則：從兩個(gè)數(shù)的最低位進(jìn)行計(jì)算，進(jìn)行到下一位的時(shí)候需要考慮進(jìn)位問(wèn)題。一直到最后，而本題所給的鏈表剛好可以用來(lái)直接計(jì)算，因?yàn)殒湵眍^都是數(shù)字最低位可以直接相加，然后一直遍歷到結(jié)束。可以用一個(gè)常數(shù)表示進(jìn)位。

運(yùn)算邏輯

在具體實(shí)現(xiàn)(鏈表)的時(shí)候：

  • 創(chuàng)建新的鏈表，每次將計(jì)算的數(shù)值插入到鏈表尾部即可。
  • 需要準(zhǔn)確表示進(jìn)位，并且最后要考慮以下進(jìn)位
  • 妥善返回正確節(jié)點(diǎn)，可以用一個(gè)頭節(jié)點(diǎn)用來(lái)使得所有節(jié)點(diǎn)都正常操作，而不需要特殊判斷。

通過(guò)代碼第一次比較啰嗦的寫(xiě)法：

當(dāng)然，如果你遍歷鏈表把各個(gè)數(shù)字取出來(lái)，使用字符串、數(shù)字轉(zhuǎn)換然后相加得到一個(gè)數(shù)字，最后在轉(zhuǎn)成字符串、鏈表的理論可以，可以自行實(shí)現(xiàn)。

優(yōu)化后的代碼為：

  1. //更簡(jiǎn)潔的寫(xiě)法 
  2. ublic ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
  3.  ListNode node=new ListNode(0); 
  4.  ListNode team=node; 
  5.  int jin=0;//進(jìn)位 
  6.  while(l1!=null||l2!=null) 
  7.  { 
  8.    int num=jin; 
  9.    if(l1!=null) 
  10.    { 
  11.      num+=l1.val;l1=l1.next; 
  12.    } 
  13.    if(l2!=null) 
  14.    { 
  15.      num+=l2.val;l2=l2.next; 
  16.    } 
  17.    jin=num/10; 
  18.    num%=10; 
  19.    team.next=new ListNode(num); 
  20.    team=team.next; 
  21.  
  22.  } 
  23.  if(jin!=0)team.next=new ListNode(jin); 
  24.  return node.next; 

兩數(shù)相加2(力扣445)

題目描述：

給你兩個(gè) 非空 鏈表來(lái)代表兩個(gè)非負(fù)整數(shù)。數(shù)字最高位位于鏈表開(kāi)始位置。它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)一位數(shù)字。將這兩數(shù)相加會(huì)返回一個(gè)新的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開(kāi)頭。

進(jìn)階：如果輸入鏈表不能修改該如何處理?換句話說(shuō)，你不能對(duì)列表中的節(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)。

示例：

輸入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 8 -> 0 -> 7

本題的話和上面不一樣鏈表不是逆置的，但是加法運(yùn)算其實(shí)需要從最后面對(duì)齊開(kāi)始，也就是理論上應(yīng)該從鏈表尾部開(kāi)始向前，但是這是個(gè)單鏈表，這樣運(yùn)算的話時(shí)間復(fù)雜度太高，所以我們要用空間換時(shí)間：用棧來(lái)解決。

將鏈表的節(jié)點(diǎn)依次放到兩個(gè)棧中，然后兩個(gè)棧同時(shí)取數(shù)計(jì)算。但是待返回的是個(gè)鏈表，所以采取頭插法即可(如果不頭插最后反轉(zhuǎn)也可)，具體流程可以參考如下圖：

邏輯

實(shí)現(xiàn)代碼為：

  1. //更簡(jiǎn)潔的寫(xiě)法 
  2. ublic ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
  3.  ListNode node=new ListNode(0); 
  4.  ListNode team=node; 
  5.  int jin=0;//進(jìn)位 
  6.  while(l1!=null||l2!=null) 
  7.  { 
  8.    int num=jin; 
  9.    if(l1!=null) 
  10.    { 
  11.      num+=l1.val;l1=l1.next; 
  12.    } 
  13.    if(l2!=null) 
  14.    { 
  15.      num+=l2.val;l2=l2.next; 
  16.    } 
  17.    jin=num/10; 
  18.    num%=10; 
  19.    team.next=new ListNode(num); 
  20.    team=team.next; 
  21.  
  22.  } 
  23.  if(jin!=0)team.next=new ListNode(jin); 
  24.  return node.next; 

結(jié)語(yǔ)

 

到這里，大數(shù)的加減乘除基本都講解完啦，不知道你有沒(méi)有收獲，因?yàn)檫@里的大數(shù)都是用字符串的方式存儲(chǔ)和處理，遇到的最多，但是也可能遇到一些鏈表、數(shù)組等其他形式存儲(chǔ)的需要處理，但是整體的思想都是一樣的。

 

責(zé)任編輯：武曉燕 來(lái)源： bigsai
Java內(nèi)存模型
相關(guān)推薦

2021-04-02 06:17:10

大數(shù)加減乘除數(shù)據(jù)結(jié)構(gòu)算法

2021-08-31 07:02:20

Diff算法DOM

2021-10-29 22:49:57

JavaScript開(kāi)發(fā)精度

2020-05-13 09:14:16

哈希表數(shù)據(jù)結(jié)構(gòu)

2019-09-23 10:51:14

JavaJava虛擬機(jī)Linux

2020-12-07 06:19:50

監(jiān)控前端用戶

2021-07-08 10:08:03

DvaJS前端Dva

2021-08-13 05:50:01

ContainerdDockerKubernetes

2024-01-09 08:24:47

JMM核心線程

2021-10-25 16:01:01

Linux設(shè)備樹(shù)字符串

2021-03-28 18:40:02

LinuxWindowsJava

2021-06-30 08:45:02

內(nèi)存管理面試

2022-06-07 10:13:22

前端沙箱對(duì)象

2020-03-18 14:00:47

MySQL分區(qū)數(shù)據(jù)庫(kù)

2023-10-27 08:15:45

2020-10-29 08:55:04

微服務(wù)

2021-10-06 20:23:08

Linux共享內(nèi)存

2023-12-15 09:45:21

阻塞接口

2023-12-12 07:31:51

Executors工具開(kāi)發(fā)者

2024-05-13 10:45:25

中介模式面向?qū)ο?/a>數(shù)量
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)