Множење низова Леетцоде решење


Ниво тешкоће Средњи
Често питани у амазонка јабука БитеДанце Екпедиа фацебоок гоогле Хоузз Матхворкс мицрософт пророчанство Квадрат твиттер Убер Зиллов
Математика низ

Проблем Множење жица Леетцоде решење тражи да помножимо две жице које су нам дате као улаз. Тај резултат множења морамо исписати или вратити на функцију позиваоца. Дакле, да се формалније изразимо с обзиром на две жице, пронађите производ датих жица. Ове струне може имати много цифара. Дакле, не треба покушавати једноставно претворити дате низове у целе бројеве, а затим користити једноставно множење. Погледајмо неколико примера за боље разумевање.

Примери

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"

Објашњење: Сада смо у овом примеру добили два низа који се множе дајући као излаз велики низ који није могао бити сачуван у нумеричком типу података. Дакле, овај пример је један од ретких са којим би наш алгоритам требало да буде у стању да се носи.

Приступ грубе силе за решење са вишеструким жицама Леетцоде решење

Проблем Множење жица Леетцоде Солутион нас је једноставно замолио да помножимо две задате жице. Па, зашто не бисмо учинили управо то? Па, помало је незгодно успешно га применити. Али, ако се сећате како смо множили два броја, овде можемо лако користити исту технику.

Дакле, у овом приступу ћемо прећи преко једног од задатих низова с десна на лево. Када смо у индексу или знаку, множимо други низ са овим тренутним знаком. Када завршимо са множењем, на његов крај додајемо нуле. Број нула које треба додати једнак је положају тренутног карактера у његовом низу од краја - 1. Када завршимо са додавањем нула, додајемо овај низ резултату. Дакле, као што смо прешли с десна на лево првог низа, резултујући низ чува одговор.

Законик Бруте Форце

Ц ++ код за Мултипли Стрингс Леетцоде Солутион

#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

Јава код за вишеструко низове Леетцоде решење

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

Анализа сложености

Сложеност времена

НА М), где је Н величина првог низа, а М величина другог низа.

Сложеност простора

О (Н + М), пошто смо резултат похранили у засебни низ који може имати величину Н + М. Тако је сложеност простора линеарна.

Оптимизован приступ за решење са вишеструким жицама са Леетцоде-ом

Оптимизирани приступ помало је незгодно уочити у првом потезу. Оптимизирани приступ такође има исту временску сложеност као и горњи приступ грубе силе, али уклања опште трошкове преокретања низа и додавања сваког средњег резултујућег низа у одговор. У оптимизованом приступу множимо сваку цифру обе жице. Дакле, разматрамо сваки пар индекса, један индекс из првог низа, а други из другог низа. Идеја је да ако су индекси и, ј у првом и другом низу, респективно, постижу и + ј, и + ј + 1 индекси у резултујућем низу. Дакле, користећи ову чињеницу, можемо уклонити режијске трошкове који су се изгубили додавањем средњих низова, додавањем нула, преокретањем средњих низова који драстично убрзавају решење. Ако погледате доњу слику, биће боље разумети.

Множење низова Леетцоде решење

Оптимизирани код

Ц ++ код за Мултипли Стрингс Леетцоде Солутион

#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

Анализа сложености

Сложеност времена

НА М), иако је сложеност иста као и метода грубе силе, уклањање режијских трошкова драстично побољшава перформансе.

Сложеност простора

О (Н + М), јер је величина резултујућег низа Н + М, где је Н величина првог низа, а М величина другог низа.