🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系计划跟新各公司春秋招的笔试题

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📖 写在前面

夏天要来了 秋招还会远吗？

前不久春招也算是圆满结束咯，大家有拿到心仪的 offer吗？
接下来互联网的秋招也快来啦，小伙伴们有开始准备了吗？
本次给大家带来24届秋招 科大讯飞 的笔试题目三语言解析(Java/Python/Cpp)

文末有清隆学长的笔试陪伴打卡小屋活动介绍:
✨丰富的打卡奖励等你来领哦，大厂笔试题汇总，笔试面试经验贴，算法笔试模版…
💽 有兴趣的小伙伴们也可以了解一下，不要错过啦~

🎀 01.矩阵转置差值

问题描述

K小姐是一位数学爱好者,她对矩阵运算很感兴趣。最近她想到了一种新的矩阵运算方式,定义为矩阵转置差值,即矩阵中每个元素与其在转置矩阵中对应位置上元素的差的绝对值之和。

例如,对于矩阵:

$$\begin{array}{cc}4& 3\\ 2& 1\end{array}$$

其转置矩阵为:

$$\begin{array}{cc}4& 2\\ 3& 1\end{array}$$

那么原矩阵的转置差值为 $|4-4|+|3-2|+|2-3|+|1-1|=2$。

现在,K小姐拿到了一个 $n\times n$ 的矩阵,希望你能帮她计算出该矩阵的转置差值。

输入格式

第一行包含一个正整数 $n$,表示矩阵的规模。

接下来 $n$ 行,每行包含 $n$ 个空格分隔的正整数,表示矩阵中的元素。

输出格式

输出一个整数,表示该矩阵的转置差值。

样例输入

2
4 3
2 1

样例输出

2

数据范围

$1\le n\le 500$
$1\le a_{ij}\le 1000$

其中 $a_{ij}$ 表示矩阵中第 $i$ 行第 $j$ 列的元素。

题解

本题可以直接按照矩阵转置差值的定义来计算答案。我们只需要遍历矩阵的每个元素,计算其与转置矩阵中对应位置上元素的差的绝对值,然后将所有差值相加即可得到最终答案。

具体实现时,我们可以使用两重循环遍历矩阵,对于矩阵中的每个元素 $a_{ij}$,将其与转置矩阵中对应位置上的元素 $a_{ji}$ 的差的绝对值累加到答案中。这样遍历完整个矩阵后,就可以得到矩阵的转置差值了。

时间复杂度为 $O(n^2)$,空间复杂度为 $O(1)$。其中 $n$ 是矩阵的规模。

参考代码

• Python

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for i in range(n):
    for j in range(n):
        ans += abs(matrix[i][j] - matrix[j][i])

print(ans)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans += Math.abs(matrix[i][j] - matrix[j][i]);
            }
        }
        
        System.out.println(ans);
    }
}

• Cpp

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int matrix[500][500];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans += abs(matrix[i][j] - matrix[j][i]);
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

⏰ 02.K小姐的闹钟计划

问题描述

K小姐是一个非常注重时间管理的人，为了确保自己能够准时起床，她设置了 $n$ 个闹钟。某天早上，当K小姐醒来时，她看了一下当前的时间，想知道下一个闹钟会在什么时候响起，以免被吓到。

输入格式

第一行按照 $XX:XX$ 的格式输入两个数字，表示当前的时间。

第二行输入一个正整数 $n$，表示K小姐设置的闹钟数量（$1\le n\le 100$）。

接下来的 $n$ 行，每行按照 $XX:XX$ 的格式输入两个数字，表示设置的闹钟时间。

对于所有的 $n$，所有的时间保证是 $XX:XX$ 的形式，且一定在 $00:00$ 到 $23:59$ 之间。数据保证同一天内一定有一个还没响的闹钟。

输出格式

按照 $XX:XX$ 的格式输出一个时间，表示下一次闹钟响起的时间。

样例输入

12:00
3
06:00
13:00
23:59

样例输出

13:00

数据范围

$1\le n\le 100$

题解

这道题目可以通过以下步骤解决：

1. 将当前时间转换为分钟数 $nowTime$，即 $nowTime=h\times 60+m$。
2. 遍历所有闹钟时间，对于每个闹钟时间：
   • 将闹钟时间转换为分钟数 $alarmTime$。
   • 如果 $alarmTime>nowTime$，计算时间差 $gap=alarmTime-nowTime$。
   • 如果 $gap$ 比当前的最小时间差 $minGap$ 还要小，更新 $minGap$ 和对应的闹钟时间 $result$。
3. 输出 $result$，即为下一次闹钟响起的时间。

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

参考代码

• Python

def convertToMinutes(time):
    h, m = map(int, time.split(':'))
    return h * 60 + m

currentTime = input()
n = int(input())

nowTime = convertToMinutes(currentTime)
minGap = float('inf')
result = ""

for _ in range(n):
    alarmTime = input()
    alarm = convertToMinutes(alarmTime)
    if alarm > nowTime:
        gap = alarm - nowTime
        if gap < minGap:
            minGap = gap
            result = alarmTime

print(result)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String currentTime = scanner.nextLine();
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        int nowTime = convertToMinutes(currentTime);
        int minGap = Integer.MAX_VALUE;
        String result = "";

        for (int i = 0; i < n; i++) {
            String alarmTime = scanner.nextLine();
            int alarm = convertToMinutes(alarmTime);
            if (alarm > nowTime) {
                int gap = alarm - nowTime;
                if (gap < minGap) {
                    minGap = gap;
                    result = alarmTime;
                }
            }
        }

        System.out.println(result);
    }

    private static int convertToMinutes(String time) {
        String[] parts = time.split(":");
        int h = Integer.parseInt(parts[0]);
        int m = Integer.parseInt(parts[1]);
        return h * 60 + m;
    }
}

• Cpp

#include <iostream>
#include <string>
#include <climits>
using namespace std;

int toMinutes(const string& time) {
    int h = stoi(time.substr(0, 2));
    int m = stoi(time.substr(3));
    return h * 60 + m;
}

int main() {
    string curTime;
    cin >> curTime;
    int n;
    cin >> n;

    int nowTime = toMinutes(curTime);
    int minGap = INT_MAX;
    string result;

    for (int i = 0; i < n; i++) {
        string alarmTime;
        cin >> alarmTime;
        int alarm = toMinutes(alarmTime);
        if (alarm > nowTime) {
            int gap = alarm - nowTime;
            if (gap < minGap) {
                minGap = gap;
                result = alarmTime;
            }
        }
    }

    cout << result << endl;
    return 0;
}

🧷 03.K小姐的括号匹配问题

问题描述

K小姐最近在学习编程,遇到了一个有趣的问题。老师给了她一个由四种括号组成的字符串:小括号 ()、中括号 []、大括号 {} 和尖括号 <>。

然而,这个括号字符串并不一定是匹配的。为了让字符串变得匹配,K小姐需要通过最少的替换操作将其修改为匹配的括号字符串。替换操作是指将字符串中的某个括号替换为另一个括号,使得整个字符串满足以下任一条件即为匹配:

1. 空字符串。
2. 两个匹配的括号字符串连接而成,例如 ()[]。
3. 在一个匹配的括号字符串的两端加上一对匹配的括号,例如 {<>}。

K小姐想请你帮忙求出使括号字符串匹配所需的最小替换次数。

输入格式

输入仅一行,包含由四种括号字符组成的字符串。

字符串长度为偶数,不超过 $200$。

输出格式

输出一个整数,表示使括号字符串匹配所需的最小替换次数。

样例输入

[{]}

样例输出

2

数据范围

• 字符串长度为偶数,不超过 $200$。

题解

本题可以使用动态规划来解决。定义状态 $dp[i][j]$ 表示将字符串从下标 $i$ 到下标 $j$ 变成匹配括号串所需的最小替换次数。

状态转移分为三种情况考虑:

1. 如果 $s[i]$ 和 $s[j]$ 匹配,那么 $dp[i][j]=dp[i+1][j-1]$。
2. 如果 $s[i]$ 和 $s[j]$ 不匹配,可以将它们替换成匹配的括号,此时 $dp[i][j]=dp[i+1][j-1]+2$。
3. 将区间 $[i,j]$ 分成两部分,分别使其变成匹配的括号串,取最小值。即枚举分割点 $k$,有 $dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])$。

最终答案即为 $dp[0][n-1]$,其中 $n$ 为字符串长度。

时间复杂度为 $O(n^3)$,空间复杂度为 $O(n^2)$。

参考代码

• Python

def minReplacements(s):
    n = len(s)
    dp = [[n] * n for _ in range(n)]
    left = '([{<'
    right = ')]}>'
    
    def pair(c1, c2):
        if c1 in left and c2 in right:
            if left.index(c1) == right.index(c2):
                return 0
            else:
                return 1
        else:
            return 2
    
    for i in range(n - 1):
        dp[i][i+1] = pair(s[i], s[i+1])
    
    for length in range(4, n + 1, 2):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = dp[i+1][j-1] + pair(s[i], s[j])
            for k in range(i+1, j, 2):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
    
    return dp[0][n-1]

s = input().strip()
print(minReplacements(s))

• Java

import java.util.Scanner;

public class BracketMatching {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(minReplacements(s));
    }
    
    private static int minReplacements(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        String left = "([{<";
        String right = ")]}>";
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = n;
            }
        }
        
        for (int i = 0; i < n - 1; i++) {
            dp[i][i+1] = pair(s.charAt(i), s.charAt(i+1), left, right);
        }
        
        for (int len = 4; len <= n; len += 2) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = dp[i+1][j-1] + pair(s.charAt(i), s.charAt(j), left, right);
                for (int k = i + 1; k < j; k += 2) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
        
        return dp[0][n-1];
    }
    
    private static int pair(char c1, char c2, String left, String right) {
        if (left.indexOf(c1) != -1 && right.indexOf(c2) != -1) {
            if (left.indexOf(c1) == right.indexOf(c2)) {
                return 0;
            } else {
                return 1;
            }
        } else {
            return 2;
        }
    }
}

• Cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int pair(char c1, char c2, string left, string right) {
    if (left.find(c1) != string::npos && right.find(c2) != string::npos) {
        if (left.find(c1) == right.find(c2)) {
            return 0;
        } else {
            return 1;
        }
    } else {
        return 2;
    }
}

int minReplace(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, n));
    string left = "([{<";
    string right = ")]}>";
    
    for (int i = 0; i < n - 1; i++) {
        dp[i][i+1] = pair(s[i], s[i+1], left, right);
    }
    
    for (int len = 4; len <= n; len += 2) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = dp[i+1][j-1] + pair(s[i], s[j], left, right);
            for (int k = i + 1; k < j; k += 2)
              dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
    }
  return dp[0][n - 1];
}
int main(){
  string s; cin >> s;
  cout << minReplace(s) << "\n";
  return 0;
}

🎀 写在最后

🛖 这里介绍一下咱们的笔试打卡小屋

✨ 打卡小屋旨在陪伴大家，养成每日学习的好习惯。在这里，你可以：

• 🤝 与备战笔试的小伙伴相识，找到志同道合的学习小组
• 📝 通过写题解，巩固做题思路，养成良好的记录习惯
• 💡 系统掌握常考算法和数据结构，了解互联网笔试难度
• 🎁 坚持打卡，获得丰厚奖励，激励自己持之以恒

🥰 打卡奖励

打卡时长	奖励内容
7天	任选一家最新互联网笔试真题 x 1 (价值29.9r)
14天	任选一家最新互联网笔试真题 x 3 + 笔试面试经验贴
21天	任选一家最新互联网笔试真题 x 5 + 清隆三语言算法模版
28天	最新互联网大厂笔试真题汇总(价值199r) + 华为OD机试训练营 (价值89r)

7天打卡即可值回票价，心动不如行动！

🕰 每日学习安排

小屋将在每日上午发放打卡题目，包括：

• 一道算法模版题，帮助大家掌握常用算法套路
• 根据算法模版，精选一道对应的大厂笔试真题，巩固算法应用

让我们一起直击笔试重点，攻克常考题型！

📖 打卡小屋涉及题型

小屋从零基础出发，涵盖笔试常考知识点：

基础算法

• 自定义排序
• 二分
• 前缀和
• 差分
• 双指针

基础数据结构

• 栈 & 单调栈
• 队列 & 单调队列
• 并查集
• 优先队列(堆)

搜索

• DFS & BFS 基础应用
• 树的遍历
• 基础图论

动态规划 & 贪心 & 数论

• 快速幂
• 组合数
• 质数 & 因数
• 位运算
• 基础动态规划
• 常见贪心