首页 技术 正文
技术 2022年11月23日
0 收藏 478 点赞 4,923 浏览 1559 个字

回忆一下祖玛游戏。现在桌上有一串球,颜色有红色(R),黄色(Y),蓝色(B),绿色(G),还有白色(W)。 现在你手里也有几个球。
每一次,你可以从手里的球选一个,然后把这个球插入到一串球中的某个位置上(包括最左端,最右端)。接着,如果有出现三个或者三个以上颜色相同的球相连的话,就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。
找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球,输出 -1 。
示例:
输入: “WRRBBW”, “RB”
输出: -1
解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW (翻译者标注:手上球已经用完,桌上还剩两个球无法消除,返回-1)

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

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

输入: “RBYYBBRRB”, “YRBGB”
输出: 3
解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
标注:
    你可以假设桌上一开始的球中,不会有三个及三个以上颜色相同且连着的球。
    桌上的球不会超过20个,输入的数据中代表这些球的字符串的名字是 “board” 。
    你手中的球不会超过5个,输入的数据中代表这些球的字符串的名字是 “hand”。
    输入的两个字符串均为非空字符串,且只包含字符 ‘R’,’Y’,’B’,’G’,’W’。

详见:https://leetcode.com/problems/zuma-game/description/

C++:

class Solution {
public:
int findMinStep(string board, string hand)
{
int res = INT_MAX;
unordered_map<char, int> m;
for (char c : hand)
{
++m[c];
}
res = helper(board, m);
return res == INT_MAX ? -1 : res;
}
int helper(string board, unordered_map<char, int>& m)
{
board = removeConsecutive(board);
if (board.empty())
{
return 0;
}
int cnt = INT_MAX, j = 0;
for (int i = 0; i <= board.size(); ++i)
{
if (i < board.size() && board[i] == board[j])
{
continue;
}
int need = 3 - (i - j);
if (m[board[j]] >= need)
{
m[board[j]] -= need;
int t = helper(board.substr(0, j) + board.substr(i), m);
if (t != INT_MAX)
{
cnt = min(cnt, t + need);
}
m[board[j]] += need;
}
j = i;
}
return cnt;
}
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;
}
};

参考:http://www.cnblogs.com/grandyang/p/6759881.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,183
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,644
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,488
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,260
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,897
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,062