写点什么

猜数字游戏

作者:掘金安东尼
  • 2022-10-12
    广东
  • 本文字数:1291 字

    阅读完需:约 4 分钟

你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下:


写出一个秘密数字,并请朋友猜这个数字是多少。朋友每猜测一次,你就会给他一个包含下述信息的提示:


猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛),有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛)。也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。给你一个秘密数字 secret 和朋友猜测的数字 guess ,请你返回对朋友这次猜测的提示。


提示的格式为 "xAyB" ,x 是公牛个数, y 是奶牛个数,A 表示公牛,B 表示奶牛。


请注意秘密数字和朋友猜测的数字都可能含有重复数字。


示例 1:
输入:secret = "1807", guess = "7810"输出:"1A3B"解释:数字和位置都对(公牛)用 '|' 连接,数字猜对位置不对(奶牛)的采用斜体加粗标识。"1807" |"7810"
示例 2:
输入:secret = "1123", guess = "0111"输出:"1A1B"解释:数字和位置都对(公牛)用 '|' 连接,数字猜对位置不对(奶牛)的采用斜体加粗标识。"1123" "1123" | or |"0111" "0111"注意,两个不匹配的 1 中,只有一个会算作奶牛(数字猜对位置不对)。通过重新排列非公牛数字,其中仅有一个 1 可以成为公牛数字。
复制代码

题解

解法一:先匹配 Bulls,把找到的 Bulls 在两个数组中通过 splice 删除,剩下的就是 Cows,在用 indexOf 匹配到之后从 secret 中删除防止重复。也还是挺暴力的一种解法


var getHint = function(secret, guess) {        var sc = Array.from(secret);    var gue = Array.from(guess);    var A = 0;    var B = 0;    for (var i=0;i<sc.length;i++){                if(sc[i] == gue[i]){            A++;            sc.splice(i,1);            gue.splice(i--,1);        }            }    for(i=0;i<gue.length;i++){                if(sc.indexOf(gue[i])!=-1){            B++;            sc.splice(sc.indexOf(gue[i]),1);        }    }        return A + "A" + B + "B";};
复制代码


解法二:哈希表统计


/** * @param {string} secret * @param {string} guess * @return {string} */var getHint = function(secret, guess) {    let bulls = 0, cows = 0;    const n = secret.length, cntsS = new Map(), cntsG = new Map();    for(let i=0;i<n;i++){        const s = secret.charAt(i), g = guess.charAt(i);        if(s == g)            bulls++;        else{            if(cntsS.has(s))                cntsS.set(s, cntsS.get(s) + 1);            else                cntsS.set(s, 1);            if(cntsG.has(g))                cntsG.set(g, cntsG.get(g) + 1);            else                cntsG.set(g, 1);        }    }        for(const k of cntsS.keys()){        if(cntsG.has(k))            cows += Math.min(cntsS.get(k), cntsG.get(k));    }
return bulls + "A" + cows + "B";};
复制代码

总结

两个循环可以被一个 map 优化,这类题目可以汇总起来一起理解~

发布于: 刚刚阅读数: 4
用户头像

安东尼陪你度过漫长编程岁月~ 2022-07-14 加入

真正的大师,永远怀着一颗学徒的心(易)

评论

发布
暂无评论
猜数字游戏_算法_掘金安东尼_InfoQ写作社区