403. 青蛙过河¶

难度：困难

一只青蛙想要过河。假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号升序表示），请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。

开始时，青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。另请注意，青蛙只能向前方（终点的方向）跳跃。

示例 1：

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

示例 2：

输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

提示：

2 <= stones.length <= 2000
0 <= stones[i] <= 2^31 - 1
stones[0] == 0

Reference

题解¶

根据题意，在任何状态，青蛙都最多只有三种状态可以选择，因此可以使用深度优先搜索查找所有的状态。假设青蛙跳了$k$格达到当前节点

当青蛙达到最后一个节点时返回true，
当青蛙到达一个节点时，检查前面的$k-1, k, k+1$个单元格是否有石子，
当青蛙无法继续向前移动时返回false并进行回溯。

bool dfs(int *stones, int stonesSize, int currentPos, int lastStep)
{
    if (currentPos == stonesSize - 1)
        return true;
    int i = 0, j = 0, cur_id = stones[currentPos];
    bool ret = false;
    for (i = -1; i < 2; i++)
    {
        if (lastStep + i <= 0)
            continue;
        for (j = currentPos + 1; !ret && j < stonesSize && stones[j] <= cur_id + lastStep + i; j++)
            if (stones[j] == cur_id + lastStep + i)
                ret = ret || dfs(stones, stonesSize, j, lastStep + i);
    }
    return ret;
}

bool canCross(int* stones, int stonesSize){
    return dfs(stones, stonesSize, 0, 0);
}

如上dfs算法会对所有的分支进行遍历，直到找出最终结果。会造成大量时间的浪费。构造如下输入数据即可使该算法超时：

[0,1,2,3,4,5,...,998, +infty]

其中+infty指充分大的整数。

因此，我们需要加入一个数组，用于记忆不同位置的到终点的可达性：

bool dfs(int *stones, int *buf, int stonesSize, int currentPos, int lastStep)
{
    if (buf[currentPos] != -1)
        return buf[currentPos];
    if (currentPos == stonesSize - 1)
        return true;
    int i = 0, j = 0, cur_id = stones[currentPos];
    bool ret = false;
    for (i = -1; i < 2; i++)
    {
        if (lastStep + i <= 0)
            continue;
        for (j = currentPos + 1; !ret && j < stonesSize && stones[j] <= cur_id + lastStep + i; j++)
            if (stones[j] == cur_id + lastStep + i)
                ret = ret || dfs(stones, buf, stonesSize, j, lastStep + i);
    }
    buf[currentPos] = ret;
    return ret;
}

bool canCross(int* stones, int stonesSize){
    int *buf = (int *)malloc(sizeof(int) * stonesSize);
    memset(buf, 0xff, sizeof(int) * stonesSize);
    return dfs(stones, buf, stonesSize, 0, 0);
}

但这个算法只能通过一部分测例，部分测例无法通过（如示例1，[0,1,3,5,6,8,12,17]）。我们查看一下青蛙在节点间跳跃的情况：

$jump_sequence$

当算法走到节点5时，首先会尝试路径5->6->8，但此时在节点8青蛙最多只能跳3步，从而被记忆化标记为不可到达终点，但实际上如果直接采取路径5->8则可以从节点8跳到节点12。即某个位置的终点可达性受到上一步跳动步数的影响，我们在进行记忆化时需要记忆每个节点在每个跳动步数情况下的可达性。

如下使用二分查找代替遍历，并使用拉链法存储每个节点的可达性，链表节点中存储相应的跳动步数。

struct BufNode
{
    int success;
    int lastStep;
    struct BufNode *next;
};

struct BufNode *getNode(int success, int lastStep, struct BufNode *next)
{
    struct BufNode *ret = (struct BufNode *)malloc(sizeof(struct BufNode));
    ret->success = success;
    ret->lastStep = lastStep;
    ret->next = next;
    return ret;
}

bool check(struct BufNode *buf, int lastStep, int *success)
{
    if (buf == NULL)
        return NULL;
    if (buf->lastStep == lastStep)
    {
        if (success)
            *success = buf->success;
        return true;
    }
    return check(buf->next, lastStep, success);
}

int bSearch(int *stones, int lo, int hi, int target)
{
    int mid;
    while (lo < hi)
    {
        mid = (lo + hi) >> 1;
        if (target < stones[mid])
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo - 1;
}

bool dfs(int *stones, struct BufNode **buf, int stonesSize, int currentPos, int lastStep)
{
    int success = false;
    if (check(buf[currentPos], lastStep, &success))
        return success;
    if (currentPos == stonesSize - 1)
        return true;
    int i = 0, j = 0, cur_id = stones[currentPos];
    bool ret = false;
    for (i = -1; i < 2; i++)
    {
        if (lastStep + i <= 0)
            continue;
        j = bSearch(stones, currentPos + 1, stonesSize, cur_id + lastStep + i);
        if (stones[j] == cur_id + lastStep + i)
            ret = ret || dfs(stones, buf, stonesSize, j, lastStep + i);
    }
    buf[currentPos] = getNode(ret, lastStep, buf[currentPos]);
    return ret;
}

bool canCross(int* stones, int stonesSize){
    struct BufNode **buf = (struct BufNode **)malloc(sizeof(struct BufNode *) * stonesSize);
    memset(buf, 0, sizeof(struct BufNode *) * stonesSize);
    return dfs(stones, buf, stonesSize, 0, 0);
}

403. 青蛙过河¶

题解¶

评论