Java递归实现二进制序列1间跳步计数 新增禁止连续跳3位需求咨询

核心修改思路 #

• 新增递归参数标记上一次跳跃类型：原来的递归逻辑没有记录上一步的跳跃步长，我们需要新增一个布尔参数lastJumpIs3，标识上一次跳跃是否为跨越3位的操作，首次调用时传false即可。
• 限制跳3位的分支触发条件：所有对应跨越3位的递归分支（即调用substring(3)的逻辑），只有在上一次跳跃不是3位的时候才会生效，否则直接跳过该分支，避免连续两次跳3位。
• 保持对外接口兼容：重载原有的calculate方法，对外暴露的无额外参数的方法不变，内部调用新增参数的递归方法即可。

修改后的完整代码 #

// 对外暴露的原有方法，保持接口不变
public int calculate(String number) {
    // 初始调用，上一次没有跳跃，不会触发连续跳3位限制
    return calculate(number, false);
}

// 新增的内部递归方法，多了标记上一次跳跃类型的参数
private int calculate(String number, boolean lastJumpIs3) {
    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
    
    //递归调用逻辑增加跳3位的限制判断
    if (aux.equalsIgnoreCase("001")) {
        // 该分支只能选择跳3位，上一次已经是跳3位的话直接返回0（无合法路径）
        return lastJumpIs3 ? 0 : calculate(number.substring(3, number.length()), true);
    } else if (aux.equalsIgnoreCase("010")) {
        // 跳2位，标记本次不是跳3位
        return calculate(number.substring(2, number.length()), false);
    } else if (aux.equalsIgnoreCase("011")) {
        int res = 0;
        // 跳2位的分支正常累加
        res += calculate(number.substring(2, number.length()), false);
        // 跳3位的分支只有上一次不是跳3位时才累加
        if (!lastJumpIs3) {
            res += calculate(number.substring(3, number.length()), true);
        }
        return res;
    } else if (aux.equalsIgnoreCase("100")) {
        // 跳1位，标记本次不是跳3位
        return calculate(number.substring(1, number.length()), false);
    } else if (aux.equalsIgnoreCase("101")) {
        int res = 0;
        // 跳1位的分支正常累加
        res += calculate(number.substring(1, number.length()), false);
        // 跳3位的分支加限制
        if (!lastJumpIs3) {
            res += calculate(number.substring(3, number.length()), true);
        }
        return res;
    } else if (aux.equalsIgnoreCase("110")) {
        int res = 0;
        // 跳1位
        res += calculate(number.substring(1, number.length()), false);
        // 跳2位
        res += calculate(number.substring(2, number.length()), false);
        return res;
    } else if (aux.equalsIgnoreCase("111")) {
        int res = 0;
        // 跳1位
        res += calculate(number.substring(1, number.length()), false);
        // 跳2位
        res += calculate(number.substring(2, number.length()), false);
        // 跳3位的分支加限制
        if (!lastJumpIs3) {
            res += calculate(number.substring(3, number.length()), true);
        }
        return res;
    }
    return 0;
}

逻辑说明 #

你提到的1xx1xx1非法路径场景，在第一次跳3位到第四个1时，下一层递归会收到lastJumpIs3=true的标记，当再次遇到跳3位到第七个1的分支时，会直接跳过该分支，不会计入最终结果，完全符合新增规则要求。

内容的提问来源于stack exchange，提问作者vik440