302. Smallest Rectangle Enclosing Black Pixels

Jrain 发布于2019-08-14 14:24 / 3609人阅读

摘要：题目解答这道题我第一眼看到就想到把每个点都扫一遍，找到最小最大边界值，然后作差相乘。但是我知道这是有冗余的，只需要边界值的话，并不需要扫每一个点，查找的话，最快还是所以有个第二种解法，但是边界还是很容易出错，要分清取舍。

题目：
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
"0010",
"0110",
"0100"
]
and x = 0, y = 2,
Return 6.

解答：
这道题我第一眼看到就想到dfs把每个点都扫一遍，找到最小最大边界值，然后作差相乘。但是我知道这是有冗余的，只需要边界值的话，并不需要扫每一个点，查找的话，最快还是binary search,所以有个第二种解法，但是边界还是很容易出错，要分清取舍。
1.DFS

private class Interval{
    int min, max;
    public Interval(int min, int max) {
        this.min = min;
        this.max = max;
    }
}

public void search(char[][] image, int x, int y, Interval row, Interval col, boolean[][] visited) {
    visited[x][y] = true;
    row.max = Math.max(row.max, x); 
    row.min = Math.min(row.min, x);
    col.max = Math.max(col.max, y);
    col.min = Math.min(col.min, y);
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int k = 0; k < dir.length; k++) {
        int i = x + dir[k][0], j = y + dir[k][1];
        if (i < 0 || i > image.length - 1 || j < 0 || j > image[0].length - 1) {
            continue;
        }
        if (!visited[i][j] && image[i][j] == "1") {
            search(image, i, j, row, col, visited);
        }
    }
}

public int minArea(char[][] image, int x, int y) {
    if (image == null || image.length == 0 || image[0].length == 0) return 0;
    
    int m = image.length, n = image[0].length;
    
    Interval row = new Interval(m - 1, 0);
    Interval col = new Interval(n - 1, 0);
    boolean[][] visited = new boolean[m][n];
    
    search(image, x, y, row, col, visited);
    
    return (row.max - row.min + 1) * (col.max - col.min + 1);
}

2.Binary Search

public int searchColumns(char[][] image, int i, int j, int top, int bottom, String def) {
    while (i != j) {
        int k = top, mid = (i + j) / 2;
        while (k < bottom && image[k][mid] == "0") ++k;
        if (k < bottom && def.equals("min") || k >= bottom && def.equals("max")) {
            j = mid;
        } else {
            i = mid + 1;
        }
    }
    return i;
}

public int searchRows(char[][] image, int i, int j, int left, int right, String def) {
    while (i != j) {
        int k = left, mid = (i + j) / 2;
        while (k < right && image[mid][k] == "0") k++;
        if (k < right && def.equals("min") || k >= right && def.equals("max")) {
            j = mid;
        } else {
            i = mid + 1;
        }
    }
    return i;
}

public int minArea(char[][] image, int x, int y) {
    if (image == null || image.length == 0 || image[0].length == 0) return 0;
    int m = image.length, n = image[0].length;
    int left = searchColumns(image, 0, y, 0, m, "min");
    int right = searchColumns(image, y + 1, n, 0, m, "max");
    int top = searchRows(image, 0, x, left, right, "min");
    int bottom = searchRows(image, x + 1, m, left, right, "max");
    
    return (right - left) * (bottom - top);
}

GPU云服务器云服务器 Pixels Enclosing Smallest Rectangle

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64988.html

302. Smallest Rectangle Enclosing Black Pixels

摘要：标签写的是，那么考虑枚举的方式，四个边界的范围分别是那么分别二分找四个边界。的复杂度是，要好于。 302. Smallest Rectangle Enclosing Black Pixels 题目链接：https://leetcode.com/problems... 首先想到的是dfs查找，用left，right，up，down四个变量分别表示最左边，最右边最上面和最下面，最后面积就是...

feng409 2019-08-16 10:29 评论0 收藏0
JavaScript常用八种继承方案

摘要：原型式继承利用一个空对象作为中介，将某个对象直接赋值给空对象构造函数的原型。其中表示构造函数，一个类中只能有一个构造函数，有多个会报出错误如果没有显式指定构造方法，则会添加默认的方法，使用例子如下。（关注福利，关注本公众号回复[资料]领取优质前端视频，包括Vue、React、Node源码和实战、面试指导）showImg(https://segmentfault.com/img/rem...

wpw 2019-08-23 12:42 评论0 收藏0
我来重新学习js 的面向对象（part 5）

摘要：无限增殖返回苹果返回香蕉返回返回使用的新语法方法会创建一个新对象，使用现有的对象来提供新创建的对象的。是新增的，用来规范原型式继承。这里将返回的新对象放到子类的原型对象里面，这样子类就拥有了父类的原型对象，也就实现了方法的继承。这是最后的最后了，我会顺便总结一下各种继承方式的学习和理解。（老板要求什么的，管他呢）一、继承-组合继承、伪经典继承 showImg(https://seg...

BicycleWarrior 2019-08-23 12:20 评论0 收藏0
使用JavaScript和D3.js实现数据可视化

摘要：它的全称是数据驱动文档，并且它被称为一个互动和动态的数据可视化库网络。我们将使用文本编辑器和浏览器。出于测试目的，建议使用工具来检查和调试和，例如或。使矩形反映数据目前，我们阵列中的所有矩形沿轴具有相同的位置，并且不代表高度方面的数据。欢迎大家前往腾讯云+社区，获取更多腾讯海量技术实践干货哦~ 本文由独木桥先生发表于云+社区专栏介绍 D3.js是一个JavaScript库。它的...

mingde 2019-08-23 10:56 评论0 收藏0
opencv python 画图操作/画线/画矩形/画圆/画多边形/添加文字

摘要：代码画圆圆心位置半径应用在上面绘制的矩形内绘制一个圆。字体类型检查文档以获取支持的字体字体比例指定字体大小常规的东西，如颜色，粗细，线型等。应用我们将在图像上写白色的几个字母代码 Drawing Functions in OpenCV 学习目标函数 cv2.line(), cv2.circle() , cv2.rectangle(), cv2.ellipse(), cv2.putTe...

SQC 2019-07-30 17:01 评论0 收藏0