מולטיפּלי סטרינגס לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן עפּל ביטעדאַנסע עקספּעדיאַ facebook גוגל האָוזז מאַטהוואָרקס מייקראָסאָפֿט אָראַקל קוואַדראַט טוויטטער ובער זיללאָוו
אַלגערידאַמז קאָדירונג אינטערוויו interviewprep LeetCode LeetCodeSolutions מאַט שטריקל

דער פּראָבלעם Multiply Strings לעעטקאָדע לייזונג פרעגט אונדז צו מערן צוויי סטרינגס וואָס זענען געגעבן צו אונדז ווי ינפּוט. מיר זענען פארלאנגט צו דרוקן אָדער צוריקקומען דעם רעזולטאַט פון מאַלטאַפּלייינג צו די רופן פונקציע. אַזוי צו לייגן עס מער פאָרמאַלי צוויי סטרינגס, געפֿינען די פּראָדוקט פון די געגעבן סטרינגס. די סטרינגס קענען האָבן פילע דידזשאַץ. אַזוי איר זאָל נישט פּרובירן צו פשוט גער די געגעבן סטרינגס אין ינטאַדזשערז און נוצן אַ פּשוט קייפל. לאָמיר נעמען אַ ביסל ביישפילן פֿאַר בעסער פארשטאנד.

ביישפילן  

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"

דערקלערונג: איצט, אין דעם בייַשפּיל, מיר באַקומען צוויי סטרינגס וואָס זענען געמערט צו געבן אַ גרויס שטריקל ווי רעזולטאַט וואָס קען נישט האָבן שוין געראטעוועט אין אַ נומעריק דאַטן טיפּ. דער ביישפּיל איז איינער פון די ווייניק וואָס אונדזער אַלגערידאַם זאָל קענען צו האַנדלען מיט.

זע אויך
בויען די רעקטאַנגלע לעעטקאָדע סאַלושאַן

ברוט פאָרס צוגאַנג פֿאַר מולטיפלי סטרינגס לעעטקאָדע סאַלושאַן  

די פּראָבלעם מולטיפּלי סטרינגס לעעטקאָדע סאַלושאַן פשוט געבעטן אונדז צו מערן צוויי געגעבן סטרינגס. אַזוי, וואָס טאָן ניט טאָן מיר טאָן דאָס פּונקט? נו, עס איז אַ ביסל טריקי צו הצלחה ימפּלאַמענטאַד עס. אָבער, אויב איר געדענקען ווי מיר געוויינט צו פאַרמערן צוויי נומערן, מיר קענען לייכט נוצן די זעלבע טעכניק דאָ.

אַזוי, אין דעם צוגאַנג, מיר וועלן פאָרן איבער איינער פון די געגעבן סטרינגס פון רעכט צו לינקס. ווען מיר זענען ביי אַן אינדעקס אָדער אַ כאַראַקטער, מיר מערן גאַנץ די אנדערע שטריקל מיט דעם קראַנט כאַראַקטער. אַמאָל מיר זענען פאַרטיק מיט אונדזער קייפל, מיר לייגן זעראָעס צו דעם סוף. די נומער פון זעראָעס וואָס זענען צוגעלייגט איז גלייַך צו די שטעלע פון ​​דעם קראַנט כאַראַקטער אין די שטריקל פֿון די סוף - 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

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N * M), וווּ N איז די גרייס פון דער ערשטער שטריקל און M די גרייס פון די רגע שטריקל.

זע אויך
געפֿינען די מאַקסימום לעוועל סומע אין ביינערי בוים

ספעיס קאַמפּלעקסיטי

אָ (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

דזשאַוואַ קאָוד פֿאַר קייפל סטרינגס לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N * M), כאָטש די קאַמפּלעקסיטי איז די זעלבע ווי די ברוט קראַפט אופֿן, רימוווינג די אָוווערכעד קאָס ימפּרוווז די פאָרשטעלונג דראַסטיקלי.

זע אויך
דער גרעסטער עלעמענט אין BST מיט קעסיידערדיק עקסטרע פּלאַץ

ספעיס קאַמפּלעקסיטי

אָ (N + M), ווייַל די גרייס פון די ריזאַלטיד שטריקל איז N + M, ווו N איז די גרייס פון דער ערשטער שטריקל, און M איז די גרייס פון די רגע שטריקל.