В этой задаче Leetcode нам дается список домино, каждое домино имеет 2 значения от 1 до 6 (я думаю, что обычно домино также может иметь значение 0, но здесь это не имеет особого значения), верхнее значение и нижнее значение. Вы хотите, чтобы все верхние значения или все нижние значения были равны. Для этого вы можете перевернуть домино, меняя местами верхнее и нижнее значение. Вопрос в том, как это сделать за минимально возможное количество ходов? Если это невозможно, верните -1.
Чтобы решить эту проблему, мы сначала можем заметить, что решить проблему можно только в том случае, если число появляется хотя бы один раз на каждом домино. Вот почему я представил метод count
, который возвращает количество домино, на котором присутствует каждое из возможных значений:
func count(A []int, B []int) [7]int { var count [7]int for i, v := range A { count[v]++ if (A[i] != B[i]) { count[B[i]]++ } } return count }
Если count[i]
совпадает с len(A)
, то можно решить проблему для значения i
.
Затем я представил метод cost
, он вычисляет минимальную стоимость выравнивания всех верхних или нижних значений для соответствия i
. Для этого он вычисляет стоимость их выравнивания внизу (costB
) и стоимость выравнивания их вверху (costA
), а затем возвращает минимальное значение.
func cost(A []int, B []int, value int) int { costA := 0 costB := 0 for i, v := range A { if (v != value) { costA++ } if (value != B[i]) { costB++ } } if (costA < costB) { return costA } return costB }
Используя эти методы, мы сначала находим все потенциальные значения, которые могут быть выровнены (максимум 2), за O(N)
время, поскольку мы проходим A
и B
один раз.
Затем для всех возможных значений (O(1)
) мы еще раз просматриваем A
и B
, чтобы рассчитать стоимость. Мы возвращаем лучшее найденное нами значение, если оно есть. Поэтому мы решили задачу за линейное время.
Вот полный код:
func minDominoRotations(A []int, B []int) int { count := count(A, B) res := -1 for i := range count { if (count[i] == len(A)) { cost := cost(A, B, i) if (res == -1 || cost < res) { res = cost } } } return res } func count(A []int, B []int) [7]int { var count [7]int for i, v := range A { count[v]++ if (A[i] != B[i]) { count[B[i]]++ } } return count } func cost(A []int, B []int, value int) int { costA := 0 costB := 0 for i, v := range A { if (v != value) { costA++ } if (value != B[i]) { costB++ } } if (costA < costB) { return costA } return costB }
Он превосходит 100% решений Go во времени и пространстве:
Во всяком случае, я считаю эту задачу несколько проще, чем простую задачу того же конкурса, которую я разрабатываю здесь. Здесь я постарался сделать это по-настоящему простым и не терять время, пытаясь сделать что-то более сложное, чем было на самом деле.
Удачного кодирования!