- 浏览: 130552 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
原题链接:https://leetcode.com/problems/permutations-ii/
[分析] 同Permutation一题的区别在于输入数组可能包含重复元素,在面试时即使面试官没有明确指出也该想到。如何处理重复元素不致得到重复结果呢?基本思路是排序然后跳过重复元素。Method1 每次循环递归都要排序且要复制一次数组,时间和空间消耗都比较大,Method2是Code Ganker大神的思路,使用一个额外数组used表示元素是否已经被排好位置。去重的关键是for循环一开始的if判断,理解起来有些费劲,大神的解释:只对第一个未被使用的进行递归,如果第一个重复元素前面的元素还没在当前结果中,那么我们不需要进行递归,这一次结果会出现在第一个的递归函数结果中。举例理解下:假设元素 a 有重复, 下标 i 和 i-1 处均是 a, 处理 i 下标时发现 i-1 下标的 a 还未被使用,这种情况下 i 应当跳过,因为循环是从前往后的推进的,i-1 已先被循环处理过,在这层递归中假设元素将排在位置 k 处,则若不跳过 i ,i 也被放在位置 k 处,最终将导致结果重复。
[ref] Code Ganker大神博客
http://blog.csdn.net/linhuanmars/article/details/21570835
[分析] 同Permutation一题的区别在于输入数组可能包含重复元素,在面试时即使面试官没有明确指出也该想到。如何处理重复元素不致得到重复结果呢?基本思路是排序然后跳过重复元素。Method1 每次循环递归都要排序且要复制一次数组,时间和空间消耗都比较大,Method2是Code Ganker大神的思路,使用一个额外数组used表示元素是否已经被排好位置。去重的关键是for循环一开始的if判断,理解起来有些费劲,大神的解释:只对第一个未被使用的进行递归,如果第一个重复元素前面的元素还没在当前结果中,那么我们不需要进行递归,这一次结果会出现在第一个的递归函数结果中。举例理解下:假设元素 a 有重复, 下标 i 和 i-1 处均是 a, 处理 i 下标时发现 i-1 下标的 a 还未被使用,这种情况下 i 应当跳过,因为循环是从前往后的推进的,i-1 已先被循环处理过,在这层递归中假设元素将排在位置 k 处,则若不跳过 i ,i 也被放在位置 k 处,最终将导致结果重复。
[ref] Code Ganker大神博客
http://blog.csdn.net/linhuanmars/article/details/21570835
public class Solution { public List<List<Integer>> permuteUnique2(int[] nums) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) return result; Arrays.sort(nums); recur(nums, new boolean[nums.length], new ArrayList<Integer>(), result); return result; } public void recur(int[] nums, boolean[] used, List<Integer> item, List<List<Integer>> result) { if (item.size() == nums.length) { result.add(new ArrayList<Integer>(item)); return; } for (int i = 0; i < nums.length; i++) { if (i > 0 && !used[i - 1] && nums[i] == nums[i - 1]) continue; if (!used[i]) { item.add(nums[i]); used[i] = true; recur(nums, used, item, result); used[i] = false; item.remove(item.size() - 1); } } } public List<List<Integer>> permuteUnique(int[] num) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(num == null || num.length == 0) return result; Arrays.sort(num); return permutate(num, 0); } private List<List<Integer>> permutate(int[] num, int beg){ List<List<Integer>> result = new ArrayList<List<Integer>>(); if(beg == num.length - 1){ List<Integer> item = new ArrayList<Integer>(); item.add(num[beg]); result.add(item); return result; } int origin = num[beg]; for(int i = beg; i < num.length; i++){ if(i != beg && num[i] == num[i - 1]) continue; num[beg] = num[i]; num[i] = origin; int[] sub = Arrays.copyOf(num, num.length); Arrays.sort(sub, beg + 1, num.length); for(List<Integer> item : permutate(sub, beg + 1)){ item.add(0, num[beg]); result.add(item); } num[i] = num[beg]; num[beg] = origin; } return result; } }
发表评论
-
Leetcode - Palindrome Permutation II
2015-08-28 21:17 2185Given a string s, return all th ... -
Leetcode - Factor Combination
2015-08-28 09:53 821Numbers can be regarded as prod ... -
Leetcode - Generate Parentheses
2015-08-08 17:01 485[分析] 第一个思路(错误的~):假设递归函数返回 n - ... -
Leetcode - Word Search II
2015-08-03 21:25 935iven a 2D board and a list of w ... -
Leetcode - Word Search
2015-08-03 21:03 479Given a 2D board and a word, fi ... -
Leetcode - Subset
2015-08-02 12:06 915[分析] 三种思路 思路1:每层递归新加一个元素,第一层递归, ... -
Leetcode - Subset II
2015-08-02 12:13 922[分析] 延续Subset三种思路,关键是添加去重处理 思路 ... -
Leetcode - Gray Code
2015-08-01 17:26 545原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation Sequence
2015-08-01 17:19 481原题链接:https://leetcode.com/probl ... -
Leetcode - Combination
2015-08-01 08:36 458[分析] 从 n 个数中取 k 个数,第一个数有 n 种取法… ... -
Leetcode - Combination Sum III
2015-07-31 22:04 499[分析] 思路就是枚举k个数所有可能的组合并判断是否符合条件。 ... -
Leetcode - Combination Sum II
2015-07-31 21:06 576[分析] 输入数组中的每个元素至多使用一次,相较于Combin ... -
Leetcode - Combination Sum
2015-07-31 20:21 554Given a set of candidate number ... -
Leetcode - Sudoku Solver
2015-07-31 09:14 434[分析] 做Valid Sudoku时表示3*3区块的下标想得 ... -
Leetcode - N Queues II
2015-07-30 20:52 377[分析] 做完N皇后第一题,这个就so easy~ pu ... -
Leetcode - N-Queens
2015-07-30 20:38 407[分析] N皇后摆放规则:两个皇后不能共存于同一行、同一列以及 ... -
Leetcode - Word Ladder II
2015-06-26 09:19 501Given two words (start and end) ... -
Leetcode - Combination Sum III
2015-06-10 10:09 512Find all possible combinati ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 748Given a string s, partition s s ... -
Leetcode - WordBreak III
2015-04-16 08:30 424Given a string s and a dictio ...
相关推荐
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...
266:https://leetcode-cn.com/problems/palindrome-permutation/ 题目: 思路:判断能否形成回文串,那只要数奇数个字符的种类是否大于2,大于2肯定不可以形成 代码: 409:...
leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...
leetcode TOP 题目 说明 flag TOP hash_map STL TOP 链表操作 链表 TOP 标记每次的begin,一旦发现重复,则需要从这个字母上一次出现的地方的下一个字符为begin 数组 TOP 两指针o(n)遍历变形二分查找,第一个数组找...
1)Permutation_Palindrome - Easy - Codechef - {涵盖了地图(stl)和回文逻辑的最佳使用} 2)句子中单词的出现 - 简单 - Coding Ninjas - {Learned to use 'getline','stringstream','map','itreating over a map'...
lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划阶段,在这个阶段我将用我自己的话来...Permutation (Medium) 34. Find First and Last Position of Element in Sorted Arr
Source file for LeetCode Permutations Problem
137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...
II - Input array is sorted (E) 653. Two Sum IV - Input is a BST (E) -> 2 26. Remove Duplicates from Sorted Array (E) 27. Remove Element (E) 31. Next Permutation (M) * -> index 주의, 부등호 하나 틀림 ...
Permutation 解决方法:掌握排列组合的字典序规律,即可。这个规律找不到,我最后还是直接看答案的。 LeetCode: 581. Shortest Unsorted Continuous Subarray 解决方法:无序列中最大最小值 2018-08-17 19:47 ...
next_permutation.py - 将数字重新排列为按字典顺序排列的下一个更大的数字排列 permutations2.py - 返回所有可能的唯一排列 3sum_2.py - 查找数组中所有唯一的三元组,其总和为零。 3sum.py - 查找数组中所有唯一的...
leetcode卡Python 中的数据结构 leetcode, geekforgeeks 等解决了各种类型的问题。 ************************************ 回溯跟踪 **************** ************************ ************************ 回溯 ****...
leetcode中国 LeetCode | LuoGu 题型记录 P1980 计数问题 (数位dp, 朴素算法) P1047 校门外的树 (线段树, ...全排列问题(next_permutation, dfs(最主要需要记住,置位后需要清0(f[i]=0))) P3392 涂国旗(组合) P23
Permutation], , [77 Combination], [78 Subset], [90 Subset II], [39 Combination Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] ...
leetcode_0031_next_permutation.c leetcode_0033_search_rotate.c : binary search, offer11 81 leetcode_0034_first_last_pos.c : binary search leetcode_0035_search_inseart.c : binary search leetcode...
31.Next_Permutation_下一个排列【LeetCode单题讲解系列】
leetcode 658完整程序力扣笔记 不。 标题 笔记/类 困难 标签 19 中等的 Two pointers Fast-slow Linked list 25 难的 Linked list Recursion 41 难的 Array Hashmap 53 简单的 DP Tricky dp[i] 61 中等的 Linked ...
nextPermutation 等。 : KMP, RabinKarp : 路径压缩、按秩合并。 : 质数测试、筛选等。 : 阶乘、模阶乘、二项式系数、帕斯卡三角。 : 欧几里得公约数,扩展欧几里得,模拟元。 : create2DArray, create3DArray, ...
Permutation 算法也可用于迭代地查找数组的排列。 也可用于迭代查找数组的排列。 13 . 14 . 15 . 16 . 17 . Algorithm to find kth largest element from an unsorted array in linear time. (1) If the number of ...
NextPermutation 下一排序 完成 DFS 题目 说明 状态 NumIslands 岛屿数量 完成 DivideAndConquer 题目 说明 状态 MaxSubArray 最大子序和 完成 Back Tracing 题目 说明 状态 GenerateParenthesis 括号生成 完成 ...