Leetcode шийдлийг үржүүл


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн БайтДанс Expedia Facebook-ийн Google-ийн Хоузз Математикийн ажил Microsoft- Oracle-ийн Square Twitter Uber Зиллоу
Математик String

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"

Тайлбар: Одоо энэ жишээнд тоон өгөгдлийн төрөлд хадгалах боломжгүй байсан хоёр мөрийг үржүүлж, том мөрийг гаргалтанд өгөх болно. Тиймээс, энэ жишээ нь бидний алгоритмтай харьцах ёстой цөөхөн хүмүүсийн нэг юм.

Leetcode Solution-ийг үржүүлэхэд ашиглах хүчирхийллийн арга

Multiply Strings Leetcode Solution гэсэн асуудал нь өгөгдсөн хоёр мөрийг үржүүлэхийг биднээс ердөө л хүссэн. Тэгэхээр, бид яагаад үүнийг хийхгүй байгаа юм бэ? Үүнийг амжилттай хэрэгжүүлэх нь жаахан төвөгтэй юм. Гэхдээ хэрэв бид хоёр тоог хэрхэн үржүүлж байсныг санаж байвал бид ижил аргыг энд хялбархан ашиглаж болно.

Тиймээс, энэ хандлагын дагуу бид өгөгдсөн мөрнүүдийн аль нэгийг баруунаас зүүн тийш дайран өнгөрөх болно. Бид индекс эсвэл тэмдэгт дээр байхдаа бусад тэмдэгт мөрийг энэ тэмдэгтээр бүхэлд нь үржүүлдэг. Үржүүлэлтээ хийсний дараа бид түүний төгсгөлд тэгийг нэмнэ. Нэмэх ёстой тэгийн тоо нь төгсгөлийн мөрөнд байгаа тэмдэгтийн байрлалтай тэнцүү байна - 1. Тэгийг нэмж дууссаны дараа үр дүнд энэ мөрийг нэмнэ. Тиймээс эхний мөрний баруун талаас зүүн тийш дамжин өнгөрөхөд үр дүнгийн мөр хариултыг хадгалдаг.

Харгис хүчний код

Multiply Strings Leetcode Solution-д зориулсан 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

Multiply Strings Leetcode шийдлийн 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N * M), энд N нь эхний мөрний хэмжээ, M нь хоёр дахь мөрний хэмжээ юм.

Сансрын нарийн төвөгтэй байдал

O (N + M), Бид үр дүнг N + M хэмжээтэй тусдаа мөрөнд хадгалсан тул. Тиймээс сансрын нарийн төвөгтэй байдал нь шугаман юм.

Leetcode шийдлийг үржүүлэх мөрийг оновчтой болгох

Оновчтой арга нь эхний алхам дээр ажиглахад жаахан төвөгтэй байдаг. Оновчтой арга нь дээр дурьдсан харгис хүчний арга барилтай ижил цаг хугацааны нарийн төвөгтэй боловч мөрийг буцааж, хариултанд завсрын үр дүнгийн мөр тус бүрийг нэмэх нэмэлт зардлыг хасдаг. Оновчтой аргад бид хоёр мөрний цифр тус бүрийг үржүүлдэг. Тиймээс, хос индекс бүрийг авч үзье, нэг мөрийг эхний мөрөөс, нөгөө хэсгийг хоёр дахь мөрөөс. Эхний ба хоёр дахь мөрөнд заагдсан индексүүд тус тус i, j байвал үр дүнгийн мөрөнд i + j, i + j + 1 индекст хүрнэ гэсэн санаа юм. Иймээс бид энэхүү баримтыг ашиглан завсрын мөрүүдийг нэмэх, тэг нэмэх, уусмалыг эрс хурдасгах завсрын мөрүүдийг буцаах зэргээр алдагдсан нэмэлт зардлыг арилгаж чадна. Доорх зургийг харахад илүү сайн ойлгогдох болно.

Leetcode шийдлийг үржүүл

Оновчтой код

Multiply Strings Leetcode Solution-д зориулсан 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

Multiply Strings Leetcode шийдлийн Java код

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), хэдийгээр нарийн төвөгтэй байдал нь харгис хүчний аргатай ижил боловч нэмэлт зардлыг хасах нь гүйцэтгэлийг эрс сайжруулдаг.

Сансрын нарийн төвөгтэй байдал

O (N + M), үр дүнгийн мөрийн хэмжээ N + M, энд N нь эхний мөрний хэмжээ, M нь хоёр дахь мөрний хэмжээ юм.