ሕብረቁምፊዎች Leetcode መፍትሄን ያባዙ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ByteDance Expedia ፌስቡክ google ሁዝ የሂሳብ ስራዎች የ Microsoft በ Oracle አራት ማዕዘን ትዊተር በ Uber Zillow
ሒሳብ ሕብረቁምፊ

ችግሩ ብዙዎችን ያሰፋዋል 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 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

የጃቫ ኮድ ለማባዛት ሕብረቁምፊዎች Leetcode መፍትሔ

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) ፣ የት የመጀመሪያው ገመድ መጠን እና M ደግሞ የሁለተኛው ክር መጠን ነው።

የቦታ ውስብስብነት

ኦ (N + M) ፣ ውጤቱን የ N + M መጠን ሊኖረው በሚችል በተለየ ገመድ ውስጥ ስላከማንነው ፡፡ ስለዚህ የቦታ ውስብስብነት መስመራዊ ነው።

ለማባዛት ሕብረቁምፊዎች Leetcode መፍትሄ የተመቻቸ አቀራረብ

የተመቻቸ አካሄድ በመጀመሪያ ጉዞ ውስጥ ለመታየት ትንሽ አስቸጋሪ ነው ፡፡ የተመቻቸ አቀራረብ እንዲሁ ከላይ ካለው የጭካኔ ኃይል አቀራረብ ጋር ተመሳሳይ ጊዜ ውስብስብነት አለው ነገር ግን የእያንዳንዱን መካከለኛ የውጤት ገመድ ወደ ምላሹ የመመለስ እና የመጨመር የላይኛው ወጪን ያስወግዳል ፡፡ በተመቻቸ አቀራረብ ውስጥ የሁለቱም ሕብረቁምፊዎች እያንዳንዳቸው አሃዞች እናባዛለን። ስለሆነም እያንዳንዱን ጥንድ መረጃ ጠቋሚዎችን እንመለከታለን ፣ አንደኛውን ጠቋሚ ከመጀመሪያው ክር እና ሁለተኛው ደግሞ ከሁለተኛው ሕብረቁምፊ ፡፡ ሀሳቡ መረጃ ጠቋሚዎቹ i ፣ j በአንደኛ እና በሁለተኛ ደረጃ በቅደም ተከተል ከሆነ በውጤቱ ሕብረቁምፊ ውስጥ የ i + j ፣ i + j + 1 ጠቋሚዎችን ያገኛሉ ፡፡ ስለዚህ ይህንን እውነታ በመጠቀም የመሃከለኛውን ሕብረቁምፊዎች በመጨመር ፣ ዜሮዎችን በመጨመር ፣ መፍትሄውን በከፍተኛ ሁኔታ የሚያፋጥኑ መካከለኛ ሕብረቁምፊዎችን በመቀየር የጠፋውን አናት ማስወገድ እንችላለን ፡፡ ከዚህ በታች ያለውን ምስል መመልከቱ በተሻለ ለመረዳት ያደርገዋል ፡፡

ሕብረቁምፊዎች Leetcode መፍትሄን ያባዙ

የተመቻቸ ኮድ

የ 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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N * M) ፣ ምንም እንኳን ውስብስብነቱ እንደ የጭካኔ ኃይል ዘዴ ተመሳሳይ ቢሆንም ፣ የራስጌ ወጪዎችን ማስወገድ አፈፃፀሙን በእጅጉ ያሻሽላል።

የቦታ ውስብስብነት

ኦ (N + M) ፣ ምክንያቱም የውጤቱ ሕብረቁምፊ መጠን N + M ነው ፣ የት ኤን የመጀመሪያው ገመድ መጠን ነው ፣ እና M ደግሞ የሁለተኛው ሕብረቁምፊ መጠን ነው።