可达性

状态转移可达

55. 跳跃游戏 mid

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

不断更新可触达的范围

class Solution {
    public boolean canJump(int[] nums) {
        int reach = nums[0];
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (reach < i) return false;
            reach = Math.max(reach, i + nums[i]);
        }
        return true;
    }
}

97. 交错字符串 mid

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

解法 DP

将 s1, s2 拉成 2 维的, 找一条通路到右下角

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
        if (l1 + l2 != l3) return false;
        // 字符串通常需要给 "" 留位置
        boolean[][] dp = new boolean[l1 + 1][l2 + 1];
        dp[0][0] = true;
        for (int i = 0; i <= l1; i++) {
            for (int j = 0; j <= l2; j++) {
                if (i > 0) dp[i][j] |= (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
                if (j > 0) dp[i][j] |= (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[l1][l2];
    }
}

134. 加油站 mid

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i]升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i]升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

解法 1

假设 A 点出发, C 点不可达, 那么 A=>C 之间的点都可达, 都可达意味着到达之前都带着油
所以, 从 A=>C 之间的点出发都不行
这时, 从 C 点重新出发, 尝试

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // 从i出发
        for (int i = 0; i < n; ) {
            int cnt = 0;
            for (int sum = 0; cnt < n; cnt++) {
                int j = (i + cnt) % n;
                sum += gas[j] - cost[j];
                if (sum < 0) break;
            }
            if (cnt == n) return i;
            i += cnt + 1;
        }
        return -1;
    }
}

解法 2

sum(净油耗) >= 0 才能过
最低点要尽可能高, 也就是进入最低点的时候有积累, 也就是从最低点的下一个位置开始

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int min = Integer.MAX_VALUE;
        int res = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += gas[i] - cost[i];
            if (min >= sum) {
                min = sum;
                res = i;
            }
        }
        if (sum >= 0) return (res + 1) % n;
        return -1;
    }
}