什么是回溯算法
本篇内容介绍了“什么是回溯算法”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
成都创新互联公司长期为上千客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为路南企业提供专业的成都网站设计、成都网站制作,路南网站改版等技术服务。拥有十余年丰富建站经验和众多成功案例,为您定制开发。
Example 1:
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
Analysis
回溯算法
与LeetCode - Medium - 46. Permutations类似,不同之处在于给定一个可包含重复数字的序列,要返回所有不重复的全排列,这里涉及到去重。
去重一定要对元素进行排序,这样我们才方便通过相邻的节点来判断是否重复使用。
以示例中的 [1,1,2]为例 (为了方便举例,已经排序)抽象为一棵树,去重过程如图:
图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。
拓展
去重最为关键的代码为:
if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) continue;
如果将!used[i - 1]改成 used[i - 1], 结果也是正确的!很神奇。
if (used[i] || i > 0 && nums[i - 1] == nums[i] && used[i - 1]) continue;
这是为什么呢,就是上面我刚说的,如果要对树层中前一位去重,就用!used[i - 1]。如果要对树枝前一位去重用used[i - 1]。
对于排列问题,树层上去重和树枝上去重,都是可以的,但是树层上去重效率更高!
用[1,1] 来举一个例子。
树层上去重(!used[i - 1]),的树形结构如下:
树枝上去重(used[i - 1])的树型结构如下:
用[1,1,1] 再来举一个例子。
树层上去重(!used[i - 1]),的树形结构如下:
树枝上去重(used[i - 1])的树型结构如下: 显然,树层上对前一位去重非常彻底,效率很高,树枝上对前一位去重虽然最后可以得到答案,但是做了很多无用搜索。
小结
树层上去重要加上!used[i - 1],似非而是,代码结合图加深理解吧!
参考
回溯算法:排列问题(二)
Submission
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class PermutationsII { public List> permuteUnique(int[] nums) { List
> result = new ArrayList<>(); List
path = new ArrayList<>(); boolean[] used = new boolean[nums.length]; Arrays.sort(nums); backtracking(path, nums, used, result); return result; } private void backtracking(List path, int[] nums, boolean[] used, List > result) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i] || i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) continue; used[i] = true; path.add(nums[i]); backtracking(path, nums, used, result); path.remove(path.size() - 1); used[i] = false; } } }
Test
import static org.junit.Assert.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder; import org.hamcrest.Matcher; import org.junit.Test; @SuppressWarnings("unchecked") public class PermutationsIITest { private final int[] array1 = {1, 1, 2}; private final int[] array2 = {1, 2, 3}; private final int[] array3 = {0, 1, 0, 0, 9}; private final Matcher>> expected1 = containsInAnyOrder(Arrays.asList(1,1,2), // Arrays.asList(1,2,1), Arrays.asList(2,1,1)); private final Matcher >> expected2 = containsInAnyOrder(Arrays.asList(1,2,3), Arrays.asList(1,3,2),// Arrays.asList(2,1,3), Arrays.asList(2,3,1), Arrays.asList(3,1,2), Arrays.asList(3, 2, 1)); private final String expected3String = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,0,1],"// + "[0,0,9,1,0],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,0,1],"// + "[0,9,0,1,0],[0,9,1,0,0],[1,0,0,0,9],[1,0,0,9,0],[1,0,9,0,0],"// + "[1,9,0,0,0],[9,0,0,0,1],[9,0,0,1,0],[9,0,1,0,0],[9,1,0,0,0]"; private final Matcher >> expected3 = containsInAnyOrder(string2IntegerList(expected3String)); @Test public void test() { PermutationsII obj = new PermutationsII(); assertThat(obj.permuteUnique(array1), expected1); assertThat(obj.permuteUnique(array2), expected2); assertThat(obj.permuteUnique(array3), expected3); } private List [] string2IntegerList(String original){ List [] result; original = original.substring(1, original.length() - 1); String[] strs = original.split("\\],\\["); result = new ArrayList[strs.length]; for(int i = 0; i < strs.length; i++) { String[] nums = strs[i].split(","); List list = new ArrayList<>(); for(String num : nums) { list.add(Integer.valueOf(num)); } result[i] = list; } return result; } @Test public void testString2IntegerList() { String str = "[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,1,0]," + "[0,0,9,0,1],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,1,0]," + "[0,9,0,0,1],[0,9,1,0,0],[0,9,0,1,0],[0,9,0,0,1],[1,0,0,0,9]," + "[1,0,0,9,0],[1,0,9,0,0],[1,9,0,0,0],[9,0,0,1,0],[9,0,0,0,1]," + "[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1],[9,1,0,0,0],[9,0,0,1,0]," + "[9,0,0,0,1],[9,0,1,0,0],[9,0,0,1,0],[9,0,0,0,1]"; System.out.println(string2IntegerList(str)); } }
“什么是回溯算法”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
分享文章:什么是回溯算法
URL链接:http://myzitong.com/article/ghspsd.html