Leetcode: 【每日一题】- 2019-09-03 - 神奇的九位数

[azl397985856]

能不能找出一个九位数，这个数包含了1-9这九个数字，并且这九个数的前n位能被n整除，若这个数为abcdefghi，则ab可以被2整除，abc可以被3整除... abcdefghi可以被9整除。

请尽量优化你的复杂度，包括但不限于剪枝

[xiongcaihu]

``` .js
/**
*能被2整除的数，个位上的数能被2整除（偶数都能被2整除），那么这个数能被2整除

能被3整除的数，各个数位上的数字和能被3整除，那么这个数能被3整除

能被4整除的数，个位和十位所组成的两位数能被4整除，那么这个数能被4整除

能被5整除的数，个位上为0或5的数都能被5整除，那么这个数能被5整除

能被6整除的数，各数位上的数字和能被3整除的偶数，如果一个数既能被2整除又能被3整除，那么这个数能被6整除

能被7整除的数，若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，余类推。

能被8整除的数，一个整数的末3位若能被8整除，则该数一定能被8整除。

能被9整除的数，各个数位上的数字和能被9整除，那么这个数能被9整除
*
*/
function find9Number() {
for (var a = 1; a <= 9; a++) { //1
for (var b = 1; b <= 9; b++) { // 2
if (a == b) continue;
if (b % 2 != 0) continue;

        for (var c = 1; c <= 9; c++) { //3
            if (c == b || c == a) {
                continue;
            }
            if ((a + b + c) % 3 != 0) {
                continue;
            }
            for (var d = 1; d <= 9; d++) { // 4
                if (d == a || d == b || d == c) {
                    continue;
                }

                if ((c * 10 + d) % 4 != 0) continue;

                for (var e = 1; e <= 9; e++) { // 5
                    if (e == a || e == b || e == c || e == d) {
                        continue;
                    }
                    if (e != 5) continue;

                    for (var f = 1; f <= 9; f++) { //6
                        if (f == a || f == b || f == c || f == d || f == e) {
                            continue;
                        }
                        if ((a + b + c + d + e + f) % 3 != 0 || f % 2 != 0) {
                            continue;
                        }
                        for (var g = 1; g <= 9; g++) { // 7
                            if (g == a || g == b || g == c || g == d || g == e || g == f) {
                                continue;
                            }
                            var str = '' + a + b + c + d + e + f;
                            if ((Number(str) - g * 2) % 7 != 0) continue;

                            for (var h = 1; h <= 9; h++) { // 8
                                if (h == a || h == b || h == c || h == d || h == e || h == f || h == g) continue;
                                var str = '' + f + g + h;
                                if (Number(str) % 8 != 0) continue;
                                for (var i = 1; i <= 9; i++) { // 9
                                    if ((a + b + c + d + e + f + g + h + i) % 9 != 0) continue;

                                    console.log(a, b, c, d, e, f, g, h, i);
                                    return Number("" + a + b + c + d + e + f + g + h + i);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

}
```

[xiongcaihu]

简化一下
.js function findNumber() { var flag = 1, map = new Set(), a = 1, b = 1, c = 1, d = 1, e = 1, f = 1, g = 1, h = 1, i = 1; while (true) { switch (flag) { case 1: while (map.has(a) && a <= 9) a++; a > 9 ? flag = 10 : (flag = 2, map.add(a)); break; case 2: while ((map.has(b) || b % 2 != 0) && b <= 9) b++; b > 9 ? (flag = 1, map.delete(a), a++, b = 1) : (flag = 3, map.add(b)); break; case 3: while ((map.has(c) || (a + b + c) % 3 != 0) && c <= 9) c++; c > 9 ? (flag = 2, map.delete(b), b++, c = 1) : (flag = 4, map.add(c)); break; case 4: while ((map.has(d) || (c * 10 + d) % 4 != 0) && d <= 9) d++; d > 9 ? (flag = 3, map.delete(c), c++, d = 1) : (flag = 5, map.add(d)); break; case 5: while ((map.has(e) || e != 5) && e <= 9) e++; e > 9 ? (flag = 4, map.delete(d), d++, e = 1) : (flag = 6, map.add(e)); break; case 6: while ((map.has(f) || ((a + b + c + d + e + f) % 3 != 0 || f % 2 != 0)) && f <= 9) f++; f > 9 ? (flag = 5, map.delete(e), e++, f = 1) : (flag = 7, map.add(f)); break; case 7: while ((map.has(g) || (Number("" + a + b + c + d + e + f) - g * 2) % 7 != 0) && g <= 9) g++; g > 9 ? (flag = 6, map.delete(f), f++, g = 1) : (flag = 8, map.add(g)); break; case 8: while ((map.has(h) || Number('' + f + g + h) % 8 != 0) && h <= 9) h++; h > 9 ? (flag = 7, map.delete(g), g++, h = 1) : (flag = 9, map.add(h)); break; case 9: while ((map.has(i) || (a + b + c + d + e + f + g + h + i) % 9 != 0) && i <= 9) i++; i > 9 ? (flag = 8, map.delete(h), h++, i = 1) : flag = 10; break; case 10: return "" + a + b + c + d + e + f + g + h + i; } } }

[watchpoints]

认领

[azl397985856]

认领

帅哥 快一个月了 出来解题了

[ruoguang]

/**
 * 找出一个九位数，这个数包含了1-9这九个数字，并且这九个数的前n位能被n整除，
 * 若这个数为abcdefghi，则ab可以被2整除，abc可以被3整除... abcdefghi可以被9整除。
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(result()); //381654729
    }


    public static int result() {
        int result = -1;
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        int e = 0;
        int f = 0;
        int g = 0;
        int h = 0;
        int i = 0;
        HashSet<Integer> set = new HashSet<Integer>();

        for (int j = 123456789; j <= 987654321; j++) {
            a = j / 100000000;
            b = j / 10000000 % 10;
            c = j / 1000000 % 10;
            d = j / 100000 % 10;
            e = j / 10000 % 10;
            f = j / 1000 % 10;
            g = j / 100 % 10;
            h = j / 10 % 10;
            i = j % 10;
            set.clear();
            set.add(a);
            set.add(b);
            set.add(c);
            set.add(d);
            set.add(e);
            set.add(f);
            set.add(g);
            set.add(h);
            set.add(i);
            if (!set.contains(0)) {
                if (set.size() == 9) {
                    if (b % 2 == 0) {
                        if (e == 0 || e == 5) {
                            if ((a + b + c) % 3 == 0) {
                                if ((a * 1000 + b * 100 + c * 10 + d) % 4 == 0) {
                                    if ((a * 100000 + b * 10000 + c * 1000 + d * 100 + e * 10 + f) % 6 == 0) {
                                        if ((a * 1000000 + b * 100000 + c * 10000 + d * 1000 + e * 100 + f * 10 + g) % 7 == 0) {
                                            if ((a * 10000000 + b * 1000000 + c * 100000 + d * 10000 + e * 1000 + f * 100 + g * 10 + h) % 8 == 0) {
                                                result = a * 100000000 + b * 10000000 + c * 1000000 + d * 100000 + e * 10000 + f * 1000 + g * 100 + h * 10 + i;
                                                break;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        return result;
    }
}