算法天枰称重 (枚举法和进制转换实现逢十进一)

题意：

方法1（枚举法）

思路：

• 先找到所有小于1000000的3的幂的数：[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441]
• 根据题意可知每一个数的前面的系数只有三种可能性[-1, 0, 1]
• 那么有inputNum = (系数)*1 + (系数)*3 + (系数)*9 + (系数)*27 + (系数)*81 + (系数)*243 + (系数)*729 + (系数)*2187 + (系数)*6561 + (系数)*19683 + (系数)*59049 + (系数)*177147 + (系数)*531441
• 使用14层循环(手有点酸)遍历[-1, 0, 1]，表示上面14个系数，再根据上面的匹配条件来筛选出每一个数的系数

 private static String fn(int inputNum) { StringBuilder builder = new StringBuilder(); int[] arr = {-1, 0, 1}; for (int a : arr) for (int b : arr) for (int c : arr) for (int d : arr) for (int e : arr) for (int f : arr) for (int g : arr) for (int h : arr) for (int i : arr) for (int j : arr) for (int k : arr) for (int l : arr) for (int m : arr) for (int n : arr) { int o = 1 * a; int p = 3 * b; int q = 9 * c; int r = 27 * d; int s = 81 * e; int t = 243 * f; int u = 729 * g; int v = 2187 * h; int w = 6561 * i; int x = 19683 * j; int y = 59049 * k; int z = 177147 * l; int z1 = 531441 * m; int z2 = 1594323 * n; // 如果相加后与输入值匹配，则将相应的非0数添加到builder中 // 如果数大于0则在其前面加上"+" if (o + p + q + r + s + t + u + v + w + x + y + z + z1 + z2 == inputNum) { builder.append(z2 != 0 ? (z2 > 0 ? "+" + z2 : "" + z2) : ""); builder.append(z1 != 0 ? (z1 > 0 ? "+" + z1 : "" + z1) : ""); builder.append(z != 0 ? (z > 0 ? "+" + z : "" + z) : ""); builder.append(y != 0 ? (y > 0 ? "+" + y : "" + y) : ""); builder.append(x != 0 ? (x > 0 ? "+" + x : "" + x) : ""); builder.append(w != 0 ? (w > 0 ? "+" + w : "" + w) : ""); builder.append(v != 0 ? (v > 0 ? "+" + v : "" + v) : ""); builder.append(u != 0 ? (u > 0 ? "+" + u : "" + u) : ""); builder.append(t != 0 ? (t > 0 ? "+" + t : "" + t) : ""); builder.append(s != 0 ? (s > 0 ? "+" + s : "" + s) : ""); builder.append(r != 0 ? (r > 0 ? "+" + r : "" + r) : ""); builder.append(q != 0 ? (q > 0 ? "+" + q : "" + q) : ""); builder.append(p != 0 ? (p > 0 ? "+" + p : "" + p) : ""); builder.append(o != 0 ? (o > 0 ? "+" + o : "" + o) : ""); } } // 删去第一个"+" builder.deleteCharAt(0); return builder.toString(); } public static void main(String[] args) { System.out.println(fn(50000)); // 打印: 59049-6561-2187-243-81+27-3-1 } 

方法2（变种三进制）

1. 引导问题：把砝码重量改为2的指数幂（1,2,4,8,16…）

   使用二进制来解决该问题：

   1. 把inputNum转为二进制，例如称量重量为11的物体，11的二进制为1011
   2. 二进制的每一位数可以表示两种状态：1—> 取对应位的2次幂，0—> 不取对应位的2次幂
   3. 把1011(二进制)转为十进制：8*1 + 4*0 + 2*1 + 1*1，即11 = 8 + 2 + 1，而8,2,1恰好就是砝码的重量

2. 类比上面的方法，使用三进制来解决该问题

   1. 把inputNum转为三进制，例如称量重量为11的物体，11的三进制为102
   2. 如果类比上面二进制的方法：11 = 9*1 + 3*0 + 2*1，取一次9，取2次1，不符合题意，因为要求每种重量的砝码只能取一次
   3. 改变一下规则：让三进制数逢2进1，原位数自减1，例如102(三进制)—> 1 1 -1—> 11 = 9*1 + 3*1 + 1*(-1)—> 取一次9取一次3放在右盘，取一次1放在左盘

   使用该方法前建议做一下这道题：LeetCode 415. 字符串相加
   下面的代码是类比逢10进1，改为的逢2进1，并且都是对字符内容运算的处理

    // 让三进制数逢2进1，原位数自减1，例如102(三进制)---> 1  1  -1---> 11 = 9*1 + 3*1 + 1*(-1) // 220121 ---> -1 3 0 1 2 1 ---> -1 0 1 1 2 1 ---> -1 0 1 1 -1 2 ---> -1 0 1 1 -1 -1 1 //      -1 0 1 1 -1 -1 1 //       0 1 2 3  4  5 6 //       1 3 9 27 ... public static String fn2(int inputNum) { // 转为三进制 String x = Integer.toString(inputNum, 3); // 翻转转为字符数组 char[] c = new StringBuilder(x).reverse().toString().toCharArray(); int add = 0; ArrayList<Integer> list = new ArrayList<>(); int i = 0; while (i < c.length || add != 0) { // 三进制的每一位数字 int y = i < c.length ? c[i] - '0' : 0; // 因为有逢2进1的处理，所以会有进位 int num = y + add; // 对每一位大于等于2的数进行余2减1后添加到集合中(保证最终放到集合中的元素是[-1,0,1]) list.add(num >= 2 ? num % 2 - 1 : num); // 大于2的数进位1 add = num / 2; i++; } // 上面循环结束后就得到了一个三进制转十进制每一位数对应的系数的列表 StringBuilder builder = new StringBuilder(); // 倒序遍历列表，将相应系数乘上对应位数添加到StringBuilder中 for (int j = list.size() - 1; j >= 0; j--) { int number = (int) (list.get(j) * Math.pow(3, j)); builder.append(number != 0 ? (number > 0 ? "+" + number : number + "") : ""); } return builder.deleteCharAt(0).toString(); } 

收获

• 用枚举法解决问题的核心思想：

  1. 找到题目中隐藏的恒等条件(题目也可能直接给出)，比如本题中的隐藏的恒等条件就是：inputNum = (系数)*1 + (系数)*3 + (系数)*9 + (系数)*27 + (系数)*81 + (系数)*243 + (系数)*729 + (系数)*2187 + (系数)*6561 + (系数)*19683 + (系数)*59049 + (系数)*177147 + (系数)*531441 + (系数)*1594323，系数取值为[-1, 0, 1]
  2. 嵌套遍历循环隐藏恒等条件中不定的量(这些不定量也可能有一些取值条件，比如说互不相等，那么在每层循环中还需添加相应的条件再进行下一层循环)，本题中隐藏恒等条件中的不定量就是系数，系数的取值条件是[-1, 0, 1]
  3. 在最后一层循环中通过题目的问题建立筛选条件

• 三目运算符嵌套三目运算符的使用：条件1 ? (条件2 ? A : B) : C

  不满足条件1则执行C
  满足条件1不满足条件2则执行B
  满足条件1又满足条件2则执行A

• StringBuilder中有两个用来删去其中字符串内容的方法

  1. delete(int start, int end)，区间左闭右开同substring()，返回修改后的StringBuilder
  2. deleteCharAt(int index) ，返回修改后的StringBuilder

• 将一个十进制数转为radix进制数的方法：Integer.toString(int i, int radix);

本文地址：https://blog.csdn.net/k909397116/article/details/107884438