一个算法问题 - ITeye问答

问答首页 → 移动开发技术

0 0

一个算法问题5

完成一个方法，返回一种排列组合的所有字符串结果的数目。排列组合的规则如下：

1）排列组合的的字符串由a~z 26个小写字母组成；

2）方法入参为每个字符串长度；

3）每个字符串中的后一个字符的字母顺序要大于前一个字符；例如：abc 合法；bac、aac 不合法；

这个问题没有头绪，递归好像不好实现，望大家答疑解惑！

数据结构

2014年8月20日 13:59

WilliamHoward
26
0 0 3

采纳的答案

aac不行，说明不能重复
1~26个不重复
x=1，y=26
x=2，y=25+24+...+1
x=3，y=(24+23+...+1)+(23+22+...+1)+...(2+1)+1
...
x=26，y=1
两种思路，第一种不递归
用一个list，然后用循环把所有可能的字符串
例如x=4，则是aaaa,aaab,...baaa,baab,...zzzz全都枚举，并进行你上述的规则校验，校验通过就判断list中是否有了，没有就放进去，最后list的size就是结果。
第二种，递归
假设x=3，第一个字母有a~z（y和z经过校验不可以），然后取第二个字母，取第三个字母，每次取出字母都要符合你的规则，取完回到取第一个字母，依次，直到第一个字母取不出（假设字母是1~26，如果x=20，那么7也就是g是最后能取出的，h就取不出了）则递归结束，每取完一遍用计数器+1，递归完成时，计数器的数字就是结果。

2014年8月20日 16:30

h248980496
461
1 1 20

4条评论

0 0

上面的公式没写对。应该是这个

[url]http://baike.baidu.com/picture/2104972/2104972/0/6c63514aa4a6e77409f7efff?fr=lemma&ct=single [/url]

2014年8月21日 12:09

mfkvfn
40
0 0 3

添加评论

0 0

你只要的是数目，所以就是一个数学的排序组合问题。
可以这样理解：长度为N时结果就是从26个字母中取出N个不同字母的组合情况。因为按规则3来看N个不同字母最后的排列只能是一种情况“按字母大小排序”。

所以题目可以改为：
从26个小写字母中取出N个字母，然后按字母顺序进行排列。一共有多少种情况。
答案就是A(26,N)。26是下标，N是上标。根据数学公式，结果为
26*(26-1)*(26-2)*...*(26-N)
A(26,N)=------------------------------
(N*(N-1)*(N-2)*..*1

2014年8月21日 12:05

mfkvfn
40
0 0 3

2条评论

0 0

这是数学问题，应该可以推出一个公式。跟算法没有关系。

2014年8月21日 11:55

mfkvfn
40
0 0 3

添加评论

0 0

这个就是base36，换句话说就是36进制的数字
0,1,2.。。。9,a....z(z意思就是36)
各种语言基本都内置多进制支持，除了显式支持的2进制，8进制，16进制，基本都支持到62进制（0-9，a-z，A-Z）。
比如Integer.pareseInt(string,进制）-->Java里面

这样，你这个问题就是转换为下面的问题了：

输入给你一个多位数字，由几个单个数字构成

求由这几个数字构成的所有数字，要求高位比低位数字大。

这就是一个很简单的循环就能搞定的问题了。

求出所有数字后，转换为相应字符串即可。

2014年8月21日 10:19

red008
217
0 1 24

1条评论

0 0

我是这样认为的：

这个问题的本质实际上是树的路径遍历，原因是可以将问题结果作为树根，第一层为结果，第二层为所有可能的字母，第三层为对于每个可能的字母，顺序大于该字母的字母作为子节点.而树的高度+1则为字符串长度。比如假设只有abc三个字母结果(a,b,c) ==> a(bc),b(c),c(NULL) 第二层 ==> ab(c) bc(NULL)。

使用递归的方式，显然是能够解决问题的，不再赘述，但是效率较低。众所周知，树的路径遍历问题实际上是可以转化为循环方式的，方法如下：

使用一个队列，取名为Q；

第一步：ROOT ==> Q 作为初始化；
第二部：取Q的第一个元素（Q删除），取名为E
    情况1：队列为空：结束程序；
    情况2：sizeOf(E)即E包含的字母个数 = 输入长度+1 --------输出E
    情况3：否则罗列所有大于Q的字母X， (E+X) ==>Q （E+X的目的是为了记住路径内容）；
第三部：GOTO 第二步

也可以使用栈，区别是使用队列为广度遍历的方式，使用栈为深度遍历的方式，与递归比较类似。

2014年8月21日 10:01

鳄鱼旭
248
0 0 17