20210902神策后端笔试

神策数据后端，8/31发的笔试链接，3日内做完就行。牛客网笔试。

10道单选，5道多选，3道编程题。
哇神策编程题就那几个吗。。。好多人都是重题。实不相瞒我看了两个笔经，碰到了。

感谢大佬的分享：

编程题

题目简述：

:sob:

括号匹配：字符串(1)23(4()5)6，输出里面每对括号对应下标（必然匹配）。
很赞的整数对：三个数x,y,m。(x,y)里面有一个数大于m，就是很赞的整数对。
字符串去除重复空格，每个单词进行反转

第一题：字符串、有效括号数

给定一个字符串，打印里面匹配的括号的个数和下标，比如：
(1)23(4()5)6，一共有三对括号，下标0和2是一对，5和10是一对，7和8是一对。输入数据的括号均能成对出现，以下输入是不存在的：((1)
输入描述：一个包含数字和括号的字符串，一行
输出描述：多行输出，第一行是成对括号的个数，后面每行是一个括号的下标。

输入：(1)
输出：
1
0
2
说明：共有1对成对的括号，其下标为0和2

栈的应用，不过有点坑的是输出需要从小到大：

比如还是上面题目里的例子，必须要这样输出0 2 5 10 7 8 才可以，也就是第一个括号下标要 0,5,7 这样从小到大有序输出。

import java.util.*;

/**
 * Created on 2021/9/2,下午 4:15
 *
 * @author SongX64
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String s = scanner.nextLine();
            char[] chars = s.toCharArray();

            Stack<Integer> stack = new Stack<>();
            TreeMap<Integer,Integer> treeMap = new TreeMap<>();

            for (int i = 0; i < chars.length; i++) {
                if(chars[i] == '('){
                    stack.push(i);
                }else if (chars[i] == ')'){
                    treeMap.put(stack.pop(),i);
                }
            }

            System.out.println(treeMap.keySet().size());
            for (Integer key : treeMap.keySet()){
                System.out.println(key);
                System.out.println(treeMap.get(key));
            }
        }
    }
}

第二题：很赞的整数对

题目：给一个整数对(x,y)，并且允许把其中一个数修改成之前两个数的和，x+y。比如(5,2)，两数之和为7，经过一次修改可以变成(7,2)或(5,7)。再给一个整数m，问至少要做多少次上述修改操作，才能使两个数组成的数对是对m很赞的整数对。两个数中至少有一个数大于等于m，这个数对就是很赞的整数对。

输入描述：一行包含3个整数，分别是x,y,m。其中x，y是最初的两个整数，取值范围是int32；m是一个整数，取值范围是int32；
输出描述：至少要做多少次上述修改操作，才能使得数对为m的很赞整数对。

输入： 1 2 5
输出： 2
说明：经过2次操作，一种可行的但不一定是最优的操作方法是：(1,2)–>(3,2)–>(5,2)

输入：-1 4 15
输出： 4
说明：最少经过4次操作，一种可行的但不一定是最优的操作方法是：(-1,4)–>(3,4)–>(7,4)–>(11,4)–>(15,4)

输入： 0 -1 5
输出： -1
说明：经过多少次操作都无法满足要求，输出-1

最终AC95点几。。。实在想不出来了。

import java.util.Scanner;

/**
 * Created on 2021/9/2,下午 4:25
 *
 * @author SongX64
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 越界问题，所以说用Long来避免
        while (scanner.hasNextLong()) {
            long x = scanner.nextLong();
            long y = scanner.nextLong();
            long m = scanner.nextLong();

            long count = 0;
            // 循环控制标志
            boolean flag = true;

            // 已经满足条件
            if (m <= x || m <= y) {
                count = 0;
                flag = false;
            } else {
                // 不满足条件，进行操作
                // m为正，xy有0
                if (x == 0 || y == 0) {
                    count = -1;
                    flag = false;
                }
                // 相加永久等于0
                if (m != 0 && x + y == 0) {
                    count = -1;
                    flag = false;
                }
                // 不满足条件，且x和y都小于0，xy只会越加越小
                if ( x < 0 && y < 0) {
                    // m为正，xy都为负数
                    count = -1;
                    flag = false;
                }

            }
            // 判断通过，进行操作
            // 若有一个大于等于m，就可以了
            while (flag && x < m && y < m) {
                // 选择一个较小的进行替换
                if (x <= y) {
                    x += y;
                } else {
                    y += x;
                }
                count++;
            }
            System.out.println(count);
        }
    }
}

第三题：字符串反转

给定字符串s,要求把s中多于一个的连续空压缩成一个空格，并将连续的非空格字符串倒序打印出来，例如，给定”abc def efg”，打印”cba fed gfe”。

输入：abc def efg
输出： cba fed gfe

直接字符数组处理的，AC100。

import java.util.Scanner;

/**
 * Created on 2021/9/2,下午 4:38
 *
 * @author SongX64
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String s = scanner.nextLine();
            s.trim();
            char[] chars = s.toCharArray();
            StringBuilder stringBuilder = new StringBuilder();

            // 快慢指针
            for (int i = 0; i < chars.length; ) {
                // 快指针找到空格
                int j = i;
                while (j < chars.length && chars[j] != ' ') {
                    j++;
                }
                // 记录单词末尾空格位置，然后逆序单词
                int temp = j;
                while (j!=i){
                    j--;
                    stringBuilder.append(chars[j]);
                }
                // 添加一个空格，之后慢指针跳过多个空格
                stringBuilder.append(' ');
                i = temp;
                while (i < chars.length && chars[i] == ' '){
                    i++;
                }
            }
            System.out.println(stringBuilder);
        }
    }
}