시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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을 추가하고, 중간 문자열을 반전하여 솔루션 속도를 크게 높일 때 손실되었던 오버 헤드를 제거 할 수 있습니다. 아래 이미지를 보면 더 잘 이해할 수 있습니다.
최적화 된 코드
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은 두 번째 문자열의 크기입니다.
