高盛Onsite

谁可相欹

#include<iostream>
using namespace std;
2 s$ k- g4 T. Q
4 I  W# C. d. x+ k+ _( j. A' g- _int main()
{
; G6 m( L) \( u; m    int a[]={1,4,7,5,2,3};
4 i9 T  r5 v. u$ c* g    int n=sizeof(a)/sizeof(*a);
% p* g& A0 S' l! m7 r9 q" D# R( Q% j5 a
1 O0 C& A8 d3 s% }( _7 k    int b[]={5,4,5,7,8,9,2};
    int m=sizeof(b)/sizeof(*b);

/ L5 C' V; Y! g$ M    int res[10000]={0};
+ j2 b4 K; e4 A+ |$ T    int carry=0;
& @$ {1 s  ?6 k6 r    int h=0;
" A9 s, @- a  q    for(int i=n-1; i>=0; i--)
* |* G2 v, ]; a( C  g/ x1 V    {
! e; U2 j) b5 E; |# y        int k=b[m-1]*a[i];
1 a; d3 ?# U1 p, c) g5 Y        k+=carry;
4 E  n' L" X, |' D7 [7 O        res[h++]=k%10;
/ u) s- {8 {+ Q        carry=k/10;
    }

    while(carry)
  _3 M, i- |; U' ^% e    {
7 R( R6 V% g# \6 v7 y        res[h++]=carry%10;
        carry=carry/10;
! C* W8 I' t4 o    }


8 G7 |  p% G7 o: d* b/ f( `    int l=1;
    int k;
6 w. B/ f: D& r  b' N    for(int i=m-2; i>=0; i--)
' ]/ h$ o% e& m; r    {
        int carry=0;
        k=l;
0 U( g. l0 T( g$ p4 m" L        int temp[1000]={0};
, j! J& W7 A3 q6 a+ o6 E6 ]' p4 {. V
        for(int j=n-1; j>=0; j--)
" ?  i) y- }! U" U% G        {
! `# g8 }1 f) c& e            int x=b[i]*a[j];
4 J8 [% M2 [8 E            x+=carry;
            carry=x/10;
            temp[k++]=x%10;
5 ^- K9 P* x, s; }2 w        }

        while(carry)
        {
            temp[k++]=carry%10;
; T% J4 |! N) g; ^- _% |" T/ Q; u3 `3 y            carry=carry/10;
        }
/ g9 m& |6 k2 P
        for(int i=0; i<k; i++)
        {
" c# O4 U7 w' T4 `1 i4 y) B            int sum=res[i]+temp[i];
            sum+=carry;
% `9 Q+ m* j1 u$ v6 y            carry=sum/10;
1 S0 y/ O$ A5 t; O            res[i]=sum%10;
        }
2 I, V2 u) @- \9 Y! t        l++;
    }
0 B* o3 r4 f9 `" m$ e( r3 K0 ]- A
    for(int i=k-1; i>=0; i--)
        cout<<res[i]<<" ";
}

Ursula@CA

public static void main(String[] args) {
int[] num1={1,2,3,4,5};
int[] num2={1,2,4,6};
System.out.println(multiply(breakNumbers(num1), breakNumbers(num2)));
int sum=0;
Map<Integer,Integer> multiplyMap = multiply(breakNumbers(num1), breakNumbers(num2));
for (Map.Entry<Integer,Integer> entry : multiplyMap.entrySet()) {
sum +=(entry.getKey()*(Math.pow(10,entry.getValue())));
}
System.out.println(sum);
}

static Map<Integer,Integer> multiply(Map<Integer,Integer> num1,Map<Integer,Integer> num2){
Map<Integer,Integer> multiplyMap=new LinkedHashMap<Integer,Integer>();
for (Map.Entry<Integer,Integer> entry1 : num1.entrySet()) {
for (Map.Entry<Integer,Integer> entry2 : num2.entrySet()) {
multiplyMap.put(entry1.getKey()*entry2.getKey(), entry1.getValue()+entry2.getValue());
}
}
return multiplyMap;
}

static Map<Integer,Integer> breakNumbers(int[] num1){
Map<Integer,Integer> numMap=new LinkedHashMap<Integer,Integer>();
String s="";
int count=0;
for(int i=0;i<num1.length;i++){
count++;
if(count==3 || i==num1.length-1){
s+=num1[i];
numMap.put(Integer.valueOf(s), num1.length-(i+1));
s="";
count=0;
}else{
s+=num1[i];
}

}
return numMap;
}

夏绿蒂

# Reverse an array to change endianness of numbers
+ s0 e0 g! v5 w+ pdef num_array_reverse(num_array):
* y& Q% e& ^- P        left = 0
" t2 Y+ u1 T; k( Z/ h( H        right = len(num_array) - 1;
. h  W7 i. K2 x9 c9 ]' j        while (left < right):
9 |9 [% ~4 C7 x1 X1 Y' i                num_array[left], num_array[right] = num_array[right], num_array[left]
                left += 1
                right -= 1

# U7 w2 I- K7 ?6 Z" r5 Z! H# Multiply two numbers
# Input: Big-endian order
" w/ d! C' b: }# Output: Big-endian order
def multiply(num_a_array, num_b_array):
        # Convert big-endian to little-endian
        num_array_reverse(num_a_array)
8 r4 D; O$ v2 s7 N; x4 [3 R        num_array_reverse(num_b_array)
: C! x  _8 i2 V6 C
3 k. j9 b$ W& V5 J* |9 B6 a        # Initialize the result
$ B$ x' i2 [* M9 ]3 }5 V        num_result_arr = []

        # Multiply
        for i in range(0, len(num_a_array)):
                carry = 0
                j = 0
                while (j < len(num_b_array)):
                        val = num_a_array[i] * num_b_array[j] + carry
                        if (len(num_result_arr) <= i + j):
                                num_result_arr.append(0)
4 d# K$ _& L* @7 ~, ], L                        val += num_result_arr[i + j]
                        carry = val / 10
; ?& V& e; p9 Q" j$ ?4 v& x. p                        val %= 10
                        num_result_arr[i + j] = val
. u2 |% ]5 k% p: u% I' j/ I4 A                        j += 1
5 t" `. U5 X7 I- A& m8 L                if (carry):
/ F( t4 A. Y9 }                        if (len(num_result_arr) <= i + j):
                                num_result_arr.append(carry)
3 L( u1 G3 }- e5 V8 |, g$ T                        else:
# P7 g& x# D4 w/ N' I. W& O                                num_result_arr[i + j] = carry

  a( {% b1 u1 |& J        #  Convert little-endian to big-endian
" K: F' H3 E) s        num_array_reverse(num_a_array)
        num_array_reverse(num_b_array)
8 T8 D2 _. c) b) t4 ^        num_array_reverse(num_result_arr)

        return num_result_arr

def multiply_and_print(num_a_array, num_b_array):
        num_result_array = multiply(num_a_array, num_b_array)
        print("{0} x {1} = {2}".format(num_a_array, num_b_array, num_result_array))
3 i0 a- `. R1 b$ f
def main():
2 H6 \9 F( x+ }        multiply_and_print([1, 2], [1, 0])
        multiply_and_print([5, 3, 6, 2, 8, 0, 2, 8], [3, 5, 2, 3, 2, 1])

# ]; ~, W0 L) F1 e# Jmain()