程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode][Java] Multiply Strings

[LeetCode][Java] Multiply Strings

編輯:C++入門知識

[LeetCode][Java] Multiply Strings


題目:

 

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

題意:

給定兩個數字分別用字符串表示出來,返回這兩個數字的乘積,同樣用字符串表示。

注意:數字會非常大而且是非負的。

算法分析:

方法一:

直接乘會溢出,這裡可以利用java中的 BigInteger

方法二:

參考http://pisxw.com/algorithm/Multiply-Strings.html

該題需要知道,mn位數的乘積,最終結果為m+n-1位或是m+n位(進位時)。乘法計算中可以發現,結果中第i位,應該由第一個字符串中的第1位乘以第二個字符串中的第i位,第一個字符串中的第2位乘以第二個字符串中的第i-1位,.......第一個字符串中的第i位乘以第二個字符串中的第1位,最後累加求得,最後我們取個位上的數值,然後剩下的作為進位放到下一輪循環中

AC代碼:

方法一:

 

import java.math.BigInteger;  //Java
public class Solution 
{
   public String multiply(String num1, String num2) 
   {
		BigInteger temp1 = new BigInteger(num1);
		BigInteger temp2 = new BigInteger(num2);
		BigInteger result = temp1.multiply(temp2);
		return result.toString();
    }
}

方法二:

 

 

public class Solution 
{
    public String multiply(String num1, String num2)
    {
        if(num1==null || num2==null)
            return ;
        if(num1.charAt(0)=='0')
            return 0;
        if(num2.charAt(0)=='0')
            return 0;
        int num1length=num1.length();
        int num2length=num2.length();
        //分別對兩個開始字符串進行轉置,便於後面的下標遍歷
        num1=new StringBuilder(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        StringBuilder res=new StringBuilder();
        int jinwei=0;
        //從低位開始計算,最後乘積的位數為m+n-1,如果進位則是m+n
        for(int i=0;i

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved