{"id":154422,"date":"2020-09-10T07:39:26","date_gmt":"2020-09-09T23:39:26","guid":{"rendered":"http:\/\/4563.org\/?p=154422"},"modified":"2020-09-10T07:39:26","modified_gmt":"2020-09-09T23:39:26","slug":"google-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e5%b2%9b%e5%b1%bf%e7%9a%84%e4%b8%aa%e6%95%b0-ii","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=154422","title":{"rendered":"Google \u9762\u8bd5\u9898\uff1a\u5c9b\u5c7f\u7684\u4e2a\u6570 II"},"content":{"rendered":"
\n
\n
\n

Google \u9762\u8bd5\u9898\uff1a\u5c9b\u5c7f\u7684\u4e2a\u6570 II <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 3<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u7ed9\u5b9a n, m, \u5206\u522b\u4ee3\u8868\u4e00\u4e2a\u4e8c\u7ef4\u77e9\u9635\u7684\u884c\u6570\u548c\u5217\u6570, \u5e76\u7ed9\u5b9a\u4e00\u4e2a\u5927\u5c0f\u4e3a k \u7684\u4e8c\u5143\u6570\u7ec4 A. \u521d\u59cb\u4e8c\u7ef4\u77e9\u9635\u5168 0. \u4e8c\u5143\u6570\u7ec4 A \u5185\u7684 k \u4e2a\u5143\u7d20\u4ee3\u8868 k \u6b21\u64cd\u4f5c, \u8bbe\u7b2c i \u4e2a\u5143\u7d20\u4e3a (A[i].x, A[i].y), \u8868\u793a\u628a\u4e8c\u7ef4\u77e9\u9635\u4e2d\u4e0b\u6807\u4e3a A[i].x \u884c A[i].y \u5217\u7684\u5143\u7d20\u7531\u6d77\u6d0b\u53d8\u4e3a\u5c9b\u5c7f. \u95ee\u5728\u6bcf\u6b21\u64cd\u4f5c\u4e4b\u540e, \u4e8c\u7ef4\u77e9\u9635\u4e2d\u5c9b\u5c7f\u7684\u6570\u91cf. \u4f60\u9700\u8981\u8fd4\u56de\u4e00\u4e2a\u5927\u5c0f\u4e3a k \u7684\u6570\u7ec4.<\/p>\n

    \n
  • \u8bbe\u5b9a 0 \u8868\u793a\u6d77\u6d0b, 1 \u4ee3\u8868\u5c9b\u5c7f, \u5e76\u4e14\u4e0a\u4e0b\u5de6\u53f3\u76f8\u90bb\u7684 1 \u4e3a\u540c\u4e00\u4e2a\u5c9b\u5c7f.<\/li>\n<\/ul>\n

    \u70b9\u6b64\u505a\u9898<\/p>\n

    \u6837\u4f8b 1:<\/h2>\n
    \u8f93\u5165: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]] \u8f93\u51fa: [1,1,2,2]  \u89e3\u91ca:  0.  00000     00000     00000     00000 1.  00000     01000     00000     00000 2.  01000     01000     00000     00000 3.  01000     01000     00000     00010 4.  01000     01000     00000     00011 <\/code><\/pre>\n
    \u6837\u4f8b 2:<\/h2>\n
    \u8f93\u5165: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]] \u8f93\u51fa: [1,1,2,2] <\/code><\/pre>\n
    \u65b9\u6cd5\u4e00\uff1a\u66b4\u529b\u505a\u6cd5<\/h2>\n
      \n
    • \u6bcf\u6b21\u64cd\u4f5c\u540e\u505a\u4e00\u904d bfs<\/li>\n
    • \u679a\u4e3e\u4e4b\u524d\u672a\u8bbf\u95ee\u8fc7\u7684\u5c9b\u5c7f\uff0c\u5c9b\u5c7f\u6570\u91cf\u52a0\u4e00<\/li>\n
    • \u538b\u5165\u961f\u5217\u4e2d\u5f00\u59cb bfs<\/li>\n
    • \u4ece bfs \u7684\u961f\u5217\u4e2d\u53d6\u51fa\u961f\u9996\uff0c\u4e0a\u4e0b\u5de6\u53f3\u56db\u4e2a\u65b9\u5411\u6269\u5c55\u90a3\u4e9b\u6ca1\u6709\u8bbf\u95ee\u8fc7\u7684\u5c9b\u5c7f\uff0c\u6269\u5c55\u4e4b\u540e\u538b\u5165\u961f\u5217\u4e2d<\/li>\n
    • \u91cd\u590d\u6267\u884c\u7b2c\u56db\u6b65\uff0c\u4e00\u76f4\u5230\u961f\u5217\u4e3a\u7a7a<\/li>\n
    • \u8fd9\u6837\u4ece\u4e00\u4e2a\u5c9b\u5c7f\u51fa\u53d1\uff0c\u641c\u7d22\u4e86\u5b83\u80fd\u5230\u7684\u6240\u6709\u5c9b\u5c7f\uff0c\u8fd9\u4e9b\u5c9b\u5c7f\u5c06\u5408\u5e76\u6210\u4e00\u4e2a\u5927\u5c9b\u5c7f<\/li>\n
    • \u91cd\u65b0\u56de\u5230\u7b2c\u4e8c\u6b65<\/li>\n<\/ul>\n
      \u65b9\u6cd5\u4e8c\uff1a\u5e76\u67e5\u96c6\u7ef4\u62a4<\/h2>\n
      \u5e76\u67e5\u96c6\u662f\u6307\u7528\u96c6\u5408\u91cc\u7684\u4e00\u4e2a\u5143\u7d20\u6765\u5f53\u8fd9\u4e2a\u96c6\u5408\u7684\u4ee3\u8868\u5143 \u5982\u679c\u4e24\u4e2a\u5143\u7d20\u6240\u5728\u96c6\u5408\u7684\u4ee3\u8868\u5143\u76f8\u540c\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u80fd\u77e5\u9053\u8fd9\u4e24\u4e2a\u5143\u7d20\u5728\u4e00\u4e2a\u96c6\u5408\u5f53\u4e2d\u3002 \u5982\u679c\u6211\u4eec\u60f3\u5408\u5e76\u4e24\u4e2a\u96c6\u5408\uff0c\u53ea\u9700\u8981\u628a\u5176\u4e2d\u4e00\u4e2a\u96c6\u5408\u7684\u4ee3\u8868\u5143\u6539\u4e3a\u7b2c\u4e8c\u4e2a\u96c6\u5408\u7684\u4ee3\u8868\u5143<\/p>\n
        \n
      • \u8fd9\u9053\u9898\u4e2d\uff0c\u6bcf\u6b21\u5c06\u4e00\u4e2a\u6d77\u6d0b i \u53d8\u6210\u4e00\u4e2a\u5c9b\u5c7f i\uff0c\u90a3\u4e48\u5148\u5c06\u5c9b\u5c7f\u6570\u91cf\u52a0\u4e00<\/li>\n
      • \u518d\u4f9d\u6b21\u67e5\u770b\u8fd9\u4e2a\u5c9b\u5c7f\u7684\u56db\u5468\u7684\u56db\u4e2a\u65b9\u683c\n
          \n
        • \u5982\u679c\u76f8\u90bb\u7684\u65b9\u683c j \u4e5f\u662f\u5c9b\u5c7f\uff0c\u90a3\u4e48\u5148\u5224\u65ad i \u662f\u4e0d\u662f\u548c j \u5728\u540c\u4e00\u4e2a\u96c6\u5408\u91cc<\/li>\n
        • \u5982\u679c\u4e0d\u662f\u5728\u4e00\u4e2a\u96c6\u5408\u91cc\uff0c\u90a3\u4e48 i j \u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\u5c31\u662f\u8fde\u901a\u7684\uff0c\u53ef\u4ee5\u5408\u5e76\u7b97\u4e3a\u4e00\u4e2a\u96c6\u5408,\u7136\u540e\u8ba9\u5c9b\u5c7f\u6570\u91cf-1 \u3002<\/li>\n
        • \u5982\u679c\u5df2\u7ecf\u662f\u5728\u540c\u4e00\u4e2a\u96c6\u5408\u91cc\u4e86\uff0c\u90a3\u5c31\u4e0d\u7528\u5728\u8fdb\u884c\u4efb\u4f55\u64cd\u4f5c<\/li>\n<\/ul>\n<\/li>\n
        • \u6211\u4eec\u53ea\u8981\u8ba9 i \u6240\u5728\u96c6\u5408\u7684\u4ee3\u8868\u5143\u6539\u4e3a j \u6240\u5728\u96c6\u5408\u7684\u4ee3\u8868\u5143\u5c31\u5b8c\u6210\u4e86\u5408\u5e76\u64cd\u4f5c\u3002<\/li>\n
        • \u6ce8\u610f\uff1a\u6570\u636e\u4e2d\u6709\u53ef\u80fd\u591a\u6b21\u5c06\u4e00\u4e2a\u4f4d\u7f6e\u53d8\u6210\u5c9b\u5c7f\uff0c\u7b2c\u4e00\u6b21\u4ee5\u540e\u7684\u64cd\u4f5c\u90fd\u662f\u65e0\u6548\u7684\u64cd\u4f5c\uff0c\u8df3\u8fc7\u5c31\u597d\u4e86<\/li>\n
        • \u6ce8\u610f 2\uff1ax->x1->x2->x3->x4->x5->x6->……..->\u4ee3\u8868\u5143 T \u6211\u4eec\u5728\u7b2c\u4e00\u6b21\u5bfb\u627e x \u7684\u4ee3\u8868\u5143\u7684\u56de\u6eaf\u7684\u65f6\u5019 \u987a\u4fbf\u628a\u8fd9\u6761\u8def\u5f84\u7684\u6240\u6709 xi \u7684\u7236\u4eb2\u6539\u4e3a\u4e86\u4ee3\u8868\u5143 T \u8fd9\u6837\u6211\u4eec\u4ee5\u540e\u518d\u6b21\u8bbf\u95ee x….x6….T \u8fd9\u6761\u94fe\u4e0a\u7684\u5185\u5bb9\u65f6\u5019\u5c31\u53ef\u4ee5\u5f88\u5feb\u7684\u5f97\u5230\u7b54\u6848<\/li>\n<\/ul>\n
          \/\/\u4f2a\u4ee3\u7801 for i 1:n fa[i]=i \/\/\u4f2a\u4ee3\u7801\uff0c\u4e00\u5f00\u59cb\u8ba9\u6240\u6709\u7684\u7236\u4eb2\u90fd\u662f\u672c\u8eab \/\/\u6211\u4eec\u89c4\u5b9a\u4ee3\u8868\u5143\u7684\u7236\u4eb2\u4e3a\u672c\u8eab\uff0c\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u7684\u7236\u4eb2\u4e0d\u662f\u672c\u8eab\uff0c\u8bf4\u662f\u5b83\u5728\u4e00\u4e2a\u5143\u7d20\u4e2a\u6570\u5927\u4e8e 1 \u7684\u96c6\u5408\u4e2d\uff0c\u800c\u4e14\u8fd9\u4e2a\u8282\u70b9\u5e76\u4e0d\u662f\u4ee3\u8868\u5143 function find(x) \/\/\u5bfb\u627e x \u6240\u5728\u96c6\u5408\u7684\u4ee3\u8868\u5143 if(fa[x]==x)
           return x; \/\/x \u662f\u4ee3\u8868\u5143\uff0c\u76f4\u63a5\u8fd4\u56de else return fa[x]=find(fa[x]) \/\/x \u4e0d\u662f\u4ee3\u8868\u5143\uff0c\u5bfb\u627e x \u7684\u7236\u4eb2\u7684\u4ee3\u8868\u5143\u662f\u8c01\uff0c\u5e76\u4e14\u76f4\u63a5\u628a\u4ee3\u8868\u5143\u8d4b\u503c\u7ed9 x \u7684\u7236\u4eb2 function uniue \uff08 x,y \uff09\/\/\u5408\u5e76\u4e24\u4e2a\u96c6\u5408 fa[find(x)]=find(y)<\/p>\n
          \u590d\u6742\u5ea6\u5206\u6790<\/h2>\n
          \u65f6\u95f4\u590d\u6742\u5ea6<\/h3>\n
          \u66b4\u529b\u505a\u6cd5<\/h4>\n
          \u6bcf\u6b21\u64cd\u4f5c\u90fd\u4f1a\u505a\u4e00\u904d bfs\uff0c\u505a\u4e00\u904d bfs \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(NM) \u6240\u4ee5\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(KNM)\uff0cK \u662f\u64cd\u4f5c\u6b21\u6570\uff0cNM \u662f\u5730\u56fe\u957f\u548c\u5bbd \u5e76\u67e5\u96c6 \u6bcf\u6b21\u67e5\u8be2\u4ee3\u8868\u5143\u5747\u644a\u662f O(\u03b1) \u03b1\u4ee3\u8868\u53cd\u963f\u514b\u66fc\u51fd\u6570\uff0c\u53cd\u963f\u514b\u66fc\u51fd\u6570\u662f\u6e10\u8fdb\u589e\u957f\u5f88\u6162\u5f88\u6162\u7684\uff0c\u6211\u4eec\u53ef\u4ee5\u8fd1\u4f3c\u7684\u8ba4\u4e3a\u6bcf\u6b21\u67e5\u8be2\u662f O(1)\u7684\u590d\u6742\u5ea6 \u6211\u4eec\u4e00\u5171\u6709 K \u6b21\u64cd\u4f5c\uff0c\u6bcf\u6b21\u64cd\u4f5c\u6700\u591a\u5e76\u67e5\u96c6\u67e5\u8be2 4 \u6b21\uff0c\u5e76\u67e5\u96c6\u5408\u5e76 4 \u6b21,\u6240\u4ee5\u6211\u4eec\u6700\u7ec8\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(K)\u7684<\/p>\n
          \u7a7a\u95f4\u590d\u6742\u5ea6<\/h3>\n
          n\uff0cm \u662f\u8f93\u5165\u6570\u7ec4 \u7684\u957f\u548c\u5bbd \u6211\u4eec\u9700\u8981\u4e00\u4e2a fa \u6570\u7ec4\u5927\u5c0f\u4e3a nm\uff0c\u4e00\u4e2a vis \u6570\u7ec4\uff08\u6807\u8bb0\u8be5\u70b9\u6709\u6ca1\u6709\u53d8\u6210\u5c9b\u5c7f\uff09\uff0c\u6240\u4ee5\u7a7a\u95f4\u590d\u6742\u5ea6\u662f O(nm)<\/p>\n
          public class Solution {     \/**      * @param n: An integer      * @param m: An integer      * @param operators: an array of point      * @return: an integer array      *\/      public int find(int []fa, int x) {         if(x == fa[x]) {             return x;         } else {             return fa[x] = find(fa, fa[x]);         }     }     public int calc(int x, int y, int n, int m) {         return x * m + y;     }     public List<Integer> numIslands2(int n, int m, Point[] operators) {          \/\/ write your code here         List<Integer> ans = new ArrayList<>();         int [] fa = new int [n * m + 5];         Map<Integer, Boolean>visited = new HashMap<Integer, Boolean>();         int cnt = 0;         for(int i = 0; i < n; i++) {             for(int j = 0; j < m; j++) {                 fa[calc(i, j, n, m)] = calc(i, j, n, m);                 visited.put(calc(i, j, n, m), false);             }         }         \/\/\u884c\u8d70\u6570\u7ec4\uff0c\u7528\u4e8e\u904d\u5386 i \u5c9b\u5c7f\u7684\u56db\u5468\u56db\u4e2a\u65b9\u5411\u7684\u5c9b\u5c7f\u4e0b\u6807         int[] zx = {0, 0, 1, -1};         int[] zy = {1, -1, 0, 0};          if(operators == null) {             return ans;         }         for(int i = 0; i < operators.length; i++) {                int x = operators[i].x, y = operators[i].y;             \/\/ \u7b2c i \u6b21\u64cd\u4f5c\u7684\u70b9 \u5df2\u7ecf\u662f\u5c9b\u5c7f\u4e86\uff0c\u8df3\u8fc7\u5c31\u597d\u4e86             if(visited.get(calc(x, y, n, m)) == true) {                 ans.add(cnt);                 continue;             }             \/\/\u7b2c i \u6b21\u64cd\u4f5c\u7684\u70b9 \u51fa\u73b0\u4e86\u65b0\u7684\u5c9b\u5c7f             cnt++;             \/\/\u904d\u5386\u8fd9\u4e2a\u5c9b\u5c7f\u7684\u56db\u5468\u56db\u4e2a\u65b9\u5411             for(int k = 0; k < 4; k++) {                 int nx = x + zx[k];                 int ny = y + zy[k];                 \/\/\u5224\u65ad\u5f80\u56db\u5468\u8d70\u6709\u6ca1\u6709\u8d70\u8d8a\u754c\uff0c\u6216\u8005\u8d70\u5230\u6d77\u6d0b\u91cc\uff0c\u8d8a\u754c\u6216\u8005\u8d70\u5230\u6d77\u6d0b\u90fd\u662f\u6ca1\u6709\u7684\u72b6\u6001                 if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited.get(calc(nx, ny, n, m)) == false) {                     continue;                 }                 \/\/\u5224\u65ad\u56db\u5468\u7684\u5c9b\u5c7f\u662f\u4e0d\u662f\u548c\u5f53\u524d\u7b2c i \u6b21\u64cd\u4f5c\u7684\u5c9b\u5c7f \u5df2\u7ecf\u5728\u4e00\u4e2a\u96c6\u5408\u4e86                 if(find(fa, calc(x, y, n, m)) == find(fa, calc(nx, ny, n, m))) {                     continue;                 }                 \/*                 \u5982\u679c\u4e0d\u662f\u5728\u4e00\u4e2a\u96c6\u5408\u91cc\uff0c\u90a3\u4e48 i j \u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\u5c31\u662f\u8fde\u901a\u7684\uff0c\u53ef\u4ee5\u5408\u5e76\u7b97\u4e3a\u4e00\u4e2a\u96c6\u5408,\u7136\u540e\u8ba9\u5c9b\u5c7f\u6570\u91cf-1 \u3002                 \u6211\u4eec\u53ea\u8981\u8ba9 i \u6240\u5728\u96c6\u5408\u7684\u4ee3\u8868\u5143\u6539\u4e3a j \u6240\u5728\u96c6\u5408\u7684\u4ee3\u8868\u5143\u5c31\u5b8c\u6210\u4e86\u5408\u5e76\u64cd\u4f5c                 *\/                 else {                     cnt--;                     fa[find(fa, calc(x, y, n, m))] = find(fa, calc(nx, ny, n, m));                 }             }             \/\/\u6807\u8bb0\u5b83\u662f\u4e2a\u5c9b\u5c7f             visited.put(calc(x, y, n, m), true);             ans.add(cnt);         }         return ans;     } } <\/code><\/pre>\n<\/p><\/div>\n
           \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (4<\/span>)        <\/div>\n
           <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
            \n
          • \n
            \n
            \n
             \u8cc7\u6df1\u5927\u4f6c : yukong <\/span>  <\/div>\n
             <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                         dfs + \u67d3\u8272                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
          • \n
            \n
            \n
             \u8cc7\u6df1\u5927\u4f6c : no1xsyzy <\/span>  <\/div>\n
             <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                         \u65f6\u95f4\u590d\u6742\u5ea6\u90a3\u5757\u6392\u7248\u6709\u70b9\u95ee\u9898
            \u53e6\u5916\uff0cdocstring \u548c\u51fd\u6570\u672c\u4f53\u88ab\u4e24\u4e2a\u5e2e\u52a9\u51fd\u6570\u7ed9\u751f\u751f\u626f\u5f00\u6765\u4e86\u2026\u2026                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
          • \n
            \n
            \n
             \u8cc7\u6df1\u5927\u4f6c : mightofcode <\/span>  <\/div>\n
             <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                         \u5e76\u67e5\u96c6                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
          • \n
            \n
            \n
             \u8cc7\u6df1\u5927\u4f6c : mahaonan1994 <\/span>  <\/div>\n
             <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                         @Livid                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
          • \n","protected":false},"excerpt":{"rendered":"
            Google \u9762\u8bd5\u9898\uff1a\u5c9b\u5c7f\u7684\u4e2a\u6570 …<\/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\/154422"}],"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=154422"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/154422\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=154422"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=154422"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=154422"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}