首页 > 试题广场 >

珠玑妙算

[编程题]珠玑妙算

热度指数：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)

Java

Simms

巨麻烦，但是好懂

 public int[] calcResult(String A, String guess) {
        // write code here
        int [] res = new int[2];
        ArrayList<Character> deleted = new ArrayList<>();
        StringBuffer sb = new StringBuffer(A);
        StringBuffer sb2 = new StringBuffer(guess);

        int k =0;
        for(int i = 0; i < A.length(); i++){
            if(sb.charAt(i-k) == sb2.charAt(i-k)){
                res[0] ++;
                if(deleted.contains(sb.charAt(i-k))){
                    deleted.add(sb.charAt(i-k));
                }
                sb.deleteCharAt(i-k);
                sb2.deleteCharAt(i-k);
                k++;
            }
        }

        int length1 = sb.length();
        int length2 = sb2.length();
        k=0;
        for(int i = 0; i< length1; i++){
            for(int j = 0; j <length2 - k ; j++){
                if(sb.charAt(i-k) == sb2.charAt(j) && !deleted.contains(sb.charAt(i-k))){
                    res[1]++;
                    sb.deleteCharAt(i-k);
                    sb2.deleteCharAt(j);
                    k++;
                    break;
                }
            }
        }
        return res;
    }

发表于 2020-07-12 11:50:15 回复(0)

Java

派仔

import java.util.*;

public class Result {
    public int[] calcResult(String A, String guess) {
        int right = 0, unright = 0;
        boolean []visit = new boolean[guess.length()];
        for(int i=0;i<guess.length();i++){
            visit[i] = false;
        }
        for(int i=0;i<guess.length();i++){
            if(guess.charAt(i) == A.charAt(i)){
                right ++;
            }
        }
        for(int i=0;i<guess.length();i++){
            for(int j=0;j<A.length();j++){
                if(visit[j] == false && guess.charAt(i) == A.charAt(j)){
                    unright ++;
                    visit[j] = true;
                    break;
                }
            }
        }
        unright -= right;
        if(unright < 0)
            unright = 0;
        return new int []{ right, unright };
    }
}

编辑于 2019-01-17 23:07:25 回复(0)

Java

BrownLincoln

public class Result {
    public int[] calcResult(String A, String guess) {
        if(A == null || guess == null) return new int[2];
        int len = A.length();
        int hit = 0;
        int psudoHit = 0;
        int[] res = new int[2];
        //A和guess里的元素是否被使用。如果被使用过，则不能再被使用
        boolean[] markedA = new boolean[len];
        boolean[] markedG = new boolean[len];
        //先计算猜中的情况，优先
        for(int i = 0; i < len; i++) {
            char c = A.charAt(i);
            //猜中
            if(c == guess.charAt(i)) {
                markedA[i] = true;
                markedG[i] = true;
                hit++;
            }
        }
        for(int i = 0; i < len; i++) {
            if(!markedA[i]) {
                for(int j = 0; j < len; j++) {
                    if(!markedG[j] && A.charAt(i) == guess.charAt(j)) {
                        psudoHit++;
                        markedA[i] = true;
                        markedG[j] = true;
                        break;
                    }
                }
            }
        }
        res[0] = hit;
        res[1] = psudoHit;
        return res;
    }
}

发表于 2017-08-16 13:54:15 回复(0)

Java

zhiliye

import java.util.*;

public class Result {
    public int[] calcResult(String A, String guess) {
        // write code here
        int[] hit = new int[4];
        int[] res = new int[2];
        for(int i=0; i<4;i++){
            if(A.charAt(i)==guess.charAt(i)){
                res[0]++;
                hit[i] = 1;
            }
        }
        
        
        for(int i=0;i<4;i++){
            if(A.charAt(i)!=guess.charAt(i)){
                for(int j=0; j<4; j++){
                    if(A.charAt(j)==guess.charAt(i) && hit[j]==0){
                        res[1]++;
                        hit[j] = -1;
                        break;
                    }
                }
            }
        }
        return res;
    }
}

发表于 2017-07-31 11:30:18 回复(0)

Java

Holiday_12138

import java.util.*;

public class Result {
    public int[] calcResult(String A, String guess) {
        HashMap<Character,Integer> map1=new HashMap<Character,Integer>();
        HashMap<Character,Integer> map2=new HashMap<Character,Integer>();
        char[] color=new char[]{'R','Y','G','B'};
        for(int i=0;i<4;i++){
        	map1.put(color[i],0);
            map2.put(color[i],0);  
        }
        int[] res=new int[2];
        for(int i=0;i<4;i++){
            if(A.charAt(i)==guess.charAt(i))
                res[0]++;
            else{
                map1.put(A.charAt(i),map1.get(A.charAt(i))+1);
                map2.put(guess.charAt(i),map2.get(guess.charAt(i))+1);
            }
        }
        for(int i=0;i<4;i++){
            res[1]+=Math.min(map1.get(color[i]),map2.get(color[i]));
        }
        return res;
    }
}

发表于 2017-04-27 21:14:27 回复(0)