首页 > 试题广场 >

X游戏

[编程题]X游戏
  • 热度指数：6445 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？


输入描述:
输入正整数N


输出描述:
输出1到N中好数个数
示例1

输入

10

输出

4

说明

在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 15:49:31
精华题解 题目难度：二星 考察点：二分查找 方法：模拟 1.分析： 对于这个题我们首先要搞清楚什么样的数是“好数”，对于数字0-9，有如下三种情况: a. 0,1,8旋转180°之后是它本身； b. 2,5,6,9旋转180°之后是另外一个不同的数； 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 白伟仝
发表于 2020-05-08 10:03:34
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nex 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 cchangcs
发表于 2019-07-24 10:32:41
题目描述： 我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。 如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 岩之痕
发表于 2019-08-21 22:58:31
暴力搜索 复杂度O(NlogN) 暴力法，需要一个函数判断一个数是否是“好数”。好数可简化为不含3，4，7的且至少含一个2或5或6或9的数。对每个数，统计每个数字的出现数量再做判断即可。时间复杂度O(NlogN)，因为要取出每个数的每个数位。 数位DP 复杂度O(logN) 好数的个数 = （只 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 qcyeel
发表于 2021-09-05 09:23:26
javascript V8 var line = parseInt(readline()) var reg = new RegExp('\(3)|(4)|(7)') var reg2 = new RegExp('\(2)|(5)|(6)|(9)') function goodNum(line) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 brielle
发表于 2020-04-15 00:18:05
本题暴力遍历每个数再判断是否为好数是可以解决的，但是我这里提供一个非暴力的解法。(用数学找规律） 题目描述我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。 如果一个数的每位数字被旋转以后仍然还是一个数字， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 laglangyue
发表于 2020-06-01 19:22:59
排除掉坏数，剩下都是好数，坏数有两种： 只要有一位数字是3，4，7 这个数全是由0，1，8构成，不包含数字 2，5，6，9根据这两种规则可以写出judgeOK函数，然后可以在搜索上优化，本题不优化也能过将for循环变成while循环，当n的最高位是3，4，7可以直接跳过。这样能优化1/3显然这是 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 模拟 2019 数学 Java工程师 招商银行信用卡中心
上传者：小小
难度：
49条回答 7319浏览

热门推荐

通过挑战的用户

查看代码

相关试题

X游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号