[原题]
http://www.iteye.com/topic/15295
写道
假设有这样一种字符串,它们的长度不大于 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 序列,问你究竟有多少个不同的字符串能够与之相符?或者说这个序列对应的字符串集合有多大?注意,只要求个数,不要求枚举所有的字符串。
这是一个老贴子了,并且3楼帖了答案,但是我认为,这个答案是不标准的,正确与否姑且不论,题中假设的26位长的数据那个是不支持的,因为极易出内存溢出,于是我重新设计了一种算法,我认为在内存上和时间中都比原来的优秀。
其实在后面还有更好的解法,欢迎读原贴。
[解题思路]
一开始,我也受到了找到数据间的数学关系的影响。别说,还真找到了一个,只是数学太差,无法表达出来,假设为5位数,那么数据的分布是1,4,3,2,2,3,4,1...1,4,3,2,2,3,4,1.....,有什么用呢,好像没用。。
终于偶然间恍然大悟,有个最简单的规律就是,假设这是一个从a开始,每次都有A,B两种可能,但是上级已出现的概率决定了下级出现的概率,由于不需要枚举出各个数据,那么可以只要知道上级中最后的那个数出现的位置,就决定了下级有那些可能会出现的情况。
[代码实现]
import java.math.BigInteger;
public class Main {
/**
* 数组相加
*
* @param arr1
* @param arr2
* @return
*/
private static BigInteger[] add(BigInteger[] arr1, BigInteger[] arr2) {
if (arr1.length != arr2.length)
return null;
for (int i = 0; i < arr1.length; i++) {
arr1[i] = arr1[i].add(arr2[i]);
}
return arr1;
}
/**
* 数组集体相乘一个倍数
*
* @param arr
* @param num
* @return
*/
private static BigInteger[] multiply(BigInteger[] arr, BigInteger num) {
if (arr == null)
return null;
for (int i = 0; i < arr.length; i++) {
arr[i] = arr[i].multiply(num);
}
return arr;
}
/**
* 求解一个字符串中加入一个新的字符位置分布<br>
*
* 对一个定长length的字符中,在一定位置index中的前后(charAt)加入一个字符<br>
* 其将产生一个数组,可以记录新加字符所在位置<br>
* 在index前加入一个字符时,从0-index之间都有一种可能<br>
* 在index后加入一个字符时,从index+1-length之间也有一种可能
*
* @param length
* @param index
* @param charAt
* @return
*/
private static BigInteger[] child(int length, int index, char charAt) {
BigInteger[] arr = new BigInteger[length + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = new BigInteger("0");
}
if (charAt == 'A') {
for (int i = index + 1; i <= length; i++) {
arr[i] = new BigInteger("1");
}
} else {
for (int i = 0; i <= index; i++) {
arr[i] = new BigInteger("1");
}
}
return arr;
}
/**
* 取出对应字符所在位置的分布数组<br>
*
* 对于一个已经存在的数组分布来说,扩展一个charAt的字符,那么产生的新数组分布也是一定的<br>
* 遍历现存的数组分布,对其每个值进行求对应的数组分布可能,并将结果与现在记录个数相乘,累加后的结果即一个全新的数组分布
*
* @param sizes
* @param charAt
* @return
*/
private static BigInteger[] step(BigInteger[] sizes, char charAt) {
BigInteger[] newSizes = new BigInteger[sizes.length + 1];
for (int i = 0; i < newSizes.length; i++) {
newSizes[i] = new BigInteger("0");
}
for (int i = 0; i < sizes.length; i++) {
newSizes = add(newSizes, multiply(child(sizes.length, i, charAt), sizes[i]));
}
return newSizes;
}
/**
* 根据AB字符串取出符合条件的个数
*
* @param str
* @return
*/
private static BigInteger test(String str) {
BigInteger[] sizes = new BigInteger[] { new BigInteger("1") };
BigInteger sum = new BigInteger("0");
for (int i = 0; i < str.length(); i++) {
sizes = step(sizes, str.charAt(i));
}
for (int i = 0; i < sizes.length; i++) {
sum = sum.add(sizes[i]);
}
return sum;
}
public static void main(String[] args) {
System.out.println(test("AAA"));
System.out.println(test("AAB"));
System.out.println(test("ABA"));
System.out.println(test("ABAA"));
System.out.println(test("ABAB"));
System.out.println(test("AABAAABAAABAAABAAABAAABABB"));
}
}
[结论
]
运算结果如下:
1
3
5
9
16
23469961608638992720
查看结果的前几个,还是正确的,就是无法对后面的结论进行验证了,寒。。。
在使用BigInteger代替int后,不但可以实现对26位数据的计算,那怕是假设为62位,也是秒杀的。
这个算法最大的好处是不占用内存,那怕对1000的数据计算时,理论上也就约占2x1000多的数组。但是数据约大,计算的时间还是成指数倍的增长了。
PS:谁想知道1000的数据有多少种可能么?试试就知道了。我的机器上花了7分钟,居然算过来了。。
分享到:
相关推荐
hadoop2面试题 - 2012腾讯笔试的一道算法题.pdf
12-02-28网易笔试一道算法题,附件代码是我自己的解题
一道微软算法题很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用很有用...
目前 需要去面试 据说面试前需要做一道算法题 所以搜集了一些leetcode的算法题共享
考试类精品--总结一下面试常考的算法题,希望可以帮助每一位想要提升自己面试能力的同学。对于每一道算法题会总结代码、时
贪心算法 一般来说,贪婪算法有五个组成部分: 一个候选集:从中创建一个解决方案 一个选择函数:用于选择要添加到解决方案中的最佳候选项 一个可行性函数:用于确定候选项是否可以为解决方案做出贡献 一个目标函数...
NULL 博文链接:https://wanghongxu.iteye.com/blog/1835601
几乎每一次公司考试都会有一道算法题,我这有一套最常用的。
主要为大家详细介绍了一道python走迷宫算法题,用一个二维数组表示一个简单的迷宫,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
board=Algorithm&gid=8898发信人: snoowball (Snowball), 信区: Algorithm标 题: Re: 问一道算法题
说实话,一天做完一道算法题还是很吃力的,并且每个人都自己的规划和任务,也不是都有时间刷题。所以,大家可以根据具体情况来安排个人时间,有时间了多做一些,没时间就少做或不做。 目前构想的题目知识模块有:
每天一道算法题 为了应付面试,开始写博客,准备开三个系列,第一个 JS算法系列,主要整理一些面试过程中常见的算法题 ; 第二个 ECMAScript规范解析,主要是想从ES规范的角度来解析JS代码的实际执行过程,只有真正...
记录一道面试算法题餐馆问题(贪心和动态规划) 贪心算法和动态规划.pdf
AB序列,是一道经典的算法题。可以google搜索“AB”序列。 这儿是Java实现代码
已知某个班有n(1)个学生,输入每行为学生姓名(最多20个字符)和其c语言成绩(0~100),请按照成绩从高到低排序后输出。若有相同的,不能改变其顺序。
一道题目的算法优化过程 作者很详细的分析了算法的优化过程。
给定一个十进制正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有“1”的个数。 N= 2,写下1,2。这样只出现了1个“1”。 N= 12,我们会写下1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。...
【说某明餐】厅供应各种标准的营养套餐。...nv:n+1行M+1列的二维数组,其中行和列的下标均从0开始,nv[i][j]表示由前i项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
主要是对二进制文件的操作