Keshawn_lu's Blog

Leetcode 1033. 移动石子直到连续

贪心
字数统计: 491阅读时长: 2 min
2023/04/30 Share

题目简介：

三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

示例 1：

1
2
3
输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。

提示：

  1. 1 <= a <= 100
  2. 1 <= b <= 100
  3. 1 <= c <= 100
  4. a != b, b != c, c != a

思路：

首先最大次数：就是将两端的石子一步一步往中间石子靠近即可。

最小次数分为三种情况：

  • 若本身就是连续的，那就是0
  • 若三个石子之间有两个石子中间空了一格，那么我们只需将另外的那个石子放进这个空格即可，最小次数为1
  • 其余情况，都是将两端石子放在中间石子的两侧，各需要一次，总共2次。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {

        vector<int> nums = {a, b, c};

        sort(nums.begin(), nums.end());

        int max_sum = (nums[2] - nums[1] - 1) + (nums[1] - nums[0] - 1);

        int min_sum = 0;

        if(nums[2] == nums[1] + 2 || nums[1] == nums[0] + 2)
            min_sum = 1;
        else{

            if(nums[2] != nums[1] + 1)
                min_sum += 1;
            if(nums[0] != nums[1] - 1)
                min_sum += 1;
        }

        return {min_sum, max_sum};
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网