Я не могу понять, в чем логический недостаток моего кода
Я пытаюсь решить эту проблему:
На двумерной плоскости мы размещаем n камней в некоторых целочисленных точках координат. В каждой координатной точке может быть не более одного камня.
Камень можно удалить, если он находится в той же строке или в том же столбце, что и другой камень, который не был удален.
Учитывая массив камней длины n, где камни[i] = [xi, yi] представляют местоположение i-го камня, верните максимально возможное количество камней, которые можно удалить.
/**
* @param {number[][]} stones
* @return {number}
*/
var removeStones = function (stones) {
const rowMap = {}
const colMap = {}
for (let i = 0; i < stones.length; i++) {
const [row, col] = stones[i]
if (!rowMap[row]) rowMap[row] = 0
if (!colMap[col]) colMap[col] = 0
rowMap[row] += 1
colMap[col] += 1
}
return findMaxMove(stones, 0, rowMap, colMap)
};
const findMaxMove = (stones, index, rowMap, colMap) => {
if (index == stones.length) return 0
const [row, col] = stones[index]
let isInCol = colMap[col] > 1
let isInRow = rowMap[row] > 1
let removedMove = 0
if (isInCol || isInRow) {
const colMapCopy = { ...colMap, [col]: colMap[col] - 1 }
const rowMapCopy = { ...rowMap, [row]: rowMap[row] - 1 }
removedMove = 1 + findMaxMove(stones, index + 1, rowMapCopy, colMapCopy);
}
return Math.max(removedMove, findMaxMove(stones, index + 1, rowMap, colMap))
}
В каком-то случае он проходит, а в каком-то случае не проходит:
случай, когда он не работает:
stones = [[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]
Expected: 5
Output: 4
Из Интернета я узнал, что распространенную проблему можно решить с помощью набора Disjoint, но я хотел решить ее с помощью грубой силы, прежде чем погрузиться в набор Disjoint.
Любая помощь, пожалуйста
Рассмотрите возможность сохранения элемента с максимальной суммой rowMap + colMap.
@code_monk, диагональная линия?
Неудачный тестовый пример представляет эту плоскость:
. 0 5 .
. . 1 2
. . . 4
. . . 3
Поскольку ваш код удаляет камни в порядке их индекса, вы сначала удалите камни 0 и 1, оставив камень 5 осиротевшим:
. . 5 .
. . . 2
. . . 4
. . . 3
Это не оптимальное решение, так как вы можете сначала удалить 0 (как вы это сделали), но затем сначала удалить 5, а затем удалить 1. И тогда все камни можно будет удалить.
Ваш алгоритм на самом деле не является грубой силой, поскольку он исключает другие возможности. Вы реализовали алгоритм, который можно назвать жадным, но не брутфорсом. Подход грубой силы также может попытаться удалить камни в другом порядке, поскольку порядок влияет на то, сколько камней можно удалить.
о боже мой, мне никогда не приходило в голову такой порядок удаления горных пород в этом случае, я не знаю, как бы я вообще об этом подумал. Я считаю, что мне нужно развивать этот мыслительный процесс. Есть какие-нибудь предложения по этому поводу? Большое спасибо за ваше направление.
Это потому, что вам нужно выбрать правильные элементы для удаления, чтобы в итоге осталось наименьшее количество элементов. Если вы удалите элемент, потому что он следующий по порядку и его можно удалить по закону, вы можете упустить шанс сделать оптимальный выбор.