首页 > 其他 > 详细

LeetCode "Smallest Rectangle Enclosing Black Pixels"

时间:2015-11-14 08:41:21      阅读:928      评论:0      收藏:0      [点我收藏+]

Here is the thought flow: we are trying ‘find‘ the boundary - it is a search, so binary search.

技术分享
class Solution {
  bool isRowHit(vector<vector<char>>& image, int r)
  {
    int w = image[0].size();
    for(int i = 0; i < w; i ++)
      if (image[r][i] == 1)
    return true;
    return false;
  }

  bool isColHit(vector<vector<char>>& image, int c)
  {
    int h = image.size();
    for(int i = 0; i < h; i ++)
      if (image[i][c] == 1)
    return true;
    return false;
  }
  
  int bSearchL2H(function<bool(int)> f, int a, int b)
  {
    int r = a;
    while(a<=b)
    {
      int mid = (a + b) / 2;
      if(f(mid))
      {
    r = mid;
    a = mid + 1;
      }
      else
      {
    b = mid - 1;
      }
    }
    return r;    
  }
  
  int bSearchH2L(function<bool(int)> f, int a, int b)
  {
    int r = a;
    while(a<=b)
    {
      int mid = (a + b) / 2;
      if(f(mid))
      {
    r = mid;
    b = mid - 1;
      }
      else
      {
    a = mid + 1;
      }
    }
    return r;   
  }
public:
    int minArea(vector<vector<char>>& image, int x, int y) 
    {
      int h = image.size();
      int w = image[0].size();
      
      auto fr = std::bind(&Solution::isRowHit, this, image, std::placeholders::_1);
      auto fc = std::bind(&Solution::isColHit, this, image, std::placeholders::_1);
      
      int r1 = bSearchL2H(fr, x, h - 1);
      int r0 = bSearchH2L(fr, 0, x);
      int h1 = bSearchL2H(fc, y, w - 1);
      int h0 = bSearchH2L(fc, 0, y);
    
      return (h1 - h0 + 1) * (r1 - r0 + 1);
    }
};
View Code

LeetCode "Smallest Rectangle Enclosing Black Pixels"

原文:http://www.cnblogs.com/tonix/p/4963809.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!