Ранее на этой неделе друг обратился ко мне с алгоритмом. Они погружались в проблемы с сеткой и использовали меня как резиновую утку, чтобы найти решение. У нас была интересная дискуссия, когда мы решали, а затем рефакторили наши решения, и я расскажу об этом здесь.
Вопрос: учитывая квадратную сетку, представленную двумерным массивом, заполненным целыми числами, вернуть разницу в сумме диагоналей. Например, если наш ввод выглядит так:
тогда наше возвращаемое значение будет равно 0. То есть 1 + 5 + 9 = 15 и 3 + 5 + 7 = 15, а 15–15 = 0. В качестве альтернативы, если бы наш ввод выглядел так:
тогда наш выход будет 4.
Моей первой мыслью при решении этой задачи было подумать о том, как пройти через сетку. Чтобы посетить каждую точку в сетке, вы настраиваете вложенные циклы for.
Но какие позиции в сетке меня действительно волнуют здесь? Только диагонали. Как я могу получить доступ только к диагоналям? Что ж, для диагонали слева направо от g1 мне нужно добраться до g1[0][0], g1[1][1] и g1[2][2]. Для диагонали справа налево мне нужно добраться до g1[0][2], g1[1][1] и g1[2][0]. Меня не волнуют никакие другие точки в сетке, и я также могу видеть закономерность, возникающую в интересующих меня координатах. Для слева направо строка и столбец всегда будут одинаковыми. Для справа налево мне нужно инвертировать строку или столбец. Итак, вместо вложенного цикла у меня может быть один цикл, который отслеживает два указателя:
Мой первый указатель, i, начинается с 0 и проходит по всей длине матрицы. Мой второй указатель, j, начинается с последнего индекса и уменьшается до 0. Поскольку у меня есть квадрат, я знаю, что i и j имеют одинаковую длину, поэтому моему конечному условию цикла нужно отслеживать только один из них. Сейчас я делаю одну итерацию, но получаю доступ ко всем важным для меня точкам. Все, что мне нужно сделать сейчас, это просуммировать диагонали и вернуть их разницу.
Но действительно ли мне нужно вести подсчет сумм левой и правой диагоналей? В конце концов, меня волнует только их разница, которую я могу вычислить в самом цикле.
И последняя мысль — есть ли у меня какие-то выбросы, о которых стоит подумать? Мне был гарантирован квадратный ввод, но если бы я этого не сделал, я бы определенно начал с проверки, чтобы убедиться, что он квадратный. Что, если мой ввод пуст или содержит только одно значение? Если мой квадрат представляет собой одно значение, то обе диагонали являются этим значением, и разница должна быть равна 0. Если мой ввод пуст, я должен подумать, что я хочу вернуть. Я мог бы выдать ошибку. Я мог бы вернуться неопределенным. Или я мог бы вернуть 0, потому что в сумме нет разницы. Здесь я выберу последний вариант, но можно было бы поспорить и за другое решение. Итак, мой конечный продукт выглядит так:
