LeetCode 1306. 跳跃游戏 III C#
原题链接
中等
作者:
hpstory
,
2022-08-02 16:39:53
,
所有人可见
,
阅读 166
C# 递归代码
public class Solution {
public bool CanReach(int[] arr, int start) {
return Reach(arr, start, new bool[arr.Length]);
}
private bool Reach(int[] arr, int start, bool[] used){
if (start < 0 || start >= arr.Length || used[start]) return false;
if (arr[start] == 0) return true;
used[start] = true;
bool left = Reach(arr, start - arr[start], used);
bool right = Reach(arr, start + arr[start], used);
return left || right;
}
}
C# 迭代代码
public class Solution {
public bool CanReach(int[] arr, int start) {
int n = arr.Length;
bool[] used = new bool[n];
Queue<int> queue = new Queue<int>();
queue.Enqueue(start);
while (queue.Count > 0){
int current = queue.Dequeue();
if (arr[current] == 0) return true;
if ((current + arr[current]) < n && !used[current + arr[current]]){
queue.Enqueue(current + arr[current]);
used[current + arr[current]] = true;
}
if ((current - arr[current]) >= 0 && !used[current - arr[current]]){
queue.Enqueue(current - arr[current]);
used[current - arr[current]] = true;
}
}
return false;
}
}