为什么在此函数中使用模运算符？

Question

我正在努力解决一个挑战：在圆形阵列中循环。我希望有人帮助我了解我们如何知道在这行代码中使用模数运算符？

next_index = (current_index + arr[current_index]) % len(arr)

问题描述：给定一个包含正数和负数的数组。假设数组在特定索引处包含一个数字“M”。现在，如果“M”为正，我们将向前移动“M”索引，如果“M”为负，则向后移动“M”索引。您应该假设数组是圆形的，这意味着两件事：

如果在前进的过程中到达数组的末尾，我们将跳转到第一个元素继续移动。如果在向后移动时到达数组的开头，我们将跳转到最后一个元素以继续移动。写一个方法判断数组是否有环。循环应该有一个以上的元素并且应该遵循一个方向，这意味着循环不应该包含向前和向后的运动。示例：

Input: [1, 2, -1, 2, 2]
Output: true
Explanation: The array has a cycle among indices: 0 -> 1 -> 3 -> 0

代码:

def circular_array_loop_exists(arr):
  for i in range(len(arr)):
    is_forward = arr[i] >= 0  # if we are moving forward or not
    slow, fast = i, i

    # if slow or fast becomes '-1' this means we can't find cycle for this number
    while True:
      # move one step for slow pointer
      slow = find_next_index(arr, is_forward, slow)
      # move one step for fast pointer
      fast = find_next_index(arr, is_forward, fast)
      if (fast != -1):
        # move another step for fast pointer
        fast = find_next_index(arr, is_forward, fast)
      if slow == -1 or fast == -1 or slow == fast:
        break

    if slow != -1 and slow == fast:
      return True

  return False


def find_next_index(arr, is_forward, current_index):
  direction = arr[current_index] >= 0

  if is_forward != direction:
    return -1  # change in direction, return -1

  # ********** This is the line in question ***********
  next_index = (current_index + arr[current_index]) % len(arr)
  # ********** This is the line in question ***********

  # one element cycle, return -1
  if next_index == current_index:
    next_index = -1

  return next_index


def main():
  print(circular_array_loop_exists([1, 2, -1, 2, 2]))
  print(circular_array_loop_exists([2, 2, -1, 2]))
  print(circular_array_loop_exists([2, 1, -1, -2]))


main()

Answer 1

modulo-operator returns remainder 给定部门。假设我们有以下代码：

>>> lst = [i for i in range(5)]
>>> lst
[0, 1, 2, 3, 4]

如果我们尝试调用列表外的 index，我们会得到一个错误：

>>> lst[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range

因为 modulo-operator returns remainder 虽然我们可以这样做：

>>> lst[5 % len(lst)]
0

这是因为5 / 5的remainder是0。如果我们改为尝试使用 6，我们会得到以下结果：

>>> lst[6 % len(lst)]
1

再一次，因为 remainder 如果 6 / 5 是 1。

Answer 2

取模运算符returns除法的余数。您可以了解更多关于 here.

在您的上下文中，这意味着它将索引保留在循环数组中以避免索引越界。

例如，如果您有一个长度为 4 的数组，但您的下一个索引是 6，此代码 % len(arr) 会将 6 更改为 2，因为 6 % 4 = 2。所以这意味着, 它将索引环绕到数组的开头。

如果您的下一个索引是 2，因为 2 小于 4，此操作 % len(arr) 将得出余数，即 2。因此，如果索引在数组的范围内，则它保持不变。

希望对您有所帮助！

为什么在此函数中使用模运算符？

Why is the modulo operator used in this function?

python

arrays

modulo