LeetCode 488. Zuma Game

发表于   |   分类于 ，   |     |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/02/08/LeetCode-488-Zuma-Game/

访问原文「LeetCode 488. Zuma Game」

题目要求

Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.

Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.

Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

Examples:

Input: “WRRBBW”, “RB”
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

Input: “WWRRBBWW”, “WRBRW”
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Input:”G”, “GGGGG”
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty

Input: “RBYYBBRRB”, “YRBGB”
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Note:

  1. You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
  2. The number of balls on the table won’t exceed 20, and the string represents these balls is called “board” in the input.
  3. The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
  4. Both input strings will be non-empty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.

题意解析

祖玛游戏，不知道你们有没有玩儿过，我也是很久很久之前玩儿了，久到实在想不出来是什么时候的事情了。在桌上有一行球，球有5种颜色，红、黄、蓝、绿、白。你的手里也有一些这些颜色的球，每次可以选择一个球插入到桌上一行球中的任意位置，如果有3个或者3个以上相同颜色的球出现则将它们消除。然后再持续把手里的球插入到桌面一行球中，直到桌面上的这行秀全部消除。

求出能把桌面上的球全部消除的最小步数。

解法分析

这道题的主要解法就是递归加回溯了。在桌面上的一行球上从左到右进行遍历，如果遇到一个颜色的球就加入两个相同颜色的球（如果存在），如果遇到两个相同颜色的球就加入一个相同颜色的球（如果存在），然后消除所有连续3个或3个以上相同颜色的球，继续下去。不管能不能把所有的球消完，在返回结果之后都需要恢复到没有插入球的情况，然后寻找下一个插入的位置。在不断地尝试过程中记录下消除完使用的最小步数，然后返回。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
	public int findMinStep(String board, String hand) {
	if (hand == null || hand.equals("")) {
		return -1;
	}
	char[] boards = board.toCharArray();
	List<Character> boardChars = new ArrayList<>();
	
	Map<Character,Integer> handMap = new HashMap<>();
       handMap.put('R',0);
       handMap.put('Y',0);
       handMap.put('B',0);
       handMap.put('G',0);
       handMap.put('W',0);
       for (char h : hand.toCharArray()) {
           handMap.put(h, handMap.get(h) + 1);
       }
	for (char c : boards) {
		boardChars.add(c);
	}
	return findMin(boardChars, handMap);
}
private int findMin(List<Character> currentBoards, Map<Character, Integer> currentHands) {
	
	boolean isFind = true;
	while (isFind) {
		isFind = false;
		for (int i = 0; i < currentBoards.size() - 2; i++) {
			if (currentBoards.get(i) == currentBoards.get(i + 1)
					&& currentBoards.get(i + 1) == currentBoards.get(i + 2)) {
				int j = i + 2;
				while (j + 1 < currentBoards.size() && currentBoards.get(i) == currentBoards.get(j + 1)) {
					j++;
				}
				for (int m = j; m >= i; m--) {
					currentBoards.remove(m);
				}
				isFind = true;
				break;
			}
		}
	}
	if (currentBoards.isEmpty()) {
		return 0;
	}
	if (isHandEmpty(currentHands)) {
		return -1;
	}
	int count = 0;
       int min = Integer.MAX_VALUE;
       
	for (int i = 0; i < currentBoards.size(); i++) {
		char c = currentBoards.get(i);
		count++;
		
		if (i == currentBoards.size() - 1 || currentBoards.get(i+1) != c) {
               int missing = 3 - count;
               if (currentHands.get(c) >= missing) {
               	currentHands.put(c, currentHands.get(c) - missing);
                   List<Character> smallerBoard = new ArrayList<>(currentBoards);
                   for (int j = 0; j<count; j++) {
                       smallerBoard.remove(i-j);
                   }
                   int smallerFind = findMin(smallerBoard, currentHands);
                   if ( smallerFind != -1 ) {
                       min = Math.min(smallerFind + missing, min);
                   }
                   currentHands.put(c, currentHands.get(c) + missing);
               }
               count = 0;
           }
	}
	return (min == Integer.MAX_VALUE) ? -1 : min;
}
private boolean isHandEmpty(Map<Character,Integer> handMap) {
       for (int value : handMap.values()) {
           if (value > 0) return false;
       }
       return true;
   }
Jerky Lu wechat
欢迎加入微信公众号