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

Я хотел поблагодарить Джона Суиндина и @ksjazzguitar с форума FreeCodeCamp за небольшой совет, который они мне дали.

Мой подход к сложению суммы элементов второй диагонали оказался не лучшим. Мы можем увеличить производительность алгоритма с O(n * n) до O(n), удалив один цикл for из нашего предыдущего решения. Удивительно, правда? Спасибо, ребята, что указали на это! : D

Во-первых, давайте резюмируем, каким был мой подход ко второй диагональной сумме:

  • перебрать все элементы матрицы
  • если сумма индексов (i + j) равна длине матрицы минус один: i + j === n — 1
  • добавьте это число к diag2 - ›, представляющему общую сумму для второй диагонали

Хорошая, но не самая лучшая… xD

Что мы действительно можем сделать, так это выйти из второго внутреннего цикла, потому что он нам не нужен! Давайте изменим это в коде, чтобы лучше понять:

function calculateDiagonals(matrix){
    var n = matrix.length;
    var diag1 = 0;
    var diag2 = 0;
    for(var i=0; i<n; i++){
    }
}

Поскольку у нас есть квадратная матрица размера: n * n, мы получим первую сумму по диагонали, сложив элементы из индекса: [i][i], а вторую сумму по диагонали, как мы видели выше, добавив элементы из индекса: [i][n — i — 1].

Почему [n — i — 1]? Давайте снова посмотрим на матрицу размером 3 с индексами:

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)

Итерации цикла for, которые мы дадим нам для второй диагонали:

  1. n = 3, i = 0 = ›получаем элемент (0, 3 — 0 — 1) = (0, 2)
  2. n = 3, i = 1 = ›получаем элемент (1, 3 — 1 — 1) = (1, 1)
  3. n = 3, i = 1 = ›получаем элемент (2, 3 — 2 — 1) = (2, 0)

Это именно то, что мы хотели! Итак, окончательный код будет:

function calculateDiagonals(matrix){
    var n = matrix.length;
    var diag1 = 0;
    var diag2 = 0;
    for(var i=0; i<n; i++){
        diag1 += matrix[i][i];
        diag2 += matrix[i][n - i - 1];
    }
    return Math.abs(diag1 - diag2);
}

Потрясающие! Это намного быстрее, чем было раньше! :)

Заключение

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

Это то, что мы можем использовать при программировании. Даже если ваш подход хорош и алгоритм работает, может быть лучшее решение!

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