Мултиплицирајте низи Решение за лек код  


Ниво на тешкотија Медиум
Често прашувано во Амазон Јаболко ByteDance Expedia Facebook Google Houzz Математички дела Мајкрософт Oracle Плоштад Twitter Uber Zillow
алгоритми кодирање интервју интервју подготви LeetCode LeetCodeSolutions Математика Стринг

Проблемот 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"

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

Видете исто така
Конструирајте го решението за правоаголник на леткод

Пристап на брутална сила за решение на леткод за повеќекратни жици  

Проблемот Multiply Strings Leetcode Solution едноставно побара од нас да размножиме две дадени жици. Па, зошто да не го сториме токму тоа? Па, малку е незгодно успешно да се спроведе. Но, ако се сетите како порано множевме два броја, овде можеме лесно да ја користиме истата техника.

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

Кодекс на брутална сила

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

Јава код за решение за множење на жици Leetcode

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

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

Временска комплексност

О (Н * М), каде што 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

Java-код за решение за Leetcode за мултиплицирани низи

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

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

Временска комплексност

О (Н * М), иако комплексноста е иста како и методот на брутална сила, отстранувањето на режиските трошоци драстично ги подобрува перформансите.

Видете исто така
K'th Најголемиот елемент во BST со користење на постојан дополнителен простор

Комплексноста на просторот

О (Н + М), бидејќи големината на добиената низа е N + M, каде што N е големината на првата низа, а M е големината на втората низа.