找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1194|回复: 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 编辑 - F8 P* @* p! F
- u1 V/ J: U% J; H0 i
Random generate a NxN matrix with only four types of  element: 1,2,3,4. 4 M& W  C) t/ v9 i' \! ]+ J
However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)) o& x  V& _0 _
( y& r2 U+ d% M
ex:6 g+ i# ?! {, F4 j8 D
3 Z, I5 y, J2 b+ N0 G0 A
valid:
  L; \: @: G. ^8 d) Z9 m1 2 1 1: N6 p0 Q' L7 P4 d- T
3 1 4 2
. S; l/ I* y5 ^% V+ H, O2 I1 2 4 2& h! U( P! e$ I( D* |- b
3 1 2 3
8 c% D% @1 \$ T. i
: F( q8 g( o, y9 Q; z5 ~; H7 finvalid because the first column has element 1 appears three times and all 1s are connected to each other :
6 f& i' A3 D) W- @' p1 n
) [' v- v- [) ^9 o1 2 1 3, G8 y! R; o  C) v- T0 s: O
1 3 4 2  {/ u* g, C8 Q2 H9 K
1 2 4 4! t2 C2 }/ L$ ~. Q7 e, v
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;
& D) C9 X" W! r, B8 F
" B2 ?6 @) G; D' I" @) ]" _public class candyCrush {
; H6 t' G9 P0 g; G4 G( l
1 R6 Q" E) Z0 C5 H2 z0 i8 F	public static void main(String[] args) {- {' c& c7 g0 Q) O$ V
		// TODO Auto-generated method stub
) w2 N: X6 B" B% G		int[][] res = generateRandon(6);
- ?9 Z  Z6 h& u3 C1 S; W		for (int i = 0; i < res.length; i++) {
) b% ^! t& L. Z/ }* A0 p4 X  ~7 e			for (int j = 0; j < res[0].length; j++) {
' ^: S" I8 G3 }0 r! V# K				System.out.print(res[i][j]);* I2 s6 s+ H  i) {2 S& V- S
			}
% E  M( I- H5 S			System.out.println();
* R3 L4 X) d6 W		}
2 k) @1 R- U; R" B  D/ _- M& U6 g; o% V2 D& \: D
	}
* p" n$ _5 M3 U% l$ ?5 i
0 I- {. q# A9 _' l9 {% A* T" w	public static int[][] generateRandon(int size) {
, |" s) D' B0 s9 k( R& L0 v  u7 t! ~		Random r = new Random();5 w. c$ }. b+ N
		int dp[][] = new int[size][size];  m7 w& j: A. i+ b* @
		for (int x = 0; x < size; x++) {4 I( o. ~6 o2 {6 a7 O
			for (int y = 0; y < size; y++) {' e" Y, Y. h6 U& v6 {! |. L" K1 T
				int rand = r.nextInt(4) + 1; 6 S& P; B* H, |: _5 V2 I8 a" N
				if (x > 1 && y > 1) {0 ]1 f! k8 F, L# s" A1 A
					int a = dp[x - 1][y];
" a; i% U- B" _5 k0 A- \3 Y, H					int b = dp[x][y - 1];0 I* @/ e1 g4 a+ Q# }
					int c = dp[x - 2][y];
% U6 [' {: l4 e- Z) L					int d = dp[x][y - 2];, D; R# ?7 K; M3 m
					int newRand = rand;
0 W) I( K6 ]( L- }8 f					if (rand == a && rand == c && b!=d) {  _* H8 Z# E, O8 p
						newRand = a;
$ i. q$ A( ?* G, z, q! G! T						while (newRand == a) {- p6 L) ~- K: v$ {' U: ]+ u% Q
							newRand = r.nextInt(4) + 1;
3 L. u, v0 ]! W: d  m+ U						}
: H9 {- F9 o2 ]( [$ h$ X4 S/ r					}else if (rand == b && rand == d && a!=c) {5 N& r: T! _1 b# v/ F6 Z" b; `* q
						newRand = b;
5 n4 Q5 M0 T7 X, c: c: D- Z% g5 V) g' u						while (newRand == b) {. E* y# ^6 i7 X: D' l" ^# o' d$ s
							newRand = r.nextInt(4) + 1;
' k& o1 @9 J/ x, n; t* K4 x: X						}
! {# M/ q# w2 W& O: |9 ^; A( U; U					}else if(a==c && b==d){
- M! v9 V. C$ b* m5 K  E						9 Z" p6 k" X3 n8 b
						while (newRand == a||newRand==b) {
, X, H0 k; i+ ~+ ?							newRand = r.nextInt(4) + 1;
: L: R4 H! D4 F4 e" o: V						}
6 X  I( p* P9 [3 w& S. I- K4 h! J					}
  D9 J! g1 d; \5 a/ u" A					
0 v5 i; H1 J$ w$ A9 T					dp[x][y] = newRand;
* l, `) X1 ^  ]9 w: M+ n+ U4 f% b" }$ \0 {
				} else if (x <= 1 && y > 1) {
* M" f; @+ S+ d  X					int a = dp[x][y - 1];4 D: p0 U( N- t  H; D
					int b = dp[x][y - 2];% @9 Z+ a1 N, t( v1 w! W
					int newRand = rand;$ _: u, t: k' t. v+ \
					if (rand == a && rand == b) {7 d7 `+ {1 D" P" I( q
						newRand = a;
1 j% Y$ z9 x# V						while (newRand == a) {0 u" ^' S& M1 r* g" o( z7 C
							newRand = r.nextInt(4) + 1;; B4 j# R9 r1 k3 n
						}6 i0 ]. _% X) M1 y- z( i+ ^  G
					}
3 j( S" h, f3 g6 @) @					dp[x][y] = newRand;; ?9 h/ ?1 Q! m, U3 c
				} else if (y <= 1 && x > 1) {4 ^  j! y) Q& s' d! d
					int a = dp[x - 1][y];
: i, @' j8 B, T0 u* Y0 m9 O					int b = dp[x - 2][y];
( |9 O" j1 ?( I; [! }- D					int newRand = rand;
( Q8 y, W2 ~, _% V# M					if (rand == a && rand == b) {
3 m- q2 O6 b% h  Z1 I* T6 X8 `2 H						newRand = a;3 p2 H* l" C" _* z# p" g
						while (newRand == a) {
$ a3 I4 R' H2 F9 Q* y+ ]							newRand = r.nextInt(4) + 1;
1 j/ u9 v2 b) J! V8 E						}
) y' s' w' h# V. K2 b) S( i3 N					}) ^' a7 m% i) j. V% N
					dp[x][y] = newRand;
9 p5 z/ V7 e" o" l" |				}else{7 A, S# N$ p: I# C4 x- h
					dp[x][y] = rand;
6 W$ m% f& a1 q# p				}1 q! Z3 [, }2 p4 ^+ l7 X6 p
			}$ n1 Z5 d  O8 l: l
		}
/ }- A" r3 Y- F, u) p		return dp;
2 t1 Q+ B( R( L5 Z" o" _	}
; I- t/ s, ]; J* }, g8 a: m- }5 K5 H# h' O4 [
}

回复 支持 反对

使用道具 举报

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.

回复 支持 反对

使用道具 举报

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

本版积分规则

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