前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >这5道算法题 都可以套用这个模板

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

作者头像
double
发布2018-07-31 17:45:32
5030
发布2018-07-31 17:45:32
举报
文章被收录于专栏:算法channel

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 代码

代码语言:javascript
复制
 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) 集合内元素都不相同,求子集

代码语言:javascript
复制
 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) 集合内元素可能相同,求子集

代码语言:javascript
复制
 1nums = [1,2,2], 子集为:
 2
 3[
 4  [2],
 5  [1],
 6  [1,2,2],
 7  [2,2],
 8  [1,2],
 9  []
10]

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

代码语言:javascript
复制
1[1,1,2] 的不同组合序列:
2
3[
4  [1,1,2],
5  [1,2,1],
6  [2,1,1]
7]

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

代码语言:javascript
复制
1已知 “aab”,  返回:
2[ [“aa”,”b”], [“a”,”a”,”b”] ]

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-07-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档