Жолдар кодының шешімін көбейту  


Күрделілік дәрежесі орта
Жиі кіреді Amazon алма ByteDance Expedia Facebook Google Хуцз Математика Microsoft Oracle шаршы Twitter қиятын Zillow
алгоритмдер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions математика String

Жолдарды көбейту мәселесі 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"

Түсініктеме: Енді осы мысалда бізге екі жолды көбейтеміз, олар үлкен жолды шығарады, оларды сандық деректер түрінде сақтау мүмкін емес. Сонымен, бұл мысал біздің алгоритммен жұмыс істей алатын санаулы адамдардың бірі болып табылады.

Сондай-ақ, қараңыз
Leetcode шешімінің тікбұрышын тұрғызыңыз

Штрих-кодты көбейтуге арналған қателік күші  

Жолдарды көбейту Leetcode Solution мәселесі бізге берілген екі жолды көбейтуді сұрады. Сонымен, біз неге мұны жасамаймыз? Оны сәтті жүзеге асыру өте қиын. Егер сіз екі санды қалай көбейтетінімізді еске түсіретін болсаңыз, онда біз сол техниканы оңай қолдана аламыз.

Сонымен, бұл тәсілде біз берілген жолдардың бірін оңнан солға қарай өтеміз. Біз индексте немесе символда болған кезде, басқа жолдың барлығын осы ағымдағы таңбамен көбейтеміз. Біз көбейтуді аяқтағаннан кейін, оның соңына нөлдерді қосамыз. Қосылатын нөлдердің саны ағымдағы таңбаның соңынан бастап оның жолындағы жағдайына тең болады - 1. Нөлдерді қосуды аяқтағаннан кейін, осы жолды нәтижеге қосамыз. Сонымен, бірінші жолдың оңынан солына қарай жүріп өткеніміздей, нәтижелі жол жауапты сақтайды.

Дөрекі күш кодексі

Multiply Strings Leetcode Solution үшін 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

Multiply Strings Leetcode Solution үшін Java коды

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 Solution  

Оңтайландырылған тәсіл бірінші кезекте байқалуы қиын. Оңтайландырылған тәсілдің күрделілігі жоғарыда көрсетілген дөрекі күш тәсілімен бірдей, бірақ жолды кері қайтаруға және жауапқа әрбір аралық нәтижелі жолдарды қосуға кеткен шығындарды алып тастайды. Оңтайландырылған тәсілде біз екі жолдың цифрларының әрқайсысын көбейтеміз. Осылайша, біз индекстердің әр жұбын қарастырамыз, біреуі бірінші жолдан, ал екіншісі екінші жолдан. Идеясы егер бірінші және екінші жолдарда индекстер сәйкесінше i, j болса, онда олар алынған жолда i + j, i + j + 1 индекстеріне жетеді. Сонымен, осы фактіні қолдана отырып, біз аралық жолдарды қосу, нөлдерді қосу, шешімді күрт тездететін аралық жолдарды кері қайтару кезінде жоғалған шығындарды алып тастай аламыз. Төмендегі суретке қарау түсінуді жақсартады.

Жолдар кодының шешімін көбейтутүйреуіш

Оңтайландырылған код

Multiply Strings Leetcode Solution үшін 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

Күрделілікті талдау

Уақыттың күрделілігі

O (N * M), күрделілік күш қолдану әдісімен бірдей болғанымен, үстеме шығындарды алып тастау өнімділікті айтарлықтай жақсартады.

Сондай-ақ, қараңыз
K'th тұрақты қосымша кеңістікті қолданатын BST-тегі ең үлкен элемент

Ғарыштың күрделілігі

O (N + M), өйткені пайда болатын жолдың өлшемі N + M, мұндағы N - бірінші жолдың өлшемі, ал M - екінші жолдың өлшемі.