leetcode 1306. Jump Game III [Medium]

2021-12-09 159 words One minute

Contents

題目敘述

給定一非負整數陣列 arr，你一開始位於位置 start。當你位於索引值 i 時，你可以跳到 i + arr[i] 或是 i - arr[i]，判斷你是否可以抵達任何位置其陣列值為 0 。

注意你在任意時刻都不能跳出陣列。

限制： 1 ≦ arr.length ≦ 5 × 10 ^ 4 0 ≦ arr[i] < arr.length 0 ≦ start < arr.length

解題紀錄

簡單的 dfs 解決，用一個 vector<bool> 去紀錄該 index 是否走過，避免發生無限迴圈的情況，如果 record[index] == true 代表已經走過，直接返回 false，記得還要判斷這次 jump 之後有沒有跳出迴圈的範圍。

static const auto fastIO = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int len;
    vector<bool> record;
        
    bool canReach(vector<int> &arr, int start) {
        len = arr.size();
        record.resize(len);
        std::fill(record.begin(), record.end(), false);
        return dfs(arr, start);
    }
    
    bool dfs(vector<int> &arr, int index) {
        if (index < 0 || index > len || record[index]) 
            return false;
        if (arr[index] == 0) 
            return true;
        
        record[index] = true;
        return dfs(arr, index - arr[index]) || dfs(arr, index + arr[index]);
    }
};
// Runtime: 16 ms, faster than 100.00% of C++ online submissions for Jump Game III.
// Memory Usage: 30.9 MB, less than 96.35% of C++ online submissions for Jump Game III.