| 经典算法题型（一）：排列与组合 | 您所在的位置：网站首页 › 排列组合的题型总结 › 经典算法题型（一）：排列与组合 |
经典算法题型（一）：排列与组合
|
排列
一、基本概念
排序是常见的数学问题，如何使用编程罗列出所有排序的可能呢？ 下面结合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 |
【本文地址】
公司简介
联系我们