首页 > 试题广场 >

珠玑妙算

[编程题]珠玑妙算

热度指数：7154 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现有一堆球颜色是红色(R)、黄色(Y)、绿色(G)或蓝色(B)各若干个，现在随机选四个球分别放入四个槽中，得到一个序列。例如，RGGB(槽1为红色，槽2、3为绿色，槽4为蓝色)，需要你猜出这个颜色序列的组合。比如，你可能猜YRGB。要是猜对了某个槽的颜色，则算一次“猜中”。要是只是猜对了颜色但槽位猜错了，则算为一次“伪猜中”。要注意，“猜中”不能算入“伪猜中”。给定两个string A和guess。分别表示颜色序列的组合和一个猜测。需要返回一个int数组，数组第一个元素为猜中的次数，第二个元素为伪猜中的次数。

测试样例：

"RGBY","GGRR"

返回：[1,1]

算法知识视频讲解

推荐

orgcheng

从题目中可以获取隐含信息：
“猜中” 属于 “伪猜中”，但是反过来不成立。

所有需要先统计猜中，
然后再统计伪猜中个数= 可能的伪猜中个数 - 猜中个数

因此代码就比较容易写出来

import java.util.*;

public class Result {
	public int[] calcResult(String A, String guess) {
		if (A == null || guess == null) {
			return new int[] { 0, 0 };
		}
		// right 表示猜中
		// unright 表示伪猜中
		int right=0,unright=0;
		// 保存A中的<字符,字符个数>
		HashMap<Character, Integer> map = new HashMap<>();
		
		for (int i = 0; i < A.length(); ++i){
			// 统计猜中
			if(A.charAt(i) == guess.charAt(i))
				++right;
			
			// 获取A中的<字符,字符个数>
			Integer val = map.get(A.charAt(i));
			if(val==null){
				val=1;
			}else{
				val++;
			}
			map.put(A.charAt(i), val);
		}
		
		// 统计伪猜中的个数（猜中也属于伪猜中）
		for(int i=0;i<guess.length();++i){
			Integer val = map.get(guess.charAt(i));
			if(val != null && val >0){
				unright++;
				val--;
				if(val<0)
					val=0;
				map.put(guess.charAt(i), val);
			}
		}
		// 从伪猜中当中，去除猜中个数
		unright -=right;
		if(unright<0)unright = 0;
		return new int[] { right, unright };
	}
}

编辑于 2015-08-10 15:27:33 回复(1)

Python

Yannyezixin

先算出伪猜中，此时伪猜中中包含了猜中，再算出猜中，用伪猜中减去猜中就是最后正确的伪猜中个数

# -*- coding:utf-8 -*-

class Result:
    def calcResult(self, A, guess):
        t = ['R', 'Y', 'G', 'B']
        
        persudo = 0
        for i in t:
            persudo += min(A.count(i), guess.count(i))
        
        sum = 0
        for i in range(len(A)):
            if A[i] == guess[i]:
                sum += 1
                persudo -= 1
        return sum, persudo

发表于 2016-08-09 12:45:16 回复(0)