LeetCode挑战：单元素排序数组与硬币组合

"这是一份关于LeetCode问题的PDF文件，包含了两个具体的问题：SingleElementinaSortedArray和CoinChange2。这两个问题是算法题，要求在有限的时间和空间复杂度内解决。SingleElementinaSortedArray是寻找排序数组中唯一出现一次的元素，而CoinChange2则是计算用不同面值硬币组成特定金额的组合数。" 首先，我们来详细讨论第一个问题——SingleElementinaSortedArray。这个问题的目标是在一个排序数组中找到那个只出现一次的元素。给定的数组由整数构成，除了一个元素之外，其他所有元素都成对出现。例如，输入数组[1,1,2,3,3,4,4,8,8]中，数字2是唯一的单次出现的元素。 为了解决这个问题，我们可以利用排序数组的特性。由于数组已经排序，我们可以使用二分查找的方法。首先，找到数组中间的元素，然后检查其左边和右边的元素。如果中间元素与其左边或右边的元素相同，那么单次出现的元素必然在另一侧。通过不断调整搜索范围，最终我们可以在O(log n)的时间复杂度内找到这个元素，同时空间复杂度为O(1)，符合题目要求。 接下来，我们转向第二个问题——CoinChange2。这个问题是经典的动态规划问题，需要找出有多少种不同的方法可以用给定面值的硬币组成一个特定的金额。例如，当amount为5，coins为[1, 2, 5]时，有4种组合方式可以达到5：5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1。 解决CoinChange2的关键是建立一个状态转移方程。定义dp[i]表示能够组成金额i的组合数。初始状态dp[0]=1，因为没有金额时，组合数为1（即空集）。对于每个硬币，我们需要遍历所有可能的金额，更新dp[j]（j >= i），即dp[j] = dp[j] + dp[j - coin]，表示在现有金额基础上加上一个该硬币的组合数。 需要注意的是，当amount为3，coins为[2]时，由于无法组成3，所以输出结果为0。此外，题目还规定了amount和coins的范围以及组合数能容纳的最大值，确保答案不会超出32位整数的范围。 这份PDF文件提供了两个有趣的算法挑战，分别涉及排序数组的查找技巧和动态规划的运用。通过解决这些问题，不仅可以提升对数据结构和算法的理解，也有助于提高编程能力。