360开发笔试0318

40道选择题+2道算法题（ACM模式）

第一题：第一行输入整数n代表总共有n扇未开的门

第二行输入每天给了第几扇门的钥匙，例如 5 3 1 2 4; 第三天给了第一扇门的钥匙

从第一扇门开始开启，只有开了前面的门才能开后面的门

例如：5

5 3 1 2 4

输出：3 4 4 5 5

初始化，将第几扇门的钥匙第几天拿到赋值给数组。

例题初始化后的数组为： 3 4 2 5 1

之后遍历一遍就可以了比前一天小就等于前一天的值 3 4 4 5 5

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] keyDate = new int[n];
        int[] open = new int[n];
        for (int i = 0; i < n; i++) {
            keyDate[i] = scan.nextInt();
            open[keyDate[i]-1] = i + 1;//初始化
        }
        for (int i = 1; i < n; i++) {
            if(open[i] < open[i-1]) open[i] = open[i-1];
        }
        for (int i = 0; i < n-1; i++) {
            System.out.print(open[i] + " ");
        }
        System.out.print(open[n - 1]);
    }
}

第二题：给出一些方程仅包含加号等号和乘号；（没有前导0，首尾不为运算符，有且仅有一个等号）

请判断这些方程能否通过插入至多一个数位（若原方程成立则可以不插）使得方程成立。

插入一个数位即将方程视为一个字符串，并将一个0到9之间的数插入中间，开头或末尾。

输入：第一行有一个整数，代表方程的数量。

接下来T行是T个方程，方程只有一个等号，且保证输入合法性，没有前导0，前后没有运算符。

输出：对于每个方程，若其成立或可以通过往该方程中插入一个数位使得方程成立，则输入Yes，否则输出No。

例如：

16=1+2 * 3

7 * 8 * 9=54

1+1=1+22

4 * 6=22+2

15+7=1+2

11+1=1+5

输出：

Yes

思路：将0-9各个位置插入遍历一遍就可以了

注意写的计算器如果是int只能过测82%，改成long可以AC

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        for (int i = 0; i < t; i++) {
            String s = scan.next();
            if(isItFunction(s)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
    public static boolean isItFunction(String s) {
        if(s.length()>1000) return false;
        String[] str = s.split("=");
        //如果直接相等
        if(calculate(str[0]) == calculate(str[1])) return true;
        //如果插入一个字符相等
        for (int i = 0; i <= s.length(); i++) {
            StringBuilder strInsert = new StringBuilder(s);
            for (int j = 0; j <= 9; j++) {
                strInsert.insert(i, j);
                str = strInsert.toString().split("=");
                if(calculate(str[0]) == calculate(str[1])) return true;
                strInsert.deleteCharAt(i);
            }
        }
        return false;
    }
    public static long calculate(String s) {
        long sum = 0;
        String num = "";
        Stack<Long> stack = new Stack<>();
        long temp = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)){
                case '+':
                    if(temp == 0){
                        stack.push(Long.parseLong(num));
                        num = "";
                    }else{
                        stack.push(stack.pop()*Long.parseLong(num));
                        num = "";
                        temp = 0;
                    }
                    break;
                case '*':
                    if(temp == 0){
                        stack.push(Long.parseLong(num));
                        num = "";
                        temp = stack.peek();
                    }else{
                        stack.push(stack.pop()*Long.parseLong(num));
                        num = "";
                        temp = stack.peek();
                    }
                    break;
                default:
                    num += s.charAt(i);
            }
        }
        if(temp == 0){
            stack.push(Long.parseLong(num));
        }else{
            stack.push(stack.pop()*Long.parseLong(num));
        }
        while (!stack.isEmpty()){
            sum += stack.pop();
        }
        return sum;
    }
}

#360#