IDEA激活码算法-面试题 ➡️ 题目一 ➡️ 一个有效的"带分数"形式
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次方
因为1~9必须全部用一遍，不能重复，所以组成的数字有9！= 362880 组合
数字有9！= 362880 组合 按这种随意填+ 号 和 / 的都多少种 组合
所以一个数字，可以+/ 的次数为 4+3+3+2+2+1+1=16次
32880*16 = 5806080
如果这道题采取硬计算的方法 10的7次方，没有超过10的8次方，可以通过全部遍历一遍的方法计算。
定义递归函数public static void process(int num, int index) 表示当前index位置上，使用了那个数组做决定。即9！ 使用process生成。
所以主函数使用process(123456789, 8);来生成9！
当index=-1 数字生成完成
public static void process(int num, int index) {
if (index == -1) {
} else {
// 需要去指定index位置的数
for (int swap = index; swap >= 0; swap--) {
int next = swap(num, index, swap);
process(next, index - 1);
}
}
}
我们现在需要一个swap 函数来处理 int数字上位数交换的方法 swap(123456789, 8, 2); 表示123456789 第8位和第二位交换 结果为723456189
public final static int[] arr = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
public static int swap(int num, int L, int R) {
// num L位的数字是什么？
int bitL = (num / arr[L]) % 10; //123456789/100000000 = 1 1%10 = 1
int bitR = (num / arr[R]) % 10; //123456789/100 = 1234567 1234567%10 = 7
return num - (bitL - bitR) * arr[L] + (bitL - bitR) * arr[R];
}
当index=1的时候 1~9的数组组合以及完成了 ，现在来完成p1 + p2 / p3 的分割
先完成p1的分割 for (int addSplit = 8; addSplit >= 2; addSplit--)
int p1 = num / arr[addSplit];
int rest = num % arr[addSplit]; //p2 ~ p3剩下的数字
剩下 / 号分割点
for (int devSplit = (addSplit >> 1); devSplit >= 1; devSplit--)
除号分割点确定了，我们就可以做最后规则确认了
// num 固定了 8 ~ 0
// num + / 8 ~ 0
for (int addSplit = 8; addSplit >= 2; addSplit--) {//+ 号分割点
// p1
int p1 = num / arr[addSplit];
int rest = num % arr[addSplit];
for (int devSplit = (addSplit >> 1); devSplit >= 1; devSplit--) { //➗➗➗➗➗
int p2 = rest / arr[devSplit];
int p3 = rest % arr[devSplit];
if (p2 % p3 == 0) {//能够整除 ，??????记录数字答案
int ans = p1 + p2 / p3;
if (!map.containsKey(ans)) {
map.put(ans, 1);//答案放入map
} else {
map.put(ans, map.get(ans) + 1);
}
}
}
}
public class AddDevideNum {
// 1-9 所有带分数，形成的结果，都算一遍，map里去
// key 100 value 11
public static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
public final static int[] arr = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
public static int ways(int n) {
if (map.size() == 0) {
process(123456789, 8);
}
return map.containsKey(n) ? map.get(n) : 0;
}
// process, 当的数形成样子，num 123456789
// index 该哪个位置的数字去指定了
public static void process(int num, int index) {
if (index == -1) {
// num 固定了 8 ~ 0
// num + / 8 ~ 0
for (int addSplit = 8; addSplit >= 2; addSplit--) {
// p1
int p1 = num / arr[addSplit];
int rest = num % arr[addSplit];
for (int devSplit = (addSplit >> 1); devSplit >= 1; devSplit--) {
int p2 = rest / arr[devSplit];
int p3 = rest % arr[devSplit];
if (p2 % p3 == 0) {
int ans = p1 + p2 / p3;
if (!map.containsKey(ans)) {
map.put(ans, 1);
} else {
map.put(ans, map.get(ans) + 1);
}
}
}
}
} else {
// 需要去指定index位置的数
for (int swap = index; swap >= 0; swap--) {
int next = swap(num, index, swap);
process(next, index - 1);
}
}
}
// 123456789 L == 8 R == 2
// 723456189
public static int swap(int num, int L, int R) {
// num L位的数字是什么？
int bitL = (num / arr[L]) % 10;
int bitR = (num / arr[R]) % 10;
return num - (bitL - bitR) * arr[L] + (bitL - bitR) * arr[R];
}
public static void main(String[] args) {
long start;
long end;
start = System.currentTimeMillis();
System.out.println(ways(100));
end = System.currentTimeMillis();
System.out.println(end - start);
}
}
