使用余数运算符改进算法

使用余数运算符改进算法

Flying
2023-11-30 / 0 评论 / 69 阅读 / 正在检测是否收录...

JavaScript 中的 % 符号是余数运算符,它在一个数字被另一个数字除时返回余数。它在各种情况下都很方便,特别是当你需要检查可被整除性、处理循环或基于余数操作值时。特殊情况下,使用余数运算符可以改进算法。

enhancement-remainder.svg

例如,10 % 3 将会得到 1,因为 10 除以 3 等于 3,余数是 1。同样地,-10 % 3 将会得到 -1,因为它计算的是 -10 除以 3 的余数。

用途

余数运算符的一个常见用途是检查数字是奇数还是偶数。如果一个数模 2 等于 0,则它是偶数;否则,它是奇数。例如:

function isEven(number) {
  return number % 2 === 0;
}

console.log(isEven(6)); // 输出: true
console.log(isEven(7)); // 输出: false

它还有助于在循环中对数组进行循环或在特定间隔内执行任务。例如,遍历数组中每三个元素:

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

for (let i = 0; i < array.length; i++) {
  if (i % 3 === 0) {
    console.log(array[i]);
  }
}
// 输出: 1, 4, 7, 10

记住,余数运算符在编程中解决涉及余数或循环模式的各种问题时非常有用。适当使用余数运算符可以改进算法。下面我们来看一看余数运算符的经典算法案例 Save the Prisoner(拯救囚犯)。

拯救囚犯

监狱里有一些囚犯和一些糖果要分发给他们。监狱看守决定公平分发糖果的方式是让囚犯围坐在一个环形桌子周围,椅子上有顺序编号。从帽子中抽取一个椅子编号。从坐在那个椅子上的囚犯开始,依次给每个囚犯递交一颗糖果,直到所有人都分到为止。

不过,监狱看守在玩一个小玩笑。最后一颗糖果看起来和其他糖果一样,但味道很糟糕。确定哪个囚犯坐在那个椅子上会得到那颗糖果。

示例

n = 4
m = 6
s = 2

有 4 名囚犯,6 颗糖果,分发从第 2 号椅子开始。囚犯们坐在编号为 1 到 4 的座位上。囚犯在位置 2、3、4、1、2、3 接收糖果。要被警告的囚犯坐在第 3 号椅子上。

函数描述

完成 saveThePrisoner 函数。它应该返回一个整数,表示被警告的囚犯所在的椅子编号。

saveThePrisoner 具有以下参数:

  • int n:囚犯数量
  • int m:糖果数量
  • int s:开始分发糖果的椅子编号

返回

int:被警告的囚犯的椅子编号

解决方案

这个问题涉及将糖果在围坐的囚犯之间进行分发,并确定哪个囚犯会得到最后一颗糖果(这颗糖果是不受欢迎的)。我们可以通过使用模运算来解决这个问题。

以下是 JavaScript 中的解决方案:

function saveThePrisoner(n, m, s) {
  // 计算在囚犯之间分发 m 颗糖果后的余数
  // 减 1 是为了考虑从 0 开始的索引
  const remainder = (m - 1 + s) % n;

  // 如果余数为 0,则最后一个糖果会给最后一个囚犯
  return remainder === 0 ? n : remainder;
}

这个函数从椅子 s 开始计算,在一个环形桌子上坐着的 n 个囚犯之间分发 m 颗糖果后的余数。结果表示得到最后一颗糖果的囚犯所在的椅子编号。

你可以用合适的值调用这个函数,来找出哪个囚犯会得到不受欢迎的糖果。

console.log(saveThePrisoner(5, 2, 1))  // 2
console.log(saveThePrisoner(5, 2, 2))  // 3
console.log(saveThePrisoner(7, 19, 2))  // 6
console.log(saveThePrisoner(3, 7, 3))  // 3

另一个经典算法案例是 Circular Array Rotation(循环数组轮转)。

循环数组轮转

华生准备测试一下福尔摩斯,他给福尔摩斯一个数组 A0, A1 ... An-1 。
他在数组上做了一个操作并要求福尔摩斯 回答一些查询。一共有 Q 个查询。现在直觉告诉福尔摩斯,进行的操作是 K-右循环移动。

右循环移动是指把数组从 A0, A1 ... An-1 变为 An-1, A0 ... An-2。

现在,华生已经把数组进行了 K 次这样的左循环移动。

帮助福尔摩斯解决这些查询。每个查询由一个整数 X 构成, 你需要输出 Ax来回答这个查询。

函数描述

完成 circularArrayRotation 函数。它应该返回一个表示查询值的整数数组。

circularArrayRotation 具有以下参数:

  • 整数数组 a:最初整数数组
  • 整数 k:左循环移动的次数
  • 整数数组:queries:查询键组成的数组

返回

int:表示查询值的整数数组

解决方案

以下是 JavaScript 中的解决方案:

function circularArrayRotation(a, k, queries) {
  const n = a.length;
  const result = [];

  // 计算实际右循环移动后的位置
  const shift = k % n;

  // 根据右循环移动后的位置计算每个查询的结果
  for (let i = 0; i < queries.length; i++) {
    const idx = (n - shift + queries[i]) % n;
    result.push(a[idx]);
  }

  return result;
}

console.log(circularArrayRotation([1, 2, 3], 2, [1]))  // [2, 3, 1]

这个函数首先计算实际右循环移动后数组中元素的位置偏移量 shift,然后根据每个查询中的位置,计算出右循环移动后的位置,将对应位置的元素添加到结果数组中,并最终返回结果数组。

参考 ES6 语法,我们甚至可以不用循环操作:

function circularArrayRotation(a, k, queries) {
  const n = a.length;
  const shift = n - (k % n);
  return queries.map(item => a[(item + shift) % n]);
}

参考大 O 表示法,时间复杂度还是 O(n)。

另一种不使用余数运算符的方案:

function circularArrayRotation(a, k, queries) {
  const result = [];

  while (k > 0) {
    const tmp = a.pop();
    a.unshift(tmp);
    k--;
  }

  for (let i = 0; i < queries.length; i++) {
    result.push(a[queries[i]]);
  }

  return result;
}

while 语句中的数组 popunshift 操作需要额外消耗时间,很明显没前面两种方案性能好。

链接

1

评论 (0)

取消