程序员面试金典16.15_go_珠玑妙算

程序员面试金典16.15_go_珠玑妙算

首页休闲益智猜对颜色更新时间:2024-07-21
题目

珠玑妙算游戏(the game of master mind)的玩法如下。

计算机有4个槽,每个槽放一个球,颜色可能是红色(R)、黄色(Y)、绿色(G)或蓝色(B)。

例如,计算机可能有RGGB 4种(槽1为红色,槽2、3为绿色,槽4为蓝色)。

作为用户,你试图猜出颜色组合。打个比方,你可能会猜YRGB。

要是猜对某个槽的颜色,则算一次“猜中”;要是只猜对颜色但槽位猜错了,则算一次“伪猜中”。

注意,“猜中”不能算入“伪猜中”。

给定一种颜色组合solution和一个猜测guess,

编写一个方法,返回猜中和伪猜中的次数answer,其中answer[0]为猜中的次数,answer[1]为伪猜中的次数。

示例:输入: solution="RGBY",guess="GGRR" 输出: [1,1]

解释: 猜中1次,伪猜中1次。

提示:len(solution) = len(guess) = 4

solution和guess仅包含"R","G","B","Y"这4种字符

解题思路分析

1、哈希辅助;时间复杂度O(1),空间复杂度O(1)

func masterMind(solution string, guess string) []int { m := make(map[byte]int) a, b := 0, 0 for i := 0; i < len(solution); i { if solution[i] == guess[i] { a } else { m[solution[i]] } } for i := 0; i < len(guess); i { if solution[i] != guess[i] { if m[guess[i]] > 0 { b m[guess[i]]-- } } } return []int{a, b} }

2、数组辅助;时间复杂度O(1),空间复杂度O(1)

func masterMind(solution string, guess string) []int { arr := [256]int{} a, b := 0, 0 for i := 0; i < len(solution); i { if solution[i] == guess[i] { a } else { arr[solution[i]] } } for i := 0; i < len(guess); i { if solution[i] != guess[i] { if arr[guess[i]] > 0 { b arr[guess[i]]-- } } } return []int{a, b} }总结

Easy题目,数据比较小,借助哈希或者数组统计即可

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved