首页 > 其他分享 >【LeeCode】46. 全排列

【LeeCode】46. 全排列

时间:2022-11-25 23:39:45浏览次数:75  
标签:排列 LinkedList nums 46 int LeeCode result new path

【题目描述】

​https://leetcode.cn/problems/permutations/?favorite=2cktkvj​

给定一个不含重复数字的数组 ​​nums​​ ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

【示例】

【LeeCode】46. 全排列_回溯算法

【代码1】

​学习参考​

package com.company;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Test {
List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 存放符合条件结果(已经选择了那些元素)

public List<List<Integer>>permute(int[] nums){
if (nums.length == 0 ) return result;
backtrack(nums, path);
return result;
}

private void backtrack(int[] nums, LinkedList<Integer> path) {

if(nums.length == path.size()) {
result.add(new ArrayList<>(path));
}

for(int i = 0; i < nums.length; i++){
if(path.contains(nums[i])){
continue;
}
path.add(nums[i]);
backtrack(nums, path);
path.removeLast();
}
}
}

public class threeSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println(new Test().permute(arr).toString());
}
}


【代码2】

​学习参考​

package com.company;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Test {
List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 存放符合条件结果
boolean[] used; // 当前的数字是否已经被选择过 O(1)

public List<List<Integer>> fullArray(int[] nums) {
if(nums.length == 0){
return result;
}
// 如果节点不为空, 则初始化used数组
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}

private void permuteHelper(int[] nums) {
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++){
if(used[i]) {
continue;
}
used[i] = true; // 当前所处位置
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}

public class threeSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println(new Test().fullArray(arr).toString());
}

}


【回溯算法】

回溯算法(点击查看)  = 递归(数量够了就停止) + 回溯(状态重置)

模板框架如下:回溯算法模板框架如下:

【LeeCode】46. 全排列_sed_02

标签:排列,LinkedList,nums,46,int,LeeCode,result,new,path
From: https://blog.51cto.com/u_13682316/5888017

相关文章

  • P6462 [传智杯 #2 决赛] 补刀 ----- 分类
    题目描述UIM在写程序的空闲玩一款MOBA游戏。当敌方的小兵进入到我方防御塔的范围内,就会持续受到防御塔造成的伤害;当然我方英雄也可以对它造成伤害。当小兵的血量降......
  • 四种语言刷算法之全排列
    力扣46.全排列1、C/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothre......
  • 【Leecode】有效括号
    【题目描述】给定一个只包括 ​​'('​​,​​')'​​,​​'{'​​,​​'}'​​,​​'['​​,​​']'​​ ​​s​​ ,判断字符串是否有效​有效字符串需满足:左括号必须用相同......
  • 【LeeCode】M选N
    【题目描述】M选N组合算法, 有m长度的数组,从中随机选出n个,一般m远大于n【示例】例如求5中选3的组合:1,2,3   1,2,4   1,3,4  2,3,4   1,2,5   1,3......
  • luogu P4465 [国家集训队] JZPSTR
    题面传送门我真的,我哭死,如果考了我当场感谢zyq。听说std是SAM+块链,我瑟瑟发抖,然后祭出了bitset大法。据说这个是叫一种Shift-And的基于位运算的字符串匹配算法,也就是说,......
  • mysql升序排列id为0的在最后
    在实际开发中有时会有升序排列id为0的在最后的需求,这里我记录了一种在stackoverflow中比较简单的方法如下:Youmaywanttotrythefollowing:SELECT*FROMyour_tableOR......
  • 春秋云境 CVE-2022-24663复现
    靶标介绍:远程代码执行漏洞,任何订阅者都可以利用该漏洞发送带有“短代码”参数设置为PHPEverywhere的请求,并在站点上执行任意PHP代码。P.S.存在常见用户名低权限用户......
  • P4464 [国家集训队] JZPKIL 题解
    NOIP前三天,感觉绝对复习不完了的gtm1514认为已经没有什么好害怕的了,于是做起了数学题。因为摆了大烂所以只有一道。P4464[国家集训队]JZPKIL题意不再赘述。下午看......
  • 31. 下一个排列(stl的algorithm中next_permutation的实现)
    注:这题思路就是stl的algorithm中next_permutation的实现思路整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如,arr=[1,2,3] ,以下这些都可以视作 ......
  • 【算法】最后一个单词的长度,颠倒二进制位,排列序列等三道题目
    颠倒二进制位题目描述颠倒给定的32位无符号整数的二进制位。提示:请注意,在某些语言(如Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并......