【蓝桥杯】第五届-3-神奇算式

题目

由4个不同的数字，组成的一个乘法算式，它们的乘积仍然由这4个数字组成。
比如：

210 x 6 = 1260 
8 x 473 = 3784
27 x 81 = 2187 

都符合要求。
如果满足乘法交换律的算式算作同一种情况，那么，包含上边已列出的3种情况，一共有多少种满足要求的算式。
请填写该数字，通过浏览器提交答案，不要填写多余内容（例如：列出所有算式）。

答案

12种情况，如下：

3*501=3501
3*510=3510
6*201=6201
6*210=6210
8*473=8473
9*351=9351
15*93=1593
21*60=2160
21*87=2187
27*81=2781
30*51=3051
35*41=3541

分析

对于该题，我使用了枚举法，通过两个for循环，将所有算式 i*j=s都检查了一遍，但是所有算式中的i、j、s需要满足以下条件：

• 1<=i<100；
• 10<=j<1000；
• 对于String m = "" + i+ j;，m的长度必须==4;
• 对于String s = "" + (i * j);，s的长度必须==4;
• 组成m与s的数字必须相等；
• 因子i与中的数字不能重复；

题目中，我使用了ArrayList<Factor>，并创建了一个内部类：Factor，重写了equals()方法，将所有正确的结果放入ArrayList<Factor>中，通过contains()方法排除了满足交换律而重复的结果，最终得出12个结果,用时：101ms。

代码

import java.util.ArrayList;
import java.util.Arrays;

public class Three {
    static int counter;

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        fourNumber();
        System.out.println(counter);
        long end = System.currentTimeMillis();
        System.out.println(end-start+"ms");
    }
    
    public static void fourNumber() {
        ArrayList<Factor> array = new ArrayList<Factor>();
        for (int i = 1; i < 100; i++) {
            for (int j = 10; j < 1000; j++) {
                String m = "" + i + j;
                String s = "" + (i * j);
                if (!isRepeat(String.valueOf(i), String.valueOf(j))
                        && m.length() == 4 && s.length() == 4) {
                    Factor factor = new Factor(i, j, Integer.parseInt(s));
                    if (isFind(m, s) && !array.contains(factor)) {
                        array.add(factor);
                        counter++;
                        System.out.println(i+"*"+j+"="+m);
                    }
                }
            }
        }
    }

    // 判断a与b中是否出现了重复数字
    private static boolean isRepeat(String a, String b) {
        char[] arr1 = a.toCharArray();
        for (char c : arr1) {
            if (b.contains("" + c)) {
                return true;
            }
        }
        return false;
    }

    // 判断组成m与s的数字是否相等
    private static boolean isFind(String m, String s) {
        char[] arr1 = m.toCharArray();
        char[] arr2 = s.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        boolean isFind = String.valueOf(arr1).equals(String.valueOf(arr2));
        return isFind;
    }

    // 内部类，重写了equals方法
    private static class Factor {
        int a;
        int b;
        int c;

        public Factor(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        public boolean equals(Object obj) {
            if (obj instanceof Factor) {
                Factor factor = (Factor) obj;
                if ((this.a == factor.a && this.b == factor.b && this.c == factor.c)
                        || (this.a == factor.b && this.b == factor.a && this.c == factor.c)) {
                    return true;
                }
            }
            return false;
        }
    }
}