Сложность: medium
Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.
Пример:
Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]
Output: 1
👨💻 Алгоритм:
1⃣Пройдите по строкам матрицы. Для каждой пары строк, найдите все столбцы, где оба значения равны 1.
2⃣Подсчитайте количество таких столбцов. Если их больше одного, то они образуют прямоугольники.
3⃣Для каждой пары строк добавьте количество возможных прямоугольников в общий счетчик.
😎 Решение:
function countCornerRectangles($grid) {
$count = 0;
for ($i = 0; $i < count($grid); $i++) {
for ($j = $i + 1; $j < count($grid); $j++) {
$numPairs = 0;
for ($k = 0; $k < count($grid[0]); $k++) {
if ($grid[$i][$k] == 1 && $grid[$j][$k] == 1) {
$numPairs++;
}
}
if ($numPairs > 1) {
$count += $numPairs * ($numPairs - 1) / 2;
}
}
}
return $count;
}Ставь 👍 и забирай 📚 Базу знаний