Проблема с заправкой — решение Golang | Джордж Онвуасоанья | июль 2022 г. | Середина

Начните писать В сегодняшнем посте мы будем решать следующую проблему с заправочной станцией с помощью Golang.

Проблема
Дан круговой список заправок, где мы можем пройти от станции i до станции i + 1, а последняя идет обратно к первой, найдите номер станции, с которой мы начинаем, чтобы иметь возможность объехать все станции и вернуться на начальную, не исчерпав бензин

Примечание:

1. мы можем двигаться только вперед
2. бензобак начинает пустеть
3. газ[i] представляет количество газа на станции i
4. расходы[i] представляет собой стоимость перехода от станции i к следующей
5. ответ гарантированно будет уникальным
6. если нужная станция не существует, вернуть -1

NB
В реальных условиях многие водители-дальнобойщики оценивают это с помощью своего опыта, однако водители дальнего следования 10x (т. е. водители с навыками кодирования) могут решить эту проблему с первого раза.

Описание решения №1
Это решение имеет временную сложность O(n²), и это был первый метод, который пришел мне в голову, когда я думал об этой задаче. Таким образом, это метод грубой силы, который выполняет итерацию по массиву и рассматривает каждый индекс как начальную точку пересечения. Действительная станция — это станция с индексом i, с которой мы можем начать, чтобы иметь возможность пересечь все станции и вернуться к исходной (i-1), не исчерпав газа.

Когда у нас есть действительная трансверсаль от индекса i до n, где n — длина массива; циклическое условие на заправочных станциях влечет за собой то, что мы рассматриваем доступный газ от пересечения i к n, когда мы пересекаем от 0 до i. Когда мы находим i-ю заправку, которую мы можем пересечь (от i до n) и (от 0 до i), не заканчивая бензин, мы возвращаем это i.

Кодовое решение:

func Execute() {

  gas := []int{1, 5, 3, 3, 5, 3, 1, 3, 4, 5}
  cost := []int{5, 2, 2, 8, 2, 4, 2, 5, 1, 2}
  tP := -1

  for i := 0; i < len(gas); i++ {
    if gas[i] > cost[i] {
      rtTrnv := traverseScore(0, gas[i:], cost[i:])
      if rtTrnv < 0 {
        continue
      }

      lftTrnv := traverseScore(rtTrnv, gas[:i], cost[:i])
      tSum := rtTrnv + lftTrnv
      if tSum >= 0 {
        tP = i
        break
      }
    }
  }
  fmt.Println(tP)
}

func traverseScore(sum int, gas, cost []int) int {
  for k := range gas {
    sum += (gas[k] - cost[k])
    if sum < 0 {
      break
    }
  }
  return sum
}

Описание решения № 2
Опыт действительно великий учитель. Когда водитель-дальнобойщик отправляется в поездку из-за проблемы с заправкой, он отмечает в уме количество бензина, которое нужно купить на разных станциях, после нескольких поломок автомобиля с пустым бензобаком.

Мы хотим реализовать эти мыслительные заметки в коде для драйверов 10x, и это улучшит вышеприведенное решение для кодирования и уменьшит временную сложность до O (n). Основная идея состоит в том, чтобы вести учет посещенных индексов, составляющих неверный путь.

Если мы начнем с индекса станции и достигнем отрицательного значения в i, то все станции между start и i включительно будут недействительными. нам нужно сохранить предыдущую сумму, которая привела нас к отрицательному значению, чтобы нам не пришлось пересчитывать сумму, необходимую для повторного прохождения этого пути. Следующий интересующий путь обхода — от i+1

Кодовое решение:

func Execute2() {
  gas := []int{1, 5, 3, 3, 5, 3, 1, 3, 4, 5}
  cost := []int{5, 2, 2, 8, 2, 4, 2, 5, 1, 2}
  sum := 0
  tP := 0
  prevSum := 0
  for i := 0; i < len(gas); i++ {
    sum += (gas[i] - cost[i])
    if sum < 0 {
      tP = i + 1
      prevSum = sum
      sum = 0
    }
  }

  if tP == len(gas) || prevSum+sum < 0 {
    tP = -1
  }
  fmt.Println(tP)
}

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

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