RefDash_JumpToZero [source code]

public class RefDash_JumpToZero {
static
/****************************************************************************/
class Solution {
    boolean search (int[] nums, int start_index) {
        int N = nums.length;
        int[] can_zero = new int[N];
        dfs (nums, start_index, can_zero);
        return can_zero[start_index] == 1;
    }

    int dfs (int[] nums, int idx, int[] can_zero) {
        if (nums[idx] == 0) {
            can_zero[idx] = 1;
            return 1;
        }
        int res = 0;
        int step = nums[idx];
        int left_neighbor = idx - step;
        can_zero[idx] = -1;
        if (left_neighbor >= 0) {
            if (can_zero[left_neighbor] != -1 && 
                (can_zero[left_neighbor] == 1 || 
                dfs (nums, left_neighbor, can_zero) == 1))
                res = 1;
        }
        int right_neighbor = idx + step;
        if (res == 0 && right_neighbor < nums.length) {
            if (can_zero[right_neighbor] != -1 && 
                (can_zero[right_neighbor] == 1 || 
                dfs (nums, right_neighbor, can_zero) == 1))
                res = 1;
        }
        can_zero[idx] = res;
        return res;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        RefDash_JumpToZero.Solution tester = new RefDash_JumpToZero.Solution();
    }
}

题目本身比较简单, 给一个数组, 全都是非负数, 然后有不少个0, 然后给你一个start index, 然后判断能不能从这个start跳到一个是0的位置; 跳跃的方法是在当前位置, 比如nums[i] = step, 那么就是可以向左走step, 或者可以向右走step, 只要不出界就行了;

其实是一个很简单的DFS题目, 但是一开始想的很复杂, UF, DP的思路都想过, 最后面试官稍微给了提示才想起来直接DFS就行了; 而且最后我上面的答案其实是太复杂了; 这个问题其实非常简单, 直接维护一个visited, 然后从start开始走一个DFS就行了; 我上面的做法最后把整个graph全都标记了, 这个是浪费的. 当然, 假如跟你说, 最后会对很多start进行query, 那么这个思路或许还行.

最后也是被批评这个代码实际上是太复杂了. 真正实际的代码是10行之内是完全可以解决的.

Problem Description