ການແກ້ໄຂບັນຫາ Leetcode ແບບເຊືອກຫລາຍໆຄູນ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ ByteDance Expedia ເຟສບຸກ ກູໂກ Houzz ວຽກຄະນິດສາດ Microsoft Oracle Square Twitter Uber Zillow
ຄະນິດສາດ string

ບັນຫາວິທີແກ້ໄຂບັນຫາແບບໃຊ້ເຊືອກແບບຄູນຫຼາຍຂໍໃຫ້ພວກເຮົາຄູນສອງເຊືອກເຊິ່ງຖືກມອບໃຫ້ພວກເຮົາເປັນວັດສະດຸປ້ອນ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ພິມຫລືສົ່ງຄືນຜົນໄດ້ຮັບຈາກການຄູນກັບການ ທຳ ງານຂອງຜູ້ໂທ. ສະນັ້ນເພື່ອໃຫ້ມັນໃສ່ສອງສາຍຢ່າງເປັນທາງການ, ຊອກຫາຜະລິດຕະພັນຂອງສາຍເຊືອກທີ່ໃຫ້. ເຫຼົ່ານີ້ 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"

ຄຳ ອະທິບາຍ: ດຽວນີ້, ໃນຕົວຢ່າງນີ້, ພວກເຮົາໄດ້ຮັບສອງເສັ້ນທີ່ຖືກຄູນໃຫ້ສາຍໃຫຍ່ເປັນຜົນຜະລິດທີ່ບໍ່ສາມາດບັນທຶກເປັນປະເພດຂໍ້ມູນຕົວເລກໄດ້. ດັ່ງນັ້ນ, ຕົວຢ່າງນີ້ແມ່ນ ໜຶ່ງ ໃນ ຈຳ ນວນ ໜ້ອຍ ທີ່ສູດການຄິດໄລ່ຂອງພວກເຮົາຄວນຈະສາມາດຈັດການກັບ.

ວິທີການໃຊ້ ກຳ ລັງແຮງງານ ສຳ ລັບວິທີແກ້ໄຂບັນຫາ Leetcode

ບັນຫາການແກ້ໄຂບັນຫາແບບໃຊ້ເຊືອກ Leipcode ພຽງແຕ່ຂໍໃຫ້ພວກເຮົາຄູນສອງເຊືອກທີ່ໃຫ້. ສະນັ້ນ, ເປັນຫຍັງພວກເຮົາຈຶ່ງບໍ່ເຮັດແບບນັ້ນ? ດີ, ມັນເປັນເລື່ອງຍາກທີ່ຈະປະຕິບັດມັນຢ່າງສໍາເລັດຜົນ. ແຕ່, ຖ້າທ່ານຈື່ໄດ້ວ່າພວກເຮົາເຄີຍໃຊ້ເລກສອງຕົວເລກແນວໃດພວກເຮົາສາມາດໃຊ້ເທັກນິກດຽວກັນໄດ້ທີ່ນີ້.

ສະນັ້ນ, ໃນວິທີການດັ່ງກ່າວ, ພວກເຮົາຈະຂ້າມຜ່ານ ໜຶ່ງ ເສັ້ນສາຍທີ່ໄດ້ຮັບຈາກຂວາຫາຊ້າຍ. ເມື່ອພວກເຮົາຢູ່ໃນດັດສະນີຫລືຕົວລະຄອນ, ພວກເຮົາຄູນທັງ ໝົດ ຂອງສາຍອື່ນໆດ້ວຍຕົວລະຄອນປະຈຸບັນນີ້. ເມື່ອພວກເຮົາເຮັດກັບການຄູນຂອງພວກເຮົາແລ້ວ, ພວກເຮົາເພີ່ມເລກສູນຢູ່ໃນຕອນທ້າຍຂອງມັນ. ຈໍານວນຂອງສູນທີ່ຈະຖືກເພີ່ມເທົ່າກັບຕໍາ ແໜ່ງ ຂອງຕົວລະຄອນປະຈຸບັນຢູ່ໃນສາຍຂອງມັນຕັ້ງແຕ່ຕອນສຸດທ້າຍ - 1. ເມື່ອພວກເຮົາເຮັດກັບການເພີ່ມເລກສູນ, ພວກເຮົາຈະເພີ່ມສາຍນີ້ເຂົ້າໄປໃນຜົນ. ດັ່ງນັ້ນ, ດັ່ງທີ່ພວກເຮົາໄດ້ຍ້າຍຈາກຂວາຫາຊ້າຍຂອງສາຍ ທຳ ອິດ, ສາຍສະຕິງທີ່ມີຜົນໄດ້ຮັບເກັບ ຄຳ ຕອບ.

ລະຫັດ Brute Force

ລະຫັດ 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

ລະຫັດ Java ສຳ ລັບວິທີແກ້ໄຂບັນຫາ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (N * M), ບ່ອນທີ່ N ແມ່ນຂະ ໜາດ ຂອງສາຍ ທຳ ອິດແລະ M ແມ່ນຂະ ໜາດ ຂອງສາຍທີສອງ.

ຄວາມສັບສົນໃນອະວະກາດ

O (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

ລະຫັດ Java ສຳ ລັບການແກ້ໄຂບັນຫາ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (N * M), ເຖິງແມ່ນວ່າຄວາມສັບສົນຈະເທົ່າກັບວິທີການໃຊ້ ກຳ ລັງແຮງ, ການ ກຳ ຈັດຄ່າໃຊ້ຈ່າຍເກີນຂອບເຂດຈະຊ່ວຍໃຫ້ການປະຕິບັດງານແຂງແຮງຂື້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N + M), ເພາະວ່າຂະ ໜາດ ຂອງສາຍທີ່ໄດ້ຮັບແມ່ນ N + M, ເຊິ່ງ N ແມ່ນຂະ ໜາດ ຂອງສາຍ ທຳ ອິດ, ແລະ M ແມ່ນຂະ ໜາດ ຂອງສາຍທີສອງ.