找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1167|回复: 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 编辑 + [$ o: l# M/ z
/ V; P3 V* P* W) l% q1 C
Random generate a NxN matrix with only four types of  element: 1,2,3,4.
- W5 g- Q8 o% \0 RHowever, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)
# q( {  O" L; K) f1 N+ H9 l' R! h- ?, ]% @1 l6 d& K
ex:
1 c: ]- h6 C2 I" W- V: L& I3 m/ o: R% b, u* m- T+ Z
valid:
3 `$ u9 \' X5 P, |$ F+ X/ ]9 u5 X1 2 1 1( k: x% @. [  V! |. E) H4 N
3 1 4 29 c' k2 _( V) G5 A$ E+ a% @+ `
1 2 4 2+ I/ `% e1 s$ ^
3 1 2 3
% x6 c* n, l# @8 t! l- O6 ?6 C' Y$ b' N: D$ E% X5 o$ s
invalid because the first column has element 1 appears three times and all 1s are connected to each other :0 }% i# ~9 u6 i% z5 }% j

7 h; z5 w' A4 A* L7 R) ~1 2 1 3/ @; Q, A6 m& o
1 3 4 2% n8 O; H% `* L. d( s6 t9 [( f4 L
1 2 4 4
. f0 K5 {2 R3 X& B! c9 {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;' O( ^$ f. s2 Q% e, I2 `/ K8 ]+ P
" i" N- i( ]2 q# e
public class candyCrush {4 c% r* x6 m" M2 @. g: a* J
, z! i, @  _: X
	public static void main(String[] args) {
, ]& ]6 Y: @: e		// TODO Auto-generated method stub- K: x0 n  p* I& S6 W+ Z* |) O
		int[][] res = generateRandon(6);: |8 m' J0 k4 V% ~7 X& L; n" ]
		for (int i = 0; i < res.length; i++) {* w5 r! H7 ^4 W
			for (int j = 0; j < res[0].length; j++) {
  K6 u0 S3 \9 m" T				System.out.print(res[i][j]);
, I7 r7 k( P2 ?( w7 i			}
4 H* y% {# l8 n* s. l			System.out.println();
) C9 v8 J  C! t3 Y		}1 B) O! x3 L" h8 }3 B2 s0 K2 x, \

9 P( |  T- k* X* ~& {	}  w% Q3 o+ ~6 D2 s4 Y. ^; r

+ d, A8 s# Z5 S, [/ q	public static int[][] generateRandon(int size) {
% |+ Z. @0 c& S1 }1 e) C. v$ j		Random r = new Random();
5 u# u: Z4 m- a9 u7 C8 @		int dp[][] = new int[size][size];6 n! y& ~6 X2 F5 p- j6 y- l
		for (int x = 0; x < size; x++) {" G: e' p6 C, E2 {5 \' m
			for (int y = 0; y < size; y++) {! s4 n+ {9 ~5 z$ @0 t
				int rand = r.nextInt(4) + 1; 
: ~0 e1 h3 K4 U$ D% {+ V				if (x > 1 && y > 1) {
* h$ k0 M, L: k+ ~					int a = dp[x - 1][y];
4 l  N; `- T3 x6 o& ?0 E. s) Z					int b = dp[x][y - 1];7 @/ Y4 J# ^- w) j! m, y8 E; t' ^
					int c = dp[x - 2][y];+ p* ~$ y& ]) f# k4 W) R$ Z
					int d = dp[x][y - 2];2 M* Z5 F+ K& z1 D
					int newRand = rand;$ l. C3 ?0 q2 z
					if (rand == a && rand == c && b!=d) {4 K0 {4 |+ U5 b& D; R$ U
						newRand = a;
4 s7 O' f' S1 Q+ ?% G" b) C' c6 C						while (newRand == a) {# h  O( ^1 M  o4 Z! p' _. \
							newRand = r.nextInt(4) + 1;8 E. Q, ]( n4 ^
						}5 O! a* T0 S$ G$ }. d
					}else if (rand == b && rand == d && a!=c) {7 g9 N5 h5 i0 K7 _+ u
						newRand = b;; m8 s3 j- D- o$ S+ }6 X
						while (newRand == b) {
: ~  V/ g" Q3 h2 z! ~							newRand = r.nextInt(4) + 1;: j# F  f5 S+ l3 k) R+ g5 ]
						}, ^- D8 A7 ~  @! U7 d
					}else if(a==c && b==d){
- X) p/ [  V; h0 M' t$ B						
; u' z/ `; _. R3 m- R1 [						while (newRand == a||newRand==b) {
& [8 S( u1 V& D5 x3 v6 c# }5 z							newRand = r.nextInt(4) + 1;
( z4 E8 S. q, `% z% L0 J						}
9 ]: s0 Z4 K2 [3 s; w					}
0 d, Y* I0 ^2 c+ {; [1 t& K					
- _( }# I5 S- I$ Y3 o+ j					dp[x][y] = newRand;
6 z0 O* O* p8 x) j2 ]0 k6 i
* p: q" K! k2 F4 k				} else if (x <= 1 && y > 1) {6 [  u) G9 D8 i3 e  J! R
					int a = dp[x][y - 1];# Z) }0 ^5 Q  `5 u' k+ H
					int b = dp[x][y - 2];! P, }) j* r/ U9 s7 E6 N
					int newRand = rand;! e8 U: ^+ Z9 Y" s% c6 n& P. P
					if (rand == a && rand == b) {, E0 r- W( y: I5 b. x: o
						newRand = a;8 N. Z# q. D' K! `  Y; c# e
						while (newRand == a) {
9 l# d% w0 M- e5 [6 X+ m5 `							newRand = r.nextInt(4) + 1;
3 d9 D' {6 |; Q2 u4 W9 @. {						}/ ?9 U8 k' U  _2 N, z& n. A8 E
					}) r* F7 h0 K* R0 i
					dp[x][y] = newRand;
' Q1 o' j9 b2 u6 N. J# D				} else if (y <= 1 && x > 1) {
; A& ~, A1 f2 ?% T					int a = dp[x - 1][y];. h4 D0 m: c- V+ p
					int b = dp[x - 2][y];% ?. _* g; [2 z; g
					int newRand = rand;3 q+ @' K& _) f8 y! Z) [: ^$ C, V
					if (rand == a && rand == b) {# }9 P. c9 E, W' r. e/ D$ o+ l
						newRand = a;3 g3 C* J5 ~2 i% p2 z: [: Z
						while (newRand == a) {: e9 r0 W2 b  ~; z9 ]
							newRand = r.nextInt(4) + 1;
# U( n$ S2 e0 `; A7 x% D: C+ }, w6 `5 `						}
# V3 J6 n+ }8 N" y5 B6 i					}
& P4 v, C0 s/ P4 j- u' {					dp[x][y] = newRand;
3 o) D( x8 s8 ?  G				}else{
! V2 h: i: \- D5 b					dp[x][y] = rand;& v; g8 I' }% @
				}
7 z# Z+ S& [# l% i' t3 D: `			}
- x/ S2 \4 T- v: e$ j5 M		}0 c; O( ~2 z9 U% \; o( s7 I
		return dp;& l3 y+ U* Y! Q! P9 ^# X4 u
	}
$ N- H$ A7 Y; J- C9 g
" J; j4 m9 k" i5 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.

回复 支持 反对

使用道具 举报

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

本版积分规则

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