302. Smallest Rectangle Enclosing Black Pixels
LeetCode
hard
оригинал: C#
#backtracking
#csharp
#hard
#leetcode
#matrix
#search
#string
#two-pointers
Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
C# решение
сопоставлено/оригиналpublic class Solution {
public int MinArea(char[][] image, int x, int y) {
int m = image.Length, n = image[0].Length;
int left = SearchColumns(image, 0, y, 0, m, true);
int right = SearchColumns(image, y + 1, n, 0, m, false);
int top = SearchRows(image, 0, x, left, right, true);
int bottom = SearchRows(image, x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
private int SearchColumns(char[][] image, int i, int j, int top, int bottom, bool opt) {
while (i != j) {
int k = (i + j) / 2;
int t = top;
while (t < bottom && image[t][k] == '0') t++;
if ((t < bottom) == opt) {
j = k;
} else {
### Go
```go
package main
func minArea(image [][]byte, x int, y int) int {
m, n := len(image), len(image[0])
left := searchColumns(image, 0, y, 0, m, true)
right := searchColumns(image, y+1, n, 0, m, false)
top := searchRows(image, 0, x, left, right, true)
bottom := searchRows(image, x+1, m, left, right, false)
return (right - left) * (bottom - top)
}
func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
for i != j {
k := (i + j) / 2
t := top
for t < bottom && image[t][k] == '0' {
t++
}
if (t < bottom) == opt {
j = k
} else {
i = k + 1
}
}
return i
}
func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
for i != j {
k := (i + j) / 2
l := left
for l < right && image[k][l] == '0' {
l++
}
if (l < right) == opt {
j = k
} else {
i = k + 1
}
}
return i
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MinArea(char[][] image, int x, int y) {
int m = image.size(), n = image[0].size();
int left = SearchColumns(image, 0, y, 0, m, true);
int right = SearchColumns(image, y + 1, n, 0, m, false);
int top = SearchRows(image, 0, x, left, right, true);
int bottom = SearchRows(image, x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
private int SearchColumns(char[][] image, int i, int j, int top, int bottom, bool opt) {
while (i != j) {
int k = (i + j) / 2;
int t = top;
while (t < bottom && image[t][k] == '0') t++;
if ((t < bottom) == opt) {
j = k;
} else {
### Go
```go
package main
func minArea(image [][]byte, x int, y int) int {
m, n := len(image), len(image[0])
left := searchColumns(image, 0, y, 0, m, true)
right := searchColumns(image, y+1, n, 0, m, false)
top := searchRows(image, 0, x, left, right, true)
bottom := searchRows(image, x+1, m, left, right, false)
return (right - left) * (bottom - top)
}
func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
for i != j {
k := (i + j) / 2
t := top
for t < bottom && image[t][k] == '0' {
t++
}
if (t < bottom) == opt {
j = k
} else {
i = k + 1
}
}
return i
}
func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
for i != j {
k := (i + j) / 2
l := left
for l < right && image[k][l] == '0' {
l++
}
if (l < right) == opt {
j = k
} else {
i = k + 1
}
}
return i
}Java решение
сопоставлено/оригиналpublic class Solution {
public int minArea(char[][] image, int x, int y) {
int m = image.length, n = image[0].length;
int left = searchColumns(image, 0, y, 0, m, true);
int right = searchColumns(image, y + 1, n, 0, m, false);
int top = searchRows(image, 0, x, left, right, true);
int bottom = searchRows(image, x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
private int searchColumns(char[][] image, int i, int j, int top, int bottom, boolean whiteToBlack) {
while (i != j) {
int k = top, mid = (i + j) / 2;
while (k < bottom && image[k][mid] == '0') ++k;
if (k < bottom == whiteToBlack)
j = mid;
else
i = mid + 1;
}
return i;
}
private int searchRows(char[][] image, int i, int j, int left, int right, boolean whiteToBlack) {
while (i != j) {
int k = left, mid = (i + j) / 2;
while (k < right && image[mid][k] == '0') ++k;
if (k < right == whiteToBlack)
j = mid;
else
i = mid + 1;
}
return i;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
minArea(image, x, y) {
const m = image.length, n = image[0].length;
const left = this.searchColumns(image, 0, y, 0, m, true);
const right = this.searchColumns(image, y + 1, n, 0, m, false);
const top = this.searchRows(image, 0, x, left, right, true);
const bottom = this.searchRows(image, x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
searchColumns(image, i, j, top, bottom, opt) {
while (i !== j) {
const k = Math.floor((i + j) / 2);
let t = top;
while (t < bottom && image[t][k] === '0') t++;
if ((t < bottom) === opt) {
j = k;
} else {
i = k + 1;
}
}
return i;
}
searchRows(image, i, j, left, right, opt) {
while (i !== j) {
const k = Math.floor((i + j) / 2);
let l = left;
while (l < right && image[k][l] === '0') l++;
if ((l < right) === opt) {
j = k;
} else {
i = k + 1;
}
}
return i;
}
}Python решение
сопоставлено/оригиналclass Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m, n = len(image), len(image[0])
left = self.searchColumns(image, 0, y, 0, m, True)
right = self.searchColumns(image, y + 1, n, 0, m, False)
top = self.searchRows(image, 0, x, left, right, True)
bottom = self.searchRows(image, x + 1, m, left, right, False)
return (right - left) * (bottom - top)
def searchColumns(self, image: List[List[str]], i: int, j: int, top: int, bottom: int, whiteToBlack: bool) -> int:
while i != j:
k, mid = top, (i + j) // 2
while k < bottom and image[k][mid] == '0':
k += 1
if (k < bottom) == whiteToBlack:
j = mid
else:
i = mid + 1
return i
def searchRows(self, image: List[List[str]], i: int, j: int, left: int, right: int, whiteToBlack: bool) -> int:
while i != j:
k, mid = left, (i + j) // 2
while k < right and image[mid][k] == '0':
k += 1
if (k < right) == whiteToBlack:
j = mid
else:
i = mid + 1
return iGo решение
сопоставлено/оригиналpackage main
func minArea(image [][]byte, x int, y int) int {
m, n := len(image), len(image[0])
left := searchColumns(image, 0, y, 0, m, true)
right := searchColumns(image, y+1, n, 0, m, false)
top := searchRows(image, 0, x, left, right, true)
bottom := searchRows(image, x+1, m, left, right, false)
return (right - left) * (bottom - top)
}
func searchColumns(image [][]byte, i, j, top, bottom int, opt bool) int {
for i != j {
k := (i + j) / 2
t := top
for t < bottom && image[t][k] == '0' {
t++
}
if (t < bottom) == opt {
j = k
} else {
i = k + 1
}
}
return i
}
func searchRows(image [][]byte, i, j, left, right int, opt bool) int {
for i != j {
k := (i + j) / 2
l := left
for l < right && image[k][l] == '0' {
l++
}
if (l < right) == opt {
j = k
} else {
i = k + 1
}
}
return i
}Algorithm
Пример
Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6
👨💻
Алгоритм:
Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.
Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)
Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.