找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Facebook] 2017新鲜面经

[复制链接]

1087

主题

138

精华

3187

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-1-2017 10:36 PM 编辑 # r% N: u/ G1 s  u' V
$ K: B; P$ L1 L
Random generate a NxN matrix with only four types of  element: 1,2,3,4. / `) X" R3 B! {7 \
However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)- V* C" H3 X5 m4 [/ S' K

7 m- w- y- C: {! i: f8 Cex:) j# W% n9 Z7 s) z
( ]+ U0 r7 b5 Q/ }  }, q
valid:
# f; ~; `( m+ \6 t  n! x$ n1 Z" v1 2 1 1
; M! w: [3 X/ m3 1 4 28 B, l1 a; e5 Y- T, v9 x
1 2 4 29 C8 v5 n, o' A( I' ~+ @
3 1 2 3' w1 g3 w4 `( ]* c+ b

( \5 [9 _$ S' h' ^5 ]! t' rinvalid because the first column has element 1 appears three times and all 1s are connected to each other :  I1 d1 F" \7 f
5 {4 a: i$ R2 s% Y  V2 E' f0 u) z
1 2 1 3
% [! F0 r* I& K" F/ |- O) m( n* C1 3 4 2" z! F. E2 F& c0 S0 P+ H+ c
1 2 4 4( S/ p; O, l- k2 Z0 m& L
2 3 2 2

1205

主题

184

精华

3718

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

I post my solution below:

import java.util.Random;9 |9 X# G& A4 l1 ~  X. p9 S
' Y! {; }# r$ E+ _0 U1 q6 p% F
public class candyCrush {# y: w  k* a& u" S5 x- ~
. [2 |4 @- e8 T  u
	public static void main(String[] args) {
% o, v$ |. g* @3 P3 e. E) i9 K, v		// TODO Auto-generated method stub) r( q# S0 B4 d- `
		int[][] res = generateRandon(6);( J4 V- l. Z6 e! B) f
		for (int i = 0; i < res.length; i++) {* ^0 ^% A" W$ E
			for (int j = 0; j < res[0].length; j++) {
+ F3 z0 E# x- K+ W& f, _4 @				System.out.print(res[i][j]);/ U; \* r( y: Q- e2 M" J: |
			}
! U4 I0 c, b& w/ @7 Y			System.out.println();4 r$ k2 {8 S* I8 h! e+ W
		}
, l1 B3 l3 R7 V! M" `, T1 p# [
( }  t: [% w1 z$ _) X5 W# g1 D	}
: z5 ?$ O& N6 z/ s$ m* W2 w6 G3 x
	public static int[][] generateRandon(int size) {
1 Z( P3 D, {" x; |. y+ {0 L		Random r = new Random();! ~7 G9 k* J' }. ?& ]
		int dp[][] = new int[size][size];
+ u1 \: M6 k, p		for (int x = 0; x < size; x++) {
: O0 {! T# e! V" T7 X1 S$ y5 |			for (int y = 0; y < size; y++) {
* P. T( B2 O1 l) c				int rand = r.nextInt(4) + 1; $ r. u; q" ^5 ^$ D9 g7 P6 g2 }
				if (x > 1 && y > 1) {4 C5 _8 x! U9 h+ f- W0 L' L
					int a = dp[x - 1][y];$ P4 o5 m" C" e3 A  C
					int b = dp[x][y - 1];
$ q% y4 ?2 z- i3 C					int c = dp[x - 2][y];8 w9 X: N3 y5 d- I& R* v
					int d = dp[x][y - 2];! k1 E& Z! }( g, @3 j1 ^" T1 C& p
					int newRand = rand;
* g6 ^7 p7 V1 |( ^8 R% _. x					if (rand == a && rand == c && b!=d) {
' W, M4 E5 ]3 v0 U4 Q  C2 H						newRand = a;- k$ S5 X9 i; k
						while (newRand == a) {
& [( z8 T3 h& _) B% }0 }: Y							newRand = r.nextInt(4) + 1;* R8 O& `6 h" L6 ~' @$ M; P
						}
' {3 f% c5 o# n" R* Q4 C% w					}else if (rand == b && rand == d && a!=c) {
) V: F. k: i8 }; c) G/ \5 O9 U4 w						newRand = b;4 N3 y$ l# j5 R2 j* \6 M! m8 E
						while (newRand == b) {/ j# g( e. A. i5 u+ k- }
							newRand = r.nextInt(4) + 1;
4 n! }# \- f/ `# L  _- t2 N						}+ z' }" V" @0 l
					}else if(a==c && b==d){+ t# T& t4 ]& f% w2 `
						
' ?5 s$ x9 G( I5 A						while (newRand == a||newRand==b) {9 w) w; @0 K9 r
							newRand = r.nextInt(4) + 1;
* i9 ]6 \3 o6 `2 R# y4 o8 Z- g						}
$ c7 T$ C: h! \- ?					}& F( k: a# }  {/ v
					. Y5 o: J8 ^$ r5 S. `# |
					dp[x][y] = newRand;
, V) H# a6 ~) G7 c+ u) Z6 N3 \3 @5 h# U$ [7 [/ R1 u
				} else if (x <= 1 && y > 1) {' ^8 Y5 ^  C: _4 S
					int a = dp[x][y - 1];
2 j4 ]/ k) b. G7 F					int b = dp[x][y - 2];
( Z4 Y+ o  |. b4 g6 D5 ?0 h' s					int newRand = rand;- @8 h! J" z+ }' x' A
					if (rand == a && rand == b) {8 W) i9 F7 ^+ A9 J
						newRand = a;
& X! Y4 s: x. C7 y! M						while (newRand == a) {9 [7 u) z2 f2 K2 z: \1 B: [+ }
							newRand = r.nextInt(4) + 1;
' L. D/ V; d  O! o. o! ]						}& G  n3 q% z6 O/ K  G
					}( o6 q. b# B) K2 g7 p" J/ H5 {7 T
					dp[x][y] = newRand;
$ f* R& L9 {7 |; I; S+ ~. k" g# k				} else if (y <= 1 && x > 1) {( w9 F5 L5 |: V* b4 \
					int a = dp[x - 1][y];3 @  w/ F& F/ @/ d& t
					int b = dp[x - 2][y];
* ?- l# w: i# \0 x4 `+ c9 e					int newRand = rand;% w, N- f& C/ w% g
					if (rand == a && rand == b) {( r, a8 Q7 y( H, B
						newRand = a;
. z5 J' N. F3 a/ d9 D8 f# p' d						while (newRand == a) {
  F8 N% v. M, |) a0 o, v, ~. x							newRand = r.nextInt(4) + 1;
) u8 K  e" r. E: C( K0 F						}
8 Z- C( X0 @7 R2 o& w					}- I* L" _* O1 `* a0 A& W
					dp[x][y] = newRand;
: O9 ]- B4 e9 W7 g# Y0 @/ _				}else{, o/ k: d8 Q. Y5 F! G
					dp[x][y] = rand;
  G9 Y* t: F0 }				}
3 R; [  i/ [% V; k# m; n			}6 S% G$ I* s$ v5 v6 R( C/ A0 Y3 ]
		}/ [/ \. E. }- }! L! }6 f1 q
		return dp;) d# u& {: N/ ~: o9 [: L
	}* n! v% H1 G5 U0 ?6 s

, I& I) G1 a- a1 M/ r3 W: {7 H}

回复 支持 反对

使用道具 举报

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.

回复 支持 反对

使用道具 举报

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

本版积分规则

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