Day 30: Greedy Method

这是什麽

贪婪法，精神在於有限的条件下，每一步都采取对於当下最有利的选择（短视近利），使状态更接近答案。

举现实的例子，股票涨就买、跌就卖的散户心态，可以称作贪婪法。

刷题：55. Jump Game

连结

题目

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 3 * 10^4
• 0 <= nums[i][j] <= 10^5

思考

有趣的地方在於，阵列从 0 开始计算，刚好可以看作是 起点。再来，阵列的 index 可以当作是到达该格需要的步数，而每一格的 index 与 可跳的数量，刚好可以看作是当下的最大步数。
整理上述内容，拿 Example 1 与 2 制作出列表：

Example 1
index:       |0|1|2|3|4|
item:        |2|3|1|1|4|
maxJump:     |2|4|3|4|8|
Jump>Index?  |T|T|T|T|T|
每格都是 T，有能力跳到最後一格

Example 2
index:       |0|1|2|3|4|
item:        |3|2|1|0|4|
maxJump:     |3|3|3|3|8|
Jump>Index?  |T|T|T|F|T|
出现 F，没有能力跳到最後一格

解题

JS

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const canJump = (nums) => {
  const n = nums.length;

  if (n === 0) {
    return false;
  } else if (n === 1) {
    return true;
  }

  let maxJump = 0;

  for (let i = 0; i < n; i++) {
    if (i > maxJump) {
      return false;
    }

    maxJump = Math.max(maxJump, i + nums[i]);
  }

  return true;
};

Java

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;

        if (n == 0) {
            return false;
        } else if (n == 1) {
            return true;
        }

        int maxJump = 0;

        for (int i = 0; i < n; i++) {
            if (i > maxJump) {
                return false;
            }

            maxJump = Math.max(maxJump, i + nums[i]);
        }

        return true;
    }
}

C

int max(int x, int y)
{
    if (x > y)
    {
        return x;
    }

    return y;
}

bool canJump(int *nums, int numsSize)
{

    if (numsSize == 0)
    {
        return false;
    }
    else if (numsSize == 1)
    {
        return true;
    }

    int maxJump = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (i > maxJump)
        {
            return false;
        }

        maxJump = max(maxJump, i + nums[i]);
    }

    return true;
}

看法

这题给我的感觉是小试身手，只要不断比较是否大於 maxJump 即可达到答案。

结论

其实想想，贪婪法反应真实世界的情况，不少决策遵循短期可有效果的做法，不管後果如何，强势地做下去就对了。
一想到不管後果就觉得可怕，如果放任不管，硬体资源会被用掉多少？似乎又回到本系列文最初的问题，时间与空间的取舍。套用当时的看法，永远是情况调整，没有最佳解，只有最适解。