AC:1+0.6
第一题 表达式求值
package com.company;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
count("(- (* 4 5) 4 5)");
}
public static void count(String line){
Stack<String> stack = new Stack<>();
int i = 0;
String tempC = "";
while (i<line.length()){
char c = line.charAt(i);
if(c==')'){
Stack<String> tempList = new Stack<>();
String temp = stack.pop();
while(!"(".equals(temp)){
tempList.push(temp);
temp=stack.pop();
}
int ans = 0;
switch (tempList.pop()){
case "+":
while(!tempList.empty()){
ans+=Integer.parseInt(tempList.pop());
}
break;
case "-":
ans=Integer.parseInt(tempList.pop());
while(!tempList.empty()){
ans-=Integer.parseInt(tempList.pop());
}
break;
case "*":
ans=Integer.parseInt(tempList.pop());
while(!tempList.empty()){
ans*=Integer.parseInt(tempList.pop());
}
break;
}
stack.push(String.valueOf(ans));
i++;
continue;
}
if(c=='('||c=='+'||c=='-'||c=='*'){
stack.push(String.valueOf(c));
i++;
continue;
}
if(c==' '){
i++;
continue;
}
String temp = "";
while (i+1<line.length()&&c!=' '&&c!=')'){
temp+=c;
c=line.charAt(++i);
}
stack.push(temp);
temp="";
}
System.out.println(stack.pop());
}
}
第二题 新春红包礼盒
别人的代码,还没验证
public class RedPacket {
public static void main(String[] args) {
int res = splitArray(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 6);
System.out.println(res);
}
public static int splitArray(int[] nums, int m) {
int len = nums.length;
int[][] dp = new int[len + 1][m + 1];
for (int i = 0; i <= len; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
}
int[][] sum = new int[len + 1][len + 1];
for (int i = 0; i <= len; i++) {
sum[i][0] = 0;
sum[0][i] = 0;
}
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= i; j++) {
if (i == j) {
sum[i][j] = nums[i - 1];
} else {
sum[i][j] = sum[i - 1][j] + nums[i - 1];
}
}
}
for (int i = 1; i <= len; i++) {
dp[i][1] = sum[i][1];
}
for (int i = 2; i <= len; i++) {
int temp = Math.min(i, m);
for (int j = 2; j <= temp; j++) {
dp[i][j] = 0;
for (int k = j - 1; k < i; k++) {
dp[i][j] = Math.max(dp[i][j], Math.min(dp[k][j - 1], sum[i][k + 1]));
}
}
}
return dp[len][m];
}
}