Πολλαπλή λύση Leetcode Strings


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα μήλο ByteDance Expedia Facebook Google Houzz Μαθηματικά Microsoft μαντείο Πλατεία Twitter Uber Zillow
μαθηματικά κορδόνι

Το πρόβλημα 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"

Επεξήγηση: Τώρα, σε αυτό το παράδειγμα, μας δίνονται δύο χορδές που πολλαπλασιάζονται για να δώσουν μια μεγάλη συμβολοσειρά ως έξοδο που δεν θα μπορούσε να είχε αποθηκευτεί σε έναν αριθμητικό τύπο δεδομένων. Έτσι, αυτό το παράδειγμα είναι ένα από τα λίγα με τα οποία ο αλγόριθμός μας πρέπει να μπορεί να αντιμετωπίσει.

Προσέγγιση Brute Force για λύση πολλαπλών χορδών Leetcode

Το πρόβλημα Multiply Strings Leetcode Solution απλώς μας ζήτησε να πολλαπλασιάσουμε δύο δεδομένες χορδές. Λοιπόν, γιατί δεν το κάνουμε ακριβώς αυτό; Λοιπόν, είναι λίγο δύσκολο να το εφαρμόσετε με επιτυχία. Αλλά, αν θυμάστε πώς πολλαπλασιάσαμε δύο αριθμούς, μπορούμε εύκολα να χρησιμοποιήσουμε την ίδια τεχνική εδώ.

Έτσι, σε αυτήν την προσέγγιση, θα διασχίσουμε μια από τις δεδομένες χορδές από δεξιά προς αριστερά. Όταν είμαστε σε ευρετήριο ή χαρακτήρα, πολλαπλασιάζουμε ολόκληρη την άλλη συμβολοσειρά με αυτόν τον τρέχοντα χαρακτήρα. Μόλις τελειώσουμε με τον πολλαπλασιασμό μας, προσθέτουμε μηδενικά στο τέλος του. Ο αριθμός μηδενικών που πρόκειται να προστεθεί ισούται με τη θέση του τρέχοντος χαρακτήρα στη συμβολοσειρά του από το τέλος - 1. Μόλις τελειώσουμε με την προσθήκη μηδενικών, προσθέτουμε αυτήν τη συμβολοσειρά στο αποτέλεσμα. Έτσι, καθώς έχουμε διασχίσει από δεξιά προς τα αριστερά της πρώτης συμβολοσειράς, η προκύπτουσα συμβολοσειρά αποθηκεύει την απάντηση.

Κωδικός Brute Force

Κωδικός C ++ για το Multiply Strings Leetcode Solution

#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 Multiply Strings

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), όπου το Ν είναι το μέγεθος της πρώτης συμβολοσειράς και το Μ είναι το μέγεθος της δεύτερης συμβολοσειράς.

Διαστημική πολυπλοκότητα

O (N + M), αφού αποθηκεύσαμε το αποτέλεσμα σε μια ξεχωριστή συμβολοσειρά που μπορεί να έχει μέγεθος N + M. Έτσι, η διαστημική πολυπλοκότητα είναι γραμμική.

Βελτιστοποιημένη προσέγγιση για λύσεις πολλαπλών χορδών Leetcode

Η βελτιστοποιημένη προσέγγιση είναι λίγο δύσκολο να παρατηρηθεί στο πρώτο βήμα. Η βελτιστοποιημένη προσέγγιση έχει επίσης την ίδια χρονική πολυπλοκότητα με την παραπάνω προσέγγιση ωμής δύναμης αλλά αφαιρεί το γενικό κόστος της αντιστροφής της συμβολοσειράς και της προσθήκης κάθε ενδιάμεσης προκύπτουσας συμβολοσειράς στην απάντηση. Στη βελτιστοποιημένη προσέγγιση, πολλαπλασιάζουμε κάθε ένα από τα ψηφία και των δύο χορδών. Έτσι, θεωρούμε κάθε ζεύγος δεικτών, ένα ευρετήριο από την πρώτη συμβολοσειρά και το άλλο από τη δεύτερη συμβολοσειρά. Η ιδέα είναι ότι εάν οι δείκτες είναι i, j στην πρώτη και δεύτερη συμβολοσειρά αντίστοιχα, επιτυγχάνουν τους δείκτες i + j, i + j + 1 στην προκύπτουσα συμβολοσειρά. Έτσι, χρησιμοποιώντας αυτό το γεγονός, μπορούμε να αφαιρέσουμε τα γενικά έξοδα που χάθηκαν κατά την προσθήκη των ενδιάμεσων χορδών, την προσθήκη μηδενικών, την αντιστροφή των ενδιάμεσων χορδών που επιταχύνουν δραστικά τη λύση. Κοιτάζοντας την παρακάτω εικόνα θα γίνει καλύτερα κατανοητό.

Πολλαπλή λύση Leetcode Strings

Βελτιστοποιημένος κωδικός

Κωδικός C ++ για το Multiply Strings Leetcode Solution

#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 Code for Multiply Strings Leetcode Solution

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), παρόλο που η πολυπλοκότητα είναι ίδια με τη μέθοδο brute force, η αφαίρεση των γενικών εξόδων βελτιώνει δραστικά την απόδοση.

Διαστημική πολυπλοκότητα

O (N + M), επειδή το μέγεθος της προκύπτουσας συμβολοσειράς είναι N + M, όπου N είναι το μέγεθος της πρώτης συμβολοσειράς και το M είναι το μέγεθος της δεύτερης συμβολοσειράς.