Почему оператор по модулю используется в этой функции? - PullRequest
Новая
       53

Почему оператор по модулю используется в этой функции?

0 голосов
/ 20 сентября 2019

Я работал над решением задачи: цикл в круговом массиве.Мне бы хотелось, чтобы кто-нибудь помог мне понять, как мы знаем, как использовать оператор модуля в этой строке кода?

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

Описание проблемы : Мы находимсядан массив, содержащий положительные и отрицательные числа.Предположим, что массив содержит число «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()

Ответы [ 2 ]

2 голосов
/ 20 сентября 2019

Оператор модуля возвращает остаток от деления.Вы можете узнать больше о здесь .

В вашем контексте это означает, что он сохраняет индекс в круговом массиве, чтобы избежать выхода индекса за пределы.

Например,, если у вас есть массив, имеющий длину 4, но ваш следующий индекс равен 6, этот код % len(arr) меняет 6 на 2, потому что 6% 4 = 2. Таким образом, это означает, что индекс переносится в началомассива.

Если ваш следующий индекс равен 2, так как 2 меньше 4, эта операция % len(arr) приведет к остатку, равному 2. Таким образом, индекс остается неизменным, если он находится в пределахмассив.

Надеюсь, это поможет!

0 голосов
/ 20 сентября 2019

modulo-operator возвращает 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 возвращает remainder, хотя вместо этого мы можем сделать что-то подобное: 

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

Это потому, что remainder из 5 / 5 равно 0.Если вместо этого мы попробуем с 6, мы получим следующий результат: 

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

Еще раз, это потому, что remainder, если 6 / 5 равно 1.

...