- 浏览: 173663 次
- 性别:
- 来自: 济南
文章分类
最新评论
有关排列的问题我们可以与组合比较来考虑,解决这类问题我们都采用回溯法,在组合中不用考虑顺序,而在排列中就要考虑顺序,例如(1,2,3)和(2,1,3),在组合的概念中是相等的,但它们是不同的排列。下面列举leetcode中有关permutations的几道题目。
1,Permutation
给定一个数组numbers ,输出所有可能的排列。
例如:numbers = {1,2,3};
输出:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],[3,2,1].
因为我们要考虑顺序,回溯的时候我们始终从第一个元素开始遍历,如果长度等于数组的长度我们就找到结果,保存这个结果,然后返回上一层,继续遍历。代码如下:
2,Permutation2
给定一个数组numbers, 给出所有可能的排列,数组中可能存在重复元素。
例如:numbers[] = {1,1,2}
输出:[1,1,2], [1,2,1], [2,1,1].
因为有重复元素,所以在判断添加元素时不能通过元素的值来判断,我们可以通过维护一个数组,来记录已经遍历过的元素的下标,只添加没遍历过的元素。代码如下:
3,Next Permutation
给定一个排列,返回下一个比它大的排列。如果找不到比它大的元素,就返回排列中和最小的组合。
例如:
给定1, 2, 3 返回 1, 3, 2
给定3, 2, 1 返回 1, 2, 3
给定 1, 1, 5 返回 1, 5, 1
找到比它大的组合,我们不妨从后面遍历数组,找到第一个i元素,使nums[i] >nums[i-1], 找到这个位置如果直接将它们位置调换并不一定不符合提议,例如一个数组是{1,2,5,3},第一个nums[i] >nums[i-1] 的是5>2,如果直接将它们交换结果为{1,5,2,3},而正确结果应该为{1,3,2,5}。因此再找到这个i位置后,我们要遍历i元素后面的元素,如果有元素比nums[i-1]
大,就将它们位置互换,再将i后面剩余的元素按升序排列。实现代码如下:
4,Permutation Sequence
给定一个整数n,n >= 1 && n <= 9; 在给定一个整数k,要求输出第k个排列。
如果我们用回溯法列出所有排列,然后取第k个排列。代码如下:
到这样会超时,我们完全可以直接计算出第k个排列。我们都知道n个元素全排列的结果为n!,我们把这n!个排列分成n组,每个组都有(n-1)!个,那么第k个元素在第几组呢,我们不妨通过简单的例子来分析一下,当n = 3时,第一组为{1,2,3},{1,3,2}; 第二组为{2,1,3},{2,3,1} ;第三组为{3,1,2},{3,2,1},因此当k等于1或2时属于第一组;等于3,4时属于第二组;等于5,6时属于第三组,符合(k-1)%(n-1)! ,这样我们就确定了第一个元素。我们令k = k/(n-1)!,循环操作,直到n为1位置,代码如下:
1,Permutation
给定一个数组numbers ,输出所有可能的排列。
例如:numbers = {1,2,3};
输出:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],[3,2,1].
因为我们要考虑顺序,回溯的时候我们始终从第一个元素开始遍历,如果长度等于数组的长度我们就找到结果,保存这个结果,然后返回上一层,继续遍历。代码如下:
public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); if(nums == null) return llist; permutation(0, nums, list, llist); return llist; } private void permutation(int start, int[] nums, LinkedList<Integer> list, List<List<Integer>> llist) { if(list.size() == nums.length){ llist.add(new LinkedList<Integer>(list)); } for(int i = start; i < nums.length; i++) { if(list.size() < nums.length && !list.contains(nums[i])) { list.add(nums[i]); permutation(0, nums, list, llist); list.removeLast(); } } } }
2,Permutation2
给定一个数组numbers, 给出所有可能的排列,数组中可能存在重复元素。
例如:numbers[] = {1,1,2}
输出:[1,1,2], [1,2,1], [2,1,1].
因为有重复元素,所以在判断添加元素时不能通过元素的值来判断,我们可以通过维护一个数组,来记录已经遍历过的元素的下标,只添加没遍历过的元素。代码如下:
public class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); LinkedList<Integer> usedIndex = new LinkedList<Integer>(); if(nums == null) return llist; Arrays.sort(nums); permutationUnique(0, nums, list, usedIndex, llist); return llist; } private void permutationUnique(int start, int[] nums, LinkedList<Integer> list, LinkedList<Integer> usedIndex, List<List<Integer>> llist) { if(list.size() == nums.length) { llist.add(new LinkedList<Integer>(list)); } int delete = Integer.MAX_VALUE; for(int i = start; i < nums.length; i++) { if(delete == nums[i]) continue; if(!usedIndex.contains(i)) { usedIndex.add(i); list.add(nums[i]); permutationUnique(0, nums, list, usedIndex, llist); usedIndex.removeLast(); delete = list.removeLast(); } } } }
3,Next Permutation
给定一个排列,返回下一个比它大的排列。如果找不到比它大的元素,就返回排列中和最小的组合。
例如:
给定1, 2, 3 返回 1, 3, 2
给定3, 2, 1 返回 1, 2, 3
给定 1, 1, 5 返回 1, 5, 1
找到比它大的组合,我们不妨从后面遍历数组,找到第一个i元素,使nums[i] >nums[i-1], 找到这个位置如果直接将它们位置调换并不一定不符合提议,例如一个数组是{1,2,5,3},第一个nums[i] >nums[i-1] 的是5>2,如果直接将它们交换结果为{1,5,2,3},而正确结果应该为{1,3,2,5}。因此再找到这个i位置后,我们要遍历i元素后面的元素,如果有元素比nums[i-1]
大,就将它们位置互换,再将i后面剩余的元素按升序排列。实现代码如下:
public class Solution { public void nextPermutation(int[] nums) { if(nums == null) return; for(int i = nums.length - 1; i > 0; i--) { if(nums[i] > nums[i-1]) { int j = nums.length - 1; while(j > i-1 && nums[j] <= nums[i-1]) j --; int tem = nums[i-1]; nums[i-1] = nums[j]; nums[j] = tem; Arrays.sort(nums, i, nums.length); return; } } reverse(nums); } public void reverse(int[] nums) { int l = 0; int r = nums.length -1; while(l < r) { int tem = nums[l]; nums[l] = nums[r]; nums[r] = tem; l ++; r --; } } }
4,Permutation Sequence
给定一个整数n,n >= 1 && n <= 9; 在给定一个整数k,要求输出第k个排列。
如果我们用回溯法列出所有排列,然后取第k个排列。代码如下:
public class Solution { List<List<Integer>> llist = new ArrayList<List<Integer>>(); public String getPermutation(int n, int k) { List<Integer> list = new ArrayList<Integer>(); if(n == 0) return null; permutation( n, k, list); if(k <= llist.size()){ String result = ""; for(int i = 0; i < llist.get(k-1).size(); i++){ result += llist.get(k-1).get(i).toString(); } return result; } return null; } private void permutation( int n, int k, List<Integer> list){ if(list.size() == n) { llist.add(new ArrayList<Integer>(list)); return; } for(int i = 1; i <= n; i++){ if(!list.contains(i)) { list.add(i); permutation(n, k, list); list.remove(list.size()-1); } } } }
到这样会超时,我们完全可以直接计算出第k个排列。我们都知道n个元素全排列的结果为n!,我们把这n!个排列分成n组,每个组都有(n-1)!个,那么第k个元素在第几组呢,我们不妨通过简单的例子来分析一下,当n = 3时,第一组为{1,2,3},{1,3,2}; 第二组为{2,1,3},{2,3,1} ;第三组为{3,1,2},{3,2,1},因此当k等于1或2时属于第一组;等于3,4时属于第二组;等于5,6时属于第三组,符合(k-1)%(n-1)! ,这样我们就确定了第一个元素。我们令k = k/(n-1)!,循环操作,直到n为1位置,代码如下:
public class Solution { public String getPermutation(int n, int k) { ArrayList<Integer> list = new ArrayList<Integer>(); StringBuffer sb = new StringBuffer(); int[] fac = new int[n]; fac[0] = 1; for(int i = 1; i < n; i++) { fac[i] = fac[i-1] * i; } for(int i = 1; i <= n; i++) { list.add(i); } k = k - 1; for(int i = 0; i <= n - 1; i++) { int index = k /fac[n - 1 - i]; sb.append(list.get(index)); list.remove(index); k = k % fac[n - 1 - i]; } return sb.toString(); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 227You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 513Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 862Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
大部分蠕虫建模工作都是基于相对简单的随机扫描蠕虫,而且蠕虫的形态是相对固定的。随着蠕虫技术的显著提高,在传播方式上出现了较...最后在仿真的基础上对蠕虫传播的动力学机制进行了总结,对防御方法进行了初步探讨。
这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 Search in Rotated ...
Permutation in String 小年糕在线笔试 请用您熟悉的编程语言,编程实现一个比较任意两个软件版本号大小的函数,如 1.2.3a 和 1.2.4b 比较,后者版本号更大,请考虑各种情况,不可以使用系统提供的比较函数。 ...
NextPermutation 下一排序 完成 DFS 题目 说明 状态 NumIslands 岛屿数量 完成 DivideAndConquer 题目 说明 状态 MaxSubArray 最大子序和 完成 Back Tracing 题目 说明 状态 GenerateParenthesis 括号生成 完成 ...
266:https://leetcode-cn.com/problems/palindrome-permutation/ 题目: 思路:判断能否形成回文串,那只要数奇数个字符的种类是否大于2,大于2肯定不可以形成 代码: 409:...
permutation - combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only...
)的算法,前两天给学生讲课,无意间想到这个问题,回来总结了一下,可以由7种算法求解,其中动态循环类似回溯算法,实现起来比较繁琐,故总结了6种,以飨读者。所有算法均使用JavaScript编写,可直接运行。算法一:...
combine_and_permutation全排列和组合 dp_string字符串中的动态规划问题 tsp_code旅行商问题的求解 modes_install统计机器翻译环境的安装、运行 moses_server机器翻译的网页demo nginx_install_testNginx的入门 ...
在每个问题的结尾,将通过写下我所学到的、有效的和无效的内容以及原因的总结来进行复习。 任何其他结束语也将包含在摘要中。 目录: 1. Two Sum (Easy) 2. Add Two Numbers (Medium) 3. Longest Substring Without ...
Permutation Sequence Valid Sudoku Trapping Rain Water Rotate Image Plus One Climbing Stairs Set Matrix Zeroes Gas Station Candy Majority Element Rotate Array Contains Duplicate Contains Duplicate II ...
(要多看看排序算法..,多总结...!!!!!) P1923 求第k小的数 (STL中的nth_element, 快速排序的第一阶段(findK), 高级(主席树), 快读(read), 编译优化) P1036 选数(求组合数(dfs)) P1157 组合的输出(求组合数...
2.7归纳与总结. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 51 2.8借shared_ptr 实现copy-on-write. . . . . . . . . . . . . . . . . . . . . . 52 第3章多线程服务器的适用场合与常用...