رشته ها را با حل راه حل کد ضرب کنید


سطح دشواری متوسط
اغلب در آمازون سیب ByteDance Expedia فیس بوک گوگل Houzz Mathworks مایکروسافت وحی مربع توییتر حال بارگذاری Zillow
ریاضی رشته

مسئله Multiply Strings راه حل Leetcode از ما می خواهد دو رشته را که به عنوان ورودی به ما داده شده ضرب کنیم. ما باید این نتیجه ضرب را به عملکرد فراخواننده چاپ یا برگردانیم. بنابراین برای قرار دادن صحیح تر آن با دو رشته ، محصول رشته های داده شده را پیدا کنید. اینها رشته های می تواند رقم های زیادی داشته باشد. بنابراین نباید سعی کرد رشته های داده شده را به اعداد صحیح تبدیل کرد و سپس از ضرب ساده استفاده کرد. برای درک بهتر ، به چند مثال نگاهی می اندازیم.

مثال ها

First String: "2"
Second String: "3"
Resultant String: "6"

توضیح: از آنجا که هر دو رشته فقط یک رقم دارند. ما می توانیم بررسی کنیم که خروجی باید 6 باشد و این مورد است.

First String: "123"
Second String: "456"
Resultant String: "56088"

توضیح: در این مثال ، دو رشته برای ما فراهم شده است که سپس ضرب می شوند تا "56088" داده شود.

First String: "123"
Second String: "0"
Resultant String: "0"

توضیح: در اینجا ما "000" یا "00" را چاپ نکردیم. درصورتی که نتیجه 0 باشد ، ما مجبور به چاپ یک "0" هستیم.

First String: "123456789"
Second String: "987654321123456789987"
Resultant String: "121932631127876847872042371743"

توضیح: اکنون ، در این مثال ، دو رشته به ما داده شده است که ضرب می شوند تا یک رشته بزرگ به عنوان خروجی ارائه شود که نمی توانست در نوع داده عددی ذخیره شود. بنابراین ، این مثال یکی از معدود مواردی است که الگوریتم ما باید بتواند با آن کنار بیاید.

رویکرد Brute Force برای راه حل کد کد چند رشته

مسئله Multiply Strings Leetcode Solution به سادگی از ما خواست که دو رشته داده شده را ضرب کنیم. بنابراین ، چرا ما فقط این کار را نمی کنیم؟ خوب ، اجرای موفقیت آمیز آن کمی مشکل است. اما ، اگر به یاد بیاورید که چگونه دو عدد را ضرب می کردیم ، می توانیم از همین روش در اینجا به راحتی استفاده کنیم.

بنابراین ، در این روش ، ما یکی از رشته های داده شده را از راست به چپ طی می کنیم. وقتی در یک شاخص یا یک کاراکتر هستیم ، کل رشته دیگر را با این کاراکتر فعلی ضرب می کنیم. پس از پایان کار با ضرب ، صفرها را به انتهای آن اضافه می کنیم. تعداد صفرهایی که باید اضافه شوند برابر است با موقعیت کاراکتر فعلی در رشته آن از انتها - 1 - وقتی کار با افزودن صفر تمام شد ، این رشته را به نتیجه اضافه می کنیم. بنابراین ، همانطور که از راست به چپ اولین رشته عبور کردیم ، رشته حاصل جواب را ذخیره می کند.

Brute Force Code

کد C ++ برای چند راه حل راه حل کد

#include <bits/stdc++.h>
using namespace std;

inline string add_zero(int n){
    string res = "";
    while(n-- > 0)res += "0";
    return res;
}

string add_string(string& a, string& b){
    if(a.size()>b.size())swap(a,b);
    int a_len = a.size(), b_len = b.size();
    string res = "";
    int sum = 0, carry = 0;
    for(int i=0;i<b_len;i++){
        int a_idx = a_len-1-i, b_idx = b_len-1-i;
        sum = carry + (a_idx>=0 ? (a[a_idx]-'0') : 0) + (b[b_idx]-'0');
        carry = sum/10; sum %= 10;
        res += to_string(sum);
    }
    if(carry>0)
        res += to_string(carry);
    reverse(res.begin(), res.end());
    return res;
}

string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0")
        return "0";
    string res = "";
    if(num1.size()>num2.size())swap(num1, num2);
    int num1_len = num1.size(), num2_len = num2.size();
    for(int i=num1_len-1;i>=0;i--){
        int multiplier = num1[i]-'0';
        int sum = 0, carry = 0;
        string cur_res = "";
        for(int j=num2_len-1;j>=0;j--){
            sum = carry + (num2[j]-'0')*multiplier;
            carry = sum/10; sum %= 10;
            cur_res += to_string(sum);
        }
        if(carry>0)
            cur_res += to_string(carry);
        reverse(cur_res.begin(), cur_res.end());
        cur_res += add_zero(num1_len-i-1);
        res = add_string(res, cur_res);
    }
    return res;
}

int main(){
    string num1 = "123";
    string num2 = "456";
    cout<<multiply(num1, num2);
}
56088

کد جاوا برای Multiple Strings Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
     private static String add_zero(int n){
        String res = "";
        while(n-- > 0)res += "0";
        return res;
    }
    
    private static String add_string(String a, String b){
        if(a.length()>b.length()){
            String tmp = a;
            a = b;
            b = tmp;
        }
        int a_len = a.length(), b_len = b.length();
        String res = "";
        int sum = 0, carry = 0;
        for(int i=0;i<b_len;i++){
            int a_idx = a_len-1-i, b_idx = b_len-1-i;
            sum = carry + (a_idx>=0 ? (a.charAt(a_idx)-'0') : 0) + (b.charAt(b_idx)-'0');
            carry = sum/10; sum %= 10;
            res += Integer.toString(sum);
        }
        if(carry>0)
            res += Integer.toString(carry);
        StringBuilder sb = new StringBuilder(res);
        sb.reverse();
        return sb.toString();
    }
    
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        String res = "";
        if(num1.length()>num2.length()){
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        int num1_len = num1.length(), num2_len = num2.length();
        for(int i=num1_len-1;i>=0;i--){
            int multiplier = num1.charAt(i)-'0';
            int sum = 0, carry = 0;
            String cur_res = "";
            for(int j=num2_len-1;j>=0;j--){
                sum = carry + (num2.charAt(j)-'0')*multiplier;
                carry = sum/10; sum %= 10;
                cur_res += Integer.toString(sum);
            }
            if(carry>0)
                cur_res += Integer.toString(carry);
            StringBuilder sb = new StringBuilder(cur_res);
            sb.reverse();
            sb.append(add_zero(num1_len-i-1));
            res = add_string(res, sb.toString());
        }
        return res;
    }
    
    public static void main(String[] args){
    	String num1 = "123";
    	String num2 = "456";
    	System.out.println(multiply(num1, num2));
    }
}
56088

تحلیل پیچیدگی

پیچیدگی زمان

O (N * M) ، جایی که N اندازه رشته اول و M اندازه رشته دوم است.

پیچیدگی فضا

O (N + M) ، از آنجا که ما نتیجه را در یک رشته جداگانه ذخیره کردیم که می تواند اندازه N + M داشته باشد. بنابراین پیچیدگی فضا خطی است.

رویکرد بهینه شده برای راه حل کد کد چند رشته

روش بهینه سازی برای مشاهده در مرحله اول کمی مشکل است. رویکرد بهینه سازی نیز همان پیچیدگی زمانی را دارد که رویکرد نیروی بی رحم فوق است اما هزینه سربار معکوس کردن رشته و افزودن هر رشته نتیجه متوسط ​​به جواب را حذف می کند. در روش بهینه شده ، هر یک از رقم های هر دو رشته را ضرب می کنیم. بنابراین ، هر جفت شاخص را در نظر می گیریم ، یک شاخص از رشته اول و دیگری از رشته دوم. ایده این است که اگر شاخص ها به ترتیب i ، j در رشته اول و دوم باشند ، به شاخص های i + j ، i + j + 1 در رشته حاصل می رسند. بنابراین با استفاده از این واقعیت ، ما می توانیم سربار را که در افزودن رشته های میانی از بین رفته بود ، اضافه کردن صفر ، معکوس کردن رشته های میانی که سرعت را به شدت حل می کند حذف کنیم. مشاهده تصویر زیر باعث درک بهتر آن می شود.

رشته ها را با حل راه حل کد ضرب کنید

کد بهینه شده

کد C ++ برای چند راه حل راه حل کد

#include <bits/stdc++.h>
using namespace std;

string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0")
            return "0";
        if(num1.size()>num2.size())swap(num1, num2);
        int num1_len = num1.size(), num2_len = num2.size();
        int res[num1_len+num2_len];memset(res, 0, sizeof res);
        for(int i=num1_len-1;i>=0;i--){
            for(int j=num2_len-1;j>=0;j--){
                int p1 = i+j, p2 = p1+1;
                int sum = (num1[i]-'0')*(num2[j]-'0') + res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        string output = ""; int idx = -1;
        for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
            idx = i;
        for(int i=idx+1;i<num1_len+num2_len;i++)
            output += to_string(res[i]);
        return output;
    }

int main(){
    string num1 = "123";
    string num2 = "456";
    cout<<multiply(num1, num2);
}
56088

کد جاوا برای چند راه حل راه حل کد

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        if(num1.length()>num2.length()){
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        int num1_len = num1.length(), num2_len = num2.length();
        int res[] = new int[num1_len+num2_len];
        Arrays.fill(res, 0);
        for(int i=num1_len-1;i>=0;i--){
            for(int j=num2_len-1;j>=0;j--){
                int p1 = i+j, p2 = p1+1;
                int sum = (num1.charAt(i)-'0')*(num2.charAt(j)-'0') + res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        String output = ""; int idx = -1;
        for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
            idx = i;
        for(int i=idx+1;i<num1_len+num2_len;i++)
            output += Integer.toString(res[i]);
        return output;
    }
    
    public static void main(String[] args){
    	String num1 = "123";
    	String num2 = "456";
    	System.out.println(multiply(num1, num2));
    }
}
56088

تحلیل پیچیدگی

پیچیدگی زمان

O (N * M) ، حتی اگر پیچیدگی همان روش نیروی بی رحم است ، حذف هزینه های سربار عملکرد را به شدت بهبود می بخشد.

پیچیدگی فضا

O (N + M) ، زیرا اندازه رشته حاصل N + M است ، جایی که N اندازه رشته اول است و M اندازه رشته دوم است.