資訊專欄INFORMATION COLUMN
摘要：標(biāo)簽寫(xiě)的是，那么考慮枚舉的方式，四個(gè)邊界的范圍分別是那么分別二分找四個(gè)邊界。的復(fù)雜度是，要好于。
302. Smallest Rectangle Enclosing Black Pixels
題目鏈接：https://leetcode.com/problems...
首先想到的是dfs查找，用left，right，up，down四個(gè)變量分別表示最左邊，最右邊最上面和最下面，最后面積就是(right-left+1) * (down-up+1)
dfs查找的時(shí)候如果四周有沒(méi)visited過(guò)的黑點(diǎn)就繼續(xù)search，同時(shí)更新四個(gè)變量。
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]);
}
}
}
標(biāo)簽寫(xiě)的是binary search，那么考慮枚舉的方式，四個(gè)邊界的范圍分別是：left: [0, y+1], right: [y, n], up: [0, x+1], down: [x, m]
那么分別二分找四個(gè)邊界。binary search的復(fù)雜度是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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69870.html
摘要：題目解答這道題我第一眼看到就想到把每個(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 bl...
摘要：原型式繼承利用一個(gè)空對(duì)象作為中介，將某個(gè)對(duì)象直接賦值給空對(duì)象構(gòu)造函數(shù)的原型。其中表示構(gòu)造函數(shù)，一個(gè)類中只能有一個(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...
摘要：無(wú)限增殖返回蘋果返回香蕉返回返回使用的新語(yǔ)法方法會(huì)創(chuàng)建一個(gè)新對(duì)象，使用現(xiàn)有的對(duì)象來(lái)提供新創(chuàng)建的對(duì)象的。是新增的，用來(lái)規(guī)范原型式繼承。這里將返回的新對(duì)象放到子類的原型對(duì)象里面，這樣子類就擁有了父類的原型對(duì)象，也就實(shí)現(xiàn)了方法的繼承。 這是最后的最后了，我會(huì)順便總結(jié)一下各種繼承方式的學(xué)習(xí)和理解。（老板要求什么的，管他呢） 一、繼承-組合繼承、偽經(jīng)典繼承 showImg(https://seg...
摘要：它的全稱是數(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ū)專欄 介紹 D3.js是一個(gè)JavaScript庫(kù)。它的...
摘要：代碼畫(huà)圓圓心位置半徑應(yīng)用在上面繪制的矩形內(nèi)繪制一個(gè)圓。字體類型檢查文檔以獲取支持的字體字體比例指定字體大小常規(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...
閱讀 2524·2023-04-25 17:27
閱讀 1835·2019-08-30 15:54
閱讀 2377·2019-08-30 13:06
閱讀 2990·2019-08-30 11:04
閱讀 757·2019-08-29 15:30
閱讀 737·2019-08-29 15:16
閱讀 1740·2019-08-26 10:10
閱讀 3612·2019-08-23 17:02
