26屆暑期實(shí)習(xí)PDD4.20筆試題

1. 給出n個字符串，每個字符串可以選擇x_i個字符，要求從n個字符串里面選出來的字符中輸出長為k的最小字典序的字符串。

輸入每一個字符串s，轉(zhuǎn)換為[]byte然后排序，切片前x_i個字節(jié)；將這n個切出來的字節(jié)數(shù)組拼成一個大的字節(jié)數(shù)組，排序，返回

2. 根據(jù)演員之間的意見來確定薪資分配，輸入n,m表示一共有n個演員和m條意見，一條意見的格式是(a,b)，也就是有一條意見表示演員a應(yīng)該比演員b薪資高。

先建成一個有向圖，節(jié)點(diǎn)是演員編號，如果有意見(a,b)，那么就建一條(b,a)的邊；同時建一個數(shù)組，用來存儲每個節(jié)點(diǎn)的入讀?？梢钥闯?，每個節(jié)點(diǎn)的費(fèi)用只和指向該節(jié)點(diǎn)的費(fèi)用相關(guān)，這樣就可以使用BFS來做。

入度為0的節(jié)點(diǎn)入隊(duì)，入隊(duì)的是一個結(jié)構(gòu)體包括節(jié)點(diǎn)編號x以及節(jié)點(diǎn)的費(fèi)用money
隊(duì)列不為空
彈出一個節(jié)點(diǎn)t
res += t.money
b遍歷t指向的節(jié)點(diǎn)v
如果v的度數(shù)為1，將其加入隊(duì)列，v.money = t.money + 10
v的度數(shù)減去1

3. 遍歷一遍度數(shù)的數(shù)組，如果有節(jié)點(diǎn)度數(shù)大于0，表示圖中有環(huán)的存在，res = -1

3. 將一個數(shù)組變?yōu)閲?yán)格上升的數(shù)組，可以將數(shù)組中某個元素減小或增大，求最小變化的次數(shù)

沒做出來，下面是deepseek給的思路：

如果數(shù)組中的元素位置不能改變，即不能通過重新排列元素來形成嚴(yán)格遞增序列，那么我們需要找到一種方法，通過僅增加或減少某些元素的值（不能交換位置）來使數(shù)組嚴(yán)格遞增，并且操作次數(shù)最少。

方法思路

此時，問題轉(zhuǎn)化為：在保持元素原始順序的前提下，調(diào)整某些元素的值（可以增大或減小），使得整個數(shù)組嚴(yán)格遞增（nums[i] < nums[i+1]），并且調(diào)整的次數(shù)最少。

關(guān)鍵觀察

嚴(yán)格遞增約束：對于所有 i，必須滿足 nums[i] < nums[i+1]。
調(diào)整方式：可以對任意元素進(jìn)行增加或減少操作，但不能交換位置。
目標(biāo)：找到最少的調(diào)整次數(shù)，使得整個數(shù)組嚴(yán)格遞增。

動態(tài)規(guī)劃解法

我們可以使用動態(tài)規(guī)劃（DP）來解決這個問題：

定義 dp[i] 表示以 nums[i] 結(jié)尾的嚴(yán)格遞增子序列的最小操作次數(shù)。
對于每個 i，我們需要檢查所有 j < i，并確保 nums[j] < nums[i]，同時計(jì)算調(diào)整 nums[i] 或 nums[j] 的最小操作次數(shù)。

但由于直接DP的時間復(fù)雜度是 O(n^2)，對于較大的 n（如 n ≤ 1e5），我們需要更優(yōu)化的方法。

貪心優(yōu)化

我們可以采用類似 最長遞增子序列（LIS） 的貪心策略，但需要額外考慮調(diào)整后的值必須滿足嚴(yán)格遞增：

維護(hù)一個動態(tài)數(shù)組 d，其中 d[i] 表示長度為 i+1 的嚴(yán)格遞增子序列的最小末尾值。
對于每個 nums[i]，找到 d 中第一個 ≥ nums[i] 的位置 k，并用 nums[i] 替換 d[k]。
這樣，d 的長度即為最長嚴(yán)格遞增子序列的長度，最少操作次數(shù)為 n - len(d)。

但需要注意：

由于位置不能改變，我們需要確保在調(diào)整時，nums[i] 可以比前一個數(shù)大（如果選擇保留它），否則必須調(diào)整它或前面的數(shù)。
因此，直接使用LIS的長度可能不完全準(zhǔn)確，需要進(jìn)一步優(yōu)化。

最優(yōu)解法

我們可以結(jié)合 貪心 + 二分查找 的方法，并額外記錄調(diào)整后的值：

初始化 d = []。
遍歷 nums，對于每個 num：如果 num 可以放在 d 的末尾（即 num > d[-1]），直接加入 d。否則，找到 d 中第一個 ≥ num 的位置 k，并嘗試用 num 替換 d[k]（相當(dāng)于調(diào)整 d[k] 或 num）。
最少操作次數(shù)為 n - len(d)。

解決代碼

def min_operations_to_increase(nums):
    if not nums:
        return 0
    d = []
    for num in nums:
        if not d or num > d[-1]:
            d.append(num)
        else:
            left, right = 0, len(d) - 1
            pos = right
            while left <= right:
                mid = (left + right) // 2
                if d[mid] >= num:
                    pos = mid
                    right = mid - 1
                else:
                    left = mid + 1
            d[pos] = num
    return len(nums) - len(d)

代碼解釋

初始化動態(tài)數(shù)組 d：用于存儲當(dāng)前嚴(yán)格遞增子序列的最小末尾值。
遍歷 nums：如果 num 可以擴(kuò)展當(dāng)前嚴(yán)格遞增序列（num > d[-1]），直接加入 d。否則，用二分查找找到 d 中第一個 ≥ num 的位置，并用 num 替換它（相當(dāng)于調(diào)整 num 或 d[k]）。
最少操作次數(shù)：n - len(d)，即總元素?cái)?shù)減去最長嚴(yán)格遞增子序列的長度。

例子驗(yàn)證

nums = [1, 2, 3, 6, 5, 4]： LIS 為 [1, 2, 3, 6] 或 [1, 2, 3, 5]，長度 4。最少操作次數(shù) 6 - 4 = 2（調(diào)整 5 和 4）。
nums = [1, 3, 2, 4]： LIS 為 [1, 3, 4] 或 [1, 2, 4]，長度 3。最少操作次數(shù) 4 - 3 = 1（調(diào)整 2 或 3）。