成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

302. Smallest Rectangle Enclosing Black Pixels

Jrain / 3684人閱讀

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

題目：
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);
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64988.html

相關(guān)文章

  • 302. Smallest Rectangle Enclosing Black Pixels

    摘要：標簽寫的是，那么考慮枚舉的方式，四個邊界的范圍分別是那么分別二分找四個邊界。的復雜度是，要好于。 302. Smallest Rectangle Enclosing Black Pixels 題目鏈接：https://leetcode.com/problems... 首先想到的是dfs查找，用left，right，up，down四個變量分別表示最左邊，最右邊最上面和最下面，最后面積就是...

    feng409 評論0 收藏0

  • JavaScript常用八種繼承方案

    摘要：原型式繼承利用一個空對象作為中介，將某個對象直接賦值給空對象構(gòu)造函數(shù)的原型。其中表示構(gòu)造函數(shù)，一個類中只能有一個構(gòu)造函數(shù)，有多個會報出錯誤如果沒有顯式指定構(gòu)造方法，則會添加默認的方法，使用例子如下。 （關(guān)注福利，關(guān)注本公眾號回復[資料]領(lǐng)取優(yōu)質(zhì)前端視頻，包括Vue、React、Node源碼和實戰(zhàn)、面試指導）showImg(https://segmentfault.com/img/rem...

    wpw 評論0 收藏0

  • 我來重新學習js 的面向?qū)ο螅╬art 5）

    摘要：無限增殖返回蘋果返回香蕉返回返回使用的新語法方法會創(chuàng)建一個新對象，使用現(xiàn)有的對象來提供新創(chuàng)建的對象的。是新增的，用來規(guī)范原型式繼承。這里將返回的新對象放到子類的原型對象里面，這樣子類就擁有了父類的原型對象，也就實現(xiàn)了方法的繼承。 這是最后的最后了，我會順便總結(jié)一下各種繼承方式的學習和理解。（老板要求什么的，管他呢） 一、繼承-組合繼承、偽經(jīng)典繼承 showImg(https://seg...

    BicycleWarrior 評論0 收藏0

  • 使用JavaScript和D3.js實現(xiàn)數(shù)據(jù)可視化

    摘要：它的全稱是數(shù)據(jù)驅(qū)動文檔，并且它被稱為一個互動和動態(tài)的數(shù)據(jù)可視化庫網(wǎng)絡(luò)。我們將使用文本編輯器和瀏覽器。出于測試目的，建議使用工具來檢查和調(diào)試和，例如或。使矩形反映數(shù)據(jù)目前，我們陣列中的所有矩形沿軸具有相同的位置，并且不代表高度方面的數(shù)據(jù)。 歡迎大家前往騰訊云+社區(qū)，獲取更多騰訊海量技術(shù)實踐干貨哦~ 本文由獨木橋先生 發(fā)表于云+社區(qū)專欄 介紹 D3.js是一個JavaScript庫。它的...

    mingde 評論0 收藏0

  • opencv python 畫圖操作/畫線/畫矩形/畫圓/畫多邊形/添加文字

    摘要：代碼畫圓圓心位置半徑應用在上面繪制的矩形內(nèi)繪制一個圓。字體類型檢查文檔以獲取支持的字體字體比例指定字體大小常規(guī)的東西，如顏色，粗細，線型等。應用我們將在圖像上寫白色的幾個字母代碼 Drawing Functions in OpenCV 學習目標函數(shù) cv2.line(), cv2.circle() , cv2.rectangle(), cv2.ellipse(), cv2.putTe...

    SQC 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<