OptimalDivision [source code]
public class OptimalDivision {
static
/******************************************************************************/
public class Solution {
public String optimalDivision(int[] nums) {
if (nums.length == 1)
return nums[0] + "";
StringBuilder sb = new StringBuilder(nums[0] + "/" + (nums.length == 2 ? "" : "("));
for (int i = 1; i < nums.length; i++)
sb.append(nums[i] + "/");
sb.setLength(sb.length() - 1);
sb.append(nums.length == 2 ? "" : ")");
return sb.toString();
}
}
/******************************************************************************/
public static void main(String[] args) {
OptimalDivision.Solution tester = new OptimalDivision.Solution();
int[][] inputs = {
{1000, 100, 10, 2},
{3,2},
};
String[] answers = {
"1000/(100/10/2)",
"3/2",
};
for (int i = 0; i < inputs.length; i++) {
int[] nums = inputs[i];
String answer = answers[i];
System.out.println(Printer.seperator());
String output = tester.optimalDivision(nums);
System.out.println(Printer.wrapColor(Printer.array(nums), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, output.equals(answer) ? "green" : "red"));
}
}
}
这个题目简单的有点无语了. 最后的速度是: 8ms (51%), 好像其实就是最优解了;
大概意思就是多个数之间的连续除法其实, 你从recursion的角度来看(加法乘法什么的都可以用recursion的思路来理解的, 还记得吗), 实际上最后就是两个数的除法.
想要两个数的除法尽可能的大, 那么第一个数就要尽可能大, 第二个数尽可能小. 因为这里所有的数都是大于1的, 所以只要除了, 就一定会变小; 所以第一个数最好就是完全没有被除过的, 然后第二个数就是尽可能被除很多次的. 这个理解了之后, 就是把第一个数跟所有后面其他的数各自分成一组就行了;
虽然这个题目的math解看起来有点trivial, 不过这个题目的editorial给出的暴力解还是值得学习的, 这个是editorial1:
public class Solution {
public String optimalDivision(int[] nums) {
T t = optimal(nums, 0, nums.length - 1, "");
return t.max_str;
}
class T {
float max_val, min_val;
String min_str, max_str;
}
public T optimal(int[] nums, int start, int end, String res) {
T t = new T();
if (start == end) {
t.max_val = nums[start];
t.min_val = nums[start];
t.min_str = "" + nums[start];
t.max_str = "" + nums[start];
return t;
}
t.min_val = Float.MAX_VALUE;
t.max_val = Float.MIN_VALUE;
t.min_str = t.max_str = "";
for (int i = start; i < end; i++) {
T left = optimal(nums, start, i, "");
T right = optimal(nums, i + 1, end, "");
if (t.min_val > left.min_val / right.max_val) {
t.min_val = left.min_val / right.max_val;
t.min_str = left.min_str + "/" + (i + 1 != end ? "(" : "") + right.max_str + (i + 1 != end ? ")" : "");
}
if (t.max_val < left.max_val / right.min_val) {
t.max_val = left.max_val / right.min_val;
t.max_str = left.max_str + "/" + (i + 1 != end ? "(" : "") + right.min_str + (i + 1 != end ? ")" : "");
}
}
return t;
}
}
我刚开始看到这个题目的时候差点就决定这么做了, 就是一个直白的recursion, 用两个端点来控制subproblem的size, optimal value就是min和max value: 注意这里min和max都要作为DP value维护, 因为计算min需要max, 计算max需要min: reciprocity of min/max in DP.
整体来说这个算法还是一个比较教科书的recursion算法, 虽然复杂度不怎么好. 我感觉这个其实都有点像backtracking了, 不过其实并不是, 因为这里并没有decision level这个概念;
另外注意他这里这个class T的使用, 因为JAVA的返回值有限制, 所以自己定义一个类似struct一样的东西来实现 multiple return values, 这个还是一个比较常见的技巧;
editorial2就是对上面的进行一个optimization that applies to almost all exponential recursions: memozation:
public class Solution {
class T {
float max_val, min_val;
String min_str, max_str;
}
public String optimalDivision(int[] nums) {
T[][] memo = new T[nums.length][nums.length];
T t = optimal(nums, 0, nums.length - 1, "", memo);
return t.max_str;
}
public T optimal(int[] nums, int start, int end, String res, T[][] memo) {
if (memo[start][end] != null)
return memo[start][end];
T t = new T();
if (start == end) {
t.max_val = nums[start];
t.min_val = nums[start];
t.min_str = "" + nums[start];
t.max_str = "" + nums[start];
memo[start][end] = t;
return t;
}
t.min_val = Float.MAX_VALUE;
t.max_val = Float.MIN_VALUE;
t.min_str = t.max_str = "";
for (int i = start; i < end; i++) {
T left = optimal(nums, start, i, "", memo);
T right = optimal(nums, i + 1, end, "", memo);
if (t.min_val > left.min_val / right.max_val) {
t.min_val = left.min_val / right.max_val;
t.min_str = left.min_str + "/" + (i + 1 != end ? "(" : "") + right.max_str + (i + 1 != end ? ")" : "");
}
if (t.max_val < left.max_val / right.min_val) {
t.max_val = left.max_val / right.min_val;
t.max_str = left.max_str + "/" + (i + 1 != end ? "(" : "") + right.min_str + (i + 1 != end ? ")" : "");
}
}
memo[start][end] = t;
return t;
}
}
这个最后的复杂度是N^3(不要忘记每一个node里面还有一个O(N)的fanning);
这个算法还有一个比较tricky的点就是为什么除了两个val以外, 两个string也要一起维护? 这个就是因为括号的添加的问题. 括号的添加必须在每一个level分别完成, 不能指望最后有一个最终结果了之后一个1pass单独一把头搞定.
具体来说, 这个括号的添加就是每个level的两个数, 只给右边的数加括号(当然是长度要足够长, 如果长度只有1, 那么就不加了).
editorial3就是这个math的解了;
discussion的一个解释:
X1/X2/X3/../Xn will always be equal to (X1/X2) Y, no matter how you place parentheses. i.e no matter how you place parentheses, X1 always goes to the numerator and X2 always goes to the denominator. Hence you just need to maximize Y. And Y is maximized when it is equal to X3 ..Xn. So the answer is always X1/(X2/X3/../Xn) = (X1 X3 ..Xn)/X2
X1/X2/X3/../Xn will always be equal to (X1/X2) Y, no matter how you place parentheses. i.e no matter how you place parentheses, X1 always goes to the numerator and X2 always goes to the denominator. Hence you just need to maximize Y. And Y is maximized when it is equal to X3 ..Xn. So the answer is always X1/(X2/X3/../Xn) = (X1 X3 ..Xn)/X2
看来我CLRS还是没有读透;
I agree with you. Actually, I think this solution is divide and conquer rather than backtracking.
问了一下guoye, 他认为recursion这个词其实跟DP, backtracking, divide&conquer其实并不是一个类型的terminoogy. recursion只是实现DP, backtracking的手段, 这两个其实都可以用iterative来写;
这个问题这种reduce problem size的思路确实是divide&conquer更合适;
这个是guoye对于divide&conquer和backtracking的区别的解释:
这两种算法也不是完全能互换的，有的问题能用一种方法解不能用另一种。如果都能用的话一般backtrack慢
这个是discussion上面一个人写的divide&conquer:
public class Solution {
class Result {
String str;
double val;
}
public String optimalDivision(int[] nums) {
int len = nums.length;
return getMax(nums, 0, len - 1).str;
}
private Result getMax(int[] nums, int start, int end) {
Result r = new Result();
r.val = -1.0;
if (start == end) {
r.str = nums[start] + "";
r.val = (double)nums[start];
}
else if (start + 1 == end) {
r.str = nums[start] + "/" + nums[end];
r.val = (double)nums[start] / (double)nums[end];
}
else {
for (int i = start; i < end; i++) {
Result r1 = getMax(nums, start, i);
Result r2 = getMin(nums, i + 1, end);
if (r1.val / r2.val > r.val) {
r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
r.val = r1.val / r2.val;
}
}
}
//System.out.println("getMax " + start + " " + end + "->" + r.str + ":" + r.val);
return r;
}
private Result getMin(int[] nums, int start, int end) {
Result r = new Result();
r.val = Double.MAX_VALUE;
if (start == end) {
r.str = nums[start] + "";
r.val = (double)nums[start];
}
else if (start + 1 == end) {
r.str = nums[start] + "/" + nums[end];
r.val = (double)nums[start] / (double)nums[end];
}
else {
for (int i = start; i < end; i++) {
Result r1 = getMin(nums, start, i);
Result r2 = getMax(nums, i + 1, end);
if (r1.val / r2.val < r.val) {
r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
r.val = r1.val / r2.val;
}
}
}
//System.out.println("getMin " + start + " " + end + "->" + r.str + ":" + r.val);
return r;
}
}
有点verbose, 但是实际的思路是差不多的. 他的缺点就在于没有想到利用multiple return values这个技巧; 因为我们要求的是min和max, 这两者是紧密关联的, 而且都是非常容易维护的量, 所以在一个recursion里面直接完成实际上是最好的, 而不用像他这样分成两个recursion来做. 一般按照我目前的见识来说, 包括之前做tree问题的时候的经验, 如果你的算法需要两个recursion来完成, 那么多半不是最优解;
另外这个算法的作者是@shawngao, discussion里面1800+ reputation的一个厉害人物, 但是你看他, 也是有用log来debug的习惯的; 没毛病好吧;
Problem Description
Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.
However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.
Example:
Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant,
since they don't influence the operation priority. So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
Note:
The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.
Difficulty:Medium
Total Accepted:6.7K
Total Submissions:12.2K
Contributor: fallcreek
Companies
amazon
Related Topics
math string