吸血鬼算法

吸血鬼算法题目.png

官方答案：

 @Test
    public void method12() {
        /**
         * 吸血鬼数字的计算方法2
         */
        Long starDate = System.currentTimeMillis();
        int[] startDigit = new int[4];
        int[] productDigit = new int[4];
        int s1 = 0;
        int s2 = 0;
        for(int num1 = 10; num1 <= 99; num1++)
            for(int num2 = num1; num2 <= 99; num2++) {
                // Pete Hartley's theoretical result:
                // If x·y is a vampire number then
                // x·y == x+y (mod 9)
                s1++;
                if((num1 * num2) % 9 != (num1 + num2) % 9)
                    continue;
                int product = num1 * num2;
                startDigit[0] = num1 / 10;
                startDigit[1] = num1 % 10;
                startDigit[2] = num2 / 10;
                startDigit[3] = num2 % 10;
                productDigit[0] = product / 1000;
                productDigit[1] = (product % 1000) / 100;
                productDigit[2] = product % 1000 % 100 / 10;
                productDigit[3] = product % 1000 % 100 % 10;
                int count = 0;
                for(int x = 0; x < 4; x++)
                    for(int y = 0; y < 4; y++) {
                        if(productDigit[x] == startDigit[y]) {
                            count++;
                            productDigit[x] = -1;
                            startDigit[y] = -2;
                            if(count == 4)
                                System.out.println(num1 + " * " + num2
                                        + " : " + product);
                        }
                        s2++;
                    }
            }

        System.out.println(s1);
        System.out.println(s2);

        System.out.println("总共花费时间:"+(System.currentTimeMillis() - starDate));
    }

结果正确，最外层的双重for循环执行了4095次，里面的双重for循环执行了4960次，花费时间为1ms

第二种执行算法：

@Test
    public void method11() {
        /**
         * 吸血鬼数字第二种计算方法(只循环了232次)
         */
        Long starDate = System.currentTimeMillis();
        String[] ar_str1, ar_str2;
        int sum = 0;
        int from;
        int to;
        int i_val;
        int count = 0;
        // 双重循环穷举
        for (int i = 10; i < 100; i++) {
            // j=i+1避免重复
            from = Math.max(1000 / i, i + 1);
            to = Math.min(10000 / i, 100);
            for (int j = from; j < to; j++) {
                i_val = i * j;
                // 下面的这个代码，我个人并不知道为什么，汗颜
                if (i_val % 100 == 0 || (i_val - i - j) % 9 != 0) {
                    continue;
                }
                count++;
                ar_str1 = String.valueOf(i_val).split("");
                ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");
                Arrays.sort(ar_str1);
                Arrays.sort(ar_str2);
                if (Arrays.equals(ar_str1, ar_str2)) {// 排序后比较,为真则找到一组
                    sum++;
                    System.out.println("第" + sum + "组: " + i + "*" + j + "=" + i_val);
                }
            }
        }
        System.out.println("共找到" + sum + "组吸血鬼数");
        System.out.println(count);

        System.out.println("总共花费时间:"+(System.currentTimeMillis() - starDate));
    }

只执行了232次就将吸血鬼数拿到，但耗费时间为10ms；

第二次算法博客地址：https://blog.csdn.net/java2000_net/article/details/3851203