Medium

题目描述

给你一个从1开始索引的整数数组 numWays，其中 numWays[i] 表示使用某些固定硬币面额的无限供应来选择总金额 i 的方法数。每个面额都是正整数，值最多为 numWays.length。

但是，确切的硬币面额已经丢失了。你的任务是恢复可能产生给定 numWays 数组的面额集合。

返回一个包含唯一整数的排序数组，表示这个面额集合。

如果不存在这样的集合，返回空数组。

示例 1：

输入：numWays = [0,1,0,2,0,3,0,4,0,5]
输出：[2,4,6]
解释：
金额 1：0 种方法（无法选择硬币总值为1）
金额 2：1 种方法（[2]）
金额 3：0 种方法（无法选择硬币总值为3）
金额 4：2 种方法（[2,2] 和 [4]）
...

示例 2：

输入：numWays = [1,2,2,3,4]
输出：[1,2,5]

示例 3：

输入：numWays = [1,2,3,4,15]
输出：[]
解释：没有面额集合能满足这个数组。

约束条件：

  • 1 <= numWays.length <= 100
  • 0 <= numWays[i] <= 2 * 10^8

解题思路

这是一个逆向动态规划问题，我们需要从给定的方法数数组中推导出硬币面额。

核心思路：

  1. 观察关键性质：对于最小面额 c，必须有 numWays[c] == 1，因为只有一种方式组成面额 c，即使用一枚面额为 c 的硬币。

  2. 贪心策略：按照面额从小到大的顺序逐个确定硬币面额：

    • 找到最小的 c > 0 使得 numWays[c] == 1
    • 将 c 加入答案集合
    • 从数组中"移除"这个硬币的贡献

  3. 移除硬币贡献：当确定面额 c 后，需要更新 numWays 数组。对于每个金额 s >= c，执行：

    numWays[s] -= numWays[s - c]

    这是因为原来组成金额 s 的方法中，有 numWays[s - c] 种方法是通过在组成 s - c 的基础上加一枚面额 c 的硬币得到的。

  4. 验证结果：重复上述过程直到无法找到更多面额。最后检查 numWays 数组是否全为0，如果是则返回答案，否则返回空数组。

这个算法的正确性基于硬币找零问题的动态规划性质和面额的唯一性。

代码实现

class Solution {
public:
    vector<int> findCoins(vector<int>& numWays) {
        vector<int> result;
        int n = numWays.size();
        
        while (true) {
            int coin = -1;
            // 找到最小的面额，使得 numWays[面额] == 1
            for (int i = 1; i < n; i++) {
                if (numWays[i] == 1) {
                    coin = i;
                    break;
                }
            }
            
            if (coin == -1) break; // 没有找到更多面额
            
            result.push_back(coin);
            
            // 移除这个硬币的贡献
            for (int s = coin; s < n; s++) {
                numWays[s] -= numWays[s - coin];
            }
        }
        
        // 检查是否所有方法数都为0
        for (int i = 1; i < n; i++) {
            if (numWays[i] != 0) {
                return {}; // 无效解
            }
        }
        
        return result;
    }
};

class Solution:
    def findCoins(self, numWays: List[int]) -> List[int]:
        result = []
        n = len(numWays)
        
        while True:
            coin = -1
            # 找到最小的面额，使得 numWays[面额] == 1
            for i in range(1, n):
                if numWays[i] == 1:
                    coin = i
                    break
            
            if coin == -1:
                break  # 没有找到更多面额
            
            result.append(coin)
            
            # 移除这个硬币的贡献
            for s in range(coin, n):
                numWays[s] -= numWays[s - coin]
        
        # 检查是否所有方法数都为0
        for i in range(1, n):
            if numWays[i] != 0:
                return []  # 无效解
        
        return result

public class Solution {
    public IList<int> FindCoins(int[] numWays) {
        var result = new List<int>();
        int n = numWays.Length;
        
        while (true) {
            int coin = -1;
            // 找到最小的面额，使得 numWays[面额] == 1
            for (int i = 1; i < n; i++) {
                if (numWays[i] == 1) {
                    coin = i;
                    break;
                }
            }
            
            if (coin == -1) break; // 没有找到更多面额
            
            result.Add(coin);
            
            // 移除这个硬币的贡献
            for (int s = coin; s < n; s++) {
                numWays[s] -= numWays[s - coin];
            }
        }
        
        // 检查是否所有方法数都为0
        for (int i = 1; i < n; i++) {
            if (numWays[i] != 0) {
                return new List<int>(); // 无效解
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} numWays
 * @return {number[]}
 */
var findCoins = function(numWays) {
    const n = numWays.length;
    const coins = [];
    
    // Start with numWays[0] = 1 (base case)
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    
    for (let i = 1; i <= n; i++) {
        if (numWays[i - 1] > dp[i]) {
            // We need a new coin of denomination i
            coins.push(i);
            
            // Update dp array with this new coin
            for (let j = i; j <= n; j++) {
                dp[j] += dp[j - i];
            }
        }
        
        // Check if current dp[i] matches numWays[i-1]
        if (dp[i] !== numWays[i - 1]) {
            return [];
        }
    }
    
    return coins;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环最多执行 n 次（每次找一个面额），每次内层循环遍历 n 个元素，总时间复杂度为 O(n²)
空间复杂度O(1)除了返回结果数组外，只使用常数额外空间

相关题目