懒人手机网站模板济南新闻头条最新事件

题目链接

LeetCode-1033. 移动石子直到连续

题目描述

题解

题解一（Java）

作者：@仲景
这题目挺难懂的，得画画图才能更好的理解
这也是LeetCode的尿性，习惯了，非得整这种别人看不懂的鸟语
你可以这样理解，给你一个假设长度为无穷的数组，其中有3个下标的位置赋值成了1，其余的都是0
问你，每次只能从头尾选择移动1次，最多多少次能让着3个1排到一起，最少多少次能让着3个1排到一起
这样也许会更好懂一些
先说最多的情况，最多的情况就是左边的1每次1步，一直移动到中间的1的前一个索引位置，右边的1每次1步，一直移动到中间的1的后一个索引位置
首先左右两个1的距离应该是 c-a-1，因为中间还有一个b，所以还要-1，那么最多的公式就是c-a-2
那么最少情况呢，可以分成好多种
情况一：abc本身索引就是连续的，不需要动
情况二：ab连续或者bc连续，只需要把另外一个挪过来就可以了，移动1次
情况三：abc之间有空隙，但是空隙只有1个，那么随便挪动另外一个过来，最少也是移动1次
情况四：abc之间有空隙，但是空隙很多，所有a移动到b的前一个位置需要1次，c移动到b的后一个位置需要1次，那么最少也得2次
所有情况就已经讲完了，下面的图和情况1234不是一一对应的，只是用来证明情况1234的图

class Solution {public int[] numMovesStones(int a, int b, int c) {int[] arr = {a, b, c};Arrays.sort(arr);a = arr[0];b = arr[1];c = arr[2];int min = 0;// 如果c和a相差2，那abc就是连续的，不需要移动// 只有c和a之间有超过1个格子的时候才需要移动if (c - a > 2) {if (b - a <= 2 || c - b <= 2) {// 如果abc之中有任何两个元素紧挨着或者中间只有一个格子的时候，最少只需要1次就够了min = 1;} else {// 如果abc之中没有任何一个格子紧挨或者相差1个格子，那么最少需要2次min = 2;}}// 最多就是c-a-2return new int[]{min, c - a - 2};}
}