算法题 到达终点数字

到达终点数字

问题描述

在一根无限长的数轴上，你站在 0 的位置。终点在target的位置。

你可以进行移动。每次移动，你可以向左或向右移动，第n次移动（从 1 开始），可以走n步。

返回到达终点需要的最小移动次数。

注意：target可能是负数，但由于数轴对称性，我们可以只考虑正数情况。

示例：

输入: target = 3 输出: 2 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 3 。

输入: target = 2 输出: 3 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 -1 。 第三次移动，从 -1 到 2 。

算法思路

核心：

1. 对称性：target和-target的答案相同，所以可以只考虑target >= 0的情况
2. 累加和：前k步的最大可达距离是S = 1 + 2 + ... + k = k(k+1)/2
3. 调整方向：如果超过了目标点，可以通过将某些步骤改为向左走来调整位置

代码实现

方法一：逐步累加

classSolution{/** * 计算到达目标位置所需的最小移动次数 * * @param target 目标位置（可以是负数） * @return 最小移动次数 */publicintreachNumber(inttarget){// 利用对称性，只考虑非负目标target=Math.abs(target);intstep=0;// 当前移动次数intsum=0;// 当前累计移动距离（全部向右）// 逐步增加步数，直到满足条件while(sum<target||(sum-target)%2!=0){step++;sum+=step;}returnstep;}}

方法二：数学

classSolution{/** * 使用数学直接计算最小步数 * * @param target 目标位置 * @return 最小移动次数 */publicintreachNumber(inttarget){target=Math.abs(target);// 使用求根公式估算最小的k，使得 k(k+1)/2 >= target// k^2 + k - 2*target >= 0// k >= (-1 + sqrt(1 + 8*target)) / 2intk=(int)Math.ceil((-1+Math.sqrt(1+8.0*target))/2);// 计算对应的累加和intsum=k*(k+1)/2;// 如果差值是偶数，直接返回kif((sum-target)%2==0){returnk;}// 如果差值是奇数，需要继续增加步数// 增加1步：差值变化为 (sum + k + 1 - target) = (sum - target) + (k + 1)// 增加2步：差值变化为 (sum - target) + (k + 1) + (k + 2)// 由于连续两个整数中必有一个是奇数，所以最多再走2步就能得到偶数差值if((sum+k+1-target)%2==0){returnk+1;}else{returnk+2;}}}

算法分析

• 时间复杂度：

  • 方法一：O(√target)
  • 方法二：O(1) - 直接数学计算

• 空间复杂度：O(1) - 只使用常数空间

算法过程

1：target = 3

• target = 3（绝对值）
• step = 0, sum = 0
• step = 1, sum = 1（1 < 3，继续）
• step = 2, sum = 3（3 >= 3 且 (3-3)=0 是偶数）
• 返回2

2：target = 2

• target = 2（绝对值）
• step = 0, sum = 0
• step = 1, sum = 1（1 < 2，继续）
• step = 2, sum = 3（3 >= 2 但 (3-2)=1 是奇数，继续）
• step = 3, sum = 6（6 >= 2 且 (6-2)=4 是偶数）
• 返回3

3：target = 4

• step = 1, sum = 1
• step = 2, sum = 3
• step = 3, sum = 6（6 >= 4 且 (6-4)=2 是偶数）
• 返回3

路径：+1 + 2 + 3 = 6，需要减少2，所以将第1步反向：-1 + 2 + 3 = 4

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例System.out.println("Test 1 (target=3): "+solution.reachNumber(3));// 2// 测试用例2：需要调整方向System.out.println("Test 2 (target=2): "+solution.reachNumber(2));// 3// 测试用例3：负数目标System.out.println("Test 3 (target=-1): "+solution.reachNumber(-1));// 1// 测试用例4：较大目标System.out.println("Test 4 (target=10): "+solution.reachNumber(10));// 4// 测试用例5：边界情况System.out.println("Test 5 (target=0): "+solution.reachNumber(0));// 0// 测试用例6：需要多步调整System.out.println("Test 6 (target=5): "+solution.reachNumber(5));// 5// 测试用例7：较大数值System.out.println("Test 7 (target=100): "+solution.reachNumber(100));// 13// 测试用例8：验证对称性System.out.println("Test 8 (target=-3): "+solution.reachNumber(-3));// 2// 测试用例9：差值为奇数的情况System.out.println("Test 9 (target=7): "+solution.reachNumber(7));// 5// 测试用例10：刚好等于累加和System.out.println("Test 10 (target=6): "+solution.reachNumber(6));// 3}

关键点

1. 对称性：

   • 正负目标的解相同，简化问题为非负情况

2. 累加和：

   • 前k步的最大可达距离是k(k+1)/2
   • 这是所有步骤都向同一方向移动的情况

3. 反向调整：

   • 将第i步反向会使总和减少2i
   • 只能调整偶数值的距离差

4. 奇偶性：

   • 当(sum - target)为偶数时，可以直接调整
   • 当为奇数时，需要继续增加步数直到差值变为偶数
   • 最多需要再走2步（因为连续整数的奇偶性交替）

5. 数学：

   • 利用求根公式可以快速估算最小步数

常见问题

1. 为什么反向操作只能改变偶数值？

   • 原本加i，反向后减i，总变化量是-2i，必为偶数

2. 为什么最多再走2步就能解决奇数差值问题？

   • 连续两个整数中必有一个奇数
   • 如果当前差值是奇数，加上一个奇数就变成偶数
   • 如果k+1是偶数，则k+2必是奇数