26届暑期实习PDD4.20笔试题

1. 给出n个字符串，每个字符串可以选择x_i个字符，要求从n个字符串里面选出来的字符中输出长为k的最小字典序的字符串。

输入每一个字符串s，转换为[]byte然后排序，切片前x_i个字节；将这n个切出来的字节数组拼成一个大的字节数组，排序，返回

2. 根据演员之间的意见来确定薪资分配，输入n,m表示一共有n个演员和m条意见，一条意见的格式是(a,b)，也就是有一条意见表示演员a应该比演员b薪资高。

先建成一个有向图，节点是演员编号，如果有意见(a,b)，那么就建一条(b,a)的边；同时建一个数组，用来存储每个节点的入读。可以看出，每个节点的费用只和指向该节点的费用相关，这样就可以使用BFS来做。

1. 入度为0的节点入队，入队的是一个结构体包括节点编号x以及节点的费用money
2. 队列不为空
1. 弹出一个节点t
2. res += t.money
3. b遍历t指向的节点v
1. 如果v的度数为1，将其加入队列，v.money = t.money + 10
2. v的度数减去1

3. 遍历一遍度数的数组，如果有节点度数大于0，表示图中有环的存在，res = -1

3. 将一个数组变为严格上升的数组，可以将数组中某个元素减小或增大，求最小变化的次数

没做出来，下面是deepseek给的思路：

如果数组中的元素位置不能改变，即不能通过重新排列元素来形成严格递增序列，那么我们需要找到一种方法，通过仅增加或减少某些元素的值（不能交换位置）来使数组严格递增，并且操作次数最少。

方法思路

此时，问题转化为：在保持元素原始顺序的前提下，调整某些元素的值（可以增大或减小），使得整个数组严格递增（nums[i] < nums[i+1]），并且调整的次数最少。

关键观察

1. 严格递增约束：对于所有 i，必须满足 nums[i] < nums[i+1]。
2. 调整方式：可以对任意元素进行增加或减少操作，但不能交换位置。
3. 目标：找到最少的调整次数，使得整个数组严格递增。

动态规划解法

我们可以使用动态规划（DP）来解决这个问题：

• 定义 dp[i] 表示以 nums[i] 结尾的严格递增子序列的最小操作次数。
• 对于每个 i，我们需要检查所有 j < i，并确保 nums[j] < nums[i]，同时计算调整 nums[i] 或 nums[j] 的最小操作次数。

但由于直接DP的时间复杂度是 O(n^2)，对于较大的 n（如 n ≤ 1e5），我们需要更优化的方法。

贪心优化

我们可以采用类似 最长递增子序列（LIS） 的贪心策略，但需要额外考虑调整后的值必须满足严格递增：

1. 维护一个动态数组 d，其中 d[i] 表示长度为 i+1 的严格递增子序列的最小末尾值。
2. 对于每个 nums[i]，找到 d 中第一个 ≥ nums[i] 的位置 k，并用 nums[i] 替换 d[k]。
3. 这样，d 的长度即为最长严格递增子序列的长度，最少操作次数为 n - len(d)。

但需要注意：

• 由于位置不能改变，我们需要确保在调整时，nums[i] 可以比前一个数大（如果选择保留它），否则必须调整它或前面的数。
• 因此，直接使用LIS的长度可能不完全准确，需要进一步优化。

最优解法

我们可以结合 贪心 + 二分查找 的方法，并额外记录调整后的值：

1. 初始化 d = []。
2. 遍历 nums，对于每个 num： 如果 num 可以放在 d 的末尾（即 num > d[-1]），直接加入 d。否则，找到 d 中第一个 ≥ num 的位置 k，并尝试用 num 替换 d[k]（相当于调整 d[k] 或 num）。
3. 最少操作次数为 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)

代码解释

1. 初始化动态数组 d：用于存储当前严格递增子序列的最小末尾值。
2. 遍历 nums： 如果 num 可以扩展当前严格递增序列（num > d[-1]），直接加入 d。否则，用二分查找找到 d 中第一个 ≥ num 的位置，并用 num 替换它（相当于调整 num 或 d[k]）。
3. 最少操作次数：n - len(d)，即总元素数减去最长严格递增子序列的长度。

例子验证

• nums = [1, 2, 3, 6, 5, 4]： LIS 为 [1, 2, 3, 6] 或 [1, 2, 3, 5]，长度 4。最少操作次数 6 - 4 = 2（调整 5 和 4）。
• nums = [1, 3, 2, 4]： LIS 为 [1, 3, 4] 或 [1, 2, 4]，长度 3。最少操作次数 4 - 3 = 1（调整 2 或 3）。

结论

• 该方法保证了最少操作次数，且仅通过增加或减少某些元素的值来实现严格递增。
• 时间复杂度为 O(n log n)，适用于较大的 n。

4. 给出一个数组a和一个整数x，当x大于a[i]时可以与x互换，求数组a变为递增序列时的最小交换次数。

双指针。

1. i,j := 0,0
2. 当a[i] < a[i + 1]的使用，如果j <= i 那么j ++
1. 如果a[j] > x , 则进行交换 a[j],x=x,a[j]，并且cnt ++
3. 重新遍历a数组，如果存在a[i] > a[i + 1],cnt = -1即不存在