游戏规则:
有四个插口, 可以放有四个球,颜色分别为红色(R),黄色(Y),绿色(G), 和蓝色(B),放的颜色顺序位置都可以是随机的,如:RYGB,YGRB等都是合法放置。
我们需要猜测四个颜色,比如原插口放置球是RGBY;我们猜测RRGG,那么第一个R正好对应我们有一个"hit",猜了个G,但是位置没对应,就有一个"pseudo-hit".而且不能算两个G,因为原插口只有一个G。
要我们设计一个算法可以返回hits和pseudo-hits的数量。
注意:插口有RGBY,猜GGRR只能是一个hit和一个pseudo hit。原书的程序应该是有点错误的,按他的程序这个解答就是1个hit和3个pseudo hit了。
先吃透他的规则,注意特殊情况,然后就好做了。
书中提到的注意地方:
1 代码清晰,比如定义一个结构体返回结果
2 定义额外函数
这里用到的一个最基础的知识就是计算排序counting sort,这个算法很重要,好像出现的地方很多,就算不是直接使用counting sort,类似的使用方法经常出现,比如这里也用到了相关知识。计数算法参考:http://blog.csdn.net/kenden23/article/details/12437455
程序:
#include<iostream>
using namespace std;
const int SLOTSCOLORS = 4;
int rgbyToIndex(char c)
{
switch (c)
{
case 'R':
return 0;
break;
case 'G':
return 1;
break;
case 'B':
return 2;
break;
case 'Y':
return 3;
break;
default:
return -1;
break;
}
}
struct Result
{
int hits;
int pseudoHits;
Result():hits(0), pseudoHits(0){}
};
Result guessHits(char *slots, char *guess)
{
if (slots == nullptr || guess == nullptr)
{
return Result();
}
Result res;
int counting[SLOTSCOLORS];
for (int i = 0; i < SLOTSCOLORS; i++)
{
if(guess[i] == slots[i])
{
res.hits ++;
//注意:要把数组加标志-1,标明是hit,就不能计算入pseudo-hit了。
counting[rgbyToIndex(guess[i])] = -1;
}
else if (counting[rgbyToIndex(guess[i])] != -1)
{
counting[rgbyToIndex(guess[i])] = 1;
}
}
for (int i = 0; i < SLOTSCOLORS; i++)
{
if(counting[i] == 1)
res.pseudoHits ++;
}
return res;
}
int main()
{
char slots[4] = {'R','G','B','Y'};
char guess[4] = {'G','G','R','R'};
Result res = guessHits(slots, guess);
cout<<"hits : pseudo hits\n";
cout<<res.hits<<" : "<<res.pseudoHits<<endl;
system("pause");
return 0;
}
运算结果:
Reference:
Cracking the coding interview
分享到:
相关推荐
c++面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试...
面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题...
【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】...
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
flahas3.0面试题 flash as3.0面试题 as3.0面试题 as3.0面试题最新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新...
2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里...
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
最全的j2EE面试题,题量大、经典,是我面试的整理试题 1、java笔试题大集合 2、各个公司面试题 3、J2EE初学者面试题 4、J2EE面试题(打码查错题) 5、java_华为笔试题 6、java常见面试题 7、java程序员面试宝典 8、...
.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题
JavaOOP面试题 Java集合/泛型面试题 Java异常面试题 Java中的IO与NIO面试题 Java反射面试题 Java序列化面试题 Java注解面试题 多线程&并发面试题 JVM面试题 Mysql面试题 Redis面试题 Memcached面试题 MongoDB面试题 ...
c#笔试面试题 c#笔试面试题 c#笔试面试题 c#笔试面试题 c#笔试面试题
ERP工程师面试题ERP工程师面试题ERP工程师面试题ERP工程师面试题
java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题...
.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题
面试题 面试题 面试题 面试题 面试题 面试题 面试题
数据库面试题数据库面试题数据库面试题数据库面试题数据库面试题数据库面试题数据库面试题数据库面试题
大数据面试题V3.0完成了。共523道题,679页,46w+字,来源于牛客870+篇面经。 主要分为以下几部分: Hadoop面试题:100道 Zookeeper面试题:21道 Hive面试题:47道 Flume面试题:11道 Kafka面试题:59到 HBase面试题...
最新各大公司企业真实面试题-Java面试题最新各大公司企业真实面试题-Java面试题
2022java面试题、JVM面试题、多线程面试题、并发编程、Redis面试题、MySQL面试题、Java2022面试题、Netty面试题、Elasticsearch面试题、Tomcat面试题、Dubbo面试题、Kafka面试题、Linux面试题、2021面试题、java面试...