商汤研发笔试 100-100-20-100

关于第三题，始终没有找到正确的计算姿势，有dalao指教一下么

1

package Interview2020.SenseTime._1;

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] ss = s.split(" ");

        Stack<Integer> stack = new Stack<>();
        for(String t : ss){
            if(isCal(t)){
                int a2 = stack.pop();
                int a1 = stack.pop();
                if(t.equals("+")) stack.push(a1+a2);
                else if(t.equals("-")) stack.push(a1-a2);
                else if(t.equals("*")) stack.push(a1*a2);
                else if(t.equals("/")) stack.push(a1/a2);
            }
            else{
                stack.push(Integer.valueOf(t));
            }
        }

        System.out.println(stack.peek());
    }

    private static boolean isCal(String s){
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"))
            return true;
        return false;
    }
}

2

package Interview2020.SenseTime._2;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];
        for(int i=0; i < N; i++){
            nums[i] = sc.nextInt();
        }

        int max = 0;
        for(int i=1; i < N-1; i++){
            int left = i;
            int right = i;
            while(left-1 >=0 && nums[left] > nums[left-1]) left--;
            while(right+1 < N && nums[right] > nums[right+1]) right++;
            if(right - left + 1 >= 3 && left < i && right > i)
                max = Math.max(right-left+1,max);
        }

        System.out.println(max);
    }
}

3

package Interview2020.SenseTime._3;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int year = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int ini = sc.nextInt();

        //尝试暴力计算
        dp = new int[year+1];
        dp[0] = ini;
        for(int i=1; i <= year; i++){
            int part1 = (a * helper(i-1))%1000000007;
            int part2 = (b * helper(i-2))%1000000007;
            int part3 = (c * helper(i-3))%1000000007;
            int part40 = (2*i)%1000000007;
            int part41 = (part40*i)%1000000007;
            int part42 = (part41-i)%1000000007;
            int part43 = (part42+32767)%1000000007;
            int part4 = part43;

            int p1 = (part1+part2)%1000000007;
            int p2 = (p1+part3)%1000000007;
            int p3 = (p2+part4)%1000000007;
            dp[i] = p3;
        }

        System.out.println(dp[year]);
    }

    private static int helper(int i){
        if(i < 0)
            return 0;
        return dp[i];
    }
}

4

package Interview2020.SenseTime._4;

import java.util.*;

public class Main {
    private static int res = 0;
    private static Set<String> set = new HashSet<>();
    private static Set<Integer> sqrt = new HashSet<>();

    private static List<List<Integer>> used = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0; i < n; i++){
            nums[i] = sc.nextInt();
        }

        if(n == 1){
            System.out.println(res);
            return;
        }
        calculate();
        permutation(nums,0);
        System.out.println(res);
    }

    private static void calculate(){
        for(int i=0; i <= 100; i++){
            sqrt.add(i*i);
        }
    }

    private static boolean isValid(int[] nums){
        for(int i=0; i < nums.length-1; i++){
            if(!sqrt.contains(nums[i]+nums[i+1]))
                return false;
        }
        return true;
    }

    private static void permutation(int[] nums,int beginIndex){
        if(beginIndex == nums.length){
            String s = "";
            for(int i=0; i < nums.length; i++){
                s += String.valueOf(nums[i]);
            }
            if(!set.contains(s)){
                set.add(s);
                if(isValid(nums)){
                    res++;
                }
            }

//            boolean isSame = false;
//            for(int i=0; i < used.size(); i++){
//                List<Integer> t = used.get(i);
//                isSame = true;
//                for(int j=0; j < t.size(); j++){
//                    if(t.get(j) != nums[j]){
//                        isSame = false;
//                        break;
//                    }
//                }
//                if(isSame) break;
//            }
//            if(!isSame){
//                if(isValid(nums)) res++;
//            }
//            List<Integer> tt = new ArrayList<>();
//            for(int i=0; i < nums.length; i++) tt.add(nums[i]);
//            used.add(tt);
        }

        for(int curIndex=beginIndex; curIndex < nums.length; curIndex++){
            swap(nums,curIndex,beginIndex);
            permutation(nums,beginIndex+1);
            swap(nums,curIndex,beginIndex);
        }

    }

    private static void swap(int[] nums,int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

}