🍭 大家好這里是清隆學長 ，一枚熱愛算法的程序員

? 本系計劃跟新各公司春秋招的筆試題

💻 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 + mcurrentTime = 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 - nowTimeif gap < minGap:minGap = gapresult = alarmTimeprint(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 0else:return 1else:return 2for 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 - 1dp[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 基礎應用
• 樹的遍歷
• 基礎圖論

動態規劃 & 貪心 & 數論

• 快速冪
• 組合數
• 質數 & 因數
• 位運算
• 基礎動態規劃
• 常見貪心