找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: MorningXu
收起左侧

[Goldman Sachs] 高盛Onsite

[复制链接]

1156

主题

173

精华

3582

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

use linked list

1183

主题

200

精华

3760

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

C++ solution 0 n% {. T! h7 T5 P$ r- s7 \
( U2 W+ o7 `' ]; R P: t
Btw: The second example multiplication is wrong, it's 536282028 X 352321 (one less 8)

#include <algorithm>, a% G* u* S$ p6 G# R$ X' C  e
#include <vector>
/ f% @6 R. d$ z: Kusing namespace std;* `* `+ x( f  y2 i! e3 k1 L, ~
3 g6 j" G+ H  w1 O
vector<int> MultiplyVectors(const vector<int> &v1, const vector<int> &v2) {
3 ^$ l' t6 J4 y; I3 g  vector<vector<int>> sums;
8 r' c! ^) s' q  for (int i = v2.size()-1; i >= 0; --i) {
" D* G% y# g3 J& b. P. u    sums.push_back(vector<int>(v2.size()-1-i, 0));
/ l; S# d7 q1 D    int carry = 0;+ `0 _  k5 A. E3 Q' i" n
    for (int j = v1.size()-1; j >= 0; --j) {
) S4 Q! `8 C# p      int v = v1[j]*v2[i]+carry;
9 `1 A( ~. T. J1 [3 F% L0 M      sums.back().push_back(v%10);6 D7 |) ]1 D1 x! t, E3 r! w) J) Y
      carry = v/10;
9 I: I5 t/ c6 \* T  J( K, ~    }( N) q2 e8 Y- G8 h1 ^% c9 v
    if (carry != 0)
" S5 n3 Z4 T, J. o      sums.back().push_back(carry);
$ ~6 ~5 v; V( s0 E# W# E4 g  }! ~* \+ G0 J, P' b( N, u

1 h7 \. h) r1 V! b5 b- Z  size_t max_idx = 0;. r# _$ \- Q7 l
  for (size_t i = 0; i < sums.size(); ++i)
- v7 Z' P1 S" ?1 D* h: P    max_idx = max(max_idx, sums[i].size());. j: L, b5 \# Q/ y9 w

5 `5 v4 K1 \% U7 V* a" J  vector<int> ret;" [# r6 q8 l) N" @/ ?
  int v = 0;
4 A' J' d& w$ z! J# w% U* w  for (size_t i = 0; i < max_idx; ++i) {
8 c( @. R, x0 Q  k    for (size_t j = 0; j < sums.size(); ++j) {# j; t$ ~/ n0 q
      if (i < sums[j].size())- n- Z+ B# E9 ^1 s% ]% _, r7 b
        v += sums[j][i];
- D6 j3 n8 l" `6 n* ]+ ^* i0 U" G+ D; R5 Q    }; r* [- E( R- R
    ret.push_back(v%10);$ E- E& T8 G; Q
    v /= 10;( t& f( [3 ?2 I8 R; u7 V
  }5 h, {) H7 R' C
  if (v != 0)
+ p% o* m0 y. l5 s    ret.push_back(v);/ r! [: k2 m& c' V+ ]

6 E8 z5 Z0 v( L/ t( g: D  reverse(ret.begin(), ret.end());7 F4 N" Q, y; P( P0 Q9 R% e
  return ret;
" `2 x, ?5 b, I% a' \0 n}

1174

主题

171

精华

3558

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

#include<iostream>  _" J+ H4 M3 P) z; J: ~# a
using namespace std;
( a, A% C* l6 Q; c% A6 W; c0 O' [# P
int main()$ D5 t' i0 i( j2 U
{8 e; D- p  C! u. e
    int a[]={1,4,7,5,2,3};
0 G6 f( a! R6 t5 p, w5 L  P+ @  `    int n=sizeof(a)/sizeof(*a);7 x9 K7 D5 O1 R% l8 r% ^1 r+ A

6 u0 v2 ^: n; `* U5 _' V: w6 x    int b[]={5,4,5,7,8,9,2};
( {3 ~/ w5 ~( H* |  O# @+ s" M    int m=sizeof(b)/sizeof(*b);
1 W8 t4 B- o' O1 o* ]5 ~1 G/ S! L2 k6 D
    int res[10000]={0};
! {- y9 X/ s0 ?4 I: M    int carry=0;
/ R  k5 j* i4 C8 x( d    int h=0;
8 H% P- x/ H; Q    for(int i=n-1; i>=0; i--)
7 f' A9 {6 Y7 l% X& Q    {
  l6 Y  Z9 U- E/ f' p        int k=b[m-1]*a[i];
4 [9 ?% |( K+ w+ J6 f+ M/ y        k+=carry;3 U3 k; k! k9 C8 ~
        res[h++]=k%10;9 Z3 i4 b# u& g* ^8 z
        carry=k/10;6 W" i$ _0 D* B$ g' s4 T8 y
    }8 y+ H$ Y/ C% s. z8 g. k3 C. T3 G

0 p( _! ~* r: m+ T    while(carry)
& C; g* Z, F5 f) S& _5 @0 {, Q    {
- |' N5 v# q; E# a3 w# T; @$ w2 [8 K7 a        res[h++]=carry%10;- n2 ]$ e9 g5 |6 I
        carry=carry/10;7 s# f8 i0 J; S; s5 @: C1 _
    }; E* f7 T1 G( f, X2 l9 ]/ ~  N

& \4 R: ^3 D! I' G* t; Q' {1 h2 _2 X& |( v7 h- T( k  ?, y0 J$ x# H% A
    int l=1;
% j; }$ i: L4 \& B5 \# {2 N    int k;
) x" ]9 ?) a+ [. q+ m    for(int i=m-2; i>=0; i--)  x" T6 O( L1 u/ n0 ?% L, [# L
    {
# M0 E4 [6 ^- _5 ?$ c        int carry=0;- h& u3 Y8 J# ]
        k=l;
6 P, g  I$ V0 c" c7 K        int temp[1000]={0};* Z7 o3 l3 }+ F. D# {
* v. P7 f) V" V6 V
        for(int j=n-1; j>=0; j--)$ z, O) C7 ~' {* L' P. R
        {& j3 s& |+ P" a# ]
            int x=b[i]*a[j];
  M. Z" N' R  Q            x+=carry;
- N6 L, c2 H" |6 x1 }: w3 E            carry=x/10;
, \; v& Y5 p* X; f            temp[k++]=x%10;
. j4 w' _/ t/ ]+ E* ~% s5 P8 O        }$ n; V/ G( s( Z0 ]9 \! B2 m
5 s# e$ L/ R" S5 e0 @7 y
        while(carry)
1 n8 I( c2 z' d/ s3 w" N        {
' A+ L1 D" Q# ]7 L8 C& m4 |            temp[k++]=carry%10;7 x4 P& o) V; ~0 H: ^( `- z$ [; B
            carry=carry/10;3 G- x& X% ?, h4 a: q# z
        }
9 M5 q/ E5 `, V5 B& s
1 |/ f' V- G/ ^0 D' n2 s        for(int i=0; i<k; i++); ~; w! ^; U6 o" B
        {3 D* B: m" @3 {5 m2 r' C0 Y$ @
            int sum=res[i]+temp[i];9 F! ]0 J; o7 R/ [# ~
            sum+=carry;; e: \& Z8 a3 T* C
            carry=sum/10;
, Y4 w( [5 h) ~& |7 p            res[i]=sum%10;4 @8 ^- t5 g4 d) f  q- X) I- `
        }
/ Z5 [1 Y" C6 b8 {4 x, o  K& Y        l++;0 V6 C% L& j" H* C/ Z" W  N
    }
) y( q2 }" ?, [' S9 g
. E- E' F" \5 s8 R* N    for(int i=k-1; i>=0; i--)
* D, [6 Z9 d% N/ y+ u) m        cout<<res[i]<<" ";( D# ^" b! p6 c( x
}

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

本版积分规则

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