302. Smallest Rectangle Enclosing Black Pixels

Jrain 發布于2019-08-14 14:24 / 3630人閱讀

摘要：題目解答這道題我第一眼看到就想到把每個點都掃一遍，找到最小最大邊界值，然后作差相乘。但是我知道這是有冗余的，只需要邊界值的話，并不需要掃每一個點，查找的話，最快還是所以有個第二種解法，但是邊界還是很容易出錯，要分清取舍。

題目：
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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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