经典算法题型(一):排列与组合 | 您所在的位置:网站首页 › 排列组合的题型总结 › 经典算法题型(一):排列与组合 |
排列
一、基本概念
排序是常见的数学问题,如何使用编程罗列出所有排序的可能呢? 下面结合leetcode第46题给出简单的分析思路。 二、题目详情46. 全排列 *给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 三、解题分析如图所示,通过图解分析我们可以看出,只要将排列问题拆解成一个个单独的数字,并对其剩下的数字继续拆分,直到剩下一个数字,就可以得到一种解答。如:[123],取1,得:1->[23],取2,得1->2->3||如果再第二步取3,得1->3->2,以此类推得出所有结果。 四、代码及注释: package IMUHERO; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Solution46 { ArrayListres=new ArrayList(); boolean [] visited; public List permute(int[] nums) { if (nums.length==0||nums==null)return res; LinkedListlist=new LinkedList(); visited=new boolean[nums.length];//初始值为false; generatePermute(nums,0,list); return res; } public void generatePermute(int [] nums,int index,LinkedList p){ if (index==nums.length){ res.add((LinkedList)p.clone());//注意此处不能直接add(p),这样会相当于添加了一个引用,后期随着p的回溯修改,结果中的值也会随之被修改,不是我们想要的结果 return; } for (int i=0;i |
CopyRight 2018-2019 实验室设备网 版权所有 |