锁定老帖子 主题:来来来,有兴趣的人便来战这算法题吧:
该帖已经被评为精华帖
|
|
---|---|
作者 | 正文 |
发表时间:2005-08-14
引用 假设有这样一种字符串,它们的长度不大于 26 ,而且若一个这样的字符串其长度为 m ,则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成,同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ,那么它一定是由 a, b, c, d, e 这 5 个字母构成,不会多一个也不会少一个。嗯嗯,这样一来,一旦长度确定,这个字符串中有哪些字母也就确定了,唯一的区别就是这些字母的前后顺序而已。
现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序: 如果字母 b 在字母 a 的后面,那么序列的第一个字母就是 A (After),否则序列的第一个字母就是 B (Before); 如果字母 c 在字母 b 的后面,那么序列的第二个字母就是 A ,否则就是 B; 如果字母 d 在字母 c 的后面,那么 …… 不用多说了吧?直到这个字符串的结束。 这规则甚是简单,不过有个问题就是同一个 AB 序列,可能有多个字符串都与之相符,比方说序列“ABA”,就有“acdb”、“cadb”等等好几种可能性。说的专业一点,这一个序列实际上对应了一个字符串集合。那么现在问题来了:给你一个这样的 AB 序列,问你究竟有多少个不同的字符串能够与之相符?或者说这个序列对应的字符串集合有多大?注意,只要求个数,不要求枚举所有的字符串。 嘿嘿,这就是你要解决的问题了。如果不嫌慢的话大可以穷举,不过这种解法拿出来那是显然不好意思和人打招呼的。事实上,如果设 AB 序列的长度为 n ,那么这个问题是可以做到 O(n^3) 的。 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2005-08-14
15 分钟内能够做出来,就有希望通过偶老板的算法考试了 ……
|
|
返回顶楼 | |
发表时间:2005-08-14
不知道对不对哦,我算出一个公式:
ABAB.. ,这个序列长度为n, 则解码为符合序列的个数为: 用数组替代上面ABA序列为a[n] for(i=1... i=n-1) (n+1)!/2 * (a[i]-a[i-1] ==0?1:2)*/(n-i) 例如对于 ABA,用上面公式换算为; 4!/2 * 2/3 * 2/2=8 |
|
返回顶楼 | |
发表时间:2005-08-14
ABA明明只有5个阿,
cdab,cadb,cabd,acdb,acbd, 那来的8个? |
|
返回顶楼 | |
发表时间:2005-08-14
femto 写道 ABA明明只有5个阿,
cdab,cadb,cabd,acdb,acbd, 那来的8个? AAA 就只有一个 偶算错了。 |
|
返回顶楼 | |
发表时间:2005-08-14
题目中b和d看错乐,做错乐......用时完毕......go home
|
|
返回顶楼 | |
发表时间:2005-08-14
/**
Counter.java */ import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * author femto * Date: 2005-8-14 */ public class Counter { private List tmpLastCharPoses = new ArrayList(); public int count(String s) { char[] chars = s.toCharArray(); int result =0; List lastCharPoses; tmpLastCharPoses.add(new Integer(0)); for (int i = 0; i < chars.length; i++) { char aChar = chars[i]; lastCharPoses = tmpLastCharPoses; result = 0; tmpLastCharPoses = new ArrayList(); for (Iterator it = lastCharPoses.iterator(); it.hasNext();) { Integer lastCharPos = (Integer) it.next(); result += count(lastCharPos.intValue(), aChar, i); } } return result; } private int count(int lastCharPos, char aChar, int i) { if (aChar == 'A') { for (int j = lastCharPos + 1; j <= i + 1; j++) { tmpLastCharPoses.add(new Integer(j)); } return i + 1 - lastCharPos; } else if (aChar == 'B') { for (int j = 0; j <= lastCharPos; j++) { tmpLastCharPoses.add(new Integer(j)); } return lastCharPos + 1; } else { throw new RuntimeException("Oops"); } } } /** CounterTest.java */ import junit.framework.TestCase; /** * author femto * Date: 2005-8-14 */ public class CounterTest extends TestCase { public void testCount() throws Exception { assertEquals(1, new Counter().count("A")); assertEquals(1, new Counter().count("B")); assertEquals(1, new Counter().count("AA")); assertEquals(2, new Counter().count("AB")); assertEquals(2, new Counter().count("BA")); assertEquals(1, new Counter().count("BB")); assertEquals(1, new Counter().count("AAA")); assertEquals(3, new Counter().count("AAB")); assertEquals(5, new Counter().count("ABA")); assertEquals(3, new Counter().count("ABB")); assertEquals(3, new Counter().count("BAA")); assertEquals(5, new Counter().count("BAB")); assertEquals(3, new Counter().count("BBA")); assertEquals(1, new Counter().count("BBB")); assertEquals(1, new Counter().count("AAAA")); assertEquals(4, new Counter().count("AAAB")); assertEquals(9, new Counter().count("AABA")); assertEquals(6, new Counter().count("AABB")); assertEquals(9, new Counter().count("ABAA")); assertEquals(16, new Counter().count("ABAB")); assertEquals(11, new Counter().count("ABBA")); assertEquals(4, new Counter().count("ABBB")); } } |
|
返回顶楼 | |
发表时间:2005-08-14
做出来鸟?不如推荐我去google?:)刚好最近在找工作~~
junit只测了前面4个字母的组合,应该是对的了:) 算法复杂度不知道是多少?不清楚这算不算穷举 |
|
返回顶楼 | |
发表时间:2005-08-15
是一道组合数学题,明显有公式,我都忘光了。
|
|
返回顶楼 | |
发表时间:2005-08-15
嘿嘿,femto 你倒是很有捷才呀。代码没有细看,不过看你的结果没错,而且思路也对,应该是没有问题了。
不错不错!:D |
|
返回顶楼 | |