找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Facebook] 2017新鲜面经

[复制链接]

1085

主题

138

精华

3183

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-1-2017 10:36 PM 编辑 3 F* D! k1 C$ o

. a, U6 Y0 m4 |9 {# J3 O( k$ }4 URandom generate a NxN matrix with only four types of  element: 1,2,3,4. ' f& R4 M4 w/ Z; s0 G% U
However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)
/ j+ e  z6 _$ |8 U! l
6 N8 k. @, r: U; nex:
9 Y6 R6 Y7 P1 `8 A( ]) o+ z0 f' m+ Z3 d2 K8 c
valid:
4 C9 Y! u4 d9 p' g) `6 E, T1 2 1 1
# K, N- v$ ?% i3 1 4 2. S* l4 C; I" W' k
1 2 4 2* R4 j, o3 h6 A2 p
3 1 2 3
( g) i7 S( e3 H. g9 |+ S* I, c6 I( [9 w
invalid because the first column has element 1 appears three times and all 1s are connected to each other :9 i8 V6 g( F  Q3 Y! a8 e
. z1 s( x* U( |4 p: f  x' G9 Q
1 2 1 3
0 h& U) A5 W3 x3 _1 3 4 28 T/ O$ o. ]$ W8 Y; Z3 A
1 2 4 4
2 G' s( Q: M1 ]: Z2 H3 Z, F+ @; I2 3 2 2

1202

主题

184

精华

3712

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

I post my solution below:

import java.util.Random;& K* }4 T4 k3 x5 k+ X3 g
9 @* d) K1 [1 h8 }2 j
public class candyCrush {
$ d3 u7 v' `" _5 y6 d& R+ t- b6 [+ q1 B' y4 o( ~' m, T
	public static void main(String[] args) {
* l4 D& A' ~# V. v# l		// TODO Auto-generated method stub$ ^, N" N  H0 ~% c
		int[][] res = generateRandon(6);
0 L( {& C4 Q7 ]7 v! s* f4 M		for (int i = 0; i < res.length; i++) {
: c4 G  f6 Y) }, W  R			for (int j = 0; j < res[0].length; j++) {
# w9 L0 k7 x3 }/ `/ ?$ I% n+ v				System.out.print(res[i][j]);
1 q8 u( f% J" K( [2 u- P- l			}
8 s' R/ i6 b0 e& w0 F8 y( T			System.out.println();
+ `. v5 j) p/ a		}7 t" H4 I6 E  o& M; s& u6 _
5 _6 K1 `' r1 m  u5 l) G
	}, ]2 k4 c% E4 p3 Y. I, ~
" z# {7 H1 C' L0 Q; E
	public static int[][] generateRandon(int size) {6 @% F; R/ L- s
		Random r = new Random();
; c/ O/ K! ?  `% a" |		int dp[][] = new int[size][size];
3 ?7 {" y+ i! c8 R; J		for (int x = 0; x < size; x++) {) [- S* M- [+ N, ~/ X. g- G
			for (int y = 0; y < size; y++) {) M9 ?* c2 N% f
				int rand = r.nextInt(4) + 1; 3 G% z$ z7 g* R$ H7 V/ Z/ o9 ]
				if (x > 1 && y > 1) {$ V1 c+ p8 a5 T- U0 t. m( Y; H
					int a = dp[x - 1][y];
: k6 ~) U$ e2 |' l! ?4 R					int b = dp[x][y - 1];3 z" `2 q- n1 C, Z3 C7 ?
					int c = dp[x - 2][y];2 d) z& l" e9 G" n
					int d = dp[x][y - 2];; r, L( T* G% `9 s) b# {) N
					int newRand = rand;
/ f3 _$ L- l  V6 _0 A! y: f					if (rand == a && rand == c && b!=d) {
8 X0 k+ Z* J( p' D						newRand = a;
4 ]7 n% P1 _  i2 c! V5 i, T						while (newRand == a) {' }' s- S% i8 U; M
							newRand = r.nextInt(4) + 1;
  [) p% Q* N/ A! P5 h. L						}+ B. {! p+ u8 b2 ^3 ~
					}else if (rand == b && rand == d && a!=c) {
; |' n6 X/ E* R, i5 G						newRand = b;
* L6 u7 d. R" d) ]! [. r						while (newRand == b) {/ M, L, W% _. U- Z) U
							newRand = r.nextInt(4) + 1;
- z  y3 H2 I4 e1 E- @' C						}  w" [$ L4 `+ H2 A- b+ m8 l
					}else if(a==c && b==d){- I6 g8 P3 c' g  i
						$ t# S) L$ j3 t* r; y& K6 `
						while (newRand == a||newRand==b) {
. o9 O: C* `2 e( s9 ]3 ?- r) [) m							newRand = r.nextInt(4) + 1;, Y1 c' k/ b( K$ g& ]6 i) H
						}
# C0 H. G! b) h) g$ a' P9 x+ j					}! X# j7 {5 Z) H: k7 F
					
* |, \% G" ]1 O1 K  @					dp[x][y] = newRand;
: \1 |% E% p6 C& N" ?+ N( J4 |5 u
( z3 J- I" [) k) r/ B( U' e7 K8 y				} else if (x <= 1 && y > 1) {" |1 R# S- J( l' U( D
					int a = dp[x][y - 1];" a" j/ D: Y$ e/ m9 ?/ p
					int b = dp[x][y - 2];
+ u; C# \+ J7 x/ y8 ~2 R					int newRand = rand;
1 `0 r5 t2 ?! H/ h: E4 Q8 o3 N					if (rand == a && rand == b) {( R" A% b9 [/ U2 c* g
						newRand = a;. j: V/ H0 v- \1 ]# V# K# R) S5 D
						while (newRand == a) {7 P( J1 [6 x1 L6 e! m+ e& l1 |
							newRand = r.nextInt(4) + 1;: p0 k6 B5 _0 f7 d0 K! h
						}
6 B, _7 @6 h8 q) w* B3 a" b  i  ]					}
, ^6 e2 d4 z/ {0 I					dp[x][y] = newRand;+ j$ e" C1 t( {/ \) y
				} else if (y <= 1 && x > 1) {3 e0 @5 M7 I; P! J& |
					int a = dp[x - 1][y];0 ~! j$ z$ l' f  M4 K( f
					int b = dp[x - 2][y];
. a$ y2 e. b" @* M6 T& I4 o; \					int newRand = rand;
& w$ \# X0 h3 A) d" v					if (rand == a && rand == b) {
" h3 b: j! R# z: p						newRand = a;% m5 @0 {( E4 F8 I5 T; V. H, R
						while (newRand == a) {( |- Q# Q+ w' B
							newRand = r.nextInt(4) + 1;
& C: V9 h) K$ K4 R						}, A& t/ W& u% f8 P
					}
# V2 h7 ]" S9 {6 n					dp[x][y] = newRand;
  K0 e, |" Y( e' u' H				}else{( x- A5 f$ M# g9 `: d) B' N( ]
					dp[x][y] = rand;
& M3 U/ C8 ]0 {				}+ ]8 U. W2 M6 y
			}  `5 O( ?4 Q" B% S& v" `
		}
9 O6 d6 J3 ~3 x1 |! X* @; e		return dp;* @  J# K) m9 W7 Q) Z
	}
3 f% Q. K; H' P$ v+ |) R. Z, o( @  L5 x, b. m8 n: w
}

回复 支持 反对

使用道具 举报

1116

主题

164

精华

3412

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3412
发表于 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.

回复 支持 反对

使用道具 举报

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

本版积分规则

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