招商银行（深圳）笔试复盘

在线笔试，10月24日发的，10月26日晚上做的

30道八股选择题+2道算法题

1.你将得到一个仅能有左括号和右括号组成的字符串 x。你的任务是发现字符串中存在几对匹配的括号。
public class BracketMatchCounter {
    // 计算括号字符串中的匹配对数
    public static int countMatchPairs(String s) {
        int leftCount = 0;   // 记录未匹配的左括号数量
        int matchPairs = 0;  // 记录最终匹配的括号对数

        // 遍历字符串的每个字符
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                // 遇到左括号，未匹配计数+1
                leftCount++;
            } else if (c == ')') {
                // 遇到右括号且有未匹配左括号时，完成一次匹配
                if (leftCount > 0) {
                    matchPairs++;
                    leftCount--; // 消耗一个未匹配的左括号
                }
            }
            // 若存在非括号字符，直接忽略（按题目“仅含括号”的条件可不处理）
        }
        return matchPairs;
    }

    public static void main(String[] args) {
        // 定义测试用例，覆盖多种场景
        String[] testCases = {
                "(()())",  // 完全匹配，预期3对
                "())",     // 右括号多余，预期1对
                "(((",     // 左括号多余，预期0对
                "()()()",  // 连续匹配，预期3对
                ")()(",    // 交叉不匹配，预期1对
                ""         // 空字符串，预期0对
        };

        // 执行测试并输出结果
        for (String testStr : testCases) {
            int result = countMatchPairs(testStr);
            System.out.printf("字符串 \"%s\" 的匹配括号对数：%d%n", testStr, result);
        }
    }
}
2.小紫有一个 change 函数，每次传入一个整数 x，然后将 x 修改为 x 在二进制之下的一的个数。小紫想要知道在一个元素中所有元素的代价之和，一个元素的代价是将这个元素变成一，需要调用的 change 函数的次数。
public class ElementCostCalculator {
    // 1. 核心change函数：返回x二进制中1的个数
    private static int change(int x) {
        if (x == 0) return 0; // 0的二进制无1，特殊处理
        int count = 0;
        while (x != 0) {
            x = x & (x - 1); // 清除x二进制最右侧的1，高效统计1的个数
            count++;
        }
        return count;
    }

    // 2. 计算单个元素的代价：从x到1所需的change调用次数
    private static int getSingleCost(int x) {
        // 边界条件：x=1时无需调用，代价为0
        if (x == 1) return 0;
        
        int cost = 0;
        int current = x;
        // 循环调用change，直到结果为1，每调用一次代价+1
        while (current != 1) {
            current = change(current);
            cost++;
        }
        return cost;
    }

    // 3. 计算数组所有元素的代价之和
    public static int getTotalCost(int[] arr) {
        int total = 0;
        for (int num : arr) {
            // 过滤非正整数（题目隐含为正整数，避免无效值影响结果）
            if (num <= 0) {
                System.out.printf("警告：元素 %d 为非正整数，无法计算代价，已跳过%n", num);
                continue;
            }
            total += getSingleCost(num);
        }
        return total;
    }

    // 测试示例
    public static void main(String[] args) {
        // 测试数组：包含不同场景的元素
        int[] testArray = {5, 8, 1, 15, 7, 0, -3};
        int totalCost = getTotalCost(testArray);
        
        System.out.println("=====================");
        System.out.printf("数组所有元素的代价之和：%d%n", totalCost);
    }
}