2757. 生成循环数组的值 🔒

🟠   🔗 力扣 LeetCode

题目

Given a circular array arr and an integer startIndex, return a generator object gen that yields values from arr.

The first time gen.next() is called on the generator, it should should yield arr[startIndex].

Each subsequent time gen.next() is called, an integer jump will be passed into the function (Ex: gen.next(-3)).

• If jump is positive, the index should increase by that value, however if the current index is the last index, it should instead jump to the first index.
• If jump is negative, the index should decrease by the magnitude of that value, however if the current index is the first index, it should instead jump to the last index.

Example 1:

Input: arr = [1,2,3,4,5], steps = [1,2,6], startIndex = 0

Output: [1,2,4,5]

Explanation:

const gen = cycleGenerator(arr, startIndex);
gen.next().value; // 1, index = startIndex = 0
gen.next(1).value; // 2, index = 1, 0 -> 1
gen.next(2).value; // 4, index = 3, 1 -> 2 -> 3
gen.next(6).value; // 5, index = 4, 3 -> 4 -> 0 -> 1 -> 2 -> 3 -> 4

Example 2:

Input: arr = [10,11,12,13,14,15], steps = [1,4,0,-1,-3], startIndex = 1

Output: [11,12,10,10,15,12]

Explanation:

const gen = cycleGenerator(arr, startIndex);
gen.next().value; // 11, index = 1
gen.next(1).value; // 12, index = 2
gen.next(4).value; // 10, index = 0
gen.next(0).value; // 10, index = 0
gen.next(-1).value; // 15, index = 5
gen.next(-3).value; // 12, index = 2

Example 3:

Input: arr = [2,4,6,7,8,10], steps = [-4,5,-3,10], startIndex = 3

Output: [7,10,8,4,10]

Explanation:

const gen = cycleGenerator(arr, startIndex);
gen.next().value; // 7, index = 3
gen.next(-4).value; // 10, index = 5
gen.next(5).value; // 8, index = 4
gen.next(-3).value; // 4, index = 1
gen.next(10).value; // 10, index = 5

Constraints:

• 1 <= arr.length <= 10^4
• 1 <= steps.length <= 100
• -10^4 <= steps[i], arr[i] <= 10^4
• 0 <= startIndex < arr.length

题目大意

给定你一个 循环 数组 arr 和一个整数 startIndex ，返回一个生成器对象 gen ，它从 arr 中生成值。第一次调用 gen.next() 时，它应该生成 arr[startIndex] 。每次调用 gen.next() 时，都会传入一个整数参数 jump（例如：gen.next(-3) ）。

• 如果 jump 是正数，则索引应该增加该值，但如果当前索引是最后一个索引，则应跳转到第一个索引。
• 如果 jump 是负数，则索引应减去该值的绝对值，但如果当前索引是第一个索引，则应跳转到最后一个索引。

提示：

• 1 <= arr.length <= 10^4
• 1 <= steps.length <= 100
• -10^4 <= steps[i], arr[i] <= 10^4
• 0 <= startIndex < arr.length

解题思路

需要编写一个生成器函数 cycleGenerator，它接收一个数组 arr 和一个初始索引 startIndex，并返回一个生成器，这个生成器会根据传入的 jump 参数（每次通过 next(jump) 调用）来返回新的数组值。

• 通过 while (true) 使得生成器无限循环，因为数组是循环的，且没有明确的终止条件。
• 生成器通过 yield 来返回当前索引的元素 arr[startIndex]。
• 每次调用 next(jump) 时，生成器会根据 jump 值来修改当前索引，并返回数组中对应的新值。
• 当 startIndex 超出数组范围时，可以利用模运算来确保索引始终在有效范围内：
  • startIndex + jump：计算新的索引。
  • (startIndex + jump) % n：模运算确保索引不会超出数组边界。
  • ((startIndex + jump) % n + n) % n：如果模运算结果为负数（例如 -1），则加上 n 后再取模，确保索引非负。

复杂度分析

• 时间复杂度： 每次调用 next(jump) 的操作是 O(1)，因为只是做了简单的索引计算和模运算。
• 空间复杂度： O(1)，生成器只维护一个索引，没有额外的空间开销。

代码

/**
 * @param {Array} arr
 * @param {number} startIndex
 * @return {Generator<number>}
 */
var cycleGenerator = function* (arr, startIndex) {
	const n = arr.length;
	while (true) {
		// 返回当前索引的元素
		const jump = yield arr[startIndex];
		// 根据 jump 更新索引，并使用模运算确保其在合法范围内
		startIndex = (((startIndex + jump) % n) + n) % n;
	}
};