时间戳

首页 > 解决方案 > 交换元素以满足特定条件的充分算法

algorithm - 交换元素以满足特定条件的充分算法

问题描述

给你两个正数 N 和 K，找到从 N 中交换任意两个数的最小数，得到两个新数 A 和 B，并且差 (A - B) 等于 K，如果有多个解决方案，请使用A 最大的解。

例如

我们有 N = 9834216 和 K = 8826，我们交换 16 以形成新的数字 9168342，A = 9168 和 B = 342，并且 A - B = 9168 - 342 = 8826。

标签： algorithm

解决方案

let N = 9834216, K = 8826;
let count = 0;

function fn(nArr, k, n) {
  if (n == 0) {
    let temp = -k;
    if (temp <= 0) {
      return;
    }
    let tArr = [...nArr];
    while (temp > 0) {
      let temp1 = temp % 10;
      let tId = tArr.indexOf(temp1);
      if (tId < 0) {
        return;
      }
      tArr.splice(tId, 1);
      temp = Math.floor(temp / 10);
    }
    if (tArr.length == 0) {
      console.log((K - k) + "-" + (-k) + "=" + K);
      count++;
    }
  } else {
    for (let i in nArr) {
      let tArr = [...nArr];
      tArr.splice(i, 1);
      fn(tArr, k - Math.pow(10, n - 1) * nArr[i], n - 1);
    }
  }
}

function getAB(N, K) {
  let nArr = [],
    n = N;
  while (n > 0) {
    nArr.push(n % 10);
    n = Math.floor(n / 10);
  }
  nArr.sort();
  nArr.reverse();
  for (let i = nArr.length; i > nArr.length / 2; i--) {
    fn(nArr, K, i);
  }
}

getAB(N, K);
console.log(count + " solutions");

推荐阅读