这5道算法题 都可以套用这个模板

1 题目

如何求 1~n 这连续 n 个数的全排列呢? 例如 n=3时,全排列序列如下:

"123"

"132"

"213"

"231"

"312"

"321"

2 分析

首先我们拿出元素1,然后在1,2,3 这个深度方向寻找,找到满足题意的解有两个,1,2,3 和 1,3,2;

然后再在广度方向上搜索,此时的元素为2,再在1,2,3 深度方向上搜索,得到满足题意的解,2,1,3和2,3,1,

最后,在广度方向上搜索到3,再在1,2,3 深度方向上搜索,满足题意的解为 3,1,2 和 3,2,1。

3 代码

 1public class Solution
 2
 3    {
 4        public IList<IList<int>> GetPermutation(int n)
 5        {
 6            IList<IList<int>> rslt = new List<IList<int>>();
 7            dfs(rslt, new List<int>(),1,n);
 8            return rslt;
 9        }
10        // start 是dfs抽出的一个关键参数
11        private void dfs(IList<IList<int>> rslt, 
12                                 List<int> curItem, 
13                                 int start,
14                                 int digits)
15        {
16
17            //找到一个解
18            if (curItem.Count == digits) 
19            {
20                rslt.Add(new List<int>(curItem));
21                return;
22            }
23
24            //广度方向搜索
25            for (int i = 1; i <= digits; i++) 
26            {
27                //跳过重复元素
28                if (curItem.Contains(i))
29                    continue;
30                curItem.Add(i);
31                //深度方向上的递归
32                dfs(rslt, curItem, i,digits); 
33               //后进栈的元素优先出栈
34                curItem.RemoveAt(curItem.Count - 1); 
35           }
36        }
37    }

4 套用模板可求解的题目

1) 集合内元素都不相同,求子集

 1nums = [1,2,3], 子集为:
 2[
 3
 4  [3],
 5
 6  [1],
 7
 8  [2],
 9
10  [1,2,3],
11
12  [1,3],
13
14  [2,3],
15
16  [1,2],
17
18  []
19
20]

2) 集合内元素可能相同,求子集

 1nums = [1,2,2], 子集为:
 2
 3[
 4  [2],
 5  [1],
 6  [1,2,2],
 7  [2,2],
 8  [1,2],
 9  []
10]

3) 求集合的不同组合序列

1[1,1,2] 的不同组合序列:
2
3[
4  [1,1,2],
5  [1,2,1],
6  [2,1,1]
7]

4)各个分割字符串都是回文数:

1已知 “aab”,  返回:
2[ [“aa”,”b”], [“a”,”a”,”b”] ]

以上四道题目都可以套用本文中的代码模板,只需要稍作改动,不妨想一想怎么改动,已到达融会贯通的效果。

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷T21776 子序列

题目描述 你有一个长度为 nn 的数列 ,这个数列由 0,10,1 组成,进行 mm 个的操作: 1~l~r1 l r :把数列区间 [l, r][l,r] ...

43480
来自专栏计算机视觉与深度学习基础

Leetcode 212 Word Search II 字典树 + 回溯

Given a 2D board and a list of words from the dictionary, find all words in the...

21770
来自专栏Python攻城狮

科学计算工具Numpy1.ndarray的创建与数据类型2.ndarray的矩阵运算ndarray的索引与切片3.ndarray的元素处理元素判断函数元素去重排序函数4.2016年美国总统大选民意调查

Numpy:提供了一个在Python中做科学计算的基础库,重在数值计算,主要用于多维数组(矩阵)处理的库。用来存储和处理大型矩阵,比Python自身的嵌套列表结...

31430
来自专栏派森公园

最简单的NP-Hard问题

21580
来自专栏Android机器圈

算法:插入排序详解--为什么从第二项开始,而不是第一项

PS:对于插入排序这个算法,我们想要看清他就要从它的应用场景,概念,用法等去了解它,实现代码就那么几行,但有时还真是不好理解,比如说为什么从第二项开始,而不是从...

40460
来自专栏tkokof 的技术,小趣及杂念

编程小知识之 Random接口返回值

平日工作中,(伪)随机数的使用一定是避不开的,拿 C# 为例,System 命名空间下的 Random 类型一般都是我们生成(伪)随机数的第一选择:

11930
来自专栏老九学堂

【学习】Java微课堂之switch语句

知识点: ? ? 扩展知识介绍 Java随机数类Random介绍 Java实用工具类库中的类java.util.Random提供了产生各种类型随机数的方法。它可...

37450
来自专栏PHP在线

关于PHP浮点数精度损失问题

$f = 0.57; echo intval($f * 100); //56 结果可能有点出乎你的意外,PHP遵循IEEE 754双精度: 浮点数, 以64位...

31350
来自专栏tkokof 的技术,小趣及杂念

OpenGL ES Shading Language 2.0 参考笔记

声明 struct matStruct { vec4 ambientColor; vec4 diffuseColor; ...

12110
来自专栏深度学习与计算机视觉

算法-二维数组中的查找

问题: 在一个二维数组中,每一行元素都按照从左到右递增的顺序排序,每一列元素都按照从上到下递增的顺序排序。实现一个查找功能的函数,函数的输入为二维数组和一个...

206100

扫码关注云+社区

领取腾讯云代金券