Strings Leetcode Çözümünü Çarpın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma ByteDance Expedia Facebook google Houzz Riyaziyyat microsoft Kahin kvadrat cuqquldamaq Über Zillow
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Riyaziyyat SimBaxılıb 94

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problemi Çarpın Strings Leetcode həlli bizə giriş olaraq verilən iki simli çoxaltmağımızı xahiş edir. Çarpmanın bu nəticəsini zəng edən funksiyasına yazdırmamız və ya qaytarmamız lazımdır. Beləliklə, iki simli daha rəsmi şəkildə qoymaq üçün verilmiş simlərin məhsulunu tapın. Bunlar strings çox rəqəm ola bilər. Beləliklə, verilən sətirləri tam ədədə çevirməyə və sonra sadə vurmadan istifadə etməyə çalışmaq olmaz. Daha yaxşı başa düşmək üçün bir neçə nümunəyə nəzər salaq.

Nümunələr

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

İzahat: Hər iki simli yalnız bir rəqəmdən bəri. Çıxışın 6 olması lazım olduğunu yoxlaya bilərik və vəziyyət belədir.

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

İzahat: Bu nümunədə, eyni zamanda, bizə iki simli verilir, daha sonra çoxaldılaraq “56088” verilir.

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

İzahat: Burada “000” və ya “00” yazmadıq. Nəticə 0 olduqda, tək bir "0" yazdırmalıyıq.

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

İzahat: İndi, bu nümunədə, ədədi bir məlumat tipində qeyd oluna bilməyən böyük bir sətir çıxmaq üçün vurulmuş iki sətir verilir. Beləliklə, bu nümunə alqoritmimizin həll edə biləcəyi az saylardan biridir.

Çarpmaq Strings Leetcode Həlli üçün Gücün Güc Yanaşması

Çarpma Dizələrini Leetcode Solution problemi, verilən iki simli çoxaltmağımızı istədi. Bəs niyə biz bunu etmirik? Onu uğurla həyata keçirmək biraz çətindir. Ancaq iki rəqəmi necə çoxaltdığımızı xatırlasanız, burada eyni texnikanı asanlıqla istifadə edə bilərik.

Beləliklə, bu yanaşmada verilmiş simlərdən birini sağdan sola keçirik. İndeksdə və ya bir simvolda olduğumuz zaman digər simli bu cari xarakter ilə çoxaldırıq. Vurma ilə bitdikdən sonra sonuna sıfır əlavə edirik. Əlavə ediləcək sıfırların sayı cari xarakterin sonundakı simindəki mövqeyinə bərabərdir - 1. Sıfır əlavə etməklə işimizi bitirdikdən sonra nəticəyə əlavə edirik. Beləliklə, ilk simdən sağdan sola keçdiyimiz kimi, nəticələnən simli cavabı saxlayır.

Kobud Güc Kodu

Multiply Strings Leetcode Solution üçün C ++ kodu

#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 üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N * M), burada N birinci telin ölçüsü, M isə ikinci simin ölçüsüdür.

Kosmik Mürəkkəblik

O (N + M), nəticəni N + M ölçüsündə ola bilən ayrı bir sətirdə saxladığımız üçün. Beləliklə kosmik mürəkkəblik doğrudur.

Çarpmaq üçün Strings Leetcode Solution üçün optimal yanaşma

Optimallaşdırılmış yanaşma ilk addımda müşahidə etmək biraz çətindir. Optimize edilmiş yanaşma eyni zamanda yuxarıdakı kobud qüvvə yanaşması ilə eyni vaxtda mürəkkəbliyə malikdir, lakin ipi geri çəkmək və cavab verməyə hər bir aralıq nəticə sətrinin əlavə xərclərini aradan qaldırır. Optimize edilmiş yanaşmada, hər iki simin hər birinin rəqəmlərini çoxalırıq. Beləliklə, hər bir cüt indeksə nəzər yetiririk, biri birinci simdən, digəri ikinci simdən. Fikir budur ki, birinci və ikinci sətirdə göstəricilər müvafiq olaraq i, j olarsa, nəticələnən sətirdə i + j, i + j + 1 indekslərinə çatırlar. Beləliklə, bu həqiqətdən istifadə edərək, aralıq simlərin əlavə edilməsində, sıfırların əlavə edilməsində və həllini kəskin dərəcədə sürətləndirən aralıq simlərin geri çəkilməsində itirilən xərcləri aradan qaldıra bilərik. Aşağıdakı şəkilə baxmaq daha yaxşı başa düşəcəkdir.

Strings Leetcode Çözümünü ÇarpınPin

Optimallaşdırılmış kod

Multiply Strings Leetcode Solution üçün C ++ kodu

#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

Multiply Strings üçün Java Kodu Leetcode Həlli

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N * M), mürəkkəblik kobud güc metodu ilə eyni olmasına baxmayaraq, əlavə xərclərin aradan qaldırılması performansı kəskin şəkildə yaxşılaşdırır.

Kosmik Mürəkkəblik

O (N + M), çünki nəticələnən sətrin ölçüsü N + M, burada N birinci sətrin ölçüsü, M isə ikinci sətrin ölçüsüdür.

Crack Sistemi Dizayn Müsahibələri
Translate »