LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll

简介: LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

解集不能包含重复的子集。

输入格式
  • nums:一个整数数组,可能包含重复元素。
输出格式
  • 返回所有可能的子集列表。

示例

示例 1
输入: nums = [1,2,2]
输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

方法一:回溯法

解题步骤
  1. 排序:首先对数组进行排序,以方便处理重复元素。
  2. 递归构建:使用递归方法,针对每个元素选择“使用”或“不使用”,并跳过重复元素。
完整的规范代码
def subsetsWithDup(nums):
    """
    使用回溯法生成所有可能的子集,处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()  # 排序以方便处理重复元素
    results = []
    def backtrack(start, path):
        results.append(path[:])  # 添加当前子集
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue  # 跳过重复元素
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]
算法分析
  • 时间复杂度:(O(2^n * n)),其中 (n) 是数组长度。每个元素有选择和不选择两种状态,因此时间复杂度为指数级。每次添加子集到结果中的时间复杂度为 (O(n))。
  • 空间复杂度:(O(n)),递归栈的深度最多为 (n)。

方法二:迭代法

解题步骤
  1. 迭代构建:从空集开始,每次迭代添加一个新元素到所有已存在的子集中,形成新的子集,并注意处理重复元素。
完整的规范代码
def subsetsWithDup(nums):
    """
    使用迭代法生成所有可能的子集,处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = [[]]
    start, end = 0, 0
    for i in range(len(nums)):
        start = 0
        # 如果当前数字和前一个数字相同,则只在上一轮新加入的子集基础上追加
        if i > 0 and nums[i] == nums[i-1]:
            start = end + 1
        end = len(results) - 1
        for j in range(start, len(results)):
            results.append(results[j] + [nums[i]])
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]
算法分析
  • 时间复杂度:(O(2^n * n)),每个元素可能会导致结果翻倍,需要遍历并复制现有的所有子集。
  • 空间复杂度:(O(2^n)),存储所有的子集。

方法三:位掩码法

解题步骤
  1. 位掩码生成:利用位掩码的方法生成所有可能的组合。
  2. 去重处理:对于生成的每个组合,检查是否是重复的,若不是则添加到结果集中。
完整的规范代码
def subsetsWithDup(nums):
    """
    使用位掩码法生成所有可能的子集,并处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = []
    seen = set()
    n = len(nums)
    for i in range(1 << n):  # 从 0 到 2^n - 1
        subset = []
        for j in range(n):
            if i & (1 << j):  # 检查第 j 位是否为 1
                subset.append(nums[j])
        # 转换成元组检查是否重复
        subset_tuple = tuple(subset)
        if subset_tuple not in seen:
            seen.add(subset_tuple)
            results.append(subset)
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]
算法分析
  • 时间复杂度:(O(2^n * n)),位掩码方法生成所有可能的子集,并对每个子集进行处理。
  • 空间复杂度:(O(2^n)),用于存储结果和用于查重的集合。

方法四:字典树(Trie)技术

解题步骤
  1. 构建字典树:为数组中的每个元素构建一个字典树,以存储所有可能的子集组合。
  2. 遍历字典树:遍历字典树以生成所有唯一的子集。
完整的规范代码

这个方法在实际应用中比较复杂,通常不推荐用于这种类型的问题,因为它过于复杂,适合处理更具体的、需要快速查找和插入的场景。因此,这里不提供具体代码实现,而是保持理论上的探讨。

方法五:动态规划

解题步骤
  1. 初始化动态表:以空集开始,逐步添加元素。
  2. 处理重复元素:对于重复元素,仅在上一次新增的子集中添加,防止产生重复的子集。
完整的规范代码
def subsetsWithDup(nums):
    """
    动态规划法生成所有可能的子集,并处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = [[]]
    last_count = 0
    for i in range(len(nums)):
        start = last_count if i > 0 and nums[i] == nums[i-1] else 0
        last_count = len(results)
        results += [r + [nums[i]] for r in results[start:]]
    return results
# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]
算法分析
  • 时间复杂度:(O(2^n)),每次迭代都会根据当前结果数量添加新的子集。
  • 空间复杂度:(O(2^n)),存储所有生成的子集。

不同算法的优劣势对比

特征 方法一:回溯法 方法二:迭代法 方法三:位掩码法 方法四:字典树技术 方法五:动态规划
时间复杂度 (O(2^n * n)) (O(2^n * n)) (O(2^n * n)) 高于 (O(2^n)) (O(2^n))
空间复杂度 (O(n)) (O(2^n)) (O(2^n)) 可能非常高 (O(2^n))
优势 直观,易于理解 简单易实现 高效,直接 高效查找和插入 高效,易于实现
劣势 可能栈溢出 结果存储消耗大 需要额外处理重复 过于复杂 需要处理重复元素

应用示例

这些方法在处理涉及到组合生成的问题时非常有用,例如在权限管理系统中生成角色的权限组合、在统计学中用于数据分析的各种组合情况生成等。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
12天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
23 2
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
18 2
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
26天前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
2天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
4天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
17 7
|
1天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。
|
1天前
|
传感器 算法 数据安全/隐私保护
基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
```markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合,模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略,优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例,旨在最小化未覆盖区域。 ```

热门文章

最新文章