微软8.13笔试 前端JS编程题*3

1. 我觉得分子、分母有些难处理，而且分数还涉及到通分，尤其是JS的小数又涉及到精确度的问题，所以我就先求出了分母的最小公倍数，再将分数通分，最后就演变成了`在分子数组找两个数的和为最小公倍数`，这不就是两数之和的问题嘛！！
2. 但是最小公倍数值会不会太大，超过数据范围就不得而知了
3. 但是我审题不清，没注意a pair of，还想着会不会有2项、3项……之和的情况。

function solution(X, Y) {
  let minMom = getMinMom(Y);
  let newX = X.map((val, index) => (val * minMom) / Y[index]).sort();
  // 往下就是求两数之和了——————力扣第一题，呜心痛
  let map = new Map(),
    res = 0;
  for (let item of newX) {
    // 这个一半的情况留着单独讨论
    if (item === minMom / 2) {
      map.set(item, (map.get(item) || 0) + 1);
    } else {
      map.set(item, (map.get(item) || 0) + 1);
      if (map.has(minMom - item)) {
        res += map.get(minMom - item);
      }
    }
  }
  if (map.has(minMom / 2) && map.get(minMom / 2) > 1) {
    // 这里要算组合
    let count = map.get(minMom / 2);
    res += (count * (count - 1)) / 2;
  }
  return res;
}
console.log(solution([1, 1, 2], [3, 2, 3])); // 1

// 取公倍数
function getMinMom(Y) {
  let res = 1;
  Y.forEach((i) => {
    if (res % i !== 0) {
      if (i % res === 0) {
        res = i;
      } else {
        res *= i;
      }
    }
  });
  return res;
}

1. 当时就一个疑惑，比如做一次治疗要间隔Y天后再做第二次，但是Y天后一定要立刻去做嘛？还是说可能找一个更便宜的时候去呢？最后看例子以及题干的描述，觉得就是`间隔Y天后一定要接着做第二次` 
2. 然后就是暴力遍历求解了
3. 我看有人提到`前缀和`，可以参考力扣303题。确实这个可以少一点运算啦，但是这个每次治疗间隔Y天，不是一天哦，所以麻烦一点。

// 暴力解法
function solution(A, X, Y) {
  // dayCost做完治疗要花的天数；totalCost要花的钱，这样就可以遍历比较了。
  let dayCost = Y * (X - 1) + 1,
    totalCost = Number.MAX_VALUE;
  for (let i = 0; i <= A.length - dayCost; i++) {
    let count = X,
      j = i,
      cost = 0;
    while (count > 0) {
      cost += A[j];
      j += Y;
      count--;
    }
    totalCost = Math.min(totalCost, cost);
  }
  return totalCost;
}

console.log(solution([4, 2, 3, 7], 2, 2));

// 使用了前缀和
function solution(A, X, Y) {
  // dayCost做完治疗要花的天数；totalCost要花的钱；deadline是最迟这天要开始治疗，不然就来不及了
  let dayCost = Y * (X - 1) + 1,
    totalCost = Number.MAX_VALUE,
    deadline = A.length - dayCost;
  // Y 是控制了一个循环，每轮循环中的不同治疗方案才有重复的日期，才能用前缀和。
  for (let i = 0; i < Y && i <= deadline; i++) {
    // j是本轮治疗起始的日子
    let cost = 0;
    for (let j = i; j <= deadline; j += Y) {
      if (j !== i) {
        // 前缀和就这点好处啦，有的情况下就不用循环计算了
        cost = cost - A[j - Y] + A[j - Y * (X - 1)];
      } else {
        let count = X,
          index = j;
        while (count > 0) {
          cost += A[index];
          index += Y;
          count--;
        }
      }
      totalCost = Math.min(totalCost, cost);
    }
  }

  return totalCost;
}

console.log(solution([10, 3, 4, 7], 2, 3));  // 17