В этой задаче 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 во времени и пространстве:

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

Удачного кодирования!