100=3 + 69258 / 714
    100=82 +3546 / 197
    等号右边的部分，可以写成p1 + p2 / p3的形式
    要求p1和p2和p3，所使用的数字，必须把1～9使用完全，并且不重复
    满足的话，我们就说，形如p1 + p2 / p3，一个有效的”带分数”形式要求，
    p2 / p3必须整除

    输入N，返回N有多少种带分数形式
    100，有11种带分数形式
    输入的N, N<10的8次方

    • 笔试技巧，只要解法常数级别没超过10的8次方，那就可以解

    • p1p2p3 看+号和/号如何放，

      • 当+号确定了，那么/号有些地方不用放，因为p2的长度至少要≥p3的长度才能整除
    • 如下硬解， p1p2p3合在一起排列数是9的阶乘共36万+种可能， 然后每一种可能大概枚举16次， 所以总共36w*16=500多万（假设是600万，那么就是10的7次方）， 没有超过10的8次方，那么硬解就是可以的， 所以这道题就是在考你常数优化，要是代码写得不好一点， 可能就超时了，

    image.png

    准备一个map，里面填的就是对应的数字能被组成出现的次数， 然后我们第一次就把所有结果都生成好放进这个map里面，以后再查就是0ms了，只有第一次会花费点时间。

    process（123456789， 8）
    image.png

    因为这道题考的是常数级别的优化，所以若是用字符串搞到最后再转成整数，那就拉了。
    所以我们中间必须就以整数来做。
    一个数，要L位置和R位置的数交换，这个功能怎么实现？
    比如下面 6位置和2位置的数交换
    image.png
    image.png

    当 + 号位置定了， /号位置该怎么定呢？
    image.png

    得到一个结论，如果你+号位置在i，那么除号只用在i / 2位置开始试

    1. // 1-9 所有带分数，形成的结果，都算一遍，map里去
    2. // key 100 value 11
    3. public static HashMap<Integer, Integer> map = new HashMap<>();
    5. public static final int[] arr = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
    7. public static int ways(int n) {
    8.     if (map.size() == 0) {
    9.         process(123456789, 8);
    10.     }
    11.     return map.get(n);
    12. }
    14. // process, 当前数形成的样子，num 123456789
    15. // index 该哪个位置的数字去指定了
    16. private static void process(int num, int index) {
    17.     if (index == -1) {
    18.         // num 固定了， 8 ~ 0
    19.         // num + / 8 ~ 0
    20.         for (int addSplit = 8; addSplit >= 2; addSplit--) {
    21.             int p1 = num / arr[addSplit];
    22.             int rest = num % arr[addSplit];
    23.             for (int devSpilt = (addSplit >> 1); devSpilt >= 1; devSpilt--) {
    24.                 int p2 = rest / arr[devSpilt];
    25.                 int p3 = rest % arr[devSpilt];
    26.                 if (p2 % p3 == 0) {
    27.                     int ans = p1 + p2 / p3;
    28.                     if (!map.containsKey(ans)) {
    29.                         map.put(ans, 1);
    30.                     } else {
    31.                         map.put(ans, map.get(ans) + 1);
    32.                     }
    33.                 }
    34.             }
    35.         }
    36.     } else {
    37.         // 需要去指定index位置的数
    38.         for (int swap = index; swap >= 0; swap--) {
    39.             int next = swap(num, index, swap);
    40.             process(next, index - 1);
    41.         }
    42.     }
    43. }
    45. private static int swap(int num, int L, int R) {
    46.     int bitL = (num / arr[L]) % 10;
    47.     int bitR = (num / arr[R]) % 10;
    48.     return num - (bitL - bitR) * arr[L] + (bitL - bitR) * arr[R];
    49. }