302. Smallest Rectangle Enclosing Black Pixels

feng409 发布于2019-08-16 10:29 / 1236人阅读

摘要：标签写的是，那么考虑枚举的方式，四个边界的范围分别是那么分别二分找四个边界。的复杂度是，要好于。

302. Smallest Rectangle Enclosing Black Pixels

题目链接：https://leetcode.com/problems...

首先想到的是dfs查找，用left，right，up，down四个变量分别表示最左边，最右边最上面和最下面，最后面积就是(right-left+1) * (down-up+1)
dfs查找的时候如果四周有没visited过的黑点就继续search，同时更新四个变量。

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        left = y; right = y;
        up = x; down = x;
        dfs(image, new boolean[image.length][image[0].length], x, y);
        
        return (right - left + 1) * (down - up + 1);
    }
    int left, right, up, down;
    int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    private void dfs(char[][] image, boolean[][] visited, int x, int y) {
        int m = image.length, n = image[0].length;
        if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || image[x][y] == "0") return;
        visited[x][y] = true;
        // update 4 boundary
        left = Math.min(left, x);  right = Math.max(right, x);
        up = Math.min(up, y); down = Math.max(down, y);
        
        for(int[] dir : dirs) {
            dfs(image, visited, x + dir[0], y + dir[1]);
        }
    }
}

标签写的是binary search，那么考虑枚举的方式，四个边界的范围分别是：left: [0, y+1], right: [y, n], up: [0, x+1], down: [x, m]
那么分别二分找四个边界。binary search的复杂度是mlogn + nlogm，要好于dfs。

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        int left, right, up, down;
        int m = image.length, n = image[0].length;
        left = binarySearch(image, 0, y, 0, m, true, true);
        right = binarySearch(image, y+1, n, 0, m, true, false);
        up = binarySearch(image, 0, x, left, right, false, true);
        down = binarySearch(image, x+1, m, left, right, false, false);
        return (right - left) * (down - up);
    }
    
    private int binarySearch(char[][] image, int start, int end, int l, int r, boolean col, boolean inc) {
        while(start < end) {
            int k = l, mid = start + (end - start) / 2;
            while(k < r && (col ? image[k][mid] : image[mid][k]) == "0") k++;
            // k < r: find black pixel: 
            // start = mid + 1 if right or down, end = mid if left or up
            if((k < r) == inc) end = mid;
            else start = mid + 1;
        }
        
        return start;
    }
}

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

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

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

302. Smallest Rectangle Enclosing Black Pixels

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

Jrain 2019-08-14 14:24 评论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