資訊專欄INFORMATION COLUMN
Subsets Problem
Given a set of distinct integers, return all possible subsets.
NoticeElements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
If S = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]Challenge
Can you do it in both recursively and iteratively?
Solutionclass Solution {
public ArrayList> subsets(int[] nums) {
ArrayList> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
ArrayList cur = new ArrayList<>();
Arrays.sort(nums);
dfs(nums, cur, res, 0);
return res;
}
public void dfs(int[] nums, ArrayList cur, ArrayList> res, int index) {
if (index > nums.length) return;
res.add(new ArrayList (cur));
for (int i = index; i < nums.length; i++) {
cur.add(nums[i]);
dfs(nums, cur, res, i+1);
cur.remove(cur.size()-1);
}
}
}
Subsets II
Problem
Given a list of numbers that may has duplicate numbers, return all possible subsets
##Notice
Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.
Have you met this question in a real interview? Yes
If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]Challenge
Can you do it in both recursively and iteratively?
Solutionclass Solution {
public ArrayList> subsetsWithDup(ArrayList S) {
ArrayList> res = new ArrayList<>();
Collections.sort(S);
ArrayList cur = new ArrayList<>();
dfs(S, cur, res, 0);
return res;
}
public void dfs(ArrayList S, ArrayList cur, ArrayList> res, int index) {
if (index > S.size()) return;
res.add(new ArrayList (cur));
for (int i = index; i < S.size(); i++) {
if (i != index && S.get(i) == S.get(i-1)) continue;
cur.add(S.get(i));
dfs(S, cur, res, i+1);
cur.remove(cur.size()-1);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65006.html
摘要：不同數(shù)包含重復(fù)數(shù)為的時(shí)候，表示在外層的循環(huán)正在被使用，所以當(dāng)前循環(huán)遇到為一定要跳過(guò)。對(duì)當(dāng)前循環(huán)要添加的數(shù)組，在添加當(dāng)前元素后進(jìn)行遞歸，遞歸之后要將當(dāng)前元素的使用標(biāo)記改為，表示已經(jīng)使用和遞歸完畢，然后再將這個(gè)元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...
摘要：題目要求可以先參考關(guān)于的這篇博客再看接下來(lái)的內(nèi)容。思路一鏈表的形式我們可以通過(guò)例子，，，來(lái)說(shuō)明。在遞歸中我們會(huì)將起始下標(biāo)后的值依次加入當(dāng)前結(jié)果集，并將結(jié)果集加入結(jié)果集數(shù)組中。如果遇到重復(fù)的數(shù)字，則繼續(xù)遍歷下一個(gè)數(shù)字，直至遍歷結(jié)束。 題目要求 Given a collection of integers that might contain duplicates, nums, retur...
摘要：題目描述注意題目解讀找出所有的子集。思路確定子集的來(lái)源，遍歷原始列表，每一個(gè)元素都往已有的子集列表里邊添加，同時(shí)添加到已有的子集中去，產(chǎn)生新的子集。類(lèi)似于動(dòng)態(tài)規(guī)劃思想，依賴于之前的東西產(chǎn)生現(xiàn)在的東西。 題目描述 Given a collection of integers that might contain duplicates, nums, return all possible ...
摘要：寫(xiě)這個(gè)系列是因?yàn)榧o(jì)念一下去年的今天，就是年的月號(hào)，刷題第一天，今天是一周年紀(jì)念日。排除，就是返回一空的。復(fù)雜度分析算法課講過(guò)，這個(gè)復(fù)雜度是指數(shù)次，能實(shí)現(xiàn)出來(lái)就行了，沒(méi)法優(yōu)化。復(fù)雜度分析不分析了，反正指數(shù)次。 Subsets 寫(xiě)這個(gè)系列是因?yàn)榧o(jì)念一下去年的今天，就是2015年的9月14號(hào)，刷題第一天，今天是一周年紀(jì)念日。當(dāng)時(shí)只敢做easy還得抄答案的我想啥時(shí)候能做上medium啊，事到如...
摘要：深度優(yōu)先搜索復(fù)雜度時(shí)間空間遞歸棧空間思路這道題可以轉(zhuǎn)化為一個(gè)類(lèi)似二叉樹(shù)的深度優(yōu)先搜索。另外需要先排序以滿足題目要求。新的集合要一個(gè)新的，防止修改引用。 Subset I Given a set of distinct integers, nums, return all possible subsets. Note: Elements in a subset must be in n...
閱讀 1570·2021-11-23 09:51
閱讀 1106·2021-10-12 10:12
閱讀 2826·2021-09-22 16:06
閱讀 3650·2019-08-30 15:56
閱讀 3474·2019-08-30 15:53
閱讀 3119·2019-08-29 16:29
閱讀 2372·2019-08-29 15:27
閱讀 2031·2019-08-26 10:49
