💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次难度不大，考试模式为和 leetcode 相同的核心代码模式，

1️⃣ 比较经典的双指针，但其实如果只是求交集的话用差分也是ok滴

2️⃣ 前后缀分解，比较简单

3️⃣ 计数类型的动态规划，难度中等

📅 01.会议室预订系统

问题描述

LYA公司正在开发一个智能会议室预订系统。该系统需要处理两个不同部门的会议室使用时间表，以找出可以安排跨部门会议的时间段。

每个部门都有一个按时间顺序排列的会议室空闲时间列表。第一个部门的列表记为firstList，第二个部门的列表记为secondList。每个列表中的元素都是一个时间区间，表示为[start, end]，其中start是空闲时间的开始，end是结束。

你的任务是设计一个算法，找出两个部门的空闲时间的交集，这些交集就是可以安排跨部门会议的时间段。

输入格式

第一行包含两个整数 和 ，分别表示firstList和secondList的长度。

接下来的 行，每行包含两个整数 和 ，表示firstList中的一个时间区间。

然后的 行，每行包含两个整数 和 ，表示secondList中的一个时间区间。

输出格式

输出若干行，每行两个整数，表示两个部门都空闲的时间区间。如果没有交集，则输出一个空行。

样例输入1

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

样例输出1

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

样例输入2

[[1,2],[3,4]],[[2,3]]

样例输出2

[[2,2],[3,3]]

样例输入3

[],[[4,9]]

样例输出3

[]

数据范围

• 
• 
• 每个列表中的区间都是按照开始时间升序排列的
• 每个列表中的区间都不会重叠

题解

双指针

用两个指针 和 分别指向firstList和secondList的当前区间。 比较这两个区间，找出它们的交集（如果存在的话）。

算法的主要步骤如下：

1. 初始化两个指针 和 ，分别指向两个列表的开始。
2. 当两个指针都没有到达列表末尾时，执行以下操作：
   • 计算两个当前区间的交集：
     • 交集的开始时间是两个区间开始时间的较大值
     • 交集的结束时间是两个区间结束时间的较小值
   • 如果交集有效（开始时间不大于结束时间），就将这个交集加入结果列表
   • 移动指向结束时间较小的区间的指针

举个例子，假设有以下输入：

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

1. 初始时，比较 [0,3] 和 [2,6]，得到交集 [2,3]
2. 然后我们移动到 [5,9] 和 [2,6]，得到交集 [5,6]
3. 接着比较 [5,9] 和 [8,10]，得到交集 [8,9]
4. 最后，[11,13] 和 [8,10] 没有交集，算法结束

这个算法的时间复杂度是 ，其中 和 分别是两个列表的长度。这是因为我们只需要遍历每个列表一次。空间复杂度是 ，用于存储结果。

参考代码

• Python

# 定义查找交集的函数
def findIntersection(firstList, secondList):
    # 初始化指针和结果列表
    i, j = 0, 0
    result = []

    # 遍历两个列表
    while i < len(firstList) and j < len(secondList):
        # 获取当前区间
        start1, end1 = firstList[i]
        start2, end2 = secondList[j]
        
        # 计算交集
        start = max(start1, start2)
        end = min(end1, end2)
        
        # 如果存在有效交集，添加到结果中
        if start <= end:
            result.append([start, end])
        
        # 移动指针
        if end1 < end2:
            i += 1
        else:
            j += 1

    return result

• Java

import java.util.*;

public class Main {

    
    public static int[][] findIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        
        while (i < firstList.length && j < secondList.length) {
            int start1 = firstList[i][0], end1 = firstList[i][1];
            int start2 = secondList[j][0], end2 = secondList[j][1];
            
            int start = Math.max(start1, start2);
            int end = Math.min(end1, end2);
            
            if (start <= end) {
                result.add(new int[]{start, end});
            }
            
            if (end1 < end2) {
                i++;
            } else {
                j++;
            }
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> findIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
    vector<vector<int>> result;
    int i = 0, j = 0;
    
    while (i < firstList.size() && j < secondList.size()) {
        int start1 = firstList[i][0], end1 = firstList[i][1];
        int start2 = secondList[j][0], end2 = secondList[j][1];
        
        int start = max(start1, start2);
        int end = min(end1, end2);
        
        if (start <= end) {
            result.push_back({start, end});
        }
        
        if (end1 < end2) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

🌈 02.字符串分割最优化

问题描述

LYA 是一位热爱编程的高中生，最近她在研究一种特殊的字符串处理问题。她有一个由字母 'a' 和 'b' 组成的字符串 ，她想将这个字符串分割成两个非空的子字符串。LYA 定义了一个特殊的得分系统：分割后的得分等于左子字符串中 'a' 的数量加上右子字符串中 'b' 的数量。

LYA 希望找到一种分割方法，使得得分最高。她需要你的帮助来编写一个程序，计算出这个最高得分。

输入格式

输入为一行，包含一个字符串 ，仅由小写字母 'a' 和 'b' 组成。

输出格式

输出一个整数，表示能够获得的最高得分。

样例输入1

"abbbab"

样例输出1

5

说明： 将字符串 s 划分为两个非空子字符串的可行方案有： 左子字符串 = "a" 且右子字符串 = "bbbab"，得分 = 1 + 4 = 5 左子字符串 = "ab" 且右子字符串 = "bbab"，得分 = 1 + 3 = 4 左子字符串 = "abb" 且右子字符串 = "bab"，得分 = 1 + 2 = 3 左子字符串 = "abbb" 且右子字符串 = "ab"，得分 = 1 + 1 = 2 左子字符串 = "abbb