မြှောက်ကြိုးများ Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Apple ByteDance Expedia Facebook က Google Houzz သင်္ချာ Microsoft က Oracle က ရင်ပြင် တွစ်တာ Uber Zillow
သင်္ချာ ကြိုး

ပြipနာ Multiply Strings Leetcode ဖြေရှင်းချက်သည်ကျွန်ုပ်တို့အား input အဖြစ်ပေးထားသော string နှစ်ခုကိုမြှောက်ရန်တောင်းဆိုသည်။ ဤရလဒ်ကိုခေါ်ဆိုသူ၏လုပ်ဆောင်မှုသို့မြှောက်ရန်ကျွန်ုပ်တို့ထံသို့ပြန်ပို့ရန်လိုအပ်သည်။ ဒါကြောင့်ပိုပြီးပုံစံအရပေးထားတဲ့ကြိုးနှစ်ချောင်းကိုသုံးဖို့ပေးထားတဲ့ကြိုးရဲ့ထုတ်ကုန်ကိုရှာပါ။ ဤရွေ့ကား ညှို့ အများအပြားဂဏန်းရှိနိုင်ပါသည်။ ဒါကြောင့်ပေးထားတဲ့ strings တွေကိုကိန်းဂဏန်းအဖြစ်ပြောင်းပြီးရိုးရှင်းတဲ့မြှောက်ခြင်းကိုမသုံးသင့်ဘူး။ ပိုမိုကောင်းမွန်သောနားလည်မှုအတွက်ဥပမာအချို့ကိုကြည့်ကြပါစို့။

ဥပမာ

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

ရှင်းလင်းချက် - ကြိုးနှစ်ခုစလုံးမှာဂဏန်းတစ်ခုတည်းပဲရှိတာ။ ကျနော်တို့ output ကို 6 ဖြစ်သင့်ကြောင်းစစ်ဆေးနိုင်ပြီးထိုအမှုဖြစ်ပါတယ်။

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

ရှင်းလင်းချက်။ ။ ဒီဥပမာမှာကျွန်တော်တို့ကို string နှစ်ခုကိုပေးထားတယ်။ အဲဒါက "56088" ကိုမြှောက်ရမယ်။

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

ရှင်းလင်းချက် - ဒီမှာကျွန်တော်တို့ဟာ“ 000” ဒါမှမဟုတ်“ 00” ကိုမပုံနှိပ်ခဲ့ဘူး။ အကယ်၍ ရလဒ် 0 ဖြစ်သည့်အခါကျွန်ုပ်တို့သည်“ 0” တစ်ခုတည်းကိုပုံနှိပ်ရန်လိုအပ်သည်။

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

ရှင်းလင်းချက် - အခု၊ ဒီဥပမာမှာ၊ ကိန်းဂဏန်းအချက်အလက်အမျိုးအစားထဲမှာသိမ်းဆည်းလို့မရနိုင်တဲ့ output ကို string တစ်ခုကြီးကြီးပေးဖို့မြှောက်ထားတဲ့ string နှစ်ခုကိုပေးထားတယ်။ ဒါကြောင့်ဒီဥပမာသည်ကျွန်ုပ်တို့၏ algorithm ကိုကိုင်တွယ်ဖြေရှင်းသင့်သောအနည်းငယ်ထဲမှတစ်ခုဖြစ်သည်။

Multiply Strings Leetcode Solution အတွက် Brute Force ချဉ်းကပ်မှု

ပြipနာ Multiply Strings Leetcode Solution သည်ပေးထားသောညှို့နှစ်ခုကိုတိုးမြှင့်ပေးရန်ကျွန်ုပ်တို့အားရိုးရှင်းစွာတောင်းဆိုခဲ့သည်။ ဒါဆိုငါတို့ဘာကြောင့်မလုပ်နိုင်တာလဲ။ ကောင်းပြီ၊ အဲဒါကိုအောင်မြင်စွာအကောင်အထည်ဖော်ဖို့နည်းနည်းလေးခက်တယ်။ ဒါပေမယ့်၊ ကျွန်တော်တို့ဂဏန်းနှစ်လုံးကိုဘယ်လိုတိုးမြှင့်ခဲ့တယ်ဆိုတာကိုသင်မှတ်မိမယ်ဆိုရင်ဒီနေရာမှာပဲအတူတူနည်းပညာကိုအလွယ်တကူအသုံးပြုနိုင်တယ်။

ဒီတော့ဒီချဉ်းကပ်မှုမှာပေးထားတဲ့ညှို့တစ်ချောင်းကိုညာမှဘယ်ကိုဖြတ်သွားမှာပါ။ ကျွန်ုပ်တို့သည်အညွှန်းတစ်ခု (သို့) ဇာတ်ကောင်တစ်ခုတွင်ရှိနေစဉ်ကျွန်ုပ်တို့သည်အခြား string တစ်ခုလုံးကိုဤလက်ရှိစာလုံးဖြင့်မြှောက်ပါ။ ငါတို့မြှောက်ခြင်းပြုပြီးသည်နှင့်တပြိုင်နက်ကျွန်ုပ်တို့သည်အဆုံးသို့သုညပေါင်းထည့်သည်။ ထပ်ပေါင်းထည့်ရမည့်သုညအရေအတွက်သည်အဆုံးမှ စ၍ လက်ရှိစာလုံး၏တည်နေရာနှင့်ညီမျှသည်။ ၁။ သုညများကိုထည့်ပြီးသည်နှင့်ဤ string ကိုရလဒ်သို့ထည့်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ပထမအကြိမ်၏ဘယ်ဘက်မှညာသို့ဖြတ်သန်းသွားသည်နှင့်အမျှထွက်ပေါ်လာသည့် string သည်အဖြေကိုသိုလှောင်ထားသည်။

Brute Force ကုဒ်

Multiply Strings Leetcode Solution အတွက် C ++ code

#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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N * M)၊ N သည်ပထမ string ၏အရွယ်အစားဖြစ်ပြီး M သည်ဒုတိယ string ၏အရွယ်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (N + M)၊ ရလဒ်ကို N + M အရွယ်အစားရှိနိုင်သောသီးခြား string တစ်ခုတွင်သိမ်းဆည်းပြီးကတည်းက။ ထို့ကြောင့်ရှုပ်ထွေးမှုသည် linear ဖြစ်သည်။

Multiply Strings Leetcode Solution အတွက်အကောင်းဆုံးနည်းလမ်း

အဆိုပါ optimized ချဉ်းကပ်မှုပထမ ဦး ဆုံးအသွား၌စောငျ့ရှောကျဖို့နည်းနည်းလှည်သည်။ အဆိုပါ optimized ချဉ်းကပ်မှုကိုလည်းအထက်ပါ brute အင်အားသုံးချဉ်းကပ်မှုနှင့်အတူတူပင်အချိန်ရှုပ်ထွေးရှိပါတယ်ဒါပေမယ့်အဖြေမှ string ကိုနှင့်တစ် ဦး ချင်းစီအလယ်အလတ်ရလဒ်ထွက် string ကို၏ထို့အပြင်၏ overhead ကုန်ကျစရိတ်ကိုဖယ်ရှားပေးပါသည်။ အကောင်းဆုံးသောချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည်ကြိုးနှစ်ခုလုံး၏ဂဏန်းတစ်ခုစီကိုမြှောက်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်အညွှန်းကိန်းတစ်ခုစီ၊ ပထမ string မှ index တစ်ခုနှင့်ဒုတိယ string တစ်ခုမှတစ်ခုစီကိုစဉ်းစားသည်။ အဆိုပါအယူအဆမှာညွှန်းကိန်းများသည် i, j အသီးသီးပထမနှင့်ဒုတိယစာကြောင်းအသီးသီးဖြစ်ပါက i + j၊ i + j + 1 အညွှန်းများကိုရရှိသည်။ ဒါကြောင့်ဒီအချက်ကိုသုံးပြီး၊ ကြားခံညှို့ဖြည့်ခြင်း၊ သုညပေါင်းခြင်း၊ ဖြေရှင်းချက်ကိုအရှိန်အဟုန်မြှင့်တင်ပေးတဲ့အလယ်အလတ်ညှို့အားများကိုဖယ်ရှားခြင်းအတွက်ဆုံးရှုံးခဲ့ရသော overhead ကိုဖယ်ရှားနိုင်ပါတယ်။ အောက်ဖော်ပြပါပုံကိုကြည့်ခြင်းဖြင့်နားလည်ရန်ပိုကောင်းလိမ့်မည်။

မြှောက်ကြိုးများ Leetcode ဖြေရှင်းချက်

Optimized ကုဒ်

Multiply Strings Leetcode Solution အတွက် C ++ code

#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 Leetcode Solution အတွက် Java Code

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)၊ ရှုပ်ထွေးမှုသည် brute force method နှင့်အတူတူပင်ဖြစ်သော်လည်း overhead ကုန်ကျစရိတ်များကိုဖယ်ရှားခြင်းသည်စွမ်းဆောင်ရည်ကိုသိသိသာသာတိုးတက်စေသည်။

အာကာသရှုပ်ထွေးမှု

အို (N + M)၊ အဘယ်ကြောင့်ဆိုသော်ထွက်ပေါ်လာသည့် string ၏အရွယ်အစားမှာ N + M ဖြစ်သည်။ N သည်ပထမ string ၏အရွယ်ဖြစ်သည်။ M သည်ဒုတိယ string ၏အရွယ်ဖြစ်သည်။