我遇到了一个挑战,要在java中制作一个算法来计算一个字符串形式可能有多少DNA链.字符串可以包含这5个字符(A,G,C,T,？)
？在字符串中可以是(A,G,C或T)但是？可能不会导致字符串中的一对.例如,在这个字符串"A？G" ？可能只有C或T.可以有无限的问号对,因为它们最后都是字符.
功能形式就是这个
public static int chains(String base) {
// return the amount of chains
}
如果基本字符串是"A？C？" 可能的组合是6 =(AGCA,AGCG,AGCT,ATCA,ATCG,ATCT)
案件 (??? - 36)(AGAG - 1)(A ??? T - 20)
(？ - 4)(A？ - 3)(？A - 3)(?? - 12)(A？A - 3)(A？C - 2)...
给定基数(pohja)字符串的最大长度为10!
标准: 1.连续两个字符的组合是非法组合,因此不计算.
到目前为止我所拥有的:
public static int chains(String pohja) {
int sum = 1;
int length = pohja.length();
char[] arr = pohja.toCharArray();
int questionMarks = 0;
if (length == 1) {
if (pohja.equals("?"))
return 4;
else
return 1;
} else if (length == 2) {
boolean allQuestionMarks = true;
for (int i = 0; i < 2; i++) {
if (arr[i] != '?')
allQuestionMarks = false;
else
questionMarks++;
}
if (allQuestionMarks) return 12;
if (questionMarks == 1) {
return 3;
} else {
return 2;
}
} else {
questionMarks = 0;
for (int i = 0; i < length; i++) {
if (arr[i] == '?') questionMarks++;
}
for (int i = 1; i < length - 1; i++) {
boolean leftIsLetter = isLetter(arr[i - 1]);
boolean rightIsLetter = isLetter(arr[i + 1]);
boolean sameSides = false;
if (arr[i - 1] == arr[i + 1]) sameSides = true;
if (arr[i] != '?') { // middle is char
if (leftIsLetter && rightIsLetter) { // letter(left) == letter(right)
if (sameSides) {
// Do nothing!
} else {
sum *= 3;
}
} else if (!leftIsLetter && !rightIsLetter) { // !letter(left) == !letter(right)
} else { // letter(left) != letter(right)
}
} else { // Middle is ?
if (leftIsLetter && rightIsLetter) { // letter(left) == letter(right)
if (sameSides) {
sum *= 3;
} else {
sum *= 2;
}
} else if (!leftIsLetter && !rightIsLetter) { // !letter(left) == !letter(right)
sum *= 9;
} else { // letter(left) != letter(right)
if (arr[i - 1] == '?') { // ? is on the left
} else { // ? is on the right
sum *= 2;
}
}
}
}
}
return sum;
}
public static boolean isLetter(char c) {
boolean isLetter = false;
char[] dna = { 'A', 'G', 'C', 'T' };
for (int i = 0; i < 4; i++) {
if (c == dna[i]) isLetter = true;
}
return isLetter;
}
是的,我知道,我的代码很乱.如果pohja(base)的长度为3或更多,我的算法将一次检查3个字符并根据算法检查的字符修改总和.
任何人都可以暗示如何解决这个问题吗？:)提前谢谢,TuukkaX.
注意:因为你只是要求提示,所以我会保持这种模糊.如果您希望我进一步深思,请随时提问.
为了在数学上解决这个问题,你需要知道的是你可以在每个问号序列上进行替换的数量(即在基本字符串中"A?GCT???T?G",你有三个问号序列 - 两个包含一个问号,并且一个有三个).在这种情况下,您可以拥有的替换总量等于您可以为每个序列进行的替换量的乘积.
简单示例:在字符串中"A?G?",第一个问号可以替换为两个字符,而第二个问号可以替换为三个.总的来说,这是2*3 = 6合法的可能性.
计算结果的挑战在于找出如何计算更长的问号序列可以进行的替换量.我会给你最后一个提示并将解决方案作为扰流板包含在内:合法替换的数量取决于问号前后的字符.不过,我会留下以哪种方式向你发现.
澄清:
您可以进行的替换量取决于问号前后的字符是否相等.例如,
"A??A"总共有6种法律可能性并且"A??G"有7种.这需要加以考虑.
以下是如何将其用于解决方案:
现在,如何解决这样的问题
"A????A"？记住,取代的总量=每个单独序列的取代产物."A????A"是一个由四个问号组成的序列,它们之前和之后的字符是相等的.替换第二个字符有三种合法的可能性,并且它们中的每一个都留下"[G|C|T]???A"- 如同三个问号的序列,前一个和后一个字符不相等.您可以继续以递归方式执行此操作以获取可能的结果字符串总数.请记住,在基本字符串的开头和结尾处的问号需要特殊处理.
如果您仍然无法解决问题,我会给您一个方法的标题,以计算序列的合法替换数量:
private int calcSequenceSubs(int length, boolean prevFollEqual)
这可能是身体:
if (prevFollEqual){
if (length == 1) return 3;
else return 3 * calcSequenceSubs(length-1, false);
} else {
if (length == 1) return 2;
else return 2 * calcSequenceSubs(length-1, false) + calcSequenceSubs(length-1, true);
}
编辑(没有剧透的简化版):
整个字符串的合法解决方案的数量等于每个问号序列的解决方案数量的乘积.例如,"A？A？A"有两个问号序列,每个问号都有三个合法替换,因此整个字符串总共有3*3 = 9个法律解决方案.
所以,需要做的是:
棘手的部分实际上是对每个序列的合法替换量进行估算.这取决于两件事:序列的长度(显然)以及序列之前和之后的字符是否相等(例如,单个问号,当前一个和后一个字符相等时有3个可能的结果,否则有两个) .
现在,对于更长的序列,可以反复计算合法替换的总量.例如,"A ?? T"是两个问号的序列,前后字符不相等.第一个问号可以用T,G或C代替,产生"T？T","G？T"或"C？T".其中两个是一个问号的序列,其中前一个和后一个字符不相等,其中一个是前一个和后一个字符相等的一个问号的序列.
递归算法的模式总是相同的 - 如果序列的前一个和后一个字符不相等,则两个选项会产生一个序列,其中前一个和后一个字符是不同的,一个是它们相同的序列.同样,当原始序列中的前一个和后一个字符相等时,所有3个选项都导致下一步是前一个和后一个字符不同的序列.
可能解决方案的代码示例:
public static int DNAChains(String base) {
if (base == null || base.length() == 0) {
return 0;
}
int curSequence = 0;
int totalSolutions = 1;
boolean inSequence = false;
//flag to check whether there are any sequences present.
//if not, there is one solution rather than 0
char prevChar = 'x';
char follChar = 'y';
int i = 0;
char[] chars = base.toCharArray();
//handle starting sequence if present
while (i < chars.length && chars[i] == '?') {
curSequence++;
i++;
}
if (curSequence > 0) {
//exclusively ?'s needs to be treated even differently
if (i < chars.length) {
//? at the edge can be anything, so 3*false, 1*true
//if length is 1 though, there are just 3 solutions
totalSolutions *= (curSequence > 1) ? 3 * solveSequence(curSequence - 1, false) + solveSequence(curSequence - 1, true) : 3;
curSequence = 0;
} else {
//result is 4*3^(length-1)
totalSolutions = 4* ((int) Math.pow(3, chars.length-1));
}
}
//check for sequences of question marks
for (; i < chars.length; i++) {
if (chars[i] == '?') {
if (!inSequence) {
inSequence = true;
prevChar = chars[i - 1];
//there is at least one sequence -> set flag
}
curSequence++;
} else if (inSequence) {
inSequence = false;
follChar = chars[i];
totalSolutions *= solveSequence(curSequence, prevChar == follChar);
curSequence = 0;
}
}
//check if last sequence ends at the edge of the string
//if it does, handle edge case like in the beginning
if (inSequence) {
//? at the edge can be anything, so 3*false, 1*true
//if length is 1 though, there are just 3 solutions
totalSolutions *= (curSequence > 1) ? 3 * solveSequence(curSequence - 1, false) + solveSequence(curSequence - 1, true) : 3;
}
return totalSolutions;
}//end DNAChains
private static int solveSequence(int length, boolean prevFollEqual) {
if (prevFollEqual) {
//anchor
if (length == 1) {
return 3;
} else {
return 3 * solveSequence(length - 1, false);
}
} else {
//anchor
if (length == 1) {
return 2;
} else {
return 2 * solveSequence(length - 1, false) + solveSequence(length - 1, true);
}
}
}//end solveSequence
我没有彻底测试,但它似乎工作.我设法处理边缘情况(不是100%确定我是否得到了所有这些).