论坛首页 综合技术论坛

来来来,有兴趣的人便来战这算法题吧:

浏览 45091 次
该帖已经被评为精华帖
作者 正文
   发表时间:2005-08-14  
这题是这次 google 的 top coder 的 850 分例题,做过的同学先不要吱声:

引用
假设有这样一种字符串,它们的长度不大于 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) 的。
   发表时间:2005-08-14  
15 分钟内能够做出来,就有希望通过偶老板的算法考试了 ……
0 请登录后投票
   发表时间: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
0 请登录后投票
   发表时间:2005-08-14  
ABA明明只有5个阿,
cdab,cadb,cabd,acdb,acbd,
那来的8个?
0 请登录后投票
   发表时间:2005-08-14  
femto 写道
ABA明明只有5个阿,
cdab,cadb,cabd,acdb,acbd,
那来的8个?

AAA 就只有一个
  偶算错了。
0 请登录后投票
   发表时间:2005-08-14  
题目中b和d看错乐,做错乐......用时完毕......go home
0 请登录后投票
   发表时间: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"));


    }
}
0 请登录后投票
   发表时间:2005-08-14  
做出来鸟?不如推荐我去google?:)刚好最近在找工作~~
junit只测了前面4个字母的组合,应该是对的了:)
算法复杂度不知道是多少?不清楚这算不算穷举
0 请登录后投票
   发表时间:2005-08-15  
是一道组合数学题,明显有公式,我都忘光了。
0 请登录后投票
   发表时间:2005-08-15  
嘿嘿,femto 你倒是很有捷才呀。代码没有细看,不过看你的结果没错,而且思路也对,应该是没有问题了。

不错不错!:D
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics