c*******r
发帖数: 51 | | y**********a
发帖数: 824 | 2 遍历所有的可能性，计算。
public int maxResult(int[]A) {
int[]rel=new int[1];rel[0]=Integer.MIN_VALUE;
dfs(A, new int[A.length-1], 0, rel);
return rel[0];
}
void dfs(int[]A, int[]op, int i, int[] max) {
if (i==op.length) {
StringBuilder s=new StringBuilder();
s.append(Integer.toString(A[0]));
char[] opc=new char[4];
opc[0]='+';opc[1]='-';opc[2]='*';opc[3]='/';
for (int j=0;j
s.append(opc[op[j]]);
s.append(A[j+1]);
}
max[0]=Math.max(max[0], eval(s.toString()));
return;
}
for (int j=0;j<4;++j){
op[i]=j;
dfs(A, op, i+1, max);
}
}
int eval(String s) {
List rel=new ArrayList<>();
//0 : operator 1: numbers
for (int i=0, n=s.length();i
if (rel.size()==0||rel.get(rel.size()-1).charAt(0)=='0') {
int j=i+1;
while (j
rel.add("1,"+s.substring(i,j));
i=j;
} else {
rel.add("0,"+s.substring(i,i+1));
++i;
}
}
return evaluateInorder(rel);
}
int evaluateInorder(List s) {
String[] rp=new String[s.size()];
Queuestc=Collections.asLifoQueue(new ArrayDeque());
int j=0;
for (int i=0;i
if (s.get(i).charAt(0)=='0') {
char c=s.get(i).charAt(2);
if (c=='/'||c=='*') {
rp[j++]=s.get(i+1).split(",")[1];
rp[j++]=s.get(i).split(",")[1];
i+=2;
} else stc.offer(s.get(i++).split(",")[1]);
} else rp[j++]=s.get(i++).split(",")[1];
}
while (!stc.isEmpty())rp[j++]=stc.poll();
for (int i=0;i
if (rp[i].length()==1&&!Character.isDigit(rp[i].charAt(0))) {
int b=Integer.parseInt(stc.poll());
int a=Integer.parseInt(stc.poll());
char c=rp[i].charAt(0);
if (c=='*') stc.offer(Integer.toString(a*b));
if (c=='/') stc.offer(Integer.toString(a/b));
if (c=='+') stc.offer(Integer.toString(a+b));
if (c=='-') stc.offer(Integer.toString(a-b));
} else stc.offer(rp[i]);
}
return Integer.parseInt(stc.poll());
}
public static void main(String[] args) {
int[] A={1,1,2,2,1};
System.out.println(new MaxNumberWithOperators().maxResult(A));
} | m*********a
发帖数: 3299 | 3 用递归
第一个是必须是数字，有5种选择，
第二个是+/-/*//之一，选一个
然后是数字，剩下4个数字，选一个
然后是3个符号
...
...
递归完成，最后一个数字，比较这个方法的值是不是最大
【在 c*******r 的大作中提到】
: 用啥算法？
|
|
