笔试时间：2024年09月20日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

给两个二维数组a和b，长度分别为n和m，其中a[i] = {start_i, end_i}，b[i] = {start_i, end_i}。a中的区间不相交，b中的区间也不相交，且a和b中的区间均已按照左端点排好序（升序）。求a和b中相交的区间并返回。

输入描述

区间list。

0 < start_i < end_i < start_(i + 1) < 10000

输出描述

输出二维数组表示相交的所有区间。

样例输入

[[0, 3], [5, 9], [11, 13]], [[2, 6], [8, 10]]

样例输出

[[2, 3], [5, 6], [8, 9]]

参考题解

双指针

C++：[此代码未进行大量数据的测试，仅供参考]

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> findIntersection(vector<vector<int>>& a, vector<vector<int>>& b) {
        int n = a.size();
        int m = b.size();
        vector<vector<int>> ans;
        for (int i = 0, j = 0; i < n && j < m; ) {
            int l1 = a[i][0], r1 = a[i][1];
            int l2 = b[j][0], r2 = b[j][1];
            if (r1 < l2) {
                i++;
            } else if (r2 < l1) {
                j++;
            } else {
                ans.push_back({max(l1, l2), min(r1, r2)});
                if (r1 < r2) {
                    i++;
                } else {
                    j++;
                }
            }
        }
        return ans;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<int[]> findIntersection(List<int[]> a, List<int[]> b) {
        int n = a.size();
        int m = b.size();
        List<int[]> ans = new ArrayList<>();
        int i = 0, j = 0;
        
        while (i < n && j < m) {
            int l1 = a.get(i)[0], r1 = a.get(i)[1];
            int l2 = b.get(j)[0], r2 = b.get(j)[1];
            
            if (r1 < l2) {
                i++;
            } else if (r2 < l1) {
                j++;
            } else {
                ans.add(new int[] { Math.max(l1, l2), Math.min(r1, r2) });
                if (r1 < r2) {
                    i++;
                } else {
                    j++;
                }
            }
        }
        
        return ans;
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

class Solution:
    def findIntersection(self, a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
        n = len(a)
        m = len(b)
        ans = []
        i, j = 0, 0
        while i < n and j < m:
            l1, r1 = a[i][0], a[i][1]
            l2, r2 = b[j][0], b[j][1]
            if r1 < l2:
                i += 1
            elif r2 < l1:
                j += 1
            else:
                ans.append([max(l1, l2), min(r1, r2)])
                if r1 < r2:
                    i += 1
                else:
                    j += 1
        return ans

第二题

题目

给一个只有字符a和b组成的字符串s，请你计算将s分成两个非空子字符串（左边一个右边一个）的最大的分是多少？（左字符串的得分是a的个数，右字符串的得分是b的个数）。

输入描述

字符串s

2 <= s.length <= 500

输出描述

输出答案

样例输入

abbbab

样例输出

5

参考题解

遍历左字符串即可，注意非空的约束。

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int StringSplit(string str) {
        int n = str.size();
        int a = 0, b = 0;
        for (char c : str) {
            if (c == 'b') {
                b++;
            }
        }
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            if (str[i] == 'a') {
                a++;
            }else {
                b--;
            }
            ans = max(ans, a + b);
        }
        return ans;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

class Solution {
    public int StringSplit(String str) {