牛客网笔试3道

超级素数幂

如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。

思路

直接进行循环开方运算；如果x恰好可以满足开方和乘方运算即可；

代码

public class IsSuperPrime {
    public  static  void  main(String []arg)
    {
        Scanner scanner = new Scanner(System.in);
        long  number= scanner.nextLong();
        boolean IsSuperPrime = false;
        long datamax = (long)Math.pow(10,18);
        if ((number>=2)&&(number<=datamax))
        {
            int q = 2;
            double p;
            do {
                p = (int) (Math.pow(number,(1.0/q))+0.5);
                if (number == Math.pow(p,q))
                {
                    IsSuperPrime = isPrime(p);
                    if (IsSuperPrime)
                    {
                        System.out.println((int)p+" "+(int)q);
                        break;
                    }
                }
                q++;
            }while (p>=2);
            if (!IsSuperPrime)
            {
                System.out.println("No");
            }
            else
            {
                
            }
        }
    }
    public  static  boolean isPrime(double i)
    {
        boolean isPrime = true;
        for (int k = 2; k <=Math.sqrt(i);k++)
        {
            if (i%k==0)
            {
                isPrime = false;
                break;
            }
        }
        return  isPrime;
    }
}

难点

double类型是不稳定的，常会出现3！=3，3=2.99999999；所以的话一定要注意double类型，我们可以主动四舍五入，就想上面加了0.5一样；
开方运算其实很少见，难以想到；
质数的验证，从2到sqrt(自己)；如果有任意整除，就不是质数

平衡数

牛牛在研究他自己独创的平衡数，平衡数的定义是：将一个数分成左右两部分，分别成为两个新的数。
左右部分必须满足以下两点：
1，左边和右边至少存在一位。
2，左边的数每一位相乘如果等于右边的数每一位相乘，则这个数称为平衡数。
例如：1221这个数，分成12和21的话，12=21，则称1221为平衡数，再例如：1236这个数，可以分成123和123=6，所以1236也是平衡数。而1234无论怎样分也不满足平衡数。

思路

简单想想我们需要把数字拆分为单个的，所以就把他拆成char[]数组，这样就每一位都是一个数；然后在进行左右各自乘机的运算；

public class First {
    public  static  void  main(String []arg)
    {
        boolean a;
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            a=solution(in.nextInt());
            if (a)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
    static public boolean  solution(int a)
    {
        boolean result=false;
        if (a<10)
            return  false;
        int digit = (int) Math.log10(a);             //位数
        Integer a1 = a;                              //对象化a
        char []c = a1.toString().toCharArray();      //char[]数组化
        /*
        从左边取j位数，右边取剩下的，
        然后作比较
         */
        for (int j=0;j<digit;j++) {
            int x = 1;
            for (int i = 0; i <=j; i++) {       //计算左边部分的乘积，位数越高，char[]位置就越低
                x *= (c[i] - 48);
            }
            int y = 1;
            for (int i = digit; i > j; i--) {   //计算右边部分的乘积
                y *= (c[i] - 48);
            }
            if (x == y) {                       //相等的话，说明有这么一种情况左右相等了；
                result = true;
                break;
            }
        }
        return result;
    }
}

难点

这道题我做题的时候就做出来了，所以不太难，主要是得想到把数字转换成char[]；

字符串分类

牛牛有N个字符串，他想将这些字符串分类，他认为两个字符串A和B属于同一类需要满足以下条件：
A中交换任意位置的两个字符，最终可以得到B，交换的次数不限。比如：abc与bca就是同一类字符串。
现在牛牛想知道这N个字符串可以分成几类。

思路

看到题，我的第一反应是每个字符的个数相等，然后就开始各种写；超级麻烦；因为我不知道char[]数组是可以排序的 sort方法可以将其排序；我也不知道Hashset可以检测重复（只是没用过而已）；

代码

public class Two1 {
    public  static  void  main(String [] arg)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        HashSet<String> set = new HashSet<String>();
        while (n!=0)
        {
            char[] array = scanner.next().toCharArray();
            Arrays.sort(array);
            set.add(String.valueOf(array));
            n--;
        }
        System.out.println(set.size());
    }
}

难点

char[]有排序方法；
Hashset由于不可放入重复元素，所以通过他的长度就可以知道有几个不一样的啦；

2017-03-24