当前位置: 首页 > news >正文

广安建设厅官方网站福田祥菱官网

广安建设厅官方网站,福田祥菱官网,wordpress更新配置文件,四川建设网地址电话文章目录题目标题和出处难度题目描述要求示例数据范围解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目 标题和出处 标题:猜数字游戏 出处:299. 猜数字游戏 难度 4 级 题目描述 要求 你在和朋友一起玩猜数字(Bulls…

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:猜数字游戏

出处:299. 猜数字游戏

难度

4 级

题目描述

要求

你在和朋友一起玩猜数字(Bulls and Cows)游戏。

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

  • 「公牛」的数量,即猜测数字中有多少位数字在秘密数字中出现且位置正确。
  • 「奶牛」的数量,即猜测数字中有多少位数字在秘密数字中出现但位置错误,即猜测数字中有多少位非公牛数字可以通过重新排列变成公牛数字。

给你一个秘密数字 secret\texttt{secret}secret 和朋友猜测的数字 guess\texttt{guess}guess,请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB"\texttt{"xAyB"}"xAyB"x\texttt{x}x 是公牛个数,y\texttt{y}y 是奶牛个数。请注意 secret\texttt{secret}secretguess\texttt{guess}guess 都可能含有重复数字。

示例

示例 1:

输入:secret="1807",guess="7810"\texttt{secret = "1807", guess = "7810"}secret = "1807", guess = "7810"
输出:"1A3B"\texttt{"1A3B"}"1A3B"
解释:数字和位置都对(公牛)用 ‘|’\texttt{`|'}‘|’ 连接,数字猜对位置不对(奶牛)用下划线表示。
"1807"\texttt{"1807"}"1807"
|\texttt{~~|}  |
"7‾810‾"\texttt{"}\underline{\texttt{7}}\texttt{8}\underline{\texttt{10}}\texttt{"}"7810"

示例 2:

输入:secret="1123",guess="0111"\texttt{secret = "1123", guess = "0111"}secret = "1123", guess = "0111"
输出:"1A1B"\texttt{"1A1B"}"1A1B"
解释:数字和位置都对(公牛)用 ‘|’\texttt{`|'}‘|’ 连接,数字猜对位置不对(奶牛)用下划线表示。
"1123"\texttt{"1123"}"1123"
|\texttt{~~|}  |
"011‾1"\texttt{"01}\underline{\texttt{1}}\texttt{1"}"0111"

"1123"\texttt{"1123"}"1123"
|\texttt{~~|}  |
"0111‾"\texttt{"011}\underline{\texttt{1}}\texttt{"}"0111"
注意,两个不匹配的 1\texttt{1}1 中,只有一个会算作奶牛(数字猜对位置不对),因为通过重新排列非公牛数字之后只有一个 1\texttt{1}1 可以成为公牛数字。

示例 3:

输入:secret="1",guess="0"\texttt{secret = "1", guess = "0"}secret = "1", guess = "0"
输出:"0A0B"\texttt{"0A0B"}"0A0B"

示例 4:

输入:secret="1",guess="1"\texttt{secret = "1", guess = "1"}secret = "1", guess = "1"
输出:"1A0B"\texttt{"1A0B"}"1A0B"

数据范围

  • 1≤secret.length,guess.length≤1000\texttt{1} \le \texttt{secret.length, guess.length} \le \texttt{1000}1secret.length, guess.length1000
  • secret.length=guess.length\texttt{secret.length = guess.length}secret.length = guess.length
  • secret\texttt{secret}secretguess\texttt{guess}guess 仅由数字组成

解法一

思路和算法

公牛为 secret\textit{secret}secretguess\textit{guess}guess 的相同下标处数字相同的下标个数,统计公牛的方法是:同时遍历 secret\textit{secret}secretguess\textit{guess}guess,对于每个下标,如果 secret\textit{secret}secretguess\textit{guess}guess 在相同下标处的数字相同,则将公牛的数量加 111

奶牛为 secret\textit{secret}secretguess\textit{guess}guess 的不同下标处数字相同的下标个数,统计奶牛的方法是:使用两个哈希表分别记录 secret\textit{secret}secretguess\textit{guess}guess 中的每个数字的出现次数(排除公牛的情况),同时遍历 secret\textit{secret}secretguess\textit{guess}guess,对于每个下标,如果 secret\textit{secret}secretguess\textit{guess}guess 在相同下标处的数字不同,则将该下标处的两个数字在对应的哈希表中的出现次数分别加 111,遍历结束之后,000999 的每个数字在奶牛中的数量为该数字在两个哈希表中的出现次数的较小值,计算每个数字在奶牛中的数量之和,即为奶牛的数量。

由于统计公牛和奶牛都需要同时遍历 secret\textit{secret}secretguess\textit{guess}guess,因此可以在一次遍历中完成统计公牛和奶牛的操作。遍历过程中,如果 secret\textit{secret}secretguess\textit{guess}guess 在相同下标处的数字相同则将公牛的数量加 111,如果 secret\textit{secret}secretguess\textit{guess}guess 在相同下标处的数字不同则将该下标处的两个数字在 secret\textit{secret}secretguess\textit{guess}guess 中的出现次数分别加 111,遍历结束之后遍历 000999secret\textit{secret}secretguess\textit{guess}guess 中的出现次数,统计奶牛的数量。

实现方面,由于数字范围是 000999,因此可以使用两个数组分别记录 secret\textit{secret}secretguess\textit{guess}guess 中的每个数字的出现次数。

代码

class Solution {public String getHint(String secret, String guess) {int bulls = 0, cows = 0;int[] secretCounts = new int[10];int[] guessCounts = new int[10];int length = secret.length();for (int i = 0; i < length; i++) {int secretDigit = secret.charAt(i) - '0';int guessDigit = guess.charAt(i) - '0';if (secretDigit == guessDigit) {bulls++;} else {secretCounts[secretDigit]++;guessCounts[guessDigit]++;}}for (int i = 0; i < 10; i++) {cows += Math.min(secretCounts[i], guessCounts[i]);}return String.format("%dA%dB", bulls, cows);}
}

复杂度分析

  • 时间复杂度:O(n+C)O(n + C)O(n+C),其中 nnn 是字符串 secret\textit{secret}secretguess\textit{guess}guess 的长度,CCC 是数字的个数,C=10C = 10C=10。需要 O(n)O(n)O(n) 的时间遍历字符串 secret\textit{secret}secretguess\textit{guess}guess 各一次统计公牛数量和每个数字的出现次数,需要 O(C)O(C)O(C) 的时间遍历 000999 的所有数字统计奶牛数量。

  • 空间复杂度:O(C)O(C)O(C),其中 CCC 是数字的个数,C=10C = 10C=10。需要使用两个哈希表分别记录 secret\textit{secret}secretguess\textit{guess}guess 中的每个数字的出现次数。

解法二

思路和算法

解法一需要使用两个哈希表分别记录 secret\textit{secret}secretguess\textit{guess}guess 中的每个数字的出现次数,在遍历 secret\textit{secret}secretguess\textit{guess}guess 之后还需要遍历 000999 的每个数字计算奶牛的数量。可以只用一个哈希表,在遍历 secret\textit{secret}secretguess\textit{guess}guess 的同时计算奶牛的数量。

使用一个哈希表记录每个数字的出现次数(排除公牛的情况),遍历 secret\textit{secret}secretguess\textit{guess}guess 的过程中,对于 secret\textit{secret}secret 中出现的每个数字将出现次数加 111,对于 guess\textit{guess}guess 中出现的每个数字将出现次数减 111。上述操作的思想是:对于 secret\textit{secret}secret 中的每个数字,只有当 guess\textit{guess}guess 中存在一个不同位置的相同数字时,才是一个奶牛,反之亦然。

当遍历到一个下标时,将 secret\textit{secret}secretguess\textit{guess}guess 在该下标处的数字分别记为 secretDigit\textit{secretDigit}secretDigitguessDigit\textit{guessDigit}guessDigit,如果 secretDigit=guessDigit\textit{secretDigit} = \textit{guessDigit}secretDigit=guessDigit 则将公牛的数量加 111,如果 secretDigit≠guessDigit\textit{secretDigit} \ne \textit{guessDigit}secretDigit=guessDigit 则按照如下操作统计奶牛:

  1. 如果哈希表中 secretDigit\textit{secretDigit}secretDigit 的出现次数小于 000,则在之前遍历的 guess\textit{guess}guess 的数字中有多余的 secretDigit\textit{secretDigit}secretDigit,因此将奶牛的数量加 111

  2. 如果哈希表中 guessDigit\textit{guessDigit}guessDigit 的出现次数大于 000,则在之前遍历的 secret\textit{secret}secret 的数字中有多余的 guessDigit\textit{guessDigit}guessDigit,因此将奶牛的数量加 111

  3. secretDigit\textit{secretDigit}secretDigit 在哈希表中的出现次数加 111,将 guessDigit\textit{guessDigit}guessDigit 在哈希表中的出现次数减 111

遍历结束之后,即可知道奶牛的数量。

代码

class Solution {public String getHint(String secret, String guess) {int bulls = 0, cows = 0;int[] digits = new int[10];int length = secret.length();for (int i = 0; i < length; i++) {int secretDigit = secret.charAt(i) - '0';int guessDigit = guess.charAt(i) - '0';if (secretDigit == guessDigit) {bulls++;} else {if (digits[secretDigit] < 0) {cows++;}if (digits[guessDigit] > 0) {cows++;}digits[secretDigit]++;digits[guessDigit]--;}}return String.format("%dA%dB", bulls, cows);}
}

复杂度分析

  • 时间复杂度:O(n)O(n)O(n),其中 nnn 是字符串 secret\textit{secret}secretguess\textit{guess}guess 的长度。需要遍历字符串 secret\textit{secret}secretguess\textit{guess}guess 各一次统计公牛数量和奶牛数量。

  • 空间复杂度:O(C)O(C)O(C),其中 CCC 是数字的个数,C=10C = 10C=10。需要使用一个哈希表记录每个数字的出现次数。

http://www.yayakq.cn/news/192628/

相关文章:

  • 毕业设计可以做自己的网站吗毕业设计做网站想法
  • 越秀电子商务网站建设宁波网络推广公司价格
  • 大连门户网站开发济南网站系统优化
  • 公司网站设计的费用wordpress 链接失效
  • 沈阳建站公司模板淘宝网站建设策划报告
  • ps做网站的效果图网站制作 苏州
  • 附近建网站公司济南网站建设模板
  • 建站之星怎么收费企业网站icp备案
  • 网站开发哪家公司好做网站需要学编程吗
  • hao123网站用什么程序做的网站建设选哪家
  • 清河做网站哪家好网页制作用什么软件
  • wordpress批量删除文章seo 网站换程序
  • 微网站建设开发工具在百度上做网站推广效果怎么样
  • 网站开发工程师分析wordpress指定文章p=
  • 做类似起点的网站盐城公司网站建设
  • 关于建设网站的请示报告推动门户网站建设不断优化升级
  • 网站优化怎么弄怎样学做网络推广
  • 网站建设的目标及服务对象新公司做网站多少钱
  • 中山外贸网站建设报价门户网站建设案例
  • 网站建设服务费怎么入账个人订阅号支持微网站的建设吗
  • 网站优化公司哪家便宜网站后台 验证码错误
  • 中国建筑业未来发展展望昆山seo网站优化软件
  • 网站友情链接形式建立网站条件
  • 专业创业服务平台网站建设需求高唐建筑公司网站
  • 网吧网络维护公司wordpress目录页seo
  • 郑州做网站软件乡镇网站建设自查报告
  • 有专业做线切割配件的网站吗wordpress 免费主机
  • 房地产网站开发毕业设计宁波做企业网站公司
  • 电子商务网站建设外包服务的企业安卓定制v
  • 如何用ps做网站平面图wordpress左侧悬浮导航菜单源码