arrays - 根据给定条件遍历数组元素的算法

Question

我正在练习解决this problem ，并且已经通过了 5 个测试用例，但是一些测试用例失败了我无法弄清楚我的算法中有什么问题。尽管我尝试使用失败测试用例中的一些测试数据，但其中大部分都是正确的，但我相信有些是不正确的，因此导致我的算法失败。因此，如果有人可以深入了解实现此算法的正确方法，那将非常有帮助，或者我在实现中哪里出错了。

我的算法:

    1. Index for the move is at index '0' of string (say moving index)
    2. Loop over the string starting with index '1' of string:

       2.1. check if (moving index + leap) can outrun the array:

       2.2. If not then, check whether the character is 1 or 0 :

           2.2.1 Check for the number of '1's that are continuous, if they exceed the leap value then return false (as anyway we will not be able to jump).

           2.2.2 If its 0, then check whether its a zero after continuous '1's.

              If not so, continue moving forward one step at a time.

              If so, first try to skip over those continuous '1's by checking whether (moving index + leap) is allowed or not as per the rule.

              If not allowed, check in a while loop till what point we can move backwards one step at a time to get (moving index + leap) to satisfy.

              If not possible, return false.

我不知道这是否是解决此类问题的有效方法，非常感谢任何其他可能的方法。

代码:

import java.util.*;

public class Solution {

    public static int leapStep(int index,int leap,int len,int[] game){
        if(game[index+leap]==0){
            index += leap;
        }
        return index;
    }

    public static boolean canWin(int leap, int[] game) {
        int index = 0;
        int len = game.length;
        int consecutiveLength=0;
        for(int i=1;i<len;){
            if(index+leap>len-1){
                return true;
            }
            if(game[i]==1){
                consecutiveLength++;
                if(consecutiveLength>=leap){
                    return false;
                }
                i++;
            }else{
                if(consecutiveLength==0){
                    index =i;
                    i++;
                }else{
                    if(index+leap<=len-1){
                        int tryLeap = leapStep(index,leap,len,game);
                        if(index < tryLeap){
                            index = tryLeap;
                            tryLeap =0;
                            i = index+1;
                        }else if(index>0 && game[index-1]==0 ){
                            boolean notViable = false;
                            while(index>0){
                                if(game[index-1]!=0)
                                    return false;
                                index -= 1;
                                i = index+1;
                                tryLeap = leapStep(index,leap,len,game);
                                if(index<tryLeap){
                                    index = tryLeap;
                                    i = index+1;
                                    tryLeap=0;
                                    notViable = false;
                                    break;
                                }
                                else{
                                    notViable = true;
                                }
                            }
                            if(notViable){
                                return false;
                            }
                        }else{
                            return false;
                        }
                    }
                    consecutiveLength=0;
                }
            }
        }//closing for
         return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        while (q-- > 0) {
            int n = scan.nextInt();
            int leap = scan.nextInt();

            int[] game = new int[n];
            for (int i = 0; i < n; i++) {
                game[i] = scan.nextInt();
            }

            System.out.println( (canWin(leap, game)) ? "YES" : "NO" );
        }
        scan.close();
    }
}

Answer 1

对我来说，更好的方法是递归地解决这个问题(它通过了所有测试):

public static boolean canWin(int[] array, int index, int leap) {
    // the only case when we lose
    if (index < 0 || array[index] > 0) {
        return false;
    } 

    // if you're standing in the last entry or (index + leap) >= array.length then win
    if ((index >= array.length - 1) || ((index + leap) >= array.length)) {
        return true;
    }

    // mark it as visited so that not to iterate over it again
    array[index] = 1;
    // check all 3 conditions then recursively again
    return canWin(array, index + 1, leap) || canWin(array, index - 1, leap) || canWin(array, index + leap, leap);
}

在下面的输入中显示了几对线。每对的第一个元素代表 leap，第二个元素代表一个数组。

输入:

3

0 0 0 0 0

5

0 0 0 1 1 1

3

0 0 1 1 1 0

1

0 1 0

输出:

true

true

false

false

解释:

假设您当前的位置是index。

1. 如果它为负数或数组值大于0，则游戏失败。如果它是最后一个位置或 index + leap 至少达到数组的长度，那么根据定义赢得比赛。
2. 否则，从这里唯一可能的移动可能是 index - 1 或 index + 1 或 index + leap。因此，您对后面的每个索引重复步骤 1，并对结果进行 OR，因为找到一条路径就足够了。不要忘记将单元格的值设置为 1，因为第二次访问它没有意义 - 我们不想一遍又一遍地重复相同的 Action 并崩溃。