資訊專欄INFORMATION COLUMN
Permutations I Problem
Given a list of numbers, return all possible permutations.
ExampleFor nums = [1,2,3], the permutations are:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Do it without recursion.
SolutionRecursion
class Solution {
public ArrayList> permute(ArrayList num) {
ArrayList> res = new ArrayList>();
if (num == null || num.size() == 0) {
return res;
}
ArrayList list = new ArrayList ();
helper (nuts, list, res);
return res;
}
public void helper(ArrayList num, ArrayList list, ArrayList> res) {
if (list.size() == num.size()) {
res.add(new ArrayList (list));
return;
}
for (int i = 0; i < num.size(); i++) {
if (list.contains(num.get(i))) {
continue;
}
list.add(num.get(i));
helper(num, list, res);
list.remove(list.size() - 1);
}
}
}
Permutations II
Problem
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]Solution
sort
call backtracking function in main function
in backtracking function, when temp list size equals nums array size, save a copy of temp list to result
iteration nums array, if current num is used, or it"s same as previous num and previous num is unused (released), continue
update temp array and used boolean array at the same time in back tracking.
class Solution {
public List> permuteUnique(int[] nums) {
List> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
helper(nums, new ArrayList(), new boolean[nums.length], res);
return res;
}
private void helper(int[] nums, List temp, boolean[] used, List> res) {
if (temp.size() == nums.length) res.add(new ArrayList<>(temp));
else {
for (int i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && !used[i-1] && nums[i] == nums[i-1])) {
continue;
} else {
used[i] = true;
temp.add(nums[i]);
helper(nums, temp, used, res);
temp.remove(temp.size()-1);
used[i] = false;
}
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65480.html
摘要：當(dāng)前的值如果已經(jīng)被使用過，則繼續(xù)判斷下一個(gè)數(shù)值。則當(dāng)?shù)谝粋€(gè)被添加進(jìn)結(jié)果集時(shí)，可以繼續(xù)使用第二個(gè)作為元素添加進(jìn)結(jié)果集從而生成。假設(shè)將表示為那么結(jié)果集中會(huì)確保永遠(yuǎn)在數(shù)值的前面，從而避免了和的重復(fù)情況出現(xiàn)。 題目要求 Given a collection of numbers that might contain duplicates, return all possible unique ...
摘要：題目詳情題目要求輸入一個(gè)可能會(huì)有重復(fù)數(shù)字的數(shù)組，要求我們輸出可能組成的全排列無重復(fù)排列?？梢杂脕韺?shí)現(xiàn)，但這種實(shí)現(xiàn)方式復(fù)雜度高。另外一種實(shí)現(xiàn)思路是，新聲明一個(gè)數(shù)組來存儲(chǔ)中元素的使用狀況。以這個(gè)數(shù)組為例。 題目詳情 Given a collection of numbers that might contain duplicates, return all possible unique ...
摘要：每一輪搜索選擇一個(gè)數(shù)加入列表中，同時(shí)我們還要維護(hù)一個(gè)全局的布爾數(shù)組，來標(biāo)記哪些元素已經(jīng)被加入列表了，這樣在下一輪搜索中要跳過這些元素。 Permutations I Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permu...
摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個(gè)排列，一種辦法是我們先求出所有的排序情況，但是題目規(guī)定不能占有額外空間。每次求出一個(gè)數(shù)字后，要及時(shí)的把它從中刪除掉。采用來構(gòu)造結(jié)果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
閱讀 2683·2023-04-25 18:10
閱讀 1624·2019-08-30 15:53
閱讀 2826·2019-08-30 13:10
閱讀 3235·2019-08-29 18:40
閱讀 1140·2019-08-23 18:31
閱讀 1213·2019-08-23 16:49
閱讀 3413·2019-08-23 16:07
閱讀 888·2019-08-23 15:27
