今天面试遇了一个很有意思的消除算法题。
大概有点类似祖玛游戏，三个同样的数字在一起可以消除，连续消除分数会更高。
比如面试出题：1123133221 要求写一组算法找出去掉哪些数字会使得最高。
也就意味着算法要使这组数字变为112333221这样的一组三连消，333消除完后变成112221，继续触发连消变成111。这就算是一个三连消，分数会得分最高。总之连消越多分数越高。
规则应该大致上面这样，当时面试官会随机写一堆数字，类似这样：12342212321123123112113 我当时就懵逼了，有大佬会解这种题吗？来点思路和伪代码我研究一下
补充一下：该题最主要目的是要在一个很长的字符串中，找出去除哪些坐标的字符，可达到最大连消。这个字符可能是:adfsfs321423423121234sddaaadaa2234abj
定义数组 int total[9] = 0
先遍历一遍数字, 每一位上的数 total[x] = total[x] + 1
这里提供同一种简单的做法, 比如你举的例子, 1123133221. total[1] = 4 total[2]=3 total [3] = 3.
1112233321, 这样就OK了.
说通俗点步骤是:
1.遍历数组找到所有total[i] > 2 的数组下标并记录(例子中1 2 3).如果 total[i] < 3 && total [i] > 0, 那就先输出total[i]个i
2.对于上一步记录的下标(1 2 3) , 先正序遍历(1->2->3),对于每个下标, 输出total[i]-1 个 i
3. 对于上上一步记录的下标(1 2 3), 倒序遍历(1<-2<-3), 对于每个小标, 输出i
用栈，a栈往b栈放（放的同时计数c计数），转完连续的输统计超过二个就就让b栈回退对应的c个数并c归零，不超过就c归零
用栈，a栈往b栈放（放的同时计数c计数），转完连续的输统计超过二个就就让b栈回退对应的c个数并c归零，不超过就c归零
接着就b往a，a到b。。。,直到转完a、b栈的长度不变就结束
这种问题肯定可以是用递归啦~
java代码附上：
public static void main(String[] args) {
String blockette="3311231332213";
int point;//积分
int number;//去除数
String blocketteRe=null;
int maxPoint = 0;//最高积分
for(int i =0; i <= 9 ; i ++ ){
blocketteRe =blockette.replace(""+i, "");
point = eliminateThreeEqual(blocketteRe);
if(point>maxPoint){
maxPoint=point;
number = i;
}
System.out.println("当去除数为："+i+"时，积分为："+point);
}
}
/**
* 进行三位相同数的检验
* @Description: TODO
* @param blockette
* @return
* @author ZHANG_YX
*/
private static int eliminateThreeEqual(String blockette){
System.out.println("接收到的参数为："+blockette);
int point = 0;
//原谅我正则表达式写的丑的一匹
if(blockette.matches("([0-9]*)([0]{3}|[1]{3}|[2]{3}|[3]{3}|[4]{3}|[5]{3}|[6]{3}|[7]{3}|[8]{3}|[9]{3})([0-9]*)")){
blockette = blockette.replaceAll("[0]{3}|[1]{3}|[2]{3}|[3]{3}|[4]{3}|[5]{3}|[6]{3}|[7]{3}|[8]{3}|[9]{3}", "");
point++;
//将三位相同数去掉之后进行递归
if(!blockette.equals("")){
point+=eliminateThreeEqual(blockette);
}
}
return point;
}
简单又暴力，但是重复消除的计算还没来得及写，不过我想你肯定能写出来的呀~
送你小心心，赞给我好不好~
Java 代码最后HashMap排序下就行了，拿去参照不谢
package com.sample;
import java.util.HashMap;
public class Maths {
public static void main(String[] args) {
// TODO Auto-generated method stub
String number="12342212321123123112113";
String[] math=new String[number.length()];
HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
for (int i = 0; i < number.length(); i++) {
if(i==0){
String str=number.substring(1,number.length());
System.out.println(str);
map.put(1, sum(str));
}else{
String str=number.substring(0, i)+number.substring(i+1,number.length());
System.out.println(str);
map.put(i+1, sum(str));
}
}
for (int i = 0; i < math.length; i++) {
System.out.println(map.get(i));
}
}
public static int sum(String number){
int count=0;//记录最大连消次数,初始为0
int score=0;//最终得分
int sequence=0;//记录最大连消初始连消的索引
for(int i=0;i<number.length()-1;i++){
int countOne=0;
if(number.charAt(i)==number.charAt(i+1)){
if(i==0){
String s=number.substring(i+2);
countOne=getCount(s,countOne);
}else if(i>0&&i<(number.length()-2)){
String s1=number.substring(0,i);
String s2=number.substring(i+2);
String s=s1+s2;
count=getCount(s,count);
}else{
String s1=number.substring(0,i);
String s2=number.substring(i+2);
String s=s1+s2;
count=getCount(s,count);
}
}
if(countOne>count){
count=countOne;
sequence=i+1;
}
}
if(count==1){
score=100;
}else if(count==2){
score=100+200;
}else if(count>=3){
score=100+200+(count-2)*300;
}
System.out.println("连消次数"+count);
System.out.println("数字位数"+sequence);
System.out.println("最大得分"+score);
return score;
}
public static int getCount(String number,int count){
for (int i = 0; i < number.length()-2; i++) {
if(number.charAt(i)==number.charAt(i+1)&&number.charAt(i+1)==number.charAt(i+2)){
count++;
if(i==0){
String s=number.substring(i+2);
count=getCount(s,count);
}else if(i>0&&i<(number.length()-2)){
String s1=number.substring(0,i);
String s2=number.substring(i+2);
String s=s1+s2;
count=getCount(s,count);
}else{
String s1=number.substring(0,i);
String s2=number.substring(i+2);
String s=s1+s2;
count=getCount(s,count);
}
}
}
return count;
}
}
1.遍历数组找到所有total[i] > 2 的数组下标并记录(例子中1 2 3).如果 total[i] < 3 && total [i] > 0, 那就先输出total[i]个i
2.对于上一步记录的下标(1 2 3) , 先正序遍历(1->2->3),对于每个下标, 输出total[i]-1 个 i
3. 对于上上一步记录的下标(1 2 3), 倒序遍历(1<-2<-3), 对于每个小标, 输出i
public static double Sco(string str,double score,int count)
{
if (Dup(str))
{
//调用消除方法 返回消除后的字符串
str = Rem(str);
double s = count * score;//根据次数计算此次消除的积分
count++;
//积分为次数*基础分数 可以自己设定规则 这里我自己设定基础积分是500 系数为1.5倍
return Sco(str, score, count) + s;
}
else
{
//当没有 重复 结束递归
return 0;
}
}
public class JiFen {
public static void main(String[] sss){
suan("12342212321123123112113 ",2);
}
/**
*
* @param shu 要消除的字符串
* @param geshu 最少几个相同的可以 消除
*/
public static void suan(String shu,int geshu){
char[] chars=shu.toCharArray();
yici:for(int i=0; i<chars.length;i++){
String xiangtong=""+chars[i];
int cishu=1;// 用来判断 相同的次数
for(int j=i+1; j<chars.length;j++){
if(chars[i]==chars[j]){
xiangtong=xiangtong+chars[j];
cishu++;// 相同的次数+1
}else{
if(cishu>=geshu){
System.out.println(shu+":");
shu=shu.replaceFirst(xiangtong,"");
System.out.println("消除了："+xiangtong);
System.out.println("之后的字符串："+shu);
suan(shu,geshu);
break yici;
}
break;
}
}
}
}
}
用OC写的，下面是计算时间
11:45:08.697223
11:45:08.698699
(void)cal {
NSString * str = @"dsadnlksajd8932u984y392h3le3j2e283r8943hjf4j312r802hfe302j80e320fh3e328u832uf0h";
NSInteger num = 0; // 计数
NSMutableDictionary * dict = [NSMutableDictionary new];
for (NSInteger i = 0; i < str.length; i ++) {
NSString * charStr = [str substringWithRange:NSMakeRange(i, 1)];
NSArray * keysArr = [dict allKeys];
if ([keysArr containsObject:charStr]) {
NSInteger count = [dict[charStr] integerValue];
if (count == 2) {
num ++;
[dict removeObjectForKey:charStr];
}
else [dict setObject:[NSString stringWithFormat:@"%ld", count + 1] forKey:charStr];
}
else [dict setObject:@"1" forKey:charStr];
}
NSLog(@"%ld", num);
}
来一个c++的解法，能够得到最大连消次数和消除的索引序列
#include
using namespace std;
int numDispel(char* buff, int nLen, int nSkipIndex, int* indexBuff, int& indexLen)
{
if(nLen < 3)
return 0;
char* tempBuffer = new char[nLen];
int nTempLen = 0;
int nSpelCount = 0;
for(int i = 0; i < nLen; ++ i)
{
if(i == nSkipIndex)
continue ;
tempBuffer[nTempLen] = buff[i];
if(nTempLen >= 2)
{
if(tempBuffer[nTempLen] == tempBuffer[nTempLen - 1] &&
tempBuffer[nTempLen] == tempBuffer[nTempLen - 2])
{
nTempLen -= 2;
nSpelCount ++;
continue ;
}
}
nTempLen ++ ;
}
if(0 == nSpelCount && (nSkipIndex >= 0 && nSkipIndex < nLen))
return 0;
if(nTempLen <= 3)
return nSpelCount;
int nMaxCount = 0;
int nMaxIndex = 0;
int* maxIndexBuff = 0;
int nMaxIndexLen = 0;
for(int i = 1; i < nTempLen - 1; ++ i)
{
int* tempIndexBuff = new int[nTempLen];
int nTempIndexLen = 0;
int nTemp = numDispel(tempBuffer, nTempLen, i, tempIndexBuff, nTempIndexLen);
if(nTemp > nMaxCount)
{
nMaxCount = nTemp;
nMaxIndex = i;
if(maxIndexBuff)
{
delete[] maxIndexBuff;
}
maxIndexBuff = tempIndexBuff;
nMaxIndexLen = nTempIndexLen;
}
else
{
delete[] tempIndexBuff;
tempIndexBuff = 0;
}
}
if(maxIndexBuff)
{
maxIndexBuff[nMaxIndexLen] = nMaxIndex;
nMaxIndexLen ++;
for(int i = indexLen; i < indexLen + nMaxIndexLen; ++ i)
{
indexBuff[i] = maxIndexBuff[i - indexLen];
}
indexLen += nMaxIndexLen;
delete[] maxIndexBuff;
}
delete[] tempBuffer;
return (nSpelCount + nMaxCount);
}
int main(int argc, char* argv[])
{
char buff[] = "124332212321123123112113";
int nLen = sizeof(buff)/sizeof(char);
int* indexBuff = new int[nLen];
int nIndexLen = 0;
int nCount = numDispel(buff, nLen, -1, indexBuff, nIndexLen);
for(int i = nIndexLen - 1; i >= 0; -- i)
{
cout << indexBuff[i] << " ";
}
cout << endl;
return 0;
}