全屏类网站建设,公司入口网站app,深圳市建设网站公司,四川住房和城乡建设厅网站官网题目链接 Leetcode.1033 移动石子直到连续 Rating #xff1a; 1421 题目描述
三枚石子放置在数轴上#xff0c;位置分别为 a#xff0c;b#xff0c;c。
每一回合#xff0c;你可以从两端之一拿起一枚石子#xff08;位置最大或最小#xff09;#xff0c;并将其放入…题目链接 Leetcode.1033 移动石子直到连续 Rating 1421 题目描述
三枚石子放置在数轴上位置分别为 abc。
每一回合你可以从两端之一拿起一枚石子位置最大或最小并将其放入两端之间的任一空闲位置。形式上假设这三枚石子当前分别位于位置 x, y, z且 xyzx y zxyz。那么就可以从位置 x或者是位置 z拿起一枚石子并将该石子移动到某一整数位置 k处其中 xkzx k zxkz 且 k≠yk \neq yky。
当你无法进行任何移动时即这些石子的位置连续时游戏结束。
要使游戏结束你可以执行的最小和最大移动次数分别是多少 以长度为 2 的数组形式返回答案answer [minimum_moves, maximum_moves]
示例 1 输入a 1, b 2, c 5 输出[1, 2] 解释将石子从 5 移动到 4 再移动到 3或者我们可以直接将石子移动到 3。 示例 2 输入a 4, b 3, c 2 输出[0, 0] 解释我们无法进行任何移动。 提示
1a1001 a 1001a1001b1001 b 1001b1001c1001 c 1001c100a!b,b!c,c!aa ! b, b ! c, c ! aa!b,b!c,c!a
解法分类讨论
先将 a,b,ca,b,ca,b,c按从小到大的顺序排序。
最小值
当 b−a1b - a 1b−a1 and c−a1c - a 1c−a1时不需要移动故答案为 0当 b−a≤2b - a \leq 2b−a≤2 or c−a≤2c - a \leq 2c−a≤2时需要移动一次故答案为 1否则需要移动两次故答案为 2
最大值c−a−2c - a - 2c−a−2
时间复杂度O(1)O(1)O(1)
C代码
class Solution {
public:vectorint numMovesStones(int a, int b, int c) {vectorint arr{a,b,c};sort(arr.begin(),arr.end()); int ans;if(arr[1] - arr[0] 1 arr[2] - arr[1] 1) ans 0;else if(arr[1] - arr[0] 2 || arr[2] - arr[1] 2) ans 1;else ans 2;return {ans,arr[2] - arr[0] - 2};}
};
