Leetcode299.猜数字游戏--两种解法

客官°小女子只卖身不卖艺 2023-01-07 07:10 170阅读 0赞

# 猜数字游戏的两种解法 #

### [题目链接][Link 1] ###

### 解题思路 ###

本题目的题意很清楚，如果猜测的数字的某位和结果数字的相同位置相等，则公牛数加1。如果猜测的数字的为结果数字中存在的数字但位置不同，则母牛数目加1并且结果数字中该位置被抵消。到这里，我们很显然可以使用HashMap解决此问题。

#### 方法一 ####

这是常规思路，即用HashMap去记录结果数字中存在的数字个数即可。

class Solution {
        
        public String getHint(String secret, String guess) {
        
            int x,y;
            x=y=0;
            int n=secret.length();
            HashMap<Character,Integer> hashmap=new HashMap<Character, Integer>();
            //实现自增操作
            for(int i=0;i<n;i++) {
        
            	if(secret.charAt(i)==guess.charAt(i)) x++;
            	else {
        
    	        	Integer cur=hashmap.getOrDefault(secret.charAt(i), 0);
    	        	cur++;
    	        	hashmap.put(secret.charAt(i), cur);
            	}
            }
            for(int i=0;i<n;i++) {
        
            	if(secret.charAt(i)!=guess.charAt(i)) {
        
            		Integer cur=hashmap.getOrDefault(secret.charAt(i), 0);
            		System.out.println(cur+" "+guess.charAt(i));
    	        	if(cur!=0) {
        
    	        		cur--;
    	        		y++;
    	        		hashmap.put(secret.charAt(i), cur);
    	        	}
            	}
            }
            String ret;
            ret=x+"A"+y+"B";
            return ret;
        }
    }

#### 方法二 ####

方法一中使用了两次for循环，我们可以通过正负抵消的方法将for循环变为一次，如果在结果数字中存在该数字，让该数字的映射自加1，如果在猜测数字中存在该数字，让该数字的映射自减1即可。

class Solution {
        
        public String getHint(String secret, String guess) {
        
            int len = secret.length();
            int[] cache = new int[10];
            int x = 0, y = 0;
            for (int i = 0; i < len; i++){
        
                char cs = secret.charAt(i);
                char cg = guess.charAt(i);
                if (cs == cg) {
        
                    x++;
                }else{
        
                    if (cache[cs - '0']++ < 0) y++;
                    if (cache[cg - '0']-- > 0) y++;
                }
            }
            return x+"A"+y+"B";
        }
    }

[Link 1]: https://leetcode-cn.com/problems/bulls-and-cows/