使用kotlin解决这个问题：剑指 Offer II 103. 最少的硬币数目 中等 80 相关企业 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2： 输入：coins = [2], amount = 3 输出：-1 示例 3： 输入：coins = [1], amount = 0 输出：0 示例 4： 输入：coins = [1], amount = 1 输出：1 示例 5： 输入：coins = [1], amount = 2 输出：2 提示： 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104

可以使用动态规划来解决这个问题。定义一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数目。则有以下状态转移方程：

dp[i] = min(dp[i], dp[i - coins[j]] + 1)

其中，i 表示当前需要凑成的金额，coins[j] 表示可用的硬币面额，dp[i - coins[j]] 表示凑成剩下的金额所需的最少硬币数目，因为我们需要加上当前使用的硬币，所以需要加上 1。最终结果为 dp[amount]。

以下是使用 Kotlin 实现的代码：

fun coinChange(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { amount + 1 }
    dp[0] = 0
    for (i in 1..amount) {
        for (j in coins.indices) {
            if (coins[j] <= i) {
                dp[i] = minOf(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return if (dp[amount] > amount) -1 else dp[amount]
}

其中，dp 数组初始化为 amount+1，表示最多需要 amount+1 个硬币才能凑成总金额，如果最终结果超过了 amount，说明无法凑成总金额，返回 -1。

相关问题

使用kotlin解决这个问题：剑指 Offer II 070. 排序数组中只出现一次的数字 中等 66 相关企业 给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。 示例 1: 输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2: 输入: nums = [3,3,7,7,10,11,11] 输出: 10 提示: 1 <= nums.length <= 105 0 <= nums[i] <= 105

可以使用二分查找的思想来解决这个问题。由于数组是有序的，那么对于任意一个出现两次的数字，它们的位置一定是相邻的。因此，我们可以考虑对数组进行二分，每次取中间的数 mid，如果 mid 是出现两次的数字，则 mid-1 和 mid+1 一定与 mid 相等；如果 mid 是唯一的数字，则 mid-1 和 mid+1 一定与 mid 不相等。根据这一特点，我们可以通过二分查找找到唯一的数字。

具体来说，我们可以设 left 和 right 分别为数组的左右两端，mid = (left + right) / 2。如果 mid 满足上述条件之一，则直接返回 mid；否则，我们可以根据 mid 的位置和数值来判断唯一的数字在哪一侧，然后将 left 或 right 移动到相应的位置进行下一轮查找。最终，我们可以找到唯一的数字。

以下是 Kotlin 代码实现：

fun singleNonDuplicate(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        val mid = (left + right) / 2
        if (mid % 2 == 1) { // mid 为奇数，需要向左移动一位
            mid--
        }
        if (nums[mid] != nums[mid + 1]) { // mid 不是出现两次的数字
            right = mid
        } else { // mid 是出现两次的数字
            left = mid + 2
        }
    }
    return nums[left]
}

时间复杂度为 O(log n)，空间复杂度为 O(1)。

使用kotlin解决这个题目：剑指 Offer 56 - I. 数组中数字出现的次数 中等 817 相关企业 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

好的，以下是使用 Kotlin 解决该问题的代码：

fun findSingleNumbers(nums: IntArray): IntArray {
    var xorResult = 0
    for (num in nums) {
        xorResult = xorResult xor num
    }
    var mask = 1
    while (xorResult and mask == 0) {
        mask = mask shl 1
    }
    var num1 = 0
    var num2 = 0
    for (num in nums) {
        if (num and mask == 0) {
            num1 = num1 xor num
        } else {
            num2 = num2 xor num
        }
    }
    return intArrayOf(num1, num2)
}

该算法的思路是利用异或运算的特性，即相同数字异或为 0，不同数字异或为 1。首先将整个数组中的所有数字进行异或运算，得到的结果是两个只出现一次的数字的异或结果。然后，我们找到异或结果中任意一位为 1 的二进制位，并将其作为 mask。将数组中的每个数字都与 mask 进行与运算，得到的结果为 0 的数字再进行异或运算，得到的结果就是其中一个只出现一次的数字；而与 mask 进行与运算结果为 1 的数字再进行异或运算，得到的结果就是另一个只出现一次的数字。最后将这两个数字放入一个长度为 2 的数组中返回即可。

该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。