国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode43 multiply strings

Batkid / 3501人閱讀

摘要:題目要求將兩個形式的數字相乘的結果用的形式返回。不準使用以外的形式來記錄數字。假設,則將結果的十位和個位分別放在數組下標為和的位置上。存儲的位置等同于上一思路。然后再通過一輪遍歷將進位處理一下。

題目要求
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

 1. The length of both num1 and num2 is < 110. 
 2. Both num1 and num2 contains only digits 0-9.
 3. Both num1 and num2 does not contain any
    leading zero. 
 4. You must not use any built-in BigInteger library or
    convert the inputs to integer directly.
    
    

將兩個String形式的數字相乘的結果用String的形式返回。不準使用Int(java)以外的形式來記錄數字。

思路一:隊列

通過隊列存儲每一輪計算的結果。進行下一輪計算的時候,將上一輪的值deque出來加到當前的值上。

    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        
        StringBuilder result = new StringBuilder();
        //使用鏈表的方式實現隊列
        LinkedList queue = new LinkedList();
        int count = 0;
        //將隊尾的0添加到結果值中,并消去結尾的結果值
        if(num1.endsWith("0")){
            for(int i = num1.length() - 1 ; i>=0 ; i--){
                if(num1.charAt(i) == "0"){
                    count++;
                    result.append("0");
                }else{
                    break;
                }
            }
            num1 = num1.substring(0, num1.length()-count);
        }
        
        count = 0;
        if(num2.endsWith("0")){
            for(int i = num2.length() - 1 ; i>=0 ; i--){
                if(num2.charAt(i) == "0"){
                    count++;
                    result.append("0");
                }else{
                    break;
                }
            }
            num2 = num2.substring(0, num2.length()-count);
        }
        
        
        for(int i = num1.length()-1 ; i>=0 ; i--){    
            //乘數的值,如果乘數為0,則直接將上一輪的值添加到結果值
            int number1 = num1.charAt(i) - "0";
            if(number1 == 0){
                result.append(queue.removeFirst());
                //補進位0
                queue.add(0);
                continue;
            }
            int carry = 0;
            for(int j = num2.length()-1 ; j>=0 ; j--){
                //被乘數的值
                int number2 = num2.charAt(j) - "0";
                //第一輪無需考慮上一輪的進位
                int currentVal = number1 * number2 + carry + (i==num1.length()-1?0:queue.removeFirst());
                //如果是這一輪的末尾,直接將值添加到結果值中
                if(j== num2.length()-1){
                    result.append(currentVal % 10);
                }else{
                    queue.add(currentVal % 10);
                }
                carry = currentVal/10;
            }
            queue.add(carry);
            carry = 0;
        }
        while(!queue.isEmpty() && queue.getLast() == 0){
            queue.removeLast();
        }
        //將隊列中的非零開頭的進位添加到結果中
        while(!queue.isEmpty()){
            result.append(queue.removeFirst());
        }
        return result.reverse().toString();
        
    }
思路二:int數組存儲

根據乘法計算的規則,我們可以判斷兩個值計算后應該填到哪一個位置上。假設num1[i]*num2[j],則將結果的十位和個位分別放在數組下標為i+j和i+j+1的位置上。記得計算的時候要加上上一輪的進位。

public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] pos = new int[m + n];
   
    for(int i = m - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - "0") * (num2.charAt(j) - "0"); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];

            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  
    
    StringBuilder sb = new StringBuilder();
    for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
    return sb.length() == 0 ? "0" : sb.toString();
}

思路三:將計算和進位分開

這里將每一位的計算結果都先存儲到當前位置上,不管是否進位。存儲的位置等同于上一思路。然后再通過一輪遍歷將進位處理一下。

    public String multiply(String num1, String num2) {
       if(num1.isEmpty() || num2.isEmpty()) return "0";
        int m = num1.length(), n = num2.length();
        int[] ret = new int[m+n];
        
        for(int i = m-1; i >= 0; i--) {
            int n1 = num1.charAt(i)-"0";
            for(int j = n-1; j>=0; j--) {
                int n2 = num2.charAt(j)-"0";
                int mul = n1*n2;
                ret[i+j+1] += mul;
            }
        }
        
        int carryOver = 0;
        for(int i = ret.length-1; i>=0; i--) {
            ret[i]+=carryOver;
            carryOver = ret[i]/10;
            ret[i]%=10;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int x : ret) {
            if(x == 0 && sb.length()==0) continue;
            sb.append(x);
        }
        return sb.length()==0?"0":sb.toString();
        
    }


想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/70170.html

相關文章

  • leetcode 43 Multiply Strings

    摘要:題目詳情題目要求輸入兩個以字符串形式表示的正整數,要求我們求出它們的乘積,同樣也是字符串形式表示。要求不能直接將字符串轉換為整數進行乘法運算。想法這道題的思路就是將我們平時手算多位數乘法的計算方法,轉換成程序語言。 題目詳情 Given two non-negative integers num1 and num2 represented as strings, return the ...

    cloud 評論0 收藏0
  • 力扣(LeetCode)43

    摘要:示例輸入輸出示例輸入輸出說明和的長度小于。和均不以零開頭,除非是數字本身。舉例說明這兩個數的乘積的長度一定不會超過,分別是字符串的長度。第一輪第二輪至此該數組變為然后再從尾部處理進位。 題目地址:https://leetcode-cn.com/probl...題目描述:給定兩個以字符串形式表示的非負整數 num1 和 num2,返回 num1 和 num2 的乘積,它們的乘積也表示為字...

    itvincent 評論0 收藏0
  • LeetCode43.字符串相乘 JavaScript

    摘要:給定兩個以字符串形式表示的非負整數和,返回和的乘積,它們的乘積也表示為字符串形式。示例輸入輸出示例輸入輸出說明和的長度小于。和均不以零開頭,除非是數字本身。不能使用任何標準庫的大數類型比如或直接將輸入轉換為整數來處理。 給定兩個以字符串形式表示的非負整數 num1 和 num2,返回 num1 和 num2 的乘積,它們的乘積也表示為字符串形式。示例 1: 輸入: num1 = 2, ...

    kk_miles 評論0 收藏0
  • 43. Multiply Strings

    摘要:是最高位代表進位,表示本位。就是本位的乘積加上本位已有的值。進位就是除以的余數本位就是剩下的個位數。 43 Multiply Strings 關鍵詞,進位。 public class Solution { public String multiply(String num1, String num2) { int m = num1.length(), n = n...

    fsmStudy 評論0 收藏0
  • leetcode399. Evaluate Division

    摘要:題目要求已知一些字母之間的關系式,問是否能夠計算出其它字母之間的倍數關系如已知問是否能夠計算出的值。這里的值因為在條件中無法獲知是否等于零,因此也無法計算其真實結果,也需要返回。即代表點指向點的邊的權重為,而點指向點的邊的全中為。 題目要求 Equations are given in the format A / B = k, where A and B are variables ...

    Jensen 評論0 收藏0

發表評論

0條評論

Batkid

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<