LC-1033. 移动石子直到连续（分类讨论）

1033. 移动石子直到连续

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

输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。

分类讨论

https://leetcode.cn/problems/moving-stones-until-consecutive/solution/tan-xin-ji-suan-pythoner-xing-100-1033-y-gj78/

class Solution:
    """
    排序后，分类讨论
    1. 计算最大步数，最大步数：每次移动1个单位
        贪心：将a逐步移至b-1，c逐步移至b+1
        c - a - 2

    2. 计算最小步数，分类讨论
            情形            判断条件   最小步数
        1 abc连续           a+2==c       0
        2 ab连续 bc不连续    b==a+1       1
        3 ab不连续 bc连续    b==c-1       1
        4 ab差2 bc不连续[1,3,9] b==a+2    1
        5 ab不连续 bc差2[1,7,9] b==c-2    1
        6 其他 [1,5,8]                    2

    """
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        a, b, c = sorted([a, b, c])
        maxdis = c - a - 2
        mindis = inf
        if a + 2 == c:
            mindis = 0
        elif b == a+1 or b == c-1 or b == a+2 or b == c-2:
            mindis = 1
        else: mindis = 2
        return mindis, maxdis

合并成一句

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        a, b, c = sorted([a, b, c])
        return 0 if a + 2 == c \
                    else 1 if b in (a + 1, c - 1, a + 2, c - 2) \
                           else 2, c - a - 2

拓展：如果有一万颗石子，该怎么做？

1040. 移动石子直到连续 II

输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

输入：[100,101,104,102,103]
输出：[0,0]

分类讨论（下跳棋）

题解：https://leetcode.cn/problems/moving-stones-until-consecutive-ii/solution/tu-jie-xia-tiao-qi-pythonjavacgo-by-endl-r1eb/

class Solution {
    /**
    最大移动次数：
    	每次移动，让端点距离缩小1（下跳棋）
    最小移动次数：
    	端点可以直接移动到中间任意空位，直接一步到位
    */
    public int[] numMovesStonesII(int[] s) {
        Arrays.sort(s);
        int n = s.length;
        int e1 = s[n-2] - s[0] - n + 2; // 计算空位
        int e2 = s[n-1] - s[1] - n + 2;
        // 最大移动次数等于两种情况空位个数的最大值
        int maxMove = Math.max(e1, e2);
        if(e1 == 0 || e2 == 0){ // 特殊情况：没有空位
            return new int[]{Math.min(2, maxMove), maxMove};
        }
        int maxCnt = 0, left = 0;
        for(int right = 0; right < n; right++){ // 滑动窗口：枚举右端点
            while(s[right] - s[left] + 1 > n){ // 窗口大小大于 n
                left++;
            }
            maxCnt = Math.max(maxCnt, right - left + 1); // 维护窗口内的最大石子数
        }
        return new int[]{n - maxCnt, maxMove};
    }
}

python

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        n = len(stones)
        e1 = stones[-2] - stones[0] - n + 2
        e2 = stones[-1] - stones[1] - n + 2
        # 最大移动次数等于两种情况空位个数的最大值
        max_move = max(e1, e2)
        if e1 == 0 or e2 == 0: # 特殊情况。没有空位
            return [min(2, max_move), max_move]
        max_cnt = left = 0
        for right, sr in enumerate(stones):  # 滑动窗口：枚举右端点所在石子
            while sr - stones[left] + 1 > n:  # 窗口长度大于 n
                left += 1  # 缩小窗口长度
            max_cnt = max(max_cnt, right - left + 1)  # 维护窗口内的最大石子数
        return [n - max_cnt, max_move]

0x3f

问: 你是如何想到本题的做法的? 是否有一些通用的思考方式?

答:个人觉得这题有点构造的味道 (想算出答案，要大致知道怎么移动石子) 。对于构造题，通常是先从最基本的情况开始思考，比如本题就是从 n = 3 开始思考。在纸上多画一画，比较不同的移动方案，猜想出一个大致的结论。接着思考 n = 4,5,…的情况，验证/修正你的结论。这就是 [从特殊到一般]。如果你想做更多的构造题，可以去 Codeforces 搜索 tag: constructive algorithms。