找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1100|回复: 5
收起左侧

[Facebook] 2017新鲜面经

[复制链接]

1088

主题

138

精华

3189

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3189
发表于 2-1-2017 10:33 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 2-1-2017 10:36 PM 编辑
: Z2 H  U) q! E$ a5 M+ t) M
4 E' F6 Z2 ?, F8 VRandom generate a NxN matrix with only four types of  element: 1,2,3,4.
8 c$ H/ x" f/ t" q' n$ j" w/ LHowever, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)
  B1 F9 c+ c2 X* o
/ k& w  q, G. F: s0 {. Mex:
( y( W9 f8 s7 \+ N; s) K
7 P1 b4 u8 p4 J$ C& @valid:4 l  z* ^( y4 ~( q) @
1 2 1 14 ?) k+ l; u1 |- d
3 1 4 2; O7 r* Z* c! c! p& A% T
1 2 4 2
  p: O  r  p9 b$ m8 [6 k2 R6 M3 1 2 3$ x! x& j9 [3 N! |0 ^) e
! Q0 U2 ?. S6 V( ~
invalid because the first column has element 1 appears three times and all 1s are connected to each other :
! x, }, g  v8 o2 o( ~& k% i2 b( X
0 v" `- I- d/ w1 2 1 3# C( f& \5 m) g% V
1 3 4 24 t) \0 c5 A5 \& A+ a
1 2 4 48 U) R# w$ P1 f+ ^
2 3 2 2

1206

主题

184

精华

3720

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3720
发表于 2-1-2017 10:33 PM | 显示全部楼层

I post my solution below:

import java.util.Random;4 P% }; d% K. k) F1 b

1 F( h0 E4 p* ]2 m" b1 D9 _" ypublic class candyCrush {
4 B4 {2 S- i6 j3 V  M3 d  @8 V  E% r1 r4 W3 r
	public static void main(String[] args) {  \6 f5 V) W) Q5 T* r
		// TODO Auto-generated method stub# ?8 X4 F6 w5 R/ _9 a
		int[][] res = generateRandon(6);' l3 Z3 @4 ?! }5 g+ s, j3 \
		for (int i = 0; i < res.length; i++) {
- X3 i/ q! p9 r. w; y' m			for (int j = 0; j < res[0].length; j++) {+ \  R; ^0 G1 d! {  g" [/ R% N$ i7 a
				System.out.print(res[i][j]);
& P/ I1 x! \/ ]0 X* F			}7 @: u- q. h' @& [" r- c7 v) B% a
			System.out.println();
& \' T  @5 g2 e" f( a		}
! l9 J0 {7 }( x; t3 u& k. [
- z' }8 u  u# ?+ m. a0 m	}
, y4 y" `( r9 N" R8 C3 C, K- y
. j/ l3 [% @. b# ?2 O' y	public static int[][] generateRandon(int size) {
, |/ f# `+ P- o& H		Random r = new Random();
( ~& w3 W& M/ z" [7 b		int dp[][] = new int[size][size];
0 d$ k% B4 u$ i' \, j4 Z% j, C) z		for (int x = 0; x < size; x++) {( E. T" Y% Q: u2 |9 \
			for (int y = 0; y < size; y++) {
2 }4 D$ }. P8 i/ i				int rand = r.nextInt(4) + 1; 
1 \  k5 w; E) @  H  U# p; ]2 S				if (x > 1 && y > 1) {7 F  t9 n/ p5 k& f4 j6 P0 x
					int a = dp[x - 1][y];! o5 f# ]" Y& h0 P8 [8 |
					int b = dp[x][y - 1];+ R/ r% k& d, u" O, c% r7 G7 y
					int c = dp[x - 2][y];
; l% a2 i. i8 O9 u& X' R' I					int d = dp[x][y - 2];. _) N7 [5 u/ e) N
					int newRand = rand;. o1 V+ a0 F8 S) N( R! u
					if (rand == a && rand == c && b!=d) {+ ]$ a6 C0 N; v* W8 }
						newRand = a;" V; i9 ?& k7 ~' [4 S
						while (newRand == a) {( e, H/ L$ N! e. U
							newRand = r.nextInt(4) + 1;
3 _" _1 C; _" S8 ^: C						}0 m! p, T, n% a8 R
					}else if (rand == b && rand == d && a!=c) {' O: y: D& v- b( o6 [
						newRand = b;
/ `/ C2 c2 ]5 P$ v8 L9 k4 ?) N						while (newRand == b) {5 ~, L: z/ k# e3 c
							newRand = r.nextInt(4) + 1;5 V; Z% ]/ _1 L7 q2 y/ d
						}
  S% r% \0 l* v. q					}else if(a==c && b==d){
$ i2 M$ s; A: F6 [0 X						
; I4 x4 r  P; K; ?$ h- J, A						while (newRand == a||newRand==b) {
) C0 b+ n1 V( V; ?							newRand = r.nextInt(4) + 1;
& f7 {. q, Z7 e2 y						}' U0 {6 m2 t  u, U% @
					}) i) P6 ^5 ~3 {& {" _1 v5 o
					
# p" c3 H4 ]/ n4 y: a					dp[x][y] = newRand;
( M( q- M. v/ }: x  H! N
( z- t9 a" I" g2 j  s" |( F8 c				} else if (x <= 1 && y > 1) {
9 T8 f4 w6 _7 ^* H/ a, I  U					int a = dp[x][y - 1];( q. S  z2 J. q3 f% i* _
					int b = dp[x][y - 2];
8 U2 u6 _* w' d3 O					int newRand = rand;
2 m2 W! o) |" u					if (rand == a && rand == b) {+ s& t- J/ J' V, s& b, |
						newRand = a;  s8 p% N5 V0 y4 O* p
						while (newRand == a) {
  a% W7 t4 v9 b5 b- m! c							newRand = r.nextInt(4) + 1;
  ?, x, Z* v8 E; V  \0 J						}
& t2 f) e4 G* a					}
$ J+ i9 \4 m* O					dp[x][y] = newRand;
' V7 ?; T# x8 n! y9 m! D" o  A				} else if (y <= 1 && x > 1) {0 K( v' t7 W, k7 a" A2 p
					int a = dp[x - 1][y];; z) K3 C9 [2 ?4 V
					int b = dp[x - 2][y];
: K$ [  R; d: |; [! p6 P					int newRand = rand;2 W7 H* F7 ~. s4 r/ d
					if (rand == a && rand == b) {
  f  e4 R- ~( v& Z						newRand = a;
( B6 j' P8 \- b						while (newRand == a) {
4 K" B: `( W9 K2 S7 S3 p) ]							newRand = r.nextInt(4) + 1;5 Q% U) K( G6 c. Z; p
						}9 b/ u6 z) d  J$ E
					}
/ v* m$ g9 U& s$ x! ]/ {					dp[x][y] = newRand;' W, a' y& ]+ W" u
				}else{( b# b" T- ^5 n  q
					dp[x][y] = rand;( f9 C3 X6 D# v0 |6 X2 U' L
				}8 m: L2 @: w) A. q2 k
			}
8 G, h4 q) ]+ Y/ Q		}
! A, `5 X) W: R0 w3 \		return dp;
7 S! t, I6 }" L$ ^  G! v	}
9 a: S) S+ z+ J
0 \& m: `/ v/ p4 ~  P}

回复 支持 反对

使用道具 举报

1117

主题

164

精华

3414

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3414
发表于 2-1-2017 10:33 PM | 显示全部楼层

your solution doesn't allow the case that two elements of same type are next to each other in a row or column, but actually it is allowed. Only three or above connected elements in the same row or column are prohibited.

回复 支持 反对

使用道具 举报

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

本版积分规则

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