Massive Algorithms: LeetCode 488

LeetCode 488 - Zuma Game

https://leetcode.com/problems/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:

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.
The number of balls on the table won't exceed 20, and the string represents these balls is called "board" in the input.
The number of balls in your hand won't exceed 5, and the string represents these balls is called "hand" in the input.
Both input strings will be non-empty and only contain characters 'R','Y','B','G','W'.

X.
https://leetcode.com/problems/zuma-game/discuss/97007/Standard-test-program-is-wrong

I tried case "RRWWRRBBRR", "WB". The test program gave the expected answer -1. However, I thought the answer might be 2. Because:

RRWWRRBBRR -> RRWWRRBBR[W]R -> RRWWRRBB[B]RWR -> RRWWRRRWR -> RRWWWR -> RRR -> empty

The possible reason might be the first [W] was inserted but not adjacent to a W in the sequence. I read the description twice but didn't find any condition about it.

http://hankerzheng.com/blog/Leetcode-Zuma-Game-

首先预处理input string, 将桌面上的球转换为一个列表, 列表的每个元素表示连续相同颜色球的颜色和个数, 并且预处理时, 可以直接消除相同颜色超过三个以上的球. 因此, 对于RRBBBGYYWWWYB, 转化后的表示为[["R", 2], ["B", 3], ["G", 1], ["B", 1]]. 当前问题的最优解有以下三种可能性:

将当前区间分割为两个部分, 两个部分的最优解合并, 即可得到当前问题的解
如果当前区间第一个颜色和最后一个颜色相同, 那么第一个色块和最后一个色块可以最后合并. 当前问题的解, 即为中间区间的最优解, 加上第一个色块和最后一个色块合并后新问题的解.
如果当前区间第一个颜色和最后一个颜色相同, 并且两个色块合并后个数小于3, 并且存在中间相同颜色个数为1的色块, 那么这三个分离的色块可以合并并消除. 因此, 问题的解即为分割后, 剩下两个色块的最优解.

上述三种情况涵盖了所有的可能性. 该算法的时间复杂度为O(N^3), 其中N表示色块的个数.

https://angovia.me/2019/01/28/LeetCode-488-Zuma-Game/
https://github.com/cherryljr/LeetCode/blob/master/Zuma%20Game.java

 *  注意Note中的说明，需要重点关注的有两点：
 *      1. 游戏初始的珠子串(Board)中并不会有 >=3 个颜色相同的珠子连在一起，这跟我们玩的游戏还是不同的。
 *      2. 数据规模：珠子串长度最长不会超过 20，手里的珠子最多不会超过 5 个。
 *  根据数据规模，我们基本可以断定这道题目是使用 DFS(Backtracking) 来枚举所有插入位置进行暴力解的。
 *
 * 注意点：
 *  以下代码进行了两个部分的剪枝操作。
 *      剪枝操作1：因为如果有相同颜色珠子连在一起的话，插在它们中任意位置效果都是相同的，
 *      所以我们统一规定插在相同颜色珠子串的最后一个位置。
 *      剪枝操作2：只对插入后会被消去的地方进行插入操作。即：如果本轮操作后，无法消去一段
 *      那么该位置就不进行插入操作。
 *  而本题存在问题的也正是上述的这两个剪枝操作！很明显这是一个贪心的做法，但是这个贪心的策略是错误的。
 *  正确的做法应该是每个位置，都需要进行一遍试探性的插入才行。
 *  举个例子:
 *      board = "RRWWRRBBRR", hand = "WB"
 *  如果按照上述的做法，我们会在 [W] 或者 [B] 的后面插入手中的珠子，但是这样肯定会剩下 [RR] 没法消除
 *  因此会返回 -1. 当其实这个局面是有办法全部消去的，策略如下：
 *      RRWWRRBBRR -> RRWWRRBBR[W]R -> RRWWRRBB[B]RWR -> RRWWRRRWR -> RRWWWR -> RRR -> empty
 *  因此这里的剪枝（贪心）策略是错误的。
 *
 * 大家可能会有疑问，为什么错的还要这么做呢？
 * 因为...这题的标程都是错的啊！！！而且不贪心剪枝的话还过不去！！！坑爹啊！！！
 * 这也能解释为啥这么多人踩这道题目了...

    public int findMinStep(String board, String hand) {
        if (board == null || board.length() == 0) {
            return 0;
        }

        // 为了方面查询，我们需要统计手中珠子的信息（本题中我们可以发射手中的任意一颗珠子）
        Map<Character, Integer> balls = new HashMap<>();
        for (char c : hand.toCharArray()) {
            balls.put(c, balls.getOrDefault(c, 0) + 1);
        }
        return dfs(board, balls);
    }

    // 返回全部清楚当前board所需要的最少珠子，如果无法全部清除返回-1
    private int dfs(String board, Map<Character, Integer> balls) {
        if (board == null || board.length() == 0) {
            return 0;
        }

        int rst = Integer.MAX_VALUE;
        int i = 0, j;
        while (i < board.length()) {
            j = i + 1;
            Character color = board.charAt(i);
            // j一直向后移动，直到 j 越界 或者 指向的珠子颜色与 i 的不同
            while (j < board.length() && color == board.charAt(j)) {
                j++;
            }
            // 需要插入多少颗珠子才能消掉 i~j-1 的珠子
            int costBalls = 3 - (j - i);
            // 手中剩余足够的珠子可供插入
            if (balls.containsKey(color) && balls.get(color) >= costBalls) {
                // 消去 i~j-1 段的珠子，同时因为消去该段会导致两边的两段的珠子碰到一起
                // 可能会引发连续的消除反应，因此实现了 shrink() 来实现这点
                String newBoard = shrink(board.substring(0, i) + board.substring(j));
                // 减去花费掉的珠子数
                balls.put(color, balls.get(color) - costBalls);
                // 进行 DFS 调用子过程，求解全部消去剩下珠子需要的最少珠子数
                int subRst = dfs(newBoard, balls);
                if (subRst >= 0) {
                    // 如果可以被顺利全部消除的话，取最小值即可
                    rst = Math.min(rst, costBalls + subRst);
                }
                // Backtracking 加上之前消耗掉的珠子，进行回溯操作
                balls.put(color, balls.get(color) + costBalls);
            }
            i = j;
        }

        return rst == Integer.MAX_VALUE ? -1 : rst;
    }

    // 消除当前 board 中所有可以消除的珠子串
    private String shrink(String board) {
        int i = 0, j;
        while (i < board.length()) {
            j = i + 1;
            Character color = board.charAt(i);
            while (j < board.length() && color == board.charAt(j)) {
                j++;
            }
            if (j - i >= 3) {
                board = board.substring(0, i) + board.substring(j);
                // 当进行成功消除后，记得将 i 重置回 0 位置，重新进行检查（因为可能发生连锁反应）
                i = 0;
            } else {
                i++;
            }
        }
        return board;
    }

https://www.twblogs.net/a/5c4aa33fbd9eee6e7d81b08e/zh-cn

    private String eliminate(String s){
        for(int i = 0; i < s.length(); ){ 
            int j = i + 1;
            while(j < s.length() && s.charAt(i) == s.charAt(j))
                j++;
            if(j - i >= 3){   //subtract 
                s = s.substring(0, i) + s.substring(j);
                i = 0; // notice
            }else 
                i++;
        }
        return s;
    }

http://www.cnblogs.com/grandyang/p/6759881.html
那么这道题是一种简化版的祖玛游戏，只是一个一维数组，而且通过限定桌面上的球不超过20个，手里的球不超过5个来降低来难度，貌似是在暗示我们可以用暴力搜索法来做。这道题比较使用递归的方法来做，通过遍历所有可能的情况来找出最优解，题目希望我们用最少的球来消掉桌上所有的球，如果不能完全消掉，返回-1。我们使用哈希表来统计手中每种球的个数，然后我们遍历桌上的球，我们找连续相同球的个数，在没有可以消除的情况下，连续的个数只能是1个或2个，然后我们用3减去连续个数，就是我们需要补充的球数以使其可以被消除，那么我们在哈希表表中看我们手中的该类型的球够不够，如果够就表示可以消除，我们在哈希表中减去需要使用掉的球数，然后将消掉的球移除，对新的字符串调用递归，如果可以成功消除，会返回一个结果，该结果加上之前需要的球数用来更新结果res，注意调用完递归要恢复哈希表的状态。还有就是在刚进入递归函数时，我们要检测字符串，去除连续3个相同球的情况，这个去除函数也是个递归函数，写起来很简洁，但是很强大

https://discuss.leetcode.com/topic/79820/short-java-solution-beats-98

int MAXCOUNT = 6;   // the max balls you need will not exceed 6 since "The number of balls in your hand won't exceed 5"

public int findMinStep(String board, String hand) {
    int[] handCount = new int[26];
    for (int i = 0; i < hand.length(); ++i) ++handCount[hand.charAt(i) - 'A'];
    int rs = helper(board + "#", handCount);  // append a "#" to avoid special process while j==board.length, make the code shorter.
    return rs == MAXCOUNT ? -1 : rs;
}
private int helper(String s, int[] h) {
    s = removeConsecutive(s);     
    if (s.equals("#")) return 0;
    int  rs = MAXCOUNT, need = 0;
    for (int i = 0, j = 0 ; j < s.length(); ++j) {
        if (s.charAt(j) == s.charAt(i)) continue;
        need = 3 - (j - i);     //balls need to remove current consecutive balls.
        if (h[s.charAt(i) - 'A'] >= need) {
            h[s.charAt(i) - 'A'] -= need;
            rs = Math.min(rs, need + helper(s.substring(0, i) + s.substring(j), h));
            h[s.charAt(i) - 'A'] += need;
        }
        i = j;
    }
    return rs;
}
//remove consecutive balls longer than 3
private String removeConsecutive(String board) {
    for (int i = 0, j = 0; j < board.length(); ++j) {
        if (board.charAt(j) == board.charAt(i)) continue;
        if (j - i >= 3) return removeConsecutive(board.substring(0, i) + board.substring(j));
        else i = j;
    }
    return board;
}

https://discuss.leetcode.com/topic/75434/recursive-java-solution

    public int findMinStep(String board, String hand) {
        List<Character> boardList = new ArrayList<Character>();
        for (char c : board.toCharArray()) {
            boardList.add(c);
        }
        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);
        }
        return find(boardList, handMap);
    }
    
    private int find(List<Character> board, Map<Character, Integer> hand) {
        cleanupBoard(board);
        if (board.size() == 0) return 0;
        if (empty(hand)) return -1;
        int count = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i<board.size(); i++) {
            char c = board.get(i);
            count++;
            if (i == board.size() - 1 || board.get(i+1) != c) {
                int missing = 3 - count;
                if (hand.get(c) >= missing) {
                    hand.put(c, hand.get(c) - missing);
                    List<Character> smallerBoard = new ArrayList<>(board);
                    for (int j = 0; j<count; j++) {
                        smallerBoard.remove(i-j);
                    }
                    int smallerFind = find(smallerBoard, hand);
                    if ( smallerFind != -1 ) {
                        min = Math.min(smallerFind + missing, min);
                    }
                    hand.put(c, hand.get(c) + missing);
                }
                count = 0;
            }
        }
        return (min == Integer.MAX_VALUE) ? -1 : min;
    }
    
    private void cleanupBoard(List<Character> board) {
        int count = 0;
        boolean cleaned = false;
        for (int i = 0; i<board.size(); i++) {
            char c = board.get(i);
            count++;
            if (i == board.size() - 1 || board.get(i+1) != c) {
                if (count >= 3) {
                    for (int j = 0; j<count; j++) {
                        board.remove(i-j);
                    }
                    cleaned = true;
                    break;
                }
                count = 0;
            }
        }
        if (cleaned) {
            cleanupBoard(board);
        }
    }
    
    private boolean empty(Map<Character,Integer> hand) {
        for (int val : hand.values()) {
            if (val > 0) return false;
        }
        return true;
    }

X.
下面这种解法也是递归解法，但是思路和上面略有不同，这里我们不使用哈希表，而是使用一个集合，我们遍历手中的所有小球，如果某个小球已经在集合中存在了，说明我们已经处理过该小球了，直接跳过，否则就将该小球加入集合中。然后我们遍历桌上的小球，寻找和当前手中小球一样的位置，然后将手中小球加入当前位置，调用去除重复3个小球的函数，如果此时字符串为0了，说明当前桌上小球已经完全消掉了，返回1，因为我们此时只使用了一个小球；否则就将手中的当前小球去掉，对新的桌面和剩余手中的小球调用递归，如果得到的结果不是-1，我们用此结果加1来更新结果res

    int findMinStep(string board, string hand) {
        int res = INT_MAX;
        unordered_set<char> s;
        for (int i = 0; i < hand.size(); ++i) {
            if (s.count(hand[i])) continue;
            s.insert(hand[i]);
            for (int j = 0; j < board.size(); ++j) {
                if (board[j] != hand[i]) continue;
                string newBoard = board, newHand = hand;
                newBoard.insert(j, 1, hand[i]);
                newBoard = removeConsecutive(newBoard);
                if (newBoard.size() == 0) return 1;
                newHand.erase(i, 1);
                int cnt = findMinStep(newBoard, newHand);
                if (cnt != -1) res = min(res, cnt + 1);
            }
        }
        return res == INT_MAX ? -1 : res;
    }
    string removeConsecutive(string board) {
        for (int i = 0, j = 0; i <= board.size(); ++i) {
            if (i < board.size() && board[i] == board[j]) continue;
            if (i - j >= 3) return removeConsecutive(board.substr(0, j) + board.substr(i));
            else j = i;
        }
        return board;
    }

LeetCode 488 - Zuma Game

Labels

Popular Posts