首页 > 试题广场 >

X游戏

[编程题]X游戏
  • 热度指数:6393 时间限制: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 不是好数, 因为他们在旋转之后不变。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Solution4_X游戏 {

    static HashMap<Character, Character> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');
        map.put('2', '5');
        map.put('5', '2');
        map.put('6', '9');
        map.put('9', '6');
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isGoodNum(i)) count++;
        }
        System.out.println(count);
    }

    //自己第一时间写的,相比下面的方法显得有些笨重了...
    private static boolean isGoodNum(int x) {
        String s = String.valueOf(x);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                sb.append(map.get(s.charAt(i)));
            } else {
                return false;
            }
        }
        return x == Integer.parseInt(sb.toString()) ? false : true;
    }


    /**
     * 此法更优,如果数字是 0 1 8,flag不需要变,它序x值相等
     */
    private static boolean isGoodNum1(int x) {
        boolean flag = false;
        int a = 0;
        while (x > 0) {
            a = x % 10;
            if (a == 3 || a == 4 || a == 7) {
                return false;
            } else if (a == 2 || a == 5 || a == 6 || a == 9) {
                flag = true;
            }
            x /= 10;
        }
        return flag;
    }
}
发表于 2019-08-09 21:06:42 回复(0)
好数必须不包含3,4,7,且至少包含2,5,6,9中的任意一个
n = int(input())
cnt = 0
for i in range(1, n + 1):
    numSet = set(list(str(i)))
    if ('2' in numSet&nbs***bsp;'5' in numSet&nbs***bsp;'6' in numSet&nbs***bsp;'9' in numSet) and ('3' not in numSet and '4' not in numSet and '7' not in numSet):
        cnt += 1
print(cnt)

发表于 2021-04-09 10:53:28 回复(0)
比较暴力的方法,每次都进行判断
/*
我的想法是将每个数都拆开,看看他里面是不是只包含0,1,2,5,6,8,9,并且旋转之后两个数是否一样
*/
import java.util.Scanner;
public class Main{
    //判断是否是好数
    public static boolean isGood(int num){
        String str = String.valueOf(num);
        StringBuffer sb = new StringBuffer();
        sb.append(str);//将整数转成字符串
        for(int i = 0;i<sb.length();i++){
            if(sb.charAt(i)=='0'){
                sb.setCharAt(i,'0');
            }else if(sb.charAt(i)=='1'){
                sb.setCharAt(i,'1');
            }else if(sb.charAt(i)=='2'){
                sb.setCharAt(i,'5');
            }else if(sb.charAt(i)=='5'){
                sb.setCharAt(i,'2');
            }else if(sb.charAt(i)=='6'){
                sb.setCharAt(i,'9');
            }else if(sb.charAt(i)=='9'){
                sb.setCharAt(i,'6');
            }else if(sb.charAt(i)=='8'){
                sb.setCharAt(i,'8');
            }
            else{
                return false;
            }
        }
        //判断旋转之后两个数是否一样
        int newnum = Integer.parseInt(sb.toString());
        if(newnum!=num)return true;
        return false;
    }
    
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int count = 0;//记录个数
        for(int i = 1;i<=N;i++)
            if(isGood(i))
                count++;
        System.out.println(count);
    }
}


发表于 2020-04-19 16:45:10 回复(0)
思路简单:判断一个数是不是好数,必须有一位或一位以上的位是好数(2,5,6,9),然后其他位也必须是对称数(0,1,8)
#include<iostream>
using namespace std;
bool good(int);
int main()
{
    int n;
    while(cin>>n)
    {
        int count =0;
        for(int i=1;i<=n;i++)
        {
            if(good(i))count++;
        }
        cout<<count<<endl;
    }
    return 0;
}
bool good(int a)
{
    int go=0;
    while(a)
    {
        int t=a%10;
        if(t==2||t==5||t==6||t==9)go++;
        if(t==3||t==4||t==7)return false;
        a=a/10;
    }
    if(go>0)return true;
    else return false;
}
发表于 2019-08-22 20:14:42 回复(0)
"""
暴力枚举,判断是不是好数
"""
def is_good(s):
    if '3' in s or '4' in s or '7' in s:
        return False
    if '2' in s or '5' in s or '6' in s or '9' in s:
        return True
    return False


if __name__ == "__main__":
    N = int(input().strip())
    ans = 0
    for i in range(1, N + 1):
        if is_good(str(i)):
            ans += 1
    print(ans)

编辑于 2019-07-10 17:03:13 回复(0)
#include <bits/stdc++.h>
using namespace std;
bool f(string s){
int l = s.length();
bool change = false;
for(int i=0;i<l;i++){
if(s[i]=='2' || s[i]=='5' || s[i]=='6' || s[i]=='9'){
change = true;
continue;
}else if(s[i]=='1' || s[i]=='0' || s[i]=='8')
continue;
else
return false;
}
if(change)
return true;
else
return false;
}
int main(){
long n, cnt=0;
cin>>n;
for(long i=1;i<=n;i++){
string s = to_string(i);
if(f(s))
cnt++;
}
cout<<cnt<<endl;
return 0;
}

发表于 2019-07-07 23:33:28 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,res=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s=to_string(i);
        if((s.find("3")== string::npos&&s.find("4")== string::npos&&s.find("7")== string::npos)&&(s.find("2")!= string::npos||s.find("5")!= string::npos||s.find("6")!= string::npos||s.find("9")!= string::npos))
            res++;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-07-02 16:59:27 回复(0)
importjava.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();  //得到输入数的大小
        int count=0;  //统计
        for(int i=1;i<=n;i++){
            count+=isX(i);
        }
        System.out.println(count);
    }
    public static int isX(int x){
        String str=x+""; //转化为字符串
        if(str.contains("3")||str.contains("4")||str.contains("7")){
            return 0;  //有3,4,7都不满足条件
        }
        if(str.contains("2")||str.contains("5")||str.contains("6")||str.contains("9")){
            return 1;  //没有3,4,7,但是至少得包含一个转180度数字变化的数
        }
        return 0;
    }
}

编辑于 2019-02-26 16:04:42 回复(0)

以下是思路代码,没有通过cases,貌似有地方挂掉了
而且事实上这个代码的效率低于暴力穷举……
但我还是把这个贴出来,因为这个思路的正确写法效率可以很高。
以下是错误代码:

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
struct item {
    int nums[10];
};
class Solution {
    public :
    // 入口
    int solve(int n) {
        // 存每一位的数字
        vector<int> mods;
        // 统计有多少位
        int k = get_k(n, mods);
        // 分别对有效数和好数进行dp
        vector<item> dp0;
        vector<item> dp1;
        make_dp(k, dp0, dp1);
        int count = 0;
        // 当某一位确定强有效时变为真
        bool flag = false;
        for(int i=k-1; i>=0; i--) {
            int m = mods[i];
            // 值为1代表强有效,0代表弱有效,-1代表无效
            int u = is_useful(m);
            // 如果前面有一位已经是强有效了,那么后面弱有效就可以了
            if(flag) {
                if(u == -1) {
                    count += dp0[i].nums[m-1];
                    break;
                } else {
                    count += dp0[i].nums[m-1];
                }
            } else {
                if(u == -1) {
                    count += dp1[i].nums[m-1];
                    break;
                } else if(u == 0) {
                    count += dp1[i].nums[m-1];
                } else {
                    count += dp0[i].nums[m-1];
                    flag = true;
                }
            }
        }
        return count;
    }

    void make_dp(int k, vector<item> &dp0, vector<item> &dp1) {
        item item0; int a[] = {1,2,3,3,3,4,5,5,6,7};
        item item1; int b[] = {1,2,3,3,3,4,5,5,6,7};
        memcpy(item0.nums, a, sizeof(a));
        memcpy(item1.nums, b, sizeof(b));
        dp0.push_back(item0);
        dp1.push_back(item1);
        for(int i=1; i<k; i++) {
            item marks0;
            item marks1;
            marks0.nums[0] = pow(7,i);
            marks1.nums[0] = dp1.back().nums[9];
            for(int m=1; m<10; m++) {
                int u = is_useful(m);
                if(u==-1) {
                    marks0.nums[m] = marks0.nums[m-1];
                    marks1.nums[m] = marks1.nums[m-1];
                } else if(u==0) {
                    marks0.nums[m] = marks0.nums[m-1] + marks0.nums[0];
                    marks1.nums[m] = marks1.nums[m-1] + marks1.nums[0];
                } else {
                    marks0.nums[m] = marks0.nums[m-1] + marks0.nums[0];
                    marks1.nums[m] = marks1.nums[m-1] + marks0.nums[0];
                }
            }
            dp0.push_back(marks0);
            dp1.push_back(marks1);
        }
    }

    int is_useful(int m) {
        if(m==3||m==4||m==7) return -1;
        if(m==0||m==1||m==8) return 0;
        return 1;
    }

    int get_k(int n, vector<int> mods) {
        int k=0;
        while(n!=0) {
            mods.push_back(n % 10);
            k++;
            n/=10;
        }
        return k;
    }

    int pow(int x, int p) {
        int r = 1;
        while(p-->0) {
            r*=x;
        }
        return r;
    }
};

int main(void) {
    int n;
    scanf("%d", &n);
    int result = Solution().solve(n);
    printf("%d", result);
}
编辑于 2018-11-27 20:06:08 回复(0)
我的理解,就是如果是好数,那么这个数,各位上都要是0 1 2 5 6 8 9其中的一个数,那就很好办了,写个方法,传入这个好数n,把n变成char数组,遍历数组,比较每位上的数字是否是3 4 7,如果是,直接返回false,这个数就不是好数,否则就是好数。 然后在主方法中从1开始一直到这个数,循环遍历调用上面那个方法,返回一次true,就有一个好数 思路就是这样,代码写好,已验证,手机打的,有时间发代码。
编辑于 2018-11-16 20:42:18 回复(3)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            String str = String.valueOf(i);
            // 包含2、5、6、9中任意个,且不包含3、4、7的即为好数
            if ((str.contains("2") || str.contains("5") || str.contains("6") || str.contains("9")) && (!str.contains("3") && !str.contains("4") && !str.contains("7"))) {
                count++;
            }
        }
        System.out.println(count);
    }
}
发表于 2019-07-02 16:01:26 回复(0)
英雄器短,我就是最短的。
满足的字符串必须不包含347;并且包含2569;
所以轻松就过了
#include <iostream>
using namespace std;

int main()
{
    int num = 0;
    cin>>num;
    int counter = 0;
    string other = "2569";
    string bad = "347";
    for(int i=2;i<=num;i++)
    {
        string str = to_string(i);
        if(str.find_first_of(bad) == str.npos && str.find_first_of(other) != str.npos)
            counter++;
    }

    cout<<counter<<endl;
    return 0;
}


发表于 2019-08-23 18:04:49 回复(0)
可以用排列组合的方法解决,速度是常数级
比如1~98752
(1)先看最高位以下,即1~89999,看每一位能放的数字,可用数字是0125689,其中翻转相同有018,所以,最高位能放012568共6种可能,其余位均有7种可能,组合共6*7*7*7*7,这其中包含了翻转相同,所以要减去3*3*3*3*3,第一个3表示最高位1~8中翻转相同的数字个数,其余位均有3种可能。
(2)第一位从1~8已经放过了,那么固定第一位为9,剩下的继续排列组合。注意,如果固定的位中出现过2,5,6,9,即翻转后不同,那么后续计算不再减去翻转相同的组合,因为有翻转不同的数字固定了。注意,如果固定位出现了翻转无意义数字,则停止计算。
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main()
{
    int N, count = 0;
    int flag[10] {1,1,2,0,0,2,2,0,1,2};//这个数的性质,不可翻,翻转相同,翻转不同
    int T[10] {1,2,3,3,3,4,5,5,6,7};//这个数字之前有多少个可翻转
    int F[10] {1,2,2,2,2,2,2,2,3,3};//之前有多少个翻转相同
    vector<int> n;
    cin>>N;
    while(N!=0)
    {
        n.push_back(N%10);
        N /= 10;
    }
    count += T[n[n.size()-1]-1] * pow(7, n.size()-1) - F[n[n.size()-1]-1] * pow(3,n.size()-1);

    bool f = false;
    if(flag[n[n.size()-1]] == 2) f = true; //存在翻转不同
    int i;
    for(i = n.size()-2; i >= 0; i--)
    {
        if(n[i]==0) continue;
        if(flag[n[i+1]] == 0) break;
        count += T[n[i]-1] * pow(7, i);
        if(!f) count -= F[n[i]-1] * pow(3, i);//不存在翻转不同
        if(flag[n[i]] == 2) f = true;//出现了翻转不同的数字
    }
    if(flag[n[i+1]] != 0 && n[i] == 0 && f) count++;//最后一位是0且最大数是好数
    cout<<count;
}


发表于 2019-12-14 11:46:05 回复(0)
一次过
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            boolean is_goodNum = false;
            boolean is_badNum = false;
            int mod = i;
            while (mod > 0) {
                int yu = mod % 10;
                if (yu == 2 || yu == 5 || yu == 6 || yu == 9) {
                    is_goodNum = true;
                }
                if (yu == 3 || yu == 4 || yu == 7) {
                    is_badNum = true;
                }
                mod /= 10;
            }
            if (is_goodNum == true && is_badNum == false) {
                count++;
            }
        }
        sc.close();
        System.out.println(count);
    }
}


发表于 2022-09-03 18:41:54 回复(0)
#include<bits/stdc++.h>
using namespace std;
inline bool check(int x)
{
    int flag=0;
    while(x)
    {
        int q=x%10;
        x/=10;
        if(q==2||q==5||q==6||q==9)    flag=1;
        else if(q==0||q==1||q==8)    continue;
        else return false;
    }
    if(flag)    return true;
    else    return false;
}
int main()
{
    int n,sum=0;cin>>n;
    for(int i=1;i<=n;i++)
        if(check(i))    sum++;
    cout<<sum;
}

发表于 2022-01-22 06:58:04 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        int n=new Scanner(System.in).nextInt();
        System.out.println(rotatedDigits(n));
    }
public static int rotatedDigits(int N) {
        int count = 0;
        for (int i = 2; i <= N; i++) {
            String s = String.valueOf(i);
            s = s.replaceAll("[+0,+1,+8]", "");
            if (!"".equals(s)) {
                s = s.replaceAll("[+2,+5,+6,+9]", "");
                if ("".equals(s)) {
                    count += 1;
                }
            }
        }

        return count;
    }}
发表于 2021-07-21 19:16:15 回复(0)
#include<iostream>
#include<string>
bool ishs(int n)
{
    std::string s=std::to_string(n);
    int a=0;
    int b=0;
    int c=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0'||s[i]=='1'||s[i]=='8')a++;
        else if(s[i]=='2'||s[i]=='5'||s[i]=='6'||s[i]=='9')b++;
        else c++;
    }
    if(c!=0)return false;
    else if(b==0)return false;
    return true;
}
int main()
{
    int N;
    while(std::cin>>N)
    {
        int count=0;
        for(int i=1;i<=N;i++)
        {
            if(ishs(i))count++;
        }
        std::cout<<count<<std::endl;
    }
    return 0;
}
发表于 2020-09-20 19:22:35 回复(0)
#include<iostream>
using namespace std;
int main(){
    int n,count=0;
    int a,b,m;
    bool effecient=false;
    cin>>n;
    m=n;
    while(m)
    {
        effecient=false;
        while(n)
        {
            a=n/10;
            b=n-a*10;
            if(b==2||b==5||b==6||b==9)
            {
                effecient=true;
            }
            if(b==3||b==7||b==4)
            {
                effecient=false;
                break;
            }
            n=n/10;
        }
        if(effecient)
        count++;
        m--;
        n=m;
    }
    cout<<count;
    return 0;
}
要判断每位数,一个数字包括了3、4、7都是无效数字,退出循环,包括了2、5、6、9属于有效数字,可以进行累加,
发表于 2020-05-12 12:30:43 回复(0)
原来可以看成字符串处理,学到了学到了
发表于 2020-03-30 00:02:07 回复(0)

数位DP

先求出所有由0, 1, 2, 5, 6, 8, 9构成的且小于N的数的个数res,这些数是翻转有效的,然后求出所有由0, 1, 8构成的且小于N的数的个数las,这些数是翻转有效而且翻转后等于自己。res-las就是所求的答案。

#include <iostream>
#include <vector>

using namespace std;

int power7(int x)
{
  int res = 1;
  for (int i = 0; i < x; i ++) res *= 7;
  return res;
}

int power3(int x)
{
  int res = 1;
  for (int i = 0; i < x; i ++) res *= 3;
  return res;
}

int main()
{
  int f[7] = {0, 1, 2, 5, 6, 8, 9};
  int g[3] = {0, 1, 8};
  int n;
  cin >> n;
  vector<int> vec;
  while (n)
  {
    vec.push_back(n % 10);
    n /= 10;
  }

  int res = 0;
  int las = 0;

  for (int i = vec.size() - 1; i >=0; i --)
  {
    for (int j = 0; j < 7; j ++)
    {
      int x = f[j];
      if (x < vec[i]) res += power7(i);
    }
    if (vec[i] == 3 || vec[i] == 4 || vec[i] == 7) break;

    if (!i) res ++;
  }

  for (int i = vec.size() - 1; i >= 0; i --)
  {
    for (int j = 0; j < 3; j ++)
    {
      int x = g[j];
      if (x < vec[i]) las += power3(i);
    }
    if (!(vec[i] == 0 || vec[i] == 1 || vec[i] == 8)) break;

    if (!i) las ++;
  }

  cout << res - las << endl;
  return 0;

}
编辑于 2020-03-15 10:07:00 回复(0)