[Leetcode][python]Permutations/全排列 末蓝、 2022-06-07 01:22 181阅读 0赞 ## 题目大意 ## 求一组数的全排列 ## 解题思路 ## 回溯,想起来思路很简单,实际写的时候遇到了很多麻烦。 ## 代码 ## ### 递归 ### 可能更容易理解,但是代码复杂度高 class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ self.res = [] sub = [] self.dfs(nums,sub) return self.res def dfs(self, Nums, subList): if len(subList) == len(Nums): #print res,subList self.res.append(subList[:]) for m in Nums: if m in subList: continue subList.append(m) self.dfs(Nums,subList) subList.remove(m) ### 递归方法二 ### 例子:ABC n = nums[:i] + nums[i+1:] n = BC n = A + C = AC n = AB 最后在ABC+(BC+C)+(AC+A)+(AB+B) class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ print 'nums', nums if len(nums) <= 1: return [nums] ans = [] for i, num in enumerate(nums): n = nums[:i] + nums[i+1:] # n是剩余数的list print nums[:i], '+', nums[i+1:], '=', n for y in self.permute(n): # 直到函数有return,一个数的时候[nums],所以y是list print '递归内:' print [num], '+', y, '=',[num] + y ans.append([num] + y) print '-----End-----' return ans 输出: nums [1, 2, 3] [] + [2, 3] = [2, 3] nums [2, 3] [] + [3] = [3] nums [3] 递归内: [2] + [3] = [2, 3] -----End----- [2] + [] = [2] nums [2] 递归内: [3] + [2] = [3, 2] -----End----- 递归内: [1] + [2, 3] = [1, 2, 3] 递归内: [1] + [3, 2] = [1, 3, 2] -----End----- [1] + [3] = [1, 3] nums [1, 3] [] + [3] = [3] nums [3] 递归内: [1] + [3] = [1, 3] -----End----- [1] + [] = [1] nums [1] 递归内: [3] + [1] = [3, 1] -----End----- 递归内: [2] + [1, 3] = [2, 1, 3] 递归内: [2] + [3, 1] = [2, 3, 1] -----End----- [1, 2] + [] = [1, 2] nums [1, 2] [] + [2] = [2] nums [2] 递归内: [1] + [2] = [1, 2] -----End----- [1] + [] = [1] nums [1] 递归内: [2] + [1] = [2, 1] -----End----- 递归内: [3] + [1, 2] = [3, 1, 2] 递归内: [3] + [2, 1] = [3, 2, 1] -----End----- 答案:`[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]` 清爽版: class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ print 'nums', nums if len(nums) <= 1: return [nums] ans = [] for i, num in enumerate(nums): n = nums[:i] + nums[i+1:] for temp_list in self.permute(n): ans.append([num] + temp_list) print '-----End-----' return ans ## 总结 ##
相关 排列2 全排列 <table> <tbody> <tr> <td> <h2>排列2</h2> <strong>Time Limit: 1000/1000 MS (Java/O 小咪咪/ 2024年02月18日 22:39/ 0 赞/ 74 阅读
相关 全排列 问题描述:设有\{r1,r2,...,rn\}共n个元素,这n个元素中可能存在重复元素,试设计一个算法,列出这n个元素的不同排列。 参考代码: inclu 电玩女神/ 2022年08月05日 02:54/ 0 赞/ 231 阅读
相关 全排列 全排列 给出一个字符串或整数数组,对这个字符串或整数数组进行全排列 例如:\{1, 2, 3\} 数组,对这个整数数组进行全排列。 递归实现 实现 以你之姓@/ 2022年07月17日 15:25/ 0 赞/ 257 阅读
相关 全排列 标题:带分数 100 可以表示为带分数的形式:100 = 3 + 69258 / 714 还可以表示为:100 = 82 + 3546 / 197 注意特征:带分数 今天药忘吃喽~/ 2022年06月18日 09:51/ 0 赞/ 213 阅读
相关 全排列 方法一:采用递归的方式例子1、将数组int arr\[4\]=\{1,2,3,4\}进行全排列 static int n = 0; void Perm( ﹏ヽ暗。殇╰゛Y/ 2022年06月17日 06:19/ 0 赞/ 249 阅读
相关 全排列 题目描述 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], 以你之姓@/ 2022年04月25日 06:54/ 0 赞/ 249 阅读
相关 全排列 全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以\{1, 2, 3, 4, 5\}为 例说明如何编写全排列的递归算法。 1、首先看 男娘i/ 2022年03月19日 01:50/ 0 赞/ 293 阅读
相关 全排列 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入:"23" 输 约定不等于承诺〃/ 2022年02月15日 00:47/ 0 赞/ 315 阅读
相关 全排列 talk is cheap, show me the code. public static void permutation(char[]ss,int i){ 蔚落/ 2022年01月29日 04:55/ 0 赞/ 334 阅读
还没有评论,来说两句吧...