2021 05 27

本周的五道 Leetcode 分别是：

• 1217 玩筹码
• 55 跳跃游戏
• 62 不同路径
• 121 买卖股票的最佳时机
• 279 完全平方数

1217 玩筹码

题目描述

数轴上放置了一些筹码，每个筹码的 位置 存在数组 chips 当中。

你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

• 将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
• 将第 i 个筹码向左或者右移动 1 个单位，代价为 1。

最开始的时候，同一位置上也可能放着两个或者更多的筹码。

返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

• 示例 1：

输入：chips = [1,2,3]
输出：1
解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
复制代码

• 示例 2：

输入：chips = [2,2,2,3,3]
输出：2
解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。
复制代码

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/mi…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一 贪心思想

贪心的基本思想是尽量选择局部最优解，也就是每次尽量按照代价 0 移动筹码，如果没有代价为 0 的移动，再考虑代价为 1。

由题意，我们可以知道 chips 存储的是筹码的位置，

• 奇数位置到奇数位置 或者 偶数位置到偶数位置 的代价为 0
• 奇数位置到偶数位置 或者 偶数位置到奇数位置 的代价为 1

所以先将所有的奇数位筹码移动到其中的某一个位置，再将所有偶数位筹码移动到其中的某一个位置，此时代价为 0。

由于最后的两个位置一定是奇数位和偶数位，所以移动的代价都是 1，选择筹码数更小的哪个位置进行移动，移动的代价就是 筹码数 x 1。

以上移动奇数位和偶数位的过程也可以表示为 计算奇数（偶数）个数 。

// 贪心思想
class Solution {
    public int minCostToMoveChips(int[] position) {
        int even = 0;   // 偶数位置个数
        int odd = 0;    // 奇数位置个数
        for(int i = 0; i < position.length; ++i){
            if(position[i] % 2 == 0){
                even++;
            }else {
                odd++;
            }
        }
        return Math.min(even,odd);
    }
}
复制代码

55 跳跃游戏

题目描述

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

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

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

 – 示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
复制代码

• 示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
复制代码

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/ju…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一 动态规划

如果当前位于位置 i，能够到达最后一个下标的条件为 i 到最后的距离 小于等于 nums[i]，即 nums[i] + i <= nums.length，这就可以作为判断是否返回 true 的条件。

用 dp[i] 表示到达位置 i 后，下一跳能够到达的最远的位置，则有