刚做到的百度面试题:祖玛游戏

这是一个祖玛游戏。

一行球放在桌面上,球被涂上了红( R )、黄( Y )、蓝( B )、绿( G )和白( W )这么几种颜色,同时你也拥有几个球。

每一次,从你拥有的球当中拿出一个,插入到当前行当中(包括最左边和最右边)。然后,如果有三个或更多的同色球挨在一起,然后就消除这几个球。一直这么做直到没有更多的球可以消除。
找到最少的需要插入的球的数量,使得所有的球都可以被删除。如果不能删除所有的球,那么就返回-1 。

  • 初始的行不会拥有三个及以上的连续的同色球。
  • 行中的球的数量不会超过 20,用名为\”borad\”的输入字符串表示。
  • 你拥有的球不会超过 5 个,用名为\”hand\”的输入字符串表示。
  • 输入字符串都非空,而且仅包含字符 \’R\’,\’Y\’,\’B\’,\’G\’,\’W\’。

点这里可以在线做题

样例 1:

输入: \"WRRBBW\", \"RB\"
输出: -1
解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

样例 2:

输入: \"WWRRBBWW\", \"WRBRW\"
输出: 2
解释: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

样例 3:

输入:\"G\", \"GGGGG\"
输出: 2
解释: G -> G[G] -> GG[G] -> empty 

样例 4:

输入: \"RBYYBBRRB\", \"YRBGB\"
输出: 3
解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty 

[题解]

考点:

  • 搜索
    题解:基本思路就是搜索,c 数组统计自己各类球的数量,对 board 进行遍历,然后 j 保存一段的起点,i 向后移动至出现不同的球,然后对这段长度判断,根据 inc 判断需要几个球插入,对应的球数量减少,然后截取起点至 j 的区间和 i 至区间终点的两段拼接,继续搜索即可。
public class Solution {
    /**
     * @param board: the given board
     * @param hand: the balls in your hand
     * @return: the minimal balls you have to insert to remove all the balls on the table
     */
    private int aux(String s, int[] c){
        if(\"\".equals(s)) {
            return 0;
        }
        int res = 2 * s.length() + 1; 
        for(int i = 0; i < s.length();){
            int j = i++;    //j 保存起点
            while(i < s.length() && s.charAt(i) == s.charAt(j)) {
                i++;
            }
            int inc = 3 - i + j;  //3-(i-j) 判断消除需要几个球
            if(c[s.charAt(j)] >= inc){  //如果数量足够
                int used = inc <= 0 ? 0 : inc;    //如果 inc<=0,不需要
                c[s.charAt(j)] -= used;    //用掉 s[j]
                int temp = aux(s.substring(0, j) + s.substring(i), c);  //去除 j 至 i 的一段继续搜索
                if(temp >= 0) {
                    res = Math.min(res, used + temp);
                }
                c[s.charAt(j)] += used;	//搜索完成后补充球的数量
            }
        }
        return res == 2 * s.length() + 1 ? -1 : res;
    }
    
    public int findMinStep(String board, String hand) {
        // Write your code here
        int[] c = new int[128];
        for(char x : hand.toCharArray()){
            c[x]++;
        }
        return  aux(board, c);
    }
}

更多题解参见

Click to rate this post!
[Total: 0 Average: 0]

相关文章

发表回复

您的电子邮箱地址不会被公开。