? 春招備戰(zhàn)指南 ?

?? 學(xué)習(xí)建議：

• 先嘗試獨立解題（建議用時：90分鐘/套）
• 對照解析查漏補缺
• 配套練習(xí)題庫

?? 題面描述背景等均已深度改編，做法和題目本質(zhì)基本保持一致。

?? 感謝各位朋友們的訂閱，你們的支持是我們創(chuàng)作的最大動力

春秋招合集 -> 互聯(lián)網(wǎng)必備刷題寶典??

2025.03.15-電信題目集合

題目一：音樂節(jié)奏優(yōu)化器

1??：音符序列構(gòu)建與表示 2??：優(yōu)先隊列（最小堆）應(yīng)用 3??：貪心策略優(yōu)化音符持續(xù)時間

整體難度：中等

該題目要求通過有限次操作，使所有音符中持續(xù)時間最短的那個音符盡可能長。每次操作可以選擇一個音符，將其持續(xù)時間延長10個單位。關(guān)鍵是將輸入字符串轉(zhuǎn)換為音符序列，然后使用優(yōu)先隊列（最小堆）來高效地找到持續(xù)時間最短的音符。每次從優(yōu)先隊列中取出持續(xù)時間最短的音符，增加其持續(xù)時間后再放回隊列，重復(fù)操作k次。時間復(fù)雜度為O(n + k log n)，其中n是音符的數(shù)量，k是操作次數(shù)。

題目二：情緒識別器

1??：表情符號識別與統(tǒng)計 2??：字符串模式匹配 3??：情感傾向判斷邏輯

整體難度：簡單

該題目要求統(tǒng)計字符串中兩種表情符號(":-)"和":-("）的數(shù)量，并根據(jù)它們的數(shù)量關(guān)系判斷文本的情感傾向。通過遍歷字符串，識別并統(tǒng)計這兩種表情符號的出現(xiàn)次數(shù)，然后根據(jù)統(tǒng)計結(jié)果判斷情感傾向：高興表情多則輸出"Happy"，難過表情多則輸出"Sad"，數(shù)量相等且至少各有一個則輸出"Just so so"，沒有表情則輸出"None"。時間復(fù)雜度為O(n)，其中n是字符串的長度。

題目三：商場折扣計算器

1??：階梯式折扣規(guī)則應(yīng)用 2??：條件判斷與優(yōu)惠選擇 3??：精確小數(shù)計算與格式化

整體難度：簡單

該題目要求根據(jù)給定的購物金額，計算應(yīng)用最優(yōu)惠折扣后的最終支付金額。根據(jù)不同的金額閾值（100元、500元、2000元、5000元），分別應(yīng)用不同的折扣率（9折、8折、7折、6折）。關(guān)鍵是正確判斷適用的折扣等級，計算折扣后的金額，并將結(jié)果保留一位小數(shù)輸出。由于只需要進行簡單的條件判斷和計算，時間復(fù)雜度為O(1)。

01. 音樂節(jié)奏優(yōu)化器

問題描述

小基是一位音樂愛好者，她喜歡用字母表示不同的音調(diào)： 表示 la， 表示 xi， 表示 do， 表示 re， 表示 mi， 表示 fa， 表示 sol。當一個音調(diào)需要延長時間時，小基會使用多個相同的字母來表示該音的持續(xù)時間。例如， 表示共有 個音符，分別是：一個持續(xù)時間為 的 do，一個持續(xù)時間為 的 la，一個持續(xù)時間為 的 xi，以及一個持續(xù)時間為 的 do。

現(xiàn)在，小基有 次操作機會，每次操作可以選擇一個音符，將其持續(xù)時間延長 個單位。小基希望通過這些操作，使得最終所有音符中持續(xù)時間最短的那個音符盡可能長。

你需要幫助小基設(shè)計一個操作方案，并輸出最終每個音符的持續(xù)時間。

輸入格式

第一行輸入一個字符串，長度不超過 ，表示小基的音樂序列。字符串僅包含 到 這七種大寫字母。

第二行輸入一個正整數(shù) ，表示小基可以進行的操作次數(shù)。

輸出格式

首先輸出 行，每行包含一個正整數(shù) 和一個字符 ，表示小基對第 個音符進行操作，該音符的音調(diào)為 。

最后輸出一個字符串，格式為 ，表示最終操作后，每個音符及其持續(xù)時間。

如果有多種不同的操作方案，輸出任意一種即可。但需要保證最終音符持續(xù)時間的最小值是盡可能大的。

樣例輸入

CCABCC
3

樣例輸出

2 A
3 B
2 A
C(2)A(21)B(11)C(2)

樣例解釋

共操作3次。 對第2個音符A操作1次，持續(xù)時間變成11。 對第3個音符B操作1次，持續(xù)時間變成11。 對第2個音符A再操作1次，持續(xù)時間變成21。 操作結(jié)束后，音符持續(xù)時間的最小值為2。可以證明，這個最小值是盡可能大的。

數(shù)據(jù)范圍

• 字符串長度不超過
• 字符串僅包含 到 這七種大寫字母
• 

題解

這道題目要求我們通過有限次操作，使得所有音符中持續(xù)時間最短的那個音符盡可能長。

解題思路：

1. 首先，我們需要將輸入的字符串轉(zhuǎn)換為音符序列，每個音符包含其音調(diào)和持續(xù)時間。例如，將"CCABCC"轉(zhuǎn)換為[(C,2), (A,1), (B,1), (C,2)]。
2. 然后，我們需要進行k次操作，每次操作選擇持續(xù)時間最短的音符，將其持續(xù)時間增加10。
3. 如果有多個音符的持續(xù)時間相同且最短，我們可以任選其中一個進行操作。

為了高效地找到持續(xù)時間最短的音符，我們可以使用優(yōu)先隊列（最小堆）。每次從優(yōu)先隊列中取出持續(xù)時間最短的音符，增加其持續(xù)時間后再放回隊列。

時間復(fù)雜度：，其中n是音符的數(shù)量，k是操作次數(shù)。我們需要O(n)的時間來構(gòu)建音符序列，然后進行k次操作，每次操作需要O(log n)的時間來維護優(yōu)先隊列。 空間復(fù)雜度：，需要存儲音符序列和優(yōu)先隊列。

參考代碼

Python

import sys
import heapq
input = lambda:sys.stdin.readline().strip()

def optimize_music():
    # 讀取輸入
    music = input()
    k = int(input())
    
    # 構(gòu)建音符序列
    notes = []
    i = 0
    note_id = 1
    
    while i < len(music):
        # 找到連續(xù)相同的字符
        j = i
        while j < len(music) and music[j] == music[i]:
            j += 1
        
        # 添加音符(持續(xù)時間, 音調(diào), 編號)
        duration = j - i
        note = (duration, music[i], note_id)
        notes.append(note)
        note_id += 1
        i = j
    
    # 創(chuàng)建最小堆，按持續(xù)時間排序
    heap = [(duration, tone, idx) for duration, tone, idx in notes]
    heapq.heapify(heap)
    
    # 記錄每個音符的最終持續(xù)時間
    final_durations = {idx: duration for duration, _, idx in notes}
    final_tones = {idx: tone for _, tone, idx in notes}
    
    # 執(zhí)行k次操作
    operations = []
    for _ in range(k):
        # 取出持續(xù)時間最短的音符
        duration, tone, idx = heapq.heappop(heap)
        
        # 記錄操作
        operations.append((idx, tone))
        
        # 增加持續(xù)時間并放回堆
        new_duration = duration + 10
        final_durations[idx] = new_duration
        heapq.heappush(heap, (new_duration, tone, idx))
    
    # 輸出操作序列
    for idx, tone in operations:
        print(f"{idx} {tone}")
    
    # 輸出最終結(jié)果
    result = ""
    for idx in range(1, note_id):
        result += f"{final_tones[idx]}({final_durations[idx]})"
    
    print(result)

if __name__ == "__main__":
    optimize_music()

C++

#include <bits/stdc++.h>
using namespace std;

// 自定義比較函數(shù)，按持續(xù)時間升序排序
struct CompareNotes {
    bool operator()(const tuple<int, char, int>& a, const tuple<int, char, int>& b) {
        // 如果持續(xù)時間不同，按持續(xù)時間排序
        if (get<0>(a) != get<0>(b)) {
            return get<0>(a) > get<0>(b);
        }
        // 如果持續(xù)時間相同，按編號排序
        return get<2>(a) > get<2>(b);
    }
};

void solve() {
    string music;
    int k;
    cin >> music >> k;
    
    // 構(gòu)建音符序列
    vector<tuple<int, char, int>> notes;
    int i = 0, note_id = 1;
    
    while (i < music.size()) {
        // 找到連續(xù)相同的字符
        int j = i;
        while (j < music.size() && music[j] == music[i]) {
            j++;
        }
        
        // 添加音符(持續(xù)時間, 音調(diào), 編號)
        int duration = j - i;
        notes.emplace_back(duration, music[i], note_id++);
        i = j;
    }
    
    // 創(chuàng)建最小堆
    priority_queue<tuple<int, char, int>, vector<tuple<int, char, int>>, CompareNotes> pq;
    for (const auto& note : notes) {
        pq.push(note);
    }
    
    // 記錄每個音符的最終持續(xù)時間和音調(diào)
    unordered_map<int, int> final_durations;
    unordered_map<int, char> final_tones;
    
    for (const auto& [duration, tone, idx] : notes) {
        final_durations[idx] = duration;
        final_tones[idx] = tone;
    }
    
    // 執(zhí)行k次操作
    for (int i = 0; i < k; i++) {
        // 取出持續(xù)時間最短的音符
        auto [duration, tone, idx] = pq.top();
        pq.pop();
        
        // 輸出操作
        cout << idx << " " << tone << endl;
        
        // 增加持續(xù)時間并放回堆
        duration += 10;
        final_durations[idx] = duration;
        pq.push(make_tuple(duration, tone, idx));
    }
    
    // 輸出最終結(jié)果
    string result = "";
    for (int idx = 1; idx < note_id; idx++) {
        result += final_tones[idx] + string("(") + to_string(final_durations[idx]) + string(")");
    }
    
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String music = sc.nextLine();
        int k = sc.nextInt();
        
        // 構(gòu)建音符序列
        List<Note> notes = new ArrayList<>();
        int i = 0, noteId = 1;