c++ - 以最少的步骤将给定整数转换为另一个整数

Question

给定两个位数相同的数字 A 和 B。通过在每个步骤中增加或减少 A 中的单个数字，找到将 A 转换为 B 的最少步骤数。
例如:如果 A = 133 和 B = 343，可能的解决方案是 133 -> 233 -> 333 -> 343。所需的最少步数为 3。

我尝试了一种蛮力方法。这是我的伪代码

  while(a!=b)
  {
   if(a<b)
      {
        find (b-a)
        count number of digits in (b-a) keep it as n
        add the power(10,n) to a
        moves++;
       }
     else{
       find (a-b)
        count number of digits in (a-b) keep it as n
        subtract the power(10,n) from a
        moves++;
        }

  }

我无法获得所有测试用例的正确答案。请提出一个有效的方法来做到这一点。

Answer 1

你的问题的解决方案是

1. 逐位遍历a和b，差的绝对值加到一个变量sum
2. sum 表示需要更改的位数
3. 时间复杂度O(位数)

function solve(a, b){
    let sum = 0;
    while(a>0 && b>0){
        sum += Math.abs((a%10)-(b%10));
        a = Math.floor(a/10);
        b= Math.floor(b/10);
    }
    return sum;
}

console.log(solve(133, 343));
console.log(solve(1234, 1221));