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];
    }
}
Last modification:March 4th, 2021 at 10:25 pm