【每日一题】2019-10-28-字符串的排列

watchpoints commented 5 years ago

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab、cba。扩容如果是数字呢 1-10的数字

https://www.cnblogs.com/AndyJee/p/4655485.html

watchpoints commented 5 years ago

扩展

N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/n-queens 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

watchpoints commented 5 years ago

46全排列问题 https://leetcode-cn.com/problems/permutations-ii/

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

watchpoints commented 5 years ago

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

参考 https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

watchpoints commented 5 years ago

去重复”的思想来源 1、发现困难：

这道题我们完全可以按照第 46 题，在结果集中去重，不过在实际编码的时候，我们会发现并不好做，因为可能产生重复的是一个列表对象，如果是简单的数字，直接放在哈希表中去重就好了。

2、在以前做过的问题中寻找经验：

我们可以想象一下，在一个数组中去掉重复元素，除了使用哈希表，更容易想到的是将原始数组排序（升序、降序均可）。

可以确定的是：重复的元素一定不会是数组第 0 号索引位置的元素。因为要相同元素只保留 1 个，为了方便编码，相同元素我们保留第 1 个或者最后 1 个。

「力扣」第 15 题：“三数之和” 就利用这样的思路，在遍历到相同元素的第 2 个的时候，将当前循环 continue 掉，这一

作者：liweiwei1419 链接：https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

watchpoints commented 5 years ago