- 浏览: 130684 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Smallest Rectangle Enclosing Black Pixels
- 博客分类:
- Binary Search
- DFS
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.
[备注]
使用二分查找找出上下左右边界,其中上边界和左边界分别是包含了black区域最上面和最左边的pixel,而下边界和右边界分别是black区域下面和右边第一个white pixel,这样处理代码可以精简些,但我的思维方式却是僵硬地去找准确的四个边界。
另外,二分查找中左右边界调整的代码不容易理解,注释中给出了精简前的写法。
[ref]
https://leetcode.com/discuss/71898/1ms-java-binary-search-dfs-is-4ms
For example, given the following image:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2,
Return 6.
[备注]
使用二分查找找出上下左右边界,其中上边界和左边界分别是包含了black区域最上面和最左边的pixel,而下边界和右边界分别是black区域下面和右边第一个white pixel,这样处理代码可以精简些,但我的思维方式却是僵硬地去找准确的四个边界。
另外,二分查找中左右边界调整的代码不容易理解,注释中给出了精简前的写法。
[ref]
https://leetcode.com/discuss/71898/1ms-java-binary-search-dfs-is-4ms
public class Solution { // Solution 1: DFS, 4ms public int minArea1(char[][] image, int x, int y) { m = image.length; n = image[0].length; int[] edgePoints = {y, y, x, x}; recur(image, x, y, edgePoints); int width = edgePoints[1] - edgePoints[0] + 1; int height = edgePoints[3] - edgePoints[2] + 1; return width * height; } private int m, n; private int[] xDelta = {0, 0, 1, -1}; private int[] yDelta = {1, -1, 0, 0}; public void recur(char[][] image, int x, int y, int[] edgePoints) { if (image[x][y] != '1') return; // 0 or 2(visited) edgePoints[0] = Math.min(edgePoints[0], y); edgePoints[1] = Math.max(edgePoints[1], y); edgePoints[2] = Math.min(edgePoints[2], x); edgePoints[3] = Math.max(edgePoints[3], x); image[x][y] = '2'; for (int i = 0; i < 4; i++) { int x2 = x + xDelta[i]; int y2 = y + yDelta[i]; if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n) recur(image, x2, y2, edgePoints); } } // Solution 2: binary search, 1ms public int minArea(char[][] image, int x, int y) { int m = image.length, n = image[0].length; int left = binarySearch(image, 0, y, 0, m, false, true); // search the first pos which belong to black int right = binarySearch(image, y + 1, n, 0, m, false, false); // search the first pos which not belong to black int top = binarySearch(image, 0, x, 0, n, true, true); int bottom = binarySearch(image, x + 1, m, 0, n, true, false); return (right - left) * (bottom - top); } public int binarySearch(char[][] image, int lower, int upper, int min, int max, boolean horizontal, boolean goLower) { int mid; while (lower < upper) { mid = lower + (upper - lower) / 2; boolean inside = false; for (int i = min; i < max; i++) { if ((horizontal ? image[mid][i] : image[i][mid]) == '1') { inside = true; break; } } if (inside == goLower) { upper = mid; } else { lower = mid + 1; } /* if (inside) { // find black pixel, mid is in black region. if (goLower) { upper = mid; } else { lower = mid + 1; } } else { if (goLower) { lower = mid + 1; } else { upper = mid; } } */ } return lower; } }
发表评论
-
Lowest Common Ancestor of A Binary Tree
2015-09-26 11:39 535[分析] 最近公共祖先(LCA)是一个经典问题,以前没有好好 ... -
Leetcode - H-Index II
2015-09-06 09:39 1061Follow up for H-Index: What if ... -
Leetcode - Number of Islands
2015-09-02 09:40 2896[分析] BFS & DFS法详见实现。 这里阐述下u ... -
Leetcode - Strobogrammatic Number II
2015-08-22 11:34 1560A strobogrammatic number is a n ... -
Leetcode - Insert Interval
2015-08-14 10:12 588[分析] 这道题思路直接,但bug free需要费些心力。第一 ... -
Leetcode - Pow(x, n)
2015-08-11 09:45 434[分析] 数值计算类型题目,二分法或者借助位运算,本题两种方法 ... -
Leetcode - sqrt(x)
2015-08-10 21:40 774[分析] 这是一道数值计算的题目,Code Ganker中指出 ... -
Leetcode - Kth Smallest Element in BST
2015-08-11 10:26 619[分析] 思路1: 递归中序遍历,返回中序遍历中的第k个数。 ... -
Leetcode - Search for a Range
2015-08-10 08:32 466[分析] 思路1: 伪二分查找。若中间元素正好是target时 ... -
二分查找算法小结
2015-08-10 08:32 923在做leetcode二分查找类 ... -
Leetcode - Search in Rotated Sorted Array II
2015-08-09 18:47 443[分析] 同Search in Rotated Sorted ... -
Leetcode - Search in Rotated Sorted Array
2015-08-09 17:47 499[分析] 这题可以看做是Find Minimum in Rot ... -
Leetcode - Find Peak Element
2015-08-09 16:56 571[分析] 暴力法,按序扫描数组,找到peak element。 ... -
Leetcode - Find Minimum in Rotated Sorted Array II
2015-08-09 12:19 784[分析] Find Minimum in Rotated So ... -
Leetcode - Search Insert Position
2015-08-09 11:06 387[分析] 经典二分查找,下面代码实现了迭代方式,可以验证,若直 ... -
Leetcode - Minimum Size Subarray Sum
2015-07-22 21:01 735Given an array of n positive in ... -
Leetcode - Recover Binary Search Tree
2015-07-02 09:27 493Two elements of a binary search ... -
Leetcode - Validate Binary Search Tree
2015-07-01 08:31 564Given a binary tree, determine ... -
Leetcode - Count Complete Tree Nodes
2015-06-07 20:51 740Definition of a complete binary ...
相关推荐
本人在Clion中的实现的第小k元素,有期望值是O(n)代价的以及醉话情况为O(n)BFPRT算法
Android自定义dimens.xml,适应各种屏幕分辨率,300-450dp
smallest_rectangle2(Regions : : : Row, Column, Phi, Length1, Length2) draw_rectangle2:窗口有个箭头方向,这个方向就是矩形的角度Phi,和Phi方向一致的边为Length1,和Phi方向垂直的边为Length2 small
373._Find_K_Pairs_with_Smallest_Sums查找和最小的k对数字【LeetCode单题讲解系列】
我的思路是,用smallest_rectangle1_xld求一下CAD轮廓的最小外接矩形,得到矩形两个角的坐标(row1,column1),(row2,column2)。然后用set_part(windowhandle,row1,column1,row2,column2)。但是这样显示出来的轮廓...
代码:// find K-th Smallest Pair Distancepublic int smallestDistancePair(int[] nums
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 的 AC 代码
378.Kth_Smallest_Element_in_a_Sorted_Matrix有序矩阵中第K小的元素【LeetCode单
其中利用最小位置值(smallest position value,SPV)规则,使具有连续本质的微粒群算法能直接应用于调度问题,并通过动态调整参数平衡算法的全局搜索和局部搜索的能力。针对微粒群算法容易陷入局部最优的缺陷,利用...
一个用100行代码实现h264格式视频的编码器; 适合想了解参数在NAL中具体写入的同仁;
欧拉公式求长期率的matlab代码最小倍数 构建一个函数,以找到最小的正数,该正数可以被从1...smallest_multiple.js的文件中完成。 使用以下命令npm test : npm test 总共有两个测试。 让他们通过! 来自欧拉计划问题5
这个源代码是一个最小生成树的算法实现,采用的visual c++6.0
usb 通信 基于C8051 单片机代码。
快速示例示例: 用法: git clone " https://github.com/ranmocy/smallest-blogger.git "cd smallest-blogger/examplebundleguard 在浏览器中打开 。帖子标题我们对帖子的元信息使用 YAML 标头,如下所示: ---title...
smallest D j for i D j C 1 to n if AŒi Œsmallest smallest D i exchange AŒj with AŒsmallest The algorithm maintains the loop invariant that at the start of each iteration of the outer for ...
用C++实现的最小生成树的算法,很简单,但对于初学者来说很有用
labview实现两路电压采集。设计一个VI程序,进行两路电压信号采集。一路电压信号的范围0~3.3V, 每隔100ms采一个点,共采集50个点,另一路电压信号的范围为5~10V,采样间隔是50ms,共采集100个点。...
int smallest; for(int i=0;i;i++){ int smallPos = i; smallest = x[smallPos]; for(int j=i+1;j;j++){ if(x[j]<smallest) { smallPos=j; smallest = x[smallPos]; } } x[smallPos] = x...
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。