自己做了之后,也看看了一些别人的算法,发现跟其中一个人的差不多,所以就没有跟帖了,把自己的答案贴在了这里。
题目:
假设有这样一种字符串,它们的长度不大于 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 序列,问你究竟有多少个不同的字符串能够与之相符?或者说这个序列对应的字符串集合有多大?注意,只要求个数,不要求枚举所有的字符串。
分析:
由于后一个字母可以放置的位置与前一个字母放置的位置preAlphabetPosition有关,用递归法可以得到答案
我的解法:
public class CountAllPossible
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
int sum=countAllPossible("ABA");
System.out.println(sum);
}
public static int countAllPossible(String str)
{
return count(str,0,1);
}
public static int count(String subStr,int preAlphabetPosition,int allPossiblePosition)
{
if(subStr.charAt(0)!='A'&&subStr.charAt(0)!='B')
throw new IllegalArgumentException();
int sum=0;
if(subStr.charAt(0)=='A')
{
for (int index = 0; index <= preAlphabetPosition; index++)
{
if(subStr.length()==1)
{
sum+=1;//reach the end
}
else
{
sum+=count(subStr.substring(1),index,allPossiblePosition+1);
}
}
}
else//='B'
{
for(int index=preAlphabetPosition+1;index<=allPossiblePosition;index++)
{
if(subStr.length()==1)//reach the end
{
sum+=1;
}
else
{
sum+=count(subStr.substring(1),index,allPossiblePosition+1);
}
}
}
return sum;
}
}
分享到:
相关推荐
标题中的“一道算法题,亏在二叉树的构造和递归算法上了”暗示了这个问题主要涉及计算机科学中的数据结构,特别是二叉树,以及使用递归算法解决相关问题。在编程领域,二叉树是一种基础且重要的数据结构,常用于实现...
贪心算法 每天一道算法题:分治算法,回归算法,贪心算法,回溯算法.zip
### hadoop2面试题 - 2012腾讯笔试的一道算法题 #### 背景与题目概述 本文档提供了2012年腾讯笔试中一道关于字符串处理的算法题,该题目要求将字符串中的所有大写字母移动到字符串的末尾,同时保持其他字符的相对...
board=Algorithm&gid=8898发信人: snoowball (Snowball), 信区: Algorithm标 题: Re: 问一道算法题
说实话,一天做完一道算法题还是很吃力的,并且每个人都自己的规划和任务,也不是都有时间刷题。所以,大家可以根据具体情况来安排个人时间,有时间了多做一些,没时间就少做或不做。 目前构想的题目知识模块有:
在准备面试时,掌握一些常见的算法题是至关重要的,尤其是对于技术面试来说。这份压缩包“考试类精品--总结一下面试常考的算法题”显然为面试者提供了一个宝贵的资源,帮助他们提升自身的编程和算法解决能力。在这个...
每天一道算法题 为了应付面试,开始写博客,准备开三个系列,第一个 JS算法系列,主要整理一些面试过程中常见的算法题 ; 第二个 ECMAScript规范解析,主要是想从ES规范的角度来解析JS代码的实际执行过程,只有真正...
详细解析与解答:对于每一道算法题,提供清晰、详尽的解题思路、代码实现以及时间复杂度分析是非常重要的。这不仅能帮助用户理解问题本质,还能学习到高效的解决策略。 互动学习平台:一些资源还提供了在线的编程...
12-02-28网易笔试一道算法题,附件代码是我自己的解题
这个问题是去哪儿网2014年笔试中的一道算法题,其目标是编写一个函数`RP2AP`,接收一个相对路径字符串作为输入,并返回其对应的绝对路径。 该函数的核心逻辑如下: 1. 首先,检查输入和输出指针是否为NULL,如果...
每日一道算法题 2021-1-16, 阅读【算法图解】,刷一道二分查找的题目,. 2021-2-8,Leetcode,题号15,刷一道数组的题目,. 2020-2-17,Leetcode,题号16,刷一道数组的题目, 2020-2-18,Leetcode,题号18,刷一道...
描述中的“AlgorithmSet”和“每天一道算法题”表明这是一个系统化的算法学习资源,可能是某个开源项目或者学习计划,旨在帮助用户通过每天解决一道算法题来提升自己的编程和算法能力。"Algorithm.playground"可能是...
【标题】"YunDang-Algorithm:群策群力,每日解决一道算法题" 提供了一个关于算法学习和实践的项目,旨在帮助开发者通过每天解决一个算法问题来提升自己的编程技能。该项目的核心理念是集体智慧,鼓励团队成员共同...
LeetCode Everyday项目就是这样一个极好的资源,它鼓励开发者每天都解决一道算法题,以此来保持对编程的热情和敏锐度。这个项目不仅局限于LeetCode上的题目,而是涵盖了更广泛的算法题目,帮助程序员拓宽视野,深入...
坚持每天刷一道算法题,冲鸭!!! day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无重复字符的最长子串 day8 排序链表...
Code4God:微信平台一天一道算法题的服务器源码,部署在百度云