{"id":201374,"date":"2020-11-24T23:57:28","date_gmt":"2020-11-24T15:57:28","guid":{"rendered":"http:\/\/4563.org\/?p=201374"},"modified":"2020-11-24T23:57:28","modified_gmt":"2020-11-24T15:57:28","slug":"google-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e5%8c%85%e8%a3%b9%e9%bb%91%e8%89%b2%e5%83%8f%e7%b4%a0%e7%82%b9%e7%9a%84%e6%9c%80%e5%b0%8f%e7%9f%a9%e5%bd%a2%ef%bc%88%e5%90%ab%e4%bb%a3%e7%a0%81%e4%bc%98","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=201374","title":{"rendered":"Google \u9762\u8bd5\u9898\uff1a\u5305\u88f9\u9ed1\u8272\u50cf\u7d20\u70b9\u7684\u6700\u5c0f\u77e9\u5f62\uff08\u542b\u4ee3\u7801\u4f18\u5316\u7ecf\u8fc7\uff09"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  Google \u9762\u8bd5\u9898\uff1a\u5305\u88f9\u9ed1\u8272\u50cf\u7d20\u70b9\u7684\u6700\u5c0f\u77e9\u5f62\uff08\u542b\u4ee3\u7801\u4f18\u5316\u7ecf\u8fc7\uff09               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span>  <span><i><\/i> 4<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<p>\u4e00\u4e2a\u7531\u4e8c\u8fdb\u5236\u77e9\u9635\u8868\u793a\u7684\u56fe\uff0c0 \u8868\u793a\u767d\u8272\u50cf\u7d20\u70b9\uff0c1 \u8868\u793a\u9ed1\u8272\u50cf\u7d20\u70b9\u3002\u9ed1\u8272\u50cf\u7d20\u70b9\u662f\u8054\u901a\u7684\uff0c\u5373\u53ea\u6709\u4e00\u5757\u9ed1\u8272\u533a\u57df\u3002\u50cf\u7d20\u662f\u6c34\u5e73\u548c\u7ad6\u76f4\u8fde\u63a5\u7684\uff0c\u7ed9\u4e00\u4e2a\u9ed1\u8272\u50cf\u7d20\u70b9\u7684\u5750\u6807 (x, y) \uff0c\u8fd4\u56de\u56ca\u62ec\u6240\u6709\u9ed1\u8272\u50cf\u7d20\u70b9\u7684\u77e9\u9635\u7684\u6700\u5c0f\u9762\u79ef\u3002<\/p>\n<p>\u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n<h2>\u6837\u4f8b 1:<\/h2>\n<pre><code>\u8f93\u5165\uff1a[\"0010\",\"0110\",\"0100\"]\uff0cx=0\uff0cy=2 \u8f93\u51fa\uff1a6 \u89e3\u91ca\uff1a \u77e9\u9635\u5de6\u4e0a\u89d2\u5750\u6807\u662f(0, 1), \u53f3\u4e0b\u89d2\u7684\u5750\u6807\u662f(2, 2) <\/code><\/pre>\n<h2>\u6837\u4f8b 2:<\/h2>\n<pre><code>\u8f93\u5165\uff1a[\"1110\",\"1100\",\"0000\",\"0000\"], x = 0, y = 1 \u8f93\u51fa\uff1a6 \u89e3\u91ca\uff1a \u77e9\u9635\u5de6\u4e0a\u89d2\u5750\u6807\u662f(0,  0), \u53f3\u4e0b\u89d2\u5750\u6807\u662f(1, 3) <\/code><\/pre>\n<h2>\u7b97\u6cd5\uff1a\u4e8c\u5206<\/h2>\n<ul>\n<li>\u5173\u4e8e BFS \u548c DFS BFS \u548c DFS \u7684\u505a\u6cd5\u5c31\u662f\u904d\u5386\u8fd9\u4e2a\u9ed1\u8272\u50cf\u7d20\u8fde\u901a\u5757\uff0c\u5f97\u5230\u5404\u4e2a\u65b9\u5411\u4e0a\u7684\u5750\u6807\u6781\u503c\uff0c\u65f6\u95f4\u590d\u6742\u5ea6 O(K)\uff0cK \u4e3a\u9ed1\u8272\u50cf\u7d20\u70b9\u4e2a\u6570\uff0c\u8fd9\u79cd\u505a\u6cd5\u5728\u9ed1\u8272\u50cf\u7d20\u70b9\u6570\u91cf\u5de8\u5927\u65f6\u6548\u7387\u6781\u4f4e\u3002<\/li>\n<\/ul>\n<p>\u53e6\u5916\u5173\u4e8e BFS \u548c DFS \u5982\u4f55\u9009\u62e9\uff0c\u8fd9\u91cc\u5efa\u8bae\u4f7f\u7528 BFS\uff0c\u56e0\u4e3a DFS \u4f1a\u5360\u7528\u5927\u91cf\u7684\u7cfb\u7edf\u6808\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u4e0a\u8981\u52a3\u4e8e BFS \u4e0b\u9762\u6211\u4eec\u6765\u4ecb\u7ecd\u4e00\u79cd\u5728\u5927\u90e8\u5206\u60c5\u51b5\u4e0b\u7a7a\u95f4\u548c\u65f6\u95f4\u4e0a\u5747\u4f18\u4e8e DFS \u548c BFS \u7684\u7b97\u6cd5\u2014\u2014\u4e8c\u5206<\/p>\n<h2>\u7b97\u6cd5\u601d\u8def<\/h2>\n<ul>\n<li>\u4e8c\u5206\u627e\u5230\u56db\u4e2a\u65b9\u5411\u4e0a\u9ed1\u8272\u50cf\u7d20\u70b9\u51fa\u73b0\u7684\u5750\u6807\u6781\u503c<\/li>\n<\/ul>\n<h2>\u4ee3\u7801\u601d\u8def<\/h2>\n<ul>\n<li>\u8fd9\u8fb9\u4ee5\u4e8c\u5206\u6700\u5de6\u4fa7\u9ed1\u8272\u50cf\u7d20\u4e3a\u4f8b<\/li>\n<\/ul>\n<ol>\n<li>\u8bbe\u7f6e\u5de6\u6307\u9488\u4e3a 0\uff0c\u53f3\u6307\u9488\u4e3a y\uff0c\u56e0\u4e3a\u6211\u4eec\u4fdd\u8bc1 y \u5217\u4e0a\u5b58\u5728\u9ed1\u8272\u50cf\u7d20\uff0c\u6700\u5de6\u4fa7\u9ed1\u8272\u50cf\u7d20\u6240\u5728\u5217\u4e00\u5b9a\u5728 y \u6216\u8005\u5176\u5de6\u4fa7<\/li>\n<li>\u82e5 mid \u6240\u5728\u5217\u5b58\u5728\u9ed1\u8272\u50cf\u7d20\uff0c\u8bf4\u660e\u6700\u5de6\u4fa7\u9ed1\u8272\u50cf\u7d20\u5728 mid \u5217\u6216\u8005\u5176\u5de6\u4fa7\uff0cr = mid\uff0c\u5426\u5219 l = mid<\/li>\n<li>\u5224\u65ad l \u5217\u662f\u5426\u5b58\u5728\u9ed1\u8272\u50cf\u7d20\uff0c\u82e5\u5b58\u5728\u5219 left = l\uff0c\u5426\u5219 left = r \u3002\u6ce8\u610f\u4e00\u5b9a\u8981\u5148\u5224 l \u5217\uff0c\u56e0\u4e3a r \u53ef\u80fd\u5b58\u5728\u9ed1\u8272\u50cf\u7d20\uff0c\u4f46\u5e76\u4e0d\u662f\u6700\u5de6\u4fa7<\/li>\n<\/ol>\n<ul>\n<li>\u4ee5\u6b64\u7c7b\u63a8\u7ee7\u7eed\u627e\u5230\u6700\u53f3\u4fa7\uff0c\u6700\u4e0a\u4fa7\uff0c\u6700\u4e0b\u4fa7\u7684\u9ed1\u8272\u50cf\u7d20\u6240\u5728\u5217\u6216\u884c<\/li>\n<li>\u8ba1\u7b97\u9762\u79ef(right &#8211; left + 1) * (bottom &#8211; top + 1)\u5e76\u5c06\u5176\u8fd4\u56de<\/li>\n<li>\u8fd9\u91cc\u63d0\u4e00\u79cd\u4f18\u5316\uff0c\u627e\u5230\u6700\u5de6\u5904\u548c\u6700\u53f3\u5904\u7684\u9ed1\u8272\u50cf\u7d20\u4f4d\u7f6e left \u548c right \u540e\uff0c\u5728\u627e\u6700\u4e0a\u548c\u6700\u4e0b\u5750\u6807\u65f6\uff0c\u5bf9\u4e8e\u884c\u7684\u5224\u65ad\u53ea\u9700\u8981\u626b\u63cf[row,left]\u5230[row,right]\u5373\u53ef<\/li>\n<\/ul>\n<h2>\u590d\u6742\u5ea6\u5206\u6790<\/h2>\n<ul>\n<li>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(1)<\/li>\n<li>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(MlogN+NlogM)\uff08\u6700\u574f\u60c5\u51b5\uff09 \u6700\u574f\u60c5\u51b5\u5373\u53ea\u6709\u4e00\u4e2a\u9ed1\u8272\u50cf\u7d20\u70b9\uff0c\u90a3\u4e48\u6bcf\u6b21\u5224\u65ad\u5217\u4e0a\u6216\u884c\u4e0a\u662f\u5426\u53c8\u9ed1\u8272\u50cf\u7d20\u70b9\u9700\u8981\u626b\u63cf\u5b8c\u6574\u5217\u6216\u6574\u884c \u4e8c\u5206\u7684\u505a\u6cd5\u5f53\u9047\u5230\u9ed1\u8272\u50cf\u7d20\u70b9\u5f88\u5c11\u4e14\u7ed9\u51fa\u7684\u77e9\u9635\u5f88\u5927\u65f6\u6548\u7387\u4f1a\u53d8\u5f97\u6781\u4f4e\uff0c\u800c\u6b64\u65f6 BFS \u7684\u6548\u7387\u4f1a\u76f8\u5bf9\u9ad8\u5f88\u591a<\/li>\n<\/ul>\n<h2>\u540e\u8bb0<\/h2>\n<p>\u80fd\u5426\u505a\u5230\u5728\u4efb\u4f55\u60c5\u51b5\u4e0b\u6548\u7387\u90fd\u663e\u5f97\u76f8\u5bf9\u8f83\u9ad8\u5462\uff1f\u6211\u4eec\u53ef\u4ee5\u8bbe\u5b9a\u4e00\u4e2a\u9608\u503c cnt\uff0c\u5148\u8fdb\u884c BFS \u904d\u5386\uff0c\u5f53\u904d\u5386\u6b21\u6570\u8fbe\u5230 cnt \u65f6\u6539\u7528\u4e8c\u5206\u6cd5\u8fdb\u884c\u8ba1\u7b97<\/p>\n<pre><code> public class Solution {      \/**      * @param image: a binary matrix with '0' and '1'      * @param x: the location of one of the black pixels      * @param y: the location of one of the black pixels      * @return: an integer      *\/      public int minArea(char[][] image, int x, int y) {         if (image == null || image.length == 0 || image[0].length == 0) {             return 0;         }          int n = image.length;         int m = image[0].length;         int l = 0, r = 0;         int left = 0, right = 0, top = 0, bottom = 0;         \/\/\u4e8c\u5206\u6700\u5de6\u4fa7\u9ed1\u8272\u50cf\u7d20\u5750\u6807         l = 0;         r = y;         while (l + 1 &lt; r) {             int mid = l + (r - l) \/ 2;             if (check_column(image, mid)) {                 r = mid;             } else {                 l = mid;             }         }         if (check_column(image, l)){             left = l;         }else{             left = r;         }         \/\/\u4e8c\u5206\u6700\u53f3\u4fa7\u9ed1\u8272\u50cf\u7d20\u5750\u6807         l = y;         r = m - 1         while (l + 1 &lt; r) {             int mid = l + (r - l) \/ 2;             if (check_column(image, mid)) {                 l = mid;             } else {                 r = mid;             }         }         if (check_column(image, r)) {             right = r;         }else{             right = l;         }         \/\/\u4e8c\u5206\u6700\u4e0a\u4fa7\u9ed1\u8272\u50cf\u7d20\u5750\u6807         l = 0;         r = x;         while (l + 1 &lt; r) {             int mid = l + (r - l) \/ 2;             if (check_row(image, mid, left, right)) {                 r = mid;             } else {                 l = mid;             }         }                 if (check_row(image, l, left, right)) {             top = l;         }else{             top = r;         }         \/\/\u4e8c\u5206\u6700\u4e0b\u4fa7\u9ed1\u8272\u50cf\u7d20\u5750\u6807         l = x;         r = n - 1;         while (l + 1 &lt; r) {             int mid = l + (r - l) \/ 2;             if (check_row(image, mid, left, right)) {                 l = mid;             } else {                 r = mid;             }         }                if (check_row(image, r, left, right)) {             bottom = r;         }else{             bottom = l;         }         return (right - left + 1) * (bottom - top + 1);     }      \/\/\u5224\u65ad\u5217\u4e0a\u662f\u5426\u5b58\u5728\u9ed1\u8272\u50cf\u7d20     private boolean check_column(char[][] image, int col) {         for (int i = 0; i &lt; image.length; i++) {             if (image[i][col] == '1') {                 return true;             }         }         return false;     }     \/\/\u5224\u65ad\u884c\u4e0a\u662f\u5426\u5b58\u5728\u9ed1\u8272\u50cf\u7d20     private boolean check_row(char[][] image, int row ,int left ,int right) {         for (int j = left; j &lt;= right; j++) {             if (image[row][j] == '1') {                 return true;             }         }         return false;     } } <\/code><\/pre>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>Google \u9762\u8bd5\u9898\uff1a\u5305\u88f9\u9ed1\u8272\u50cf\u7d20&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201374"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=201374"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201374\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=201374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=201374"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=201374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}