没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全[宫水三叶的刷题日记]：BFS1

[宫水三叶的刷题日记]：BFS1

java

leetcode

需积分: 0 1 下载量 67 浏览量 2022-08-03 11:08:44 上传评论收藏 1.75MB PDF 举报

温馨提示

试读

42页

2. 从侧边栏的类别目录找到「BFS」 3. 按照「推荐指数」从大到小进行刷题，「推荐指数」相同，则按照「难度」从易到 4. 拿到题号之后，回到本合集进行检索

资源详情

资源评论

资源推荐

🍭

更多精彩内容，欢迎关注：公众号 / Github / LeetCode / 知乎 **

噔噔噔噔，这是公众号「噔噔噔噔，这是公众号「宫水三叶的刷宫水三叶的刷题题日日记记」的原」的原创专题创专题「「BFS」合集。」合集。

本合集更新时间本合集更新时间为为 2021-10-07，大概每，大概每 2-4 周会集中更新一次。周会集中更新一次。关注公众号，后台回复注公众号，后台回复

「「BFS」即可获取最新下」即可获取最新下载链载链接。接。

💡💡

下面介下面介绍绍使用本合集的最佳使用实使用本合集的最佳使用实践：：

学学习习算法：算法：

1. 打开在线目录（Github 版 & Gitee 版）；

2. 从侧边栏的类别目录找到「BFS」；

3. 按照「推荐指数」从大到小进行刷题，「推荐指数」相同，则按照「难度」从易到

难进行刷题‘

4. 拿到题号之后，回到本合集进行检索。

维维持熟持熟练练度：度：

1. 按照本合集「从上往下」进行刷题。

学学习习过程中遇到任何困过程中遇到任何困难难，欢迎加入「每日一，欢迎加入「每日一题题打卡打卡 QQ 群：群：703311589」」进进行交流行交流

🍭🍭🍭🍭🍭🍭

🍭

更多精彩内容，欢迎关注：公众号 / Github / LeetCode / 知乎 **

题题目描述目描述

这是 LeetCode 上的 90. 子集子集 II ，难度为中等中等。

Tag : 「位运算」、「回溯算法」、「状态压缩」、「DFS」

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂

集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

示例 1：

输入：nums = [1,2,2]

输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

回溯解法（回溯解法（Set））

由于是求所有的方案，而且数据范围只有 10，可以直接用爆搜来做。

同时由于答案中不能包含相同的方案，因此我们可以先对原数组进行排序，从而确保所有爆搜出

来的方案，都具有单调性，然后配合 Set 进行去重。

代码：

class Solution {

public List<List<Integer>> subsetsWithDup(int[] nums) {

Arrays.sort(nums);

Set<List<Integer>> ans = new HashSet<>();

List<Integer> cur = new ArrayList<>();

dfs(nums, 0, cur, ans);

return new ArrayList<>(ans);

}

/**

* @param nums 原输入数组

* @param u 当前决策到原输入数组中的哪一位

* @param cur 当前方案

* @param ans 最终结果集

void dfs(int[] nums, int u, List<Integer> cur, Set<List<Integer>> ans) {

// 所有位置都决策完成，将当前方案放入结果集

if (nums.length == u) {

ans.add(new ArrayList<>(cur));

return;

}

// 选择当前位置的元素，往下决策

cur.add(nums[u]);

dfs(nums, u + 1, cur, ans);

// 不选当前位置的元素（回溯），往下决策

cur.remove(cur.size() - 1);

dfs(nums, u + 1, cur, ans);

}

• 时间复杂度：排序复杂度为 O(n log n)，爆搜复杂度为 (2

)，每个方案通过深拷

贝存入答案，复杂度为 O(n)。整体复杂度为 (n ∗ 2

)

• 空间复杂度：总共有 2

个方案，每个方案最多占用 O(n) 空间，整体复杂度为

(n ∗ 2

)

回溯解法回溯解法

我们知道使用 Set 虽然是 O(1) 操作，但是只是均摊 O(1)。

因此我们来考虑不使用 Set 的做法。

我们使用 Set 的目的是为了去重，那什么时候会导致的重复呢？

其实就是相同的元素，不同的决策方案对其实就是相同的元素，不同的决策方案对应应同样的同样的结结果。果。

举个

🌰

，[1,1,1] 的数据，只选择第一个和只选择第三个（不同的决策方案），结果是一样的。

因此如果我因此如果我们们希望去重的希望去重的话话，不能单，不能单纯纯的利用「某个下的利用「某个下标标是否被选是否被选择择」」来进进行决策，而是要找到行决策，而是要找到

某个数值的某个数值的连续连续一段，根据一段，根据该该数值的选数值的选择择次数类次数类进进行决策。行决策。

还是那个

🌰

，[1,1,1] 的数据，我们可以需要找到数值为 1 的连续一段，然后决策选择 0 次、选

择 1 次、选择 2 次 … 从而确保不会出现重复

也就是也就是说说，将决策方案从「某个下，将决策方案从「某个下标标是否被选是否被选择择」修改」修改为为「相同的数值被选「相同的数值被选择择的个数」。这样肯的个数」。这样肯

定不会出定不会出现现重复，因重复，因为为 [1,1,1] 不会因不会因为为只选只选择择第一个和只选第一个和只选择择第三个第三个产产生两个生两个 [1] 的方案，只的方案，只

会因会因为为 1 被选被选择择一次，一次，产产生一个生一个 [1] 的方案。的方案。

代码：

剩余41页未读，继续阅读

内容反馈

余青葭

粉丝: 37
资源: 303

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

[宫水三叶的刷题日记]：BFS1

评论0

最新资源

[宫水三叶的刷题日记]：BFS1

评论0

[宫水三叶的刷题日记]：状压 DP1

[宫水三叶的刷题日记]：（图论）BFS1

[宫水三叶的刷题日记]：模拟1

[宫水三叶的刷题日记]：排序1

[宫水三叶的刷题日记]：三分1

[宫水三叶的刷题日记]：分治1

leetcode-BFS-1:BFS-1

BFS:BFS- JAVA源代码（Netbeans项目）-java project source code

Java小游戏-炸弹人-课程设计-论文-AI

leetcode2-BFS-1:BFS-1

[宫水三叶的刷题日记]：队列1

[宫水三叶的刷题日记]：博弈论1

[宫水三叶的刷题日记]：DFS1

[宫水三叶的刷题日记]：链表1

[宫水三叶的刷题日记]：栈1

BFSK调制解调：BFSK调制解调的实现-matlab开发

BFS 找最短路.cpp

leetcode2-BFS-4:BFS-4

广度优先搜索：BFS 使用源向量和目标向量对图执行广度优先搜索。-matlab开发

leetcode-BFS-2:BFS-2

[宫水三叶的刷题日记]：位运算1

[宫水三叶的刷题日记]：堆1

[宫水三叶的刷题日记]：双指针1

[宫水三叶的刷题日记]：二叉树1

[宫水三叶的刷题日记]：数学1

BFSK 设计使用系统生成器：BFSK 发射器使用 System Generator 10.1-matlab开发

二进制频移键控：BFSK 调制方案仿真。-matlab开发

BFSX2:BFS-X2

leetcode2-BFS-2.1:BFS-2.1

最新资源