成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

302. Smallest Rectangle Enclosing Black Pixels

Jrain / 3638人閱讀

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

題目：
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把每個(gè)點(diǎn)都掃一遍，找到最小最大邊界值，然后作差相乘。但是我知道這是有冗余的，只需要邊界值的話，并不需要掃每一個(gè)點(diǎn)，查找的話，最快還是binary search,所以有個(gè)第二種解法，但是邊界還是很容易出錯(cuò)，要分清取舍。
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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64988.html

相關(guān)文章

  • 302. Smallest Rectangle Enclosing Black Pixels

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

    feng409 評(píng)論0 收藏0

  • JavaScript常用八種繼承方案

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

    wpw 評(píng)論0 收藏0

  • 我來(lái)重新學(xué)習(xí)js 的面向?qū)ο螅╬art 5）

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

    BicycleWarrior 評(píng)論0 收藏0

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

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

    mingde 評(píng)論0 收藏0

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

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

    SQC 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<