Java计算楼梯的最大步数并跳过楼梯

Question

我最近接受了一个实习职位的面试，其中一个问题与此类似：

输入：n表示动作次数，k表示您无法踩到的楼梯

问题：杰克有n个动作要达到最大步数，但不能踩第k阶。对于每一个动作，杰克都可以停留在当前位置，也可以跳至第i步（如果他正在进行第i个动作），并且一直持续到完成第n个动作为止。

输出：n次动作内可达到的最大楼梯

它通过Hackerrank（与面试官在一起）进行了测试，在8个测试用例中，我仅通过了3个，其余时间超时

这是我的解决方案，它是即时进行编码的，我无法对其进行优化，并且想知道是否存在更加优化的解决方案：

static int maxStep(int n, int k) {
    int result = 0;
    if (n == 0) {
        return result;
    } 
    return maxStepHelper(n,0, k, result);
}

static int maxStepHelper(int n,int i,int k,int result) {
    // At n+1 steps, previous steps' results are recorded and this is mainly used to stop and show previous results
    if (i == n+1) {
        return result;
    }
    int nextStep = i + result;
    if (nextStep == k) {
       return maxStepHelper(n,i+1,k,result);
    } 
    return Math.max(maxStepHelper(n,i+1,k,result),maxStepHelper(n,i+1,k,result+i));
}

请注意，我使用了递归方法，可能没有帮助

Answer 1

这里不需要递归或动态编程。这只是一点数学。

如果您i在每个转弯处都采取(n * (n+1)) / 2步骤，则将采取步骤。k如果k是该方程式的整数解，您将进入-th步骤：

k = (n * (n+1)) / 2

重新排列：

0 = n^2 + n - 2*k

这是一个二次方程式n：

n = (-1 +/- sqrt(1 + 4*1*2*k)) / 2

如果sqrt(1 + 8*k)是奇数整数，则仅具有整数解。

所以：

• 如果sqrt(1 + 8*k)为奇数整数，则将进入k第-步。因此，只要不迈出第一步，您就会错过k1。最大步数是(n * (n+1)) / 2 - 1。

  这是您要错过的第一个动作，因为1是您可以缩短的最小步骤数。如果您错过第二个动作，则比最大动作短2步。

• 否则，只需i对每个操作采取步骤，最大步骤数为(n * (n+1)) / 2