找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Facebook] 2017新鲜面经

[复制链接]

1075

主题

136

精华

3137

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 2-1-2017 10:36 PM 编辑
+ j  q: s; B6 @) Y+ H5 P) U8 Z5 U& k$ l! n! C
Random generate a NxN matrix with only four types of  element: 1,2,3,4.
/ P/ e5 Z+ V1 H* Z" vHowever, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)
7 Z- H2 M0 H- D7 V4 Y; U" U7 t% H5 B3 p1 V$ X* F
ex:1 g5 b" n4 K3 u9 M
& o, N/ C- q3 w& u$ }$ H$ z
valid:
4 t$ W  }1 C( [6 T! s& z0 R1 2 1 1
) e2 }+ t% F0 S1 w; `3 1 4 2* K9 `' `9 c1 j5 u+ `: F# N
1 2 4 2
' o0 K1 B# ?$ M% p4 M+ e; g3 1 2 39 B' c2 r* a# G$ Z

% O: c" R) N0 N2 r& Uinvalid because the first column has element 1 appears three times and all 1s are connected to each other :# S1 @' l5 M- r& h! ?& b
# d3 |' x( j5 _, v# ^, B# D! H
1 2 1 3$ I) `& Y1 n4 n
1 3 4 2
7 `! Q! ^6 V& [# x1 2 4 4
7 O/ w1 ]" }3 `" e8 L' R7 {$ N$ g2 3 2 2

1199

主题

184

精华

3706

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

I post my solution below:

import java.util.Random;5 P0 A" Z( H/ T; s
7 N! M! |9 R6 V
public class candyCrush {
$ t) p2 h! M3 ~1 u- O8 F
5 x9 q8 C0 b4 J, v" \2 m! n5 u	public static void main(String[] args) {
( h" E6 l7 b: }) M		// TODO Auto-generated method stub
3 P, e0 |' w0 A& |) R3 K$ s3 e4 H		int[][] res = generateRandon(6);1 l# y  I9 [. I1 G+ c; s
		for (int i = 0; i < res.length; i++) {
* d% a1 Z- ^  a			for (int j = 0; j < res[0].length; j++) {
& ^4 f! e: y7 R' Q6 d				System.out.print(res[i][j]);
8 q) a1 ]1 r+ r			}
9 e; ?2 k- E% r( {- j- M			System.out.println();8 X' o' }- E5 A+ S+ f& f
		}- V: o3 Y3 C: `: _3 ^

2 v# m8 m5 r) s( n* ~0 `	}! ]' G6 v. E8 d2 r0 j9 t' {' M

$ K" s; t( _) Q# [: o& [/ G	public static int[][] generateRandon(int size) {
: ?* i: s0 m6 g  \  w4 {		Random r = new Random();  [/ J6 D2 {% t- V6 l/ H
		int dp[][] = new int[size][size];( y; n- ^9 @1 C! q1 d/ c7 b
		for (int x = 0; x < size; x++) {. i# G  ^  v0 A' ~0 }
			for (int y = 0; y < size; y++) {* u1 }0 Z. ]( z$ k* I: G
				int rand = r.nextInt(4) + 1; 
) A9 `1 D# N1 P9 P3 [6 c- @, H				if (x > 1 && y > 1) {
7 v  g$ V- y7 O. `; b					int a = dp[x - 1][y];* S# }" d+ z% @
					int b = dp[x][y - 1];8 _, P6 ^& }9 Z$ G% E8 ^, L" r4 H& H
					int c = dp[x - 2][y];2 D) U# E* ?( a# u6 D# |$ @
					int d = dp[x][y - 2];
+ [$ n0 w7 p) [2 B# |2 ]					int newRand = rand;+ j5 @' c# V) ]8 T7 c& `
					if (rand == a && rand == c && b!=d) {
) h* g$ @/ k7 Q, v						newRand = a;1 b% _2 l3 S& _) J) m
						while (newRand == a) {
, H# c/ a1 s) [							newRand = r.nextInt(4) + 1;( d  w  u) K' N2 A8 ]. \
						}
. \8 r! L, P5 e# [					}else if (rand == b && rand == d && a!=c) {
  v5 \- k" w* O! U4 U						newRand = b;. X5 u% j* {- E2 I" M% }# \, p
						while (newRand == b) {
. Y) R1 u3 ?: y7 Y* I6 G2 j. V							newRand = r.nextInt(4) + 1;
0 H5 }, y( H2 F2 `. d						}
1 l3 `- u" y, K/ h					}else if(a==c && b==d){% m- k$ r) p# X9 }$ _
						( _3 O; W6 I8 d
						while (newRand == a||newRand==b) {) c0 P; s% T! K1 R# n+ g. |0 Z* z
							newRand = r.nextInt(4) + 1;# ~' N) i/ O3 |, Y2 I9 S  E4 H
						}
4 u1 }" Y* d  b					}
3 Y1 n/ N0 q* |0 y! d- ^  W0 o					
) @  f5 h0 w) }! U/ v- ~. U					dp[x][y] = newRand;" u9 w! w( ?" k& j) N/ g

; b/ b1 p4 N- {% ~; ?1 o				} else if (x <= 1 && y > 1) {# P( O$ [* F7 {
					int a = dp[x][y - 1];$ I  R5 P7 ?1 l
					int b = dp[x][y - 2];3 ~" Z) \+ n1 X" A. k! f3 h
					int newRand = rand;
7 @! [8 y; g* O1 R( u					if (rand == a && rand == b) {8 F  k, c2 \0 w
						newRand = a;
# K2 s8 A9 C* y( {5 d+ l						while (newRand == a) {
9 n( ^$ ~8 r/ g							newRand = r.nextInt(4) + 1;
6 R* h# d  ]% |$ I, P						}
$ h+ v& w) v6 h3 t$ Q' R					}
! B/ A. A* z. L5 T3 y					dp[x][y] = newRand;3 m& I4 N8 E  S% V: f* R
				} else if (y <= 1 && x > 1) {
% h$ p3 i3 ?6 J: s					int a = dp[x - 1][y];, Z+ w- {2 W# K
					int b = dp[x - 2][y];
; l) z0 D- \- p5 ]					int newRand = rand;
8 R! s* M" m% @; T6 |					if (rand == a && rand == b) {7 @- ?( Y' d4 a
						newRand = a;9 {) p) ~; R5 B0 ~3 b1 L( C' }
						while (newRand == a) {" d( N5 U. V& [6 X8 h
							newRand = r.nextInt(4) + 1;7 T3 l$ ]- t+ K0 I% J; j; e
						}8 a% T& B) ^3 k$ j+ e8 I# u
					}
2 M- V8 Q" @" D3 T$ p					dp[x][y] = newRand;! W* _4 O) X3 @' S* M( i+ N
				}else{/ M! _! P: }9 O
					dp[x][y] = rand;  y2 Z, h3 C8 R! r
				}5 ^0 f7 _# m- ^: E
			}
# Q. d5 N; o2 P		}
( C; z' q" [& K4 q& h  M		return dp;: H0 m5 U, b- \$ q
	}
6 F  o% A" r& \* Z) `
7 f! e' o( w( @/ s, R/ P2 u}

回复 支持 反对

使用道具 举报

1112

主题

164

精华

3400

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

回复 支持 反对

使用道具 举报

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

本版积分规则

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