找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4941|回复: 3
收起左侧

[Square] Square 电面

[复制链接]

20

主题

7

精华

301

积分

高级会员

Rank: 3Rank: 3

积分
301
发表于 6-8-2015 08:29 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 6-9-2015 10:41 AM 编辑 / O( K* c3 J3 y4 K7 d
$ n  E$ Z  K2 H9 ]' Y
白人小哥,题目是2sum,但是和标准不同,要求return 全部的解,这样就比1个解复杂多了- R8 [$ R; x, H
  1.     static class Pair{  O/ q0 j' M$ |+ g% K. J/ [; M4 s
  2.         public final int left;; w) m3 g3 \7 H/ @) J
  3.         public final int right;
    0 ?- h' P* G( H" L2 H; N# I
  4.    
    6 y/ [- e2 c7 y% p. O7 v0 l: L
  5.         Pair(int left, int right) {
    / g7 j2 q; g" n" E
  6.              this.left = left;! t/ x& O) e6 O3 C& w9 L
  7.              this.right = right;
    ( e# H2 E% }1 P% C2 Y
  8.         }
    ' b+ z# G( `$ e& X: r; P
  9.         @Override
    ) U( A# p; S& I) f% t+ s& S
  10.         public int hashCode() {1 L! U) W! U- f! I9 Y, R; n' o
  11.           return left * right;
    0 \% G5 K* g6 U' l  t- R2 u
  12.         }
    " m' L# I' x2 Q/ E2 k6 j, [
  13.         @Override
    ( F+ x9 y. s$ M& d
  14.         public boolean equals(Object p) {
    " r# g. d6 Q! F; a- P1 a+ Z
  15.             return ((((Pair)p).left) == left && ((Pair)p).right == right)||
    1 s$ s0 d& ~" c( `) c6 r+ p1 G4 C
  16.               (((Pair)p).right == left && ((Pair)p).left == right);
    ! S6 r) r' Q2 f% m* z: Y( U
  17.         }9 m. p9 ~5 e- L
  18.     }/ `- C5 F6 Y" i
  19.     @Test // 通过unittest来确认题意
    , L) \8 e7 G- f  S' B9 A) S
  20.     public void testTwoSumTotal() {
    8 d" v, v# Q+ W; f$ b4 m( g0 \
  21.         int[] input = { 0, 4, 3, 0 };- L0 r% r5 q: a0 u$ R2 }! V
  22.         Pair[] output = {new Pair(4,3)};, b0 j3 S$ N& m
  23.         assertArrayEquals(output, twoIntSumTotal(input, 7).toArray());' y  A" f7 M5 `9 N
  24.         input = new int[] {2, 2, 4};
    / o( |6 @; O+ [. i/ D
  25.         output = new Pair[]{new Pair(2,4)};! e+ `# {/ ]4 C
  26.         assertArrayEquals(output, twoIntSumTotal(input, 6).toArray());
    , V2 V9 E  W& [+ s' O" |
  27.         input = new int[] {2};& o; f% p! Q( M- K0 U
  28.         output = new Pair[]{};
      y( C- \. ~6 R: v* v6 r& e5 J
  29.         assertArrayEquals(output, twoIntSumTotal(input, 6).toArray());
    " S/ |3 b. g0 B$ Q3 o
  30.         input = new int[] {3,2,2};
    * {+ F) K+ Q* j$ z
  31.         output = new Pair[]{};; f( j( z; ?6 ?% N
  32.         assertArrayEquals(output, twoIntSumTotal(input, 6).toArray());
      u* [$ s* E: {1 t
  33.         input = new int[] {3,3,3,0,3,2};  n2 g0 q- x; }& x7 t
  34.         output = new Pair[]{new Pair(3,3)};
    8 V/ a1 W9 S+ }* v& }# O
  35.         assertArrayEquals(output, twoIntSumTotal(input, 6).toArray());: W8 Z: v' ~8 i" a" G

  36. 6 N! O* P9 L% F/ f+ b4 _/ n: y
  37.         input = new int[] {0,3,1,3,3,3};
    # K8 i; G7 y: J( e. r5 y
  38.         output = new Pair[]{new Pair(0,3)};2 t7 Z/ d1 t6 z
  39.         assertArrayEquals(output, twoIntSumTotal(input, 3).toArray());0 n% N2 K8 T9 u7 A% H' X

  40.   a& O  a: Z! O4 G
  41.         input = new int[] {3,3,2,1,4,5,2,0};
    ( O: K6 E5 c2 R# \0 _  {
  42.         List<Pair> o = Arrays.asList(new Pair(3,1),new Pair(2,2), new Pair(4,0));' M# y4 w3 `2 g! P
  43.         List<Pair> r = twoIntSumTotal(input, 4);! c/ n0 o, b- F% A% J
  44.         // 测试两个list 包含相同内容的最简单写法: o, w5 a* R4 l  C) M3 x
  45.         assertTrue(o.containsAll(r) && r.containsAll(o));3 G: j9 X" ]; i4 d
  46.         input = new int[] {3,3,2,7,8,6,2,4,6,7,0,2,3,4,5,6,7,8};
    1 }8 J/ c& |$ t" n9 \" e3 {- m
  47.         o = Arrays.asList(new Pair(2,6),new Pair(8,0), new Pair(4,4),new Pair(3,5));1 l! q9 N8 p1 k5 w# W# ^/ l. {
  48.         r = twoIntSumTotal(input, 8);( R7 S$ _0 N) N  I& a  s' g0 c
  49.         assertTrue(o.containsAll(r) && r.containsAll(o));7 J# w* |, b+ P; |
  50.     }0 N; _/ _; T& a
  51.     public static List<Pair> twoIntSumTotal(int[] a, int t) {* e2 d! v5 g7 z
  52.         if (a.length < 2) return Collections.emptyList();9 b- s! }' v$ a
  53.         HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
    5 M; h- x" s" C+ n& z  e1 Q
  54.         Set<Pair> rSet = new HashSet<Pair>();1 x" f: e: k# I& ~
  55.         for (int i: a) {
    $ e7 a) O0 y3 _6 ?5 F$ Z7 F
  56.             int x = t - i;' e! g7 Q  S: k, `: S: [) w. B- b
  57.             Integer c = map.get(x);
    2 M9 i9 Y; ^# F- U+ ~0 I2 l6 L7 f
  58.             if (c != null) {$ K: S  R8 `0 _; k% v# m0 C
  59.                 if (i != x || (c == 1)) {
    . |! T. F5 L+ y. l
  60.                     rSet.add(new Pair(x, i));
    ) Q. G0 q! }" }
  61.                     if (i==x) map.put(x, 2);
    3 j8 c& A$ V, E: }' k
  62.                 }
    " Z% [3 e4 f( s
  63.                 if (i != x && !map.containsKey(i)) {
    . s- w+ b  H) b6 }  s
  64.                     map.put(i, 1);
    8 x  a2 O1 ~! a/ f1 B" Q: D
  65.                 }( x! f% j4 X; Q$ K! o5 h
  66.             } else {, c2 U4 R% \- Y8 J- }5 y' {- m- S
  67.                 if (!map.containsKey(i)) {+ d& t, h  C1 e/ v" U- r
  68.                     map.put(i, 1);+ B" Z: g/ H8 i0 }; p4 ?7 b
  69.                 }
    , h! L1 Y5 K3 w1 _( K
  70.             }
    7 v* o/ ]  |, w) S* n
  71.         }. s( U/ j/ |; m
  72.         List<Pair> r = new ArrayList<Pair>(rSet);
    : i0 K, ?4 H" Q; J
  73.         + e0 \- ^! ^$ E
  74.         return r;
    6 l4 p: r9 h" ]/ n) N! P0 w1 i
  75.     }6 {5 l' P( o  v1 B; m0 d. a
复制代码
面试过程中,我对于pair 作为hashmap的key,开始是做comparable, 结果被指出不对,override 了hashcode, 又被指出需要override 别的,想了一会,发现需要 override equals, 到处都是 twosum 一个结果,第一次见到需要全部结果的。
. J4 Y9 C! N* _  x. ~) n
3 c0 n% T) f& s3 ]4 v

! `" s2 |  b. @7 c米群网面经 这个tag如何加?我就先用文字加了
( U# I2 B, }: _5 x, {/ |- }

0

主题

0

精华

301

积分

高级会员

Rank: 3Rank: 3

积分
301
发表于 6-8-2015 11:11 PM | 显示全部楼层
用原本的2-sum 不管用sorted 和hashMap 因该都可以解吧? 还是unique 判断不同?

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 6-9-2015 10:42 AM | 显示全部楼层
The tag is applied~~~感谢您的分享~~~祝您面试工作学习顺利~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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