문자열 Leetcode 솔루션 곱하기

난이도 중급
자주 묻는 질문 아마존 Apple ByteDance Expedia Facebook 구글 Houzz 수학공부 Microsoft 신탁 사각형. Twitter 동네 짱 Zillow
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학 조회수 95

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 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 솔루션을위한 무차별 대입 접근 방식

문제 Multiply Strings Leetcode Solution은 단순히 주어진 두 개의 문자열을 곱하도록 요청했습니다. 그래서 우리는 왜 그렇게하지 않습니까? 글쎄, 성공적으로 구현하는 것은 약간 까다 롭습니다. 그러나 우리가 두 숫자를 곱하는 방법을 기억한다면 여기에서 동일한 기술을 쉽게 사용할 수 있습니다.

따라서이 접근 방식에서는 주어진 문자열 중 하나를 오른쪽에서 왼쪽으로 순회합니다. 인덱스 나 문자에있을 때 다른 문자열 전체에이 현재 문자를 곱합니다. 곱셈이 끝나면 끝에 1을 더합니다. 추가 할 XNUMX의 수는 끝부터 문자열의 현재 문자 위치와 같습니다. XNUMX입니다. XNUMX을 추가 한 후에는이 문자열을 결과에 추가합니다. 따라서 첫 번째 문자열의 오른쪽에서 왼쪽으로 이동 했으므로 결과 문자열은 답을 저장합니다.

무차별 대입 코드

Multiply Strings Leetcode 솔루션을위한 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 크기를 가질 수있는 별도의 문자열에 저장했기 때문입니다. 따라서 공간 복잡성은 선형입니다.

Multiply Strings Leetcode 솔루션을위한 최적화 된 접근 방식

최적화 된 접근 방식은 처음에 관찰하기가 약간 까다 롭습니다. 최적화 된 접근 방식은 위의 무차별 대입 접근 방식과 동일한 시간 복잡도를 갖지만 문자열을 반전하고 각 중간 결과 문자열을 답변에 추가하는 오버 헤드 비용을 제거합니다. 최적화 된 접근 방식에서는 두 문자열의 각 자릿수를 곱합니다. 따라서 우리는 첫 번째 문자열의 인덱스와 두 번째 문자열의 인덱스를 고려합니다. 아이디어는 인덱스가 첫 번째 및 두 번째 문자열에서 각각 i, j이면 결과 문자열에서 i + j, i + j + 1 인덱스를 얻는 것입니다. 따라서이 사실을 사용하여 중간 문자열을 추가하고, XNUMX을 추가하고, 중간 문자열을 반전하여 솔루션 속도를 크게 높일 때 손실되었던 오버 헤드를 제거 할 수 있습니다. 아래 이미지를 보면 더 잘 이해할 수 있습니다.

문자열 Leetcode 솔루션 곱하기

최적화 된 코드

Multiply Strings Leetcode 솔루션을위한 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

다중 문자열 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은 두 번째 문자열의 크기입니다.

균열 시스템 설계 인터뷰
Translate »