问题描述 小F正在进行一个 AB 实验,需要从整数位置 x 移动到整数位置 y。每一步可以将当前位置增加或减少,且每步的增加或减少的值必须是连续的整数(即每步的移动范围是上一步的 -1,+0 或
+1)。首末两步的步长必须是 1。求从 x 到 y 的最少步数。
输入描述 输入包含两个整数 x 和 y,表示起始位置和目标位置。
输出描述 输出从 x 到 y 所需的最小步数。
测试样例 样例1: 输入:x_position = 12, y_position = 6 输出:4 样例2: 输入:x_position = 34, y_position = 45 输出:6 样例3: 输入:x_position = 50,
y_position = 30 输出:8 样例4: 输入:x_position = 0, y_position = 0 输出:0
看到这题的第一反应是贪心序列先增后减,但是介于可以重复步数(不仅仅是+1,-1,还可以为0),我就在纠结各种情况,发现并不能有效的分类重复步数的位置和个数(因为就是可以随便重)。随后我参考了文章1和文章2,他们均很巧妙地先关注1.2…k-1.k.k-1…2.1=k^2,再根据差值选择重复部分。他们用了枚举和while,但其实通过sqrt函数可以使整个过程很简单。
对于剩余距离m,一定有m<(k+1)^2 - k^2=2k+1,所以m最大是2k,补两个k即可。
所以当0<m<=k,补一个数即可;当k<m<=2k,补两个数即可。代码如下:
public static int solution(int xPosition, int yPosition) {int distance = Math.abs(xPosition - yPosition);int k = (int) Math.floor(Math.sqrt(distance));//floor是向下取整,ceil是向上取整if (k * k == distance) {return 2 * k - 1;//不补}else{int left = distance - k*k;if(left > k){return 2*k+1;//补两个数}else{return 2*k;//补一个数}}}