力扣 754 到达终点数字 思路讲解
题意
- 从i=1开始，到i=target，所需要的最小移动次数。
- 每次移动可以向左也可以向右
- 移动的距离遵守 1,2,3,4,5,…n
思路
- 向左移动x可以等效成向右移动-x，左右移动等效成向右移动适当加-号
- 分情况讨论
- 一直往右移动，刚好到达 target,此时次数最少为n
- 一直往右移动，超过target距离为d
d为偶数
即将d/2反向，即可到达target, 最少为 n+1。证明：d/2一定在[1, n]中。
显而易见：d 的最大值为，从n-1跳了n部，即 d = n-1(偶数) (n-1)/2,一定在[1, n]中。最小次数为 n
d为奇数
由于反向操作只能将 s 减少偶数，无法处理相距奇数的情况，必须多走一两步，将相距变为偶数，才能处理。 将一个数num反向，则造成的结果为sum-2*num
1.向往回走一步n+1,在往前走一步n+2,n+2-(n+1)=1, 此时d+1一定为偶数，回到上述情况。最小次数为n+2
2.往前继续走一步,n+1, 如果n+1+d<2n为偶数，则将[n+1+d]/2改为负数，最小次数为n+1
3.往前继续一步，n+1,如果 n+1+d<2n为奇数。则继续往前一步,n+1+d+n+2必为偶数,
n+2 <= (2n+3+d)/2 <= 1.5n+1,当d=1,和d=n-1时成立，最小次数为n+2
第1种情况和第3种情况是同一种情况。
图来至于灵茶灵神题解