LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 记录每个位置可以到达的最大右边界，如果当前位置超出最大右边界，则无法跳到当前位置，也就无法到达终点（如果能到达终点，则终点前的每个位置都应该可到达）

class Solution {
 public:
  bool canJump(vector<int>& nums) {
    int mx = 0;
    for (int i = 0; i < nums.size(); ++i) {
      if (i > mx) {
        return false;
      }
      mx = max(mx, i + nums[i]);
    }
    return true;
  }
};

• 动态规划，dp[i] 表示到达 i 位置时还能跳的最大距离

class Solution {
 public:
  bool canJump(vector<int>& nums) {
    if (nums.empty()) {
      return false;
    }
    if (nums.size() == 1 && nums[0] >= 0) {
      return true;
    }
    vector<int> dp(nums.size());
    dp[0] = nums[0];
    if (dp[0] == 0) {
      return false;
    }
    for (int i = 1; i < dp.size(); ++i) {
      dp[i] = max(dp[i - 1] - 1, nums[i - 1]);
      if (dp[i] == 0) {
        return false;
      }
    }
    return true;
  }
};