Java递归调用
Java递归调用
提问于 2021-09-30 02:50:18
我想建立一个代码来遍历任何0和1的序列，并计算它可以通过多少种不同的方式通过数字，只是在‘1’之间“跳跃”。而且它每次只能跳跃不超过3位数字。
例如，数字100110101可能类似于: 1xx1xx1x1或1xx11x1x1 (通过所有的‘1’传递)。
另一个示例可以是1011011101: 1x11x111x1 (全部为'1')或1xx1x111x1或1x1xx1x1x1，依此类推...
重要的是跳跃不超过3位数。并且该数字始终以1开头和结尾。
我得到了下面的代码，我认为它是工作的。
public int calculate(String number){
if(number.length()<3){ //left fill with 0
if(number.length()==2) number = "0" + number;
else number = "00" + number;
}
if(number.length() == 3){ //for 001, 101, 011, 111
if (number.equalsIgnoreCase("111")) return 2; //2 possible ways
else return 1; //any other combination will have just one way
}
String aux = number.substring(1,4);//take the 3 next digits
//recursive calls to calculate it
if (aux.equalsIgnoreCase("001")) return calculate(number.substring(3, number.length()));
else if (aux.equalsIgnoreCase("010")) return calculate(number.substring(2, number.length()));
else if (aux.equalsIgnoreCase("011")) return calculate(number.substring(2, number.length())) + calculate(number.substring(3, number.length()));
else if (aux.equalsIgnoreCase("100")) return calculate(number.substring(1, number.length()));
else if (aux.equalsIgnoreCase("101")) return calculate(number.substring(1, number.length())) + calculate(number.substring(3, number.length()));
else if (aux.equalsIgnoreCase("110")) return calculate(number.substring(1, number.length())) + calculate(number.substring(2, number.length()));
else if (aux.equalsIgnoreCase("111")) return calculate(number.substring(1, number.length())) + calculate(number.substring(2, number.length())) + calculate(number.substring(3, number.length()));
return 0;
}问题是:我还想确保它不允许连续两次跳跃3位数。不允许使用类似于1xx1xx1的内容。但是，由于我使用的是递归调用，我不知道这是否可能。
回答 2
Stack Overflow用户
发布于 2021-09-30 03:01:48
防止连续两次跳转3位数的一种方法是将额外的状态信息传递给calculate()；您传递的额外数据将是一个布尔值，指示最后一次跳转的长度是否为3。然后，在最初调用calculate()时，只需确保指示最后一次跳转的长度不是3(因此允许第一次跳转的长度为3)。
Stack Overflow用户
发布于 2021-09-30 04:32:26
private static int countPossibilities(String inputString) {
final char validChar = '1';
final char maxDistance = 3; // max consecutive jumps. eg: maxDistance for '1xxx1' is 3.
if (inputString.length() == 1) {
return 1;
}
var indexForMaxPossibleJump = Math.min(maxDistance + 1, inputString.length() - 1);
if (inputString.charAt(indexForMaxPossibleJump) != validChar) {
indexForMaxPossibleJump = inputString.substring(0, indexForMaxPossibleJump).lastIndexOf(validChar);
}
// No jumps possible.
if (indexForMaxPossibleJump == 0) {
return 0;
}
int finalCount = 0;
var remainingString = inputString.substring(indexForMaxPossibleJump);
var maxJumpingString = inputString.substring(1, indexForMaxPossibleJump);
// calculate count if we are not jumping to max distance. i.e., taking intermediate step on 1.
for (var i = 0; i < maxJumpingString.length(); i++) {
if (maxJumpingString.charAt(i) != validChar) {
continue;
}
var countOfString = countPossibilities(maxJumpingString.substring(i) + remainingString);
finalCount += countOfString;
}
// calculate count if we are jumping to max distance.
var countOfRemainingString = countPossibilities(remainingString);
finalCount += countOfRemainingString;
return finalCount;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69385501
复制相关文章
相似问题
腾讯云开发者
