[leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏

简介: [leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏

描述
你正在和你的朋友玩 猜数字 (Bulls and Cows)游戏:你写下一个数字让你的朋友猜。每次他猜测后,你给他一个提示,告诉他有多少位数字和确切位置都猜对了(称为“Bulls”, 公牛),有多少位数字猜对了但是位置不对(称为“Cows”, 奶牛)。你的朋友将会根据提示继续猜,直到猜出秘密数字。
请写出一个根据秘密数字和朋友的猜测数返回提示的函数,用 A 表示公牛,用 B 表示奶牛。

  • 请注意秘密数字和朋友的猜测数都可能含有重复数字。
  • 你可以假设秘密数字和朋友的猜测数都只包含数字,并且它们的长度永远相等。

在线评测地址:领扣题库官网

样例1
输入:secret = "1807", guess = "7810"
输出:"1A3B"
解释:1 公牛和 3 奶牛。公牛是 8,奶牛是 0, 1 和 7。
样例2
输入:secret = "1123", guess = "0111"
输出:"1A1B"
解释:朋友猜测数中的第一个 1 是公牛,第二个或第三个 1 可被视为奶牛。

解题思路

  • 哈希表

题解:第一遍遍历计算所有相同位置大小相同的个数,分别用大小为10的数组记录两个字符串每个数字出现的次数,第二次遍历数组,相同的次数为对应位置的最小值。

class Solution {
    public String getHint(String secret, String guess) {
        int a = 0,b = 0, n = secret.length();
        int[] ds = new int[10];
        int[] dg = new int[10];
        for(int i = 0; i < n; i++){
            int x = secret.charAt(i)-'0';
            int y = guess.charAt(i)-'0';
            if(x == y) {
                a++;
            }
            ds[x]++;
            dg[y]++;
        }
        for(int i = 0; i < 10; i++) {
            b += Math.min(ds[i],dg[i]);
        }
        return a+""+'A'+(b-a)+""+'B';
    }
}

更多题解参考:九章官网solution

相关文章
|
算法 Go 索引
【LeetCode 热题100】45:跳跃游戏 II(详细解析)(Go语言版)
本文详细解析了力扣第45题“跳跃游戏II”的三种解法:贪心算法、动态规划和反向贪心。贪心算法通过选择每一步能跳到的最远位置,实现O(n)时间复杂度与O(1)空间复杂度,是面试首选;动态规划以自底向上的方式构建状态转移方程,适合初学者理解但效率较低;反向贪心从终点逆向寻找最优跳点,逻辑清晰但性能欠佳。文章对比了各方法的优劣,并提供了Go语言代码实现,助你掌握最小跳跃次数问题的核心技巧。
795 15
|
机器学习/深度学习 人工智能 算法
当AI提示词遇见精密算法:TimeGuessr如何用数学魔法打造文化游戏新体验
TimeGuessr融合AI与历史文化,首创时间与空间双维度评分体系,结合分段惩罚、Haversine距离计算与加权算法,辅以连击、速度与完美奖励机制,实现公平且富挑战性的游戏体验。
|
算法
面试场景题:如何设计一个抢红包随机算法
本文详细解析了抢红包随机算法的设计与实现,涵盖三种解法:随机分配法、二倍均值法和线段切割法。随机分配法通过逐次随机分配金额确保总额不变,但易导致两极分化;二倍均值法优化了金额分布,使每次抢到的金额更均衡;线段切割法则将总金额视为线段,通过随机切割点生成子金额,手气最佳金额可能更高。代码示例清晰,结果对比直观,为面试中类似算法题提供了全面思路。
2449 16
|
算法 Go
【LeetCode 热题100】55:跳跃游戏(详细解析)(Go语言版)
本篇解析详细讲解了 LeetCode 热题 55——跳跃游戏(Jump Game)。通过判断是否能从数组起点跳至终点,介绍了两种高效解法:贪心算法和反向思维。贪心法通过维护最远可达位置 `maxReach` 实现一次遍历,时间复杂度 O(n),空间复杂度 O(1);反向法则从终点回溯,判断是否可到达起点。两者均简洁高效,适合面试使用。延伸题目如 LeetCode 45 进一步提升挑战。
691 7
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
935 16
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
336 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
640 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行

热门文章

最新文章