Множанне радкоў, рашэнне Leetcode


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык ByteDance Expedia facebook Google Houzz Матэматыка Microsoft Аракул Плошча Twitter Uber Zillow
Матэматыка Радок

Задача Памнажэнне радкоў Леткод просіць нас памножыць дзве радкі, якія даюцца нам у якасці ўваходных дадзеных. Мы павінны надрукаваць або вярнуць гэты вынік множання ў функцыю выклікае. Такім чынам, каб фармальна сказаць, што дадзены дзве радкі, знайдзіце здабытак дадзеных радкоў. Гэтыя радкі можа мець шмат лічбаў. Такім чынам, не трэба спрабаваць проста пераўтварыць дадзеныя радкі ў цэлыя лікі, а потым выкарыстоўваць простае множанне. Давайце паглядзім некалькі прыкладаў для лепшага разумення.

Прыкладаў

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"

Тлумачэнне: Цяпер, у гэтым прыкладзе, нам дадзены дзве радкі, якія перамнажаюцца, каб у выніку атрымалася вялікая радок, якая не магла быць захавана ў лікавым тыпе дадзеных. Такім чынам, гэты прыклад - адзін з нямногіх, з якім наш алгарытм павінен мець справу.

Падыход грубай сілы да развязання множнага радка Leetcode

Праблема "Множанне радкоў", рашэнне Leetcode проста папрасіла нас памножыць дзве дадзеныя радкі. Дык чаму б нам не зрабіць гэта? Ну, гэта крыху складана паспяхова яе рэалізаваць. Але, калі вы памятаеце, як мы прымнажалі два лікі, мы можам лёгка выкарыстаць тую ж тэхніку.

Такім чынам, пры гэтым падыходзе мы пройдзем па адной з дадзеных радкоў справа налева. Калі мы знаходзімся ў індэксе альбо сімвале, мы памнажаем цэлую астатнюю радок з гэтым бягучым сімвалам. Пасля таго, як мы скончым з нашым множаннем, мы дадаем нулі ў яго канец. Колькасць нулёў, якія трэба дадаць, роўна становішчу бягучага сімвала ў яго радку з канца - 1. Пасля таго, як мы скончым з даданнем нулёў, мы дадамо гэты радок да выніку Такім чынам, як мы праходзілі справа налева па першай радку, выніковая радок захоўвае адказ.

Кодэкс грубай сілы

Код C ++ для рашэння Leetcode Multiply Strings

#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

Java-код для множнага радка 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. Такім чынам, складанасць прасторы лінейная.

Аптымізаваны падыход да рашэння Leetcode для множання радкоў

Аптымізаваны падыход трохі складана назіраць з першага ж шляху. Аптымізаваны падыход таксама мае такую ​​ж складанасць у часе, як і вышэйапісаны падыход грубай сілы, але здымае накладныя выдаткі на рэверс радка і даданне кожнай прамежкавай выніковай радка да адказу. Пры аптымізаваным падыходзе мы памнажаем кожную з лічбаў абедзвюх радкоў. Такім чынам, мы разглядаем кожную пару індэксаў, адзін індэкс з першага радка, а другі з другога радка. Ідэя заключаецца ў тым, што калі індэксы i, j у першай і другой радках адпаведна, яны атрымліваюць i + j, i + j + 1 індэксы ў выніковай радку. Такім чынам, выкарыстоўваючы гэты факт, мы можам выдаліць накладныя выдаткі, якія губляліся пры даданні прамежкавых радкоў, дадаўшы нулі, адмяняючы прамежкавыя радкі, якія рэзка паскараюць рашэнне. Гледзячы на ​​малюнак ніжэй, яго лепш зразумець.

Множанне радкоў, рашэнне Leetcode

Аптымізаваны код

Код C ++ для рашэння Leetcode Multiply Strings

#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

Java-код для множнага радка Leetcode Solution

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 - памер другой радка.