გაამრავლეთ სიმები Leetcode Solution  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Apple ByteDance Expedia Facebook Google Houzz მათემატიკის სამუშაოები microsoft Oracle Square Twitter Uber Zillow
ალგორითმები კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions მათემატიკის სიმებიანი

პრობლემა გამრავლებული სტრიქონების 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 ამოხსნისთვის  

პრობლემა გამრავლებული სტრიქონების Leetcode Solution- მა უბრალოდ მოგვმართა ორი მოცემული სტრიქონის გამრავლება. რატომ არ მოვიმოქმედეთ ეს? ცოტათი რთულია მისი წარმატებით განხორციელება. თუ გახსოვთ, როგორ ვამრავლებდით ორ რიცხვს, აქ მარტივად შეგვიძლია ერთი და იგივე ტექნიკის გამოყენება.

ამ მიდგომით, ჩვენ გადავკვეთთ მოცემულ სტრიქონს მარჯვნივ მარცხნივ. როდესაც ჩვენ მაჩვენებელთან ან სიმბოლოსთან ვართ, ჩვენ ვამრავლებთ მთელ დანარჩენ სტრიქონს ამ ამჟამინდელი სიმბოლოთი. ჩვენი გამრავლების დასრულებისთანავე, მის ბოლოს ნულებს ვუმატებთ. ნულოვნების რაოდენობა, რომელიც უნდა დაემატოს, ბოლოდან უდრის ამჟამინდელ სიმბოლოს პოზიციას მის სტრიქონში - 1. მას შემდეგ, რაც დავასრულებთ ნულების დამატებას, ამ სტრიქონს დავამატებთ შედეგს. ასე რომ, როგორც პირველი სტრიქონიდან მარჯვნივ მარცხნივ გადავიარეთ, მიღებული სტრიქონი ინახავს პასუხს.

უხეში ძალის კოდექსი

C ++ კოდი გამრავლებული სტრიქონების Leetcode ამოხსნისთვის

#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 არის მეორე სტრიქონის ზომა.

იხილეთ ასევე
იპოვნეთ მაქსიმალური დონის ჯამი Binary Tree- ში

სივრცის სირთულე

O (N + M), ვინაიდან შედეგი ცალკე სტრიქონში შევინახეთ, რომელსაც შეიძლება ჰქონდეს N + M ზომა. ამრიგად, სივრცის სირთულე ხაზოვანია.

ოპტიმიზირებული მიდგომა გამრავლებული სტრიქონების Leetcode ამოხსნისთვის  

ოპტიმიზირებული მიდგომა ცოტა სახიფათოა დასაწყისშივე დასაკვირვებლად. ოპტიმიზირებულ მიდგომას ასევე აქვს იგივე სირთულე, როგორც ზემოხსენებული უხეში ძალის მიდგომა, მაგრამ ხსნის სტრიქონის გადაბრუნების და თითოეული შუალედური შედეგიანი სტრიქონის პასუხის დამატებით ხარჯებს. ოპტიმიზირებულ მიდგომაში, გავამრავლებთ ორივე სიმების თითოეულ ციფრს. ამრიგად, განვიხილავთ ინდექსების თითოეულ წყვილს, ერთი ინდექსი პირველი სტრიქონიდან და მეორე მეორე სტრიქონიდან. იდეა ისაა, რომ თუ ინდექსები არის i, j პირველ და მეორე სტრიქონში, ისინი მიაღწევენ i + j, i + j + 1 ინდექსებს შედეგად სტრიქონში. ამ ფაქტის გამოყენებით, ჩვენ შეგვიძლია ამოვიღოთ ზედნადები, რომელიც იკარგებოდა შუალედური სტრიქონების დამატებაში, ნულების დამატება, შუალედური სტრიქონების უკუქცევა, რაც ხსნარს მკვეთრად აჩქარებს. ქვემოთ მოცემული სურათის დათვალიერება უკეთ გაგება გახდის.

გაამრავლეთ სიმები Leetcode SolutionPin

ოპტიმიზირებული კოდი

C ++ კოდი გამრავლებული სტრიქონების Leetcode ამოხსნისთვის

#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

ჯავის კოდი გამრავლებული სტრიქონების 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 არის მეორე სტრიქონის ზომა.