42 给定必买商品、可选凑单商品和若干带门槛的减钱/打折券,如何求出最小实付金额?请描述你的算法思路与复杂度。考察候选人能否将购物券使用问题抽象为组合优化问题,并设计出正确且可实现的搜索/枚举策略。 查看学习思路
44 请设计并实现一个算法,在最大子数组和问题中,当存在多个最大和区间时,优先保留区间长度最长的,若长度仍相同则保留左端点最小的区间。考察候选人对经典最大子数组和问题的理解深度,以及处理多关键字优化(和最大、长度最长、左端点最小)的能力,同时评估代码实现的严谨性。 查看学习思路
45 给定两个数组,第一个数组需要修改成非递减数组,修改第一个数组第 i 个位置的代价是第二个数组第 i 个位置的值,求最小总代价。请设计算法并分析复杂度。考察候选人将实际问题转化为动态规划模型的能力,特别是带权修改使数组非递减的经典问题,评估状态设计、转移方程和优化技巧。 查看学习思路