Shiroha白羽的博客
·
Hello 2024
原文中文，约2500字，阅读约需6分钟。
📝
内容提要
本文讨论了几道算法题，包括Alice与Bob的博弈、字符串拆分成本最小化、字符串分组成本最小化以及01字典树的构建问题。每道题目提供了解题思路和代码实现，旨在帮助读者理解算法的应用与优化。
🎯
关键要点
-
Alice与Bob的博弈问题中，玩家可以从两个钱包中选择取钱，最终结果取决于两个钱包中钱的总和对2的取模。
-
字符串拆分成本最小化问题中，允许将由'-'和'+'组成的字符串拆分成多个段，目标是使得所有段的成本之和最小。
-
字符串分组成本最小化问题中，需要将字符串拆分成两个子序列，计算相邻正序对的成本，采用贪心算法进行拆分。
-
01字典树构建问题中，给定每个叶子节点的值，判断是否可以构建出符合条件的字典树，过程类似于哈夫曼编码。
❓
延伸问答
Alice与Bob的博弈问题是如何解决的？
通过计算两个钱包中钱的总和对2的取模来判断谁会没有办法操作。
字符串拆分成本最小化的目标是什么？
目标是将由'-'和'+'组成的字符串拆分成多个段，使得所有段的成本之和最小。
如何实现字符串分组成本最小化？
采用贪心算法将字符串拆分成两个子序列，计算相邻正序对的成本。
01字典树的构建问题涉及哪些关键步骤？
判断是否可以构建字典树的关键在于检查相邻节点的值是否符合条件，类似于哈夫曼编码的过程。
在字符串拆分成本最小化中，如何处理和为0的情况？
除了和等于0的情况，其他情况都不应合成一个段。
字符串分组成本最小化的成本计算方式是什么？
每个子序列内，每有一对相邻的正序对就算一个成本。
🏷️
