1. 华为OD机考双机位C卷解题指南最多购买宝石数目最近在准备华为OD机考的朋友们应该都注意到了这个高频考题——最多购买宝石数目。这道题出现在双机位C卷中覆盖了Java、Python、JS、C/C和Go五种编程语言版本。作为参加过多次华为机考的老司机我发现这道题考察的核心其实是动态规划与贪心算法的灵活运用同时也很考验对边界条件的处理能力。这道题的场景设定非常贴近实际假设你有一笔预算面前摆着不同价格的宝石如何在不超支的情况下买到最多数量的宝石看似简单但在机考紧张的环境下很多同学容易陷入各种陷阱。接下来我就结合自己实战经验详细拆解这道题的解题思路和常见误区。2. 题目分析与核心思路2.1 问题描述还原根据多位考生的回忆题目大致描述如下给定一个整数数组gemPrices表示各宝石的价格以及一个整数budget表示总预算。要求选择尽可能多的宝石且总价格不超过预算。需要返回可以购买的最大宝石数量。示例 输入gemPrices [3,1,5,2,4], budget 7 输出3 解释可以选择价格为1、2、3的宝石总价为6 ≤ 72.2 关键考点解析这道题看似简单实则暗藏多个考察点贪心算法的应用要买到最多数量的宝石直觉告诉我们应该优先买便宜的数组处理能力需要对宝石价格数组进行排序等操作边界条件处理空数组、零预算、所有宝石都买不起等情况时间复杂度优化如何在O(nlogn)时间内解决问题2.3 最优解法思路经过多次验证的最优解法步骤如下将宝石价格数组按升序排序初始化计数器和总价变量遍历排序后的数组累加价格直到超过预算返回计数结果这种解法时间复杂度主要来自排序步骤为O(nlogn)后续遍历是O(n)整体效率很高。3. 多语言实现详解3.1 Java实现版本import java.util.Arrays; public class MaxGemPurchase { public int maxGems(int[] gemPrices, int budget) { Arrays.sort(gemPrices); int count 0; int total 0; for (int price : gemPrices) { if (total price budget) break; total price; count; } return count; } }Java实现要点使用Arrays.sort()进行排序这是Java中最优的排序方法增强for循环遍历数组更简洁提前终止循环避免不必要的计算3.2 Python实现版本def max_gems(gem_prices, budget): gem_prices.sort() count 0 total 0 for price in gem_prices: if total price budget: break total price count 1 return countPython实现特点列表的sort()方法是原地排序更节省空间动态类型让代码更简洁与Java逻辑高度一致体现算法通用性3.3 JavaScript实现function maxGems(gemPrices, budget) { gemPrices.sort((a,b) a - b); let count 0; let total 0; for (const price of gemPrices) { if (total price budget) break; total price; count; } return count; }JS注意事项sort()方法默认按字符串排序必须提供比较函数使用const和let代替var更符合现代JS规范使用for...of循环遍历数组4. 边界条件与异常处理4.1 常见边界情况在实际机考中以下边界情况容易被忽略空宝石列表应该返回0零预算除非有免费宝石否则返回0所有宝石都买不起当最便宜的宝石也超过预算时存在价格为负的宝石题目通常规定价格为正但可以询问考官确认4.2 增强版代码示例Javapublic int maxGemsEnhanced(int[] gemPrices, int budget) { if (gemPrices null || gemPrices.length 0 || budget 0) { return 0; } Arrays.sort(gemPrices); // 最便宜的也买不起 if (gemPrices[0] budget) { return 0; } int count 0; int total 0; for (int price : gemPrices) { if (price 0) continue; // 处理异常价格 if (total price budget) break; total price; count; } return count; }5. 复杂度分析与优化5.1 时间复杂度排序步骤O(nlogn)遍历步骤O(n)总体O(nlogn)这是最优复杂度因为排序本身就有O(nlogn)的下限。5.2 空间复杂度原地排序O(1)额外空间如Java的Arrays.sort()使用TimSort非原地排序O(n)5.3 可能的优化方向如果输入范围有限可以使用计数排序将复杂度降到O(n)多次查询场景下可以预计算前缀和并行化处理超大数组虽然机考中不太需要6. 机考实战技巧6.1 双机位考试注意事项提前测试开发环境确保IDE和编译器正常工作准备代码模板包括常用输入输出处理方法注意时间分配先保证正确性再优化第二机位要确保能看到你的屏幕和手部动作6.2 解题步骤建议仔细阅读题目确认所有约束条件先用自然语言描述解题思路写出伪代码或流程图实现基础版本后再考虑优化务必测试边界条件6.3 常见错误规避忘记排序直接处理没有处理空数组或零预算累加时整数溢出虽然本题不明显错误理解最多数量的含义7. 题目变种与扩展7.1 变种一恰好用完预算要求总价必须等于预算而不是不超过。这时问题变为经典的子集和问题难度提升。7.2 变种二多维约束不仅考虑价格还考虑宝石重量、体积等多维限制变成多维背包问题。7.3 扩展应用场景这类问题在实际中有广泛应用云计算资源分配广告位竞价选择投资项目组合优化8. 备考建议与资源推荐8.1 华为OD机考准备策略重点掌握常见算法排序、查找、动态规划、贪心、DFS/BFS熟悉基本数据结构数组、链表、栈、队列、哈希表、树练习时间管理平均每题不超过30分钟多练习原题和相似题目8.2 推荐练习平台LeetCode练习基础算法题牛客网有华为OD专项练习华为官方模拟平台熟悉考试环境8.3 个人心得在多次参加华为OD机考后我发现最重要的不是死记硬背题目而是培养快速分析问题和转化为已知算法的能力。比如这道宝石题关键在于识别出贪心选择性质——局部最优能导致全局最优。平时练习时建议每做完一题都思考这道题考察什么核心概念有哪些相似的题目如果约束条件变化解法该如何调整这种反思性练习比单纯刷题更有效。另外在机考中遇到这道题时建议先写出基础解法确保分数有时间再考虑优化和边界处理。双机位环境下要保持镇定把注意力集中在解题上不要过分担心监考问题。
华为OD机考双机位C卷：最多购买宝石数目解题指南
1. 华为OD机考双机位C卷解题指南最多购买宝石数目最近在准备华为OD机考的朋友们应该都注意到了这个高频考题——最多购买宝石数目。这道题出现在双机位C卷中覆盖了Java、Python、JS、C/C和Go五种编程语言版本。作为参加过多次华为机考的老司机我发现这道题考察的核心其实是动态规划与贪心算法的灵活运用同时也很考验对边界条件的处理能力。这道题的场景设定非常贴近实际假设你有一笔预算面前摆着不同价格的宝石如何在不超支的情况下买到最多数量的宝石看似简单但在机考紧张的环境下很多同学容易陷入各种陷阱。接下来我就结合自己实战经验详细拆解这道题的解题思路和常见误区。2. 题目分析与核心思路2.1 问题描述还原根据多位考生的回忆题目大致描述如下给定一个整数数组gemPrices表示各宝石的价格以及一个整数budget表示总预算。要求选择尽可能多的宝石且总价格不超过预算。需要返回可以购买的最大宝石数量。示例 输入gemPrices [3,1,5,2,4], budget 7 输出3 解释可以选择价格为1、2、3的宝石总价为6 ≤ 72.2 关键考点解析这道题看似简单实则暗藏多个考察点贪心算法的应用要买到最多数量的宝石直觉告诉我们应该优先买便宜的数组处理能力需要对宝石价格数组进行排序等操作边界条件处理空数组、零预算、所有宝石都买不起等情况时间复杂度优化如何在O(nlogn)时间内解决问题2.3 最优解法思路经过多次验证的最优解法步骤如下将宝石价格数组按升序排序初始化计数器和总价变量遍历排序后的数组累加价格直到超过预算返回计数结果这种解法时间复杂度主要来自排序步骤为O(nlogn)后续遍历是O(n)整体效率很高。3. 多语言实现详解3.1 Java实现版本import java.util.Arrays; public class MaxGemPurchase { public int maxGems(int[] gemPrices, int budget) { Arrays.sort(gemPrices); int count 0; int total 0; for (int price : gemPrices) { if (total price budget) break; total price; count; } return count; } }Java实现要点使用Arrays.sort()进行排序这是Java中最优的排序方法增强for循环遍历数组更简洁提前终止循环避免不必要的计算3.2 Python实现版本def max_gems(gem_prices, budget): gem_prices.sort() count 0 total 0 for price in gem_prices: if total price budget: break total price count 1 return countPython实现特点列表的sort()方法是原地排序更节省空间动态类型让代码更简洁与Java逻辑高度一致体现算法通用性3.3 JavaScript实现function maxGems(gemPrices, budget) { gemPrices.sort((a,b) a - b); let count 0; let total 0; for (const price of gemPrices) { if (total price budget) break; total price; count; } return count; }JS注意事项sort()方法默认按字符串排序必须提供比较函数使用const和let代替var更符合现代JS规范使用for...of循环遍历数组4. 边界条件与异常处理4.1 常见边界情况在实际机考中以下边界情况容易被忽略空宝石列表应该返回0零预算除非有免费宝石否则返回0所有宝石都买不起当最便宜的宝石也超过预算时存在价格为负的宝石题目通常规定价格为正但可以询问考官确认4.2 增强版代码示例Javapublic int maxGemsEnhanced(int[] gemPrices, int budget) { if (gemPrices null || gemPrices.length 0 || budget 0) { return 0; } Arrays.sort(gemPrices); // 最便宜的也买不起 if (gemPrices[0] budget) { return 0; } int count 0; int total 0; for (int price : gemPrices) { if (price 0) continue; // 处理异常价格 if (total price budget) break; total price; count; } return count; }5. 复杂度分析与优化5.1 时间复杂度排序步骤O(nlogn)遍历步骤O(n)总体O(nlogn)这是最优复杂度因为排序本身就有O(nlogn)的下限。5.2 空间复杂度原地排序O(1)额外空间如Java的Arrays.sort()使用TimSort非原地排序O(n)5.3 可能的优化方向如果输入范围有限可以使用计数排序将复杂度降到O(n)多次查询场景下可以预计算前缀和并行化处理超大数组虽然机考中不太需要6. 机考实战技巧6.1 双机位考试注意事项提前测试开发环境确保IDE和编译器正常工作准备代码模板包括常用输入输出处理方法注意时间分配先保证正确性再优化第二机位要确保能看到你的屏幕和手部动作6.2 解题步骤建议仔细阅读题目确认所有约束条件先用自然语言描述解题思路写出伪代码或流程图实现基础版本后再考虑优化务必测试边界条件6.3 常见错误规避忘记排序直接处理没有处理空数组或零预算累加时整数溢出虽然本题不明显错误理解最多数量的含义7. 题目变种与扩展7.1 变种一恰好用完预算要求总价必须等于预算而不是不超过。这时问题变为经典的子集和问题难度提升。7.2 变种二多维约束不仅考虑价格还考虑宝石重量、体积等多维限制变成多维背包问题。7.3 扩展应用场景这类问题在实际中有广泛应用云计算资源分配广告位竞价选择投资项目组合优化8. 备考建议与资源推荐8.1 华为OD机考准备策略重点掌握常见算法排序、查找、动态规划、贪心、DFS/BFS熟悉基本数据结构数组、链表、栈、队列、哈希表、树练习时间管理平均每题不超过30分钟多练习原题和相似题目8.2 推荐练习平台LeetCode练习基础算法题牛客网有华为OD专项练习华为官方模拟平台熟悉考试环境8.3 个人心得在多次参加华为OD机考后我发现最重要的不是死记硬背题目而是培养快速分析问题和转化为已知算法的能力。比如这道宝石题关键在于识别出贪心选择性质——局部最优能导致全局最优。平时练习时建议每做完一题都思考这道题考察什么核心概念有哪些相似的题目如果约束条件变化解法该如何调整这种反思性练习比单纯刷题更有效。另外在机考中遇到这道题时建议先写出基础解法确保分数有时间再考虑优化和边界处理。双机位环境下要保持镇定把注意力集中在解题上不要过分担心监考问题。
