山东金泰建设有限公司网站,论坛网站建设开源工具,北京比较大的软件开发公司,微信小程序设计软件移动石子直到连续【LC1033】 三枚石子放置在数轴上#xff0c;位置分别为 a#xff0c;b#xff0c;c。 每一回合#xff0c;你可以从两端之一拿起一枚石子#xff08;位置最大或最小#xff09;#xff0c;并将其放入两端之间的任一空闲位置。形式上#xff0c;假设这…移动石子直到连续【LC1033】 三枚石子放置在数轴上位置分别为 abc。 每一回合你可以从两端之一拿起一枚石子位置最大或最小并将其放入两端之间的任一空闲位置。形式上假设这三枚石子当前分别位于位置 x, y, z 且 x y z。那么就可以从位置 x 或者是位置 z 拿起一枚石子并将该石子移动到某一整数位置 k 处其中 x k z 且 k ! y。 当你无法进行任何移动时即这些石子的位置连续时游戏结束。 要使游戏结束你可以执行的最小和最大移动次数分别是多少 以长度为 2 的数组形式返回答案answer [minimum_moves, maximum_moves] 要赶紧回归学习状态 思路 排序后分类讨论 最大移动次数【贪心】 每次向中间十字移动一格使移动次数最大 最小移动次数【分情况讨论】 由于可以移动至任意位置因此最小次数最多为2 如果三颗石子已经连续那么不需要移动如果三颗石子两颗连续 那么只需移动1次如果两颗石子距离为1那么只需移动1次否则移动2次 实现 class Solution {public int[] numMovesStones(int a, int b, int c) {int[] stones {a, b, c};Arrays.sort(stones);int[] res new int[2];res[1] stones[2] - stones[0] - 2;// 最大// 最小// 已经连续 0次// 两颗连续 1次// 两颗相邻为1 1次// 否则 移动2次if(stones[2] - stones[0] 2){res[0] 0;}else if (stones[2] - stones[1] 2 || stones[1] - stones[0] 2){res[0] 1;}else {res[0] 2;}return res;}}复杂度 时间复杂度 O ( 1 ) O(1) O(1)空间复杂度 O ( 1 ) O(1) O(1)
