找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: MorningXu
收起左侧

[Goldman Sachs] 高盛Onsite

[复制链接]

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3587
发表于 2-5-2017 02:46 PM | 显示全部楼层

#include<iostream>5 N( {3 u) g; [" `8 ^- ~: |8 r
using namespace std;
2 s$ k- g4 T. Q
4 I  W# C. d. x+ k+ _( j. A' g- _int main()# r( |9 n: U. N) N/ W+ h) e
{
; 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};4 n8 V' ~) r" P" Z
    int m=sizeof(b)/sizeof(*b);, J  a% A( O- @! \, t

/ 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;' C; x, k% [* c' p6 X/ d. v
    }6 ?4 ^" `! [2 g- t# S. p9 H
: M0 C5 o" @* t- t
    while(carry)
  _3 M, i- |; U' ^% e    {
7 R( R6 V% g# \6 v7 y        res[h++]=carry%10;* t1 r) J: ~: i4 y3 {% I( }& \
        carry=carry/10;
! C* W8 I' t4 o    }) O* T  ?/ t  ?( t% @
+ v" P( w. T2 g. E

8 G7 |  p% G7 o: d* b/ f( `    int l=1;) v' ?2 N8 j' F9 j" f0 c) ~; ?% e
    int k;
6 w. B/ f: D& r  b' N    for(int i=m-2; i>=0; i--)
' ]/ h$ o% e& m; r    {& d% r( i  \! H! w
        int carry=0;$ l7 T' V7 q, P: F
        k=l;
0 U( g. l0 T( g$ p4 m" L        int temp[1000]={0};
, j! J& W7 A3 q6 a+ o6 E6 ]' p4 {. V5 q" |/ B/ E' ?4 s! `0 L
        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;4 T5 l1 u6 k1 Z) M% L+ q
            carry=x/10;. O, x+ @1 G: [/ b: E8 j9 s
            temp[k++]=x%10;
5 ^- K9 P* x, s; }2 w        }. M! A, K; {9 B1 I( n8 I  W
- m; [& m% v# y4 r
        while(carry)! ?) Z; g' [! [' t. K
        {% T( M. F9 S( A) S% a( G6 T
            temp[k++]=carry%10;
; T% J4 |! N) g; ^- _% |" T/ Q; u3 `3 y            carry=carry/10;( t: _& a8 S% c. Q9 O; t
        }
/ g9 m& |6 k2 P2 H4 {+ H/ T4 U1 A2 J6 ^3 @5 d3 o
        for(int i=0; i<k; i++)8 z. {( J2 ^0 Z' b7 n9 O) g
        {
" c# O4 U7 w' T4 `1 i4 y) B            int sum=res[i]+temp[i];( Z$ m5 v9 O) U7 M9 g2 p
            sum+=carry;
% `9 Q+ m* j1 u$ v6 y            carry=sum/10;
1 S0 y/ O$ A5 t; O            res[i]=sum%10;# s5 f; }  p- G, m
        }
2 I, V2 u) @- \9 Y! t        l++;8 ?$ T! v: Y9 W' y2 C* [9 X% Q
    }
0 B* o3 r4 f9 `" m$ e( r3 K0 ]- A* u0 X' ]" c6 i7 s+ S5 r" {, G
    for(int i=k-1; i>=0; i--)2 |3 b% m5 w$ Z5 D% |, p- ]
        cout<<res[i]<<" ";4 Q3 T/ N+ ]& ~8 |: B( j
}

1178

主题

174

精华

3584

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3584
发表于 2-5-2017 02:46 PM | 显示全部楼层

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;
}

1154

主题

153

精华

3407

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3407
发表于 2-5-2017 02:46 PM | 显示全部楼层

# 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]" R/ V" h2 l, h
                left += 1- X8 ]4 S, e% ~" I6 v: b) q
                right -= 10 C; E# ^9 j! L

# U7 w2 I- K7 ?6 Z" r5 Z! H# Multiply two numbers1 H+ e. ?# r! C3 c, ^
# Input: Big-endian order
" w/ d! C' b: }# Output: Big-endian order- J$ R+ r9 S3 K, V/ l  I) ]
def multiply(num_a_array, num_b_array):# c3 N7 E( _! \& t0 e3 d
        # Convert big-endian to little-endian0 v& S7 U/ U4 R! [; L. F
        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 = []7 @/ X7 V/ R* c: R+ M$ w
+ O/ f7 w# Q; z
        # Multiply% D& {) g4 a" y; V3 f, V
        for i in range(0, len(num_a_array)):6 A( Q' N0 |0 M5 W) T0 Z+ f% Y
                carry = 0& F; G' b+ P& p3 _6 }2 i3 Q
                j = 0  a0 P+ w% L) k6 n4 N: [: u. y
                while (j < len(num_b_array)):5 y, S8 {) ^6 J* w. _  M
                        val = num_a_array[i] * num_b_array[j] + carry' ^6 z& O4 {+ _) k/ o3 n5 J
                        if (len(num_result_arr) <= i + j):) R0 D+ ^* R  q9 a
                                num_result_arr.append(0)
4 d# K$ _& L* @7 ~, ], L                        val += num_result_arr[i + j]# K: w3 w# Z, W  ?( ]
                        carry = val / 10
; ?& V& e; p9 Q" j$ ?4 v& x. p                        val %= 109 w; [. _4 |+ _5 H- Q# e9 W) i$ k
                        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):$ Z- z! m! _! L' `2 d4 F5 j5 e
                                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& B1 K& O+ i7 T5 _5 v, @& \! J! b

  a( {% b1 u1 |& J        #  Convert little-endian to big-endian
" K: F' H3 E) s        num_array_reverse(num_a_array)( S/ \$ l  Z+ u8 r# O8 o8 g
        num_array_reverse(num_b_array)
8 T8 D2 _. c) b) t4 ^        num_array_reverse(num_result_arr)6 j7 y4 J; T: k8 d; ~3 n, X
- s8 P, j  m# S$ A3 X+ B. d$ _
        return num_result_arr! l1 H( ?+ |- q# U
. A5 _. {  `& l- {
def multiply_and_print(num_a_array, num_b_array):7 V& y% a$ ?1 C. O! L1 }+ n( R, P
        num_result_array = multiply(num_a_array, num_b_array), `! A# z, U1 l: f# b
        print("{0} x {1} = {2}".format(num_a_array, num_b_array, num_result_array))
3 i0 a- `. R1 b$ f$ [( B! ]0 X4 v, {/ X  d+ M
def main():
2 H6 \9 F( x+ }        multiply_and_print([1, 2], [1, 0])  O$ H/ F4 p9 d# z1 _) a
        multiply_and_print([5, 3, 6, 2, 8, 0, 2, 8], [3, 5, 2, 3, 2, 1])1 J8 S' {# j# e0 ^

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

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表