LeetCode/src/question/Question200.java · Roderland/algorithm

代码拉取完成,页面将自动刷新

扫描微信二维码支付

取消

支付完成

richgiteeai

Watch

不关注关注所有动态仅关注版本发行动态关注但不提醒动态

1 Star 0 Fork 0

Roderland/algorithm

代码 Issues 0 Pull Requests 0 Wiki 统计流水线

服务

加入 Gitee

与超过 1400万开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)

免费加入

已有帐号? 立即登录

文件

master

分支 (1)

管理

master

该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。

项目仓库所选许可证以仓库主分支所使用许可证为准

克隆/下载

HTTPS SSH SVN SVN+SSH 下载ZIP

提示

下载代码请复制以下命令到终端执行

为确保你提交的代码身份被 Gitee 正确识别,请执行以下命令完成配置

git config --global user.name userName 
git config --global user.email userEmail

初次使用 SSH 协议进行代码克隆、推送等操作时,需按下述提示完成 SSH 配置

1 生成 RSA 密钥

2 获取 RSA 公钥内容,并配置到 SSH公钥中

在 Gitee 上使用 SVN,请访问使用指南

使用 HTTPS 协议时,命令行会出现如下账号密码验证步骤。基于安全考虑,Gitee 建议配置并使用私人令牌替代登录密码进行克隆、推送等操作

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # 私人令牌

分支 1

标签 0

algorithm

LeetCode

src

question

Question200.java

Question200.java 3.80 KB

package question;

import java.util.Arrays;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question200 {
 public static void main(String[] args) {
 char[][] ints = {
 {'1', '0', '0', '1', '1', '1', '0', '1', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'}, {
 '1', '0', '0', '1', '1', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '0', '1', '0'}, {
 '0', '0', '0', '1', '1', '1', '1', '0', '1', '0', '1', '1', '0', '0', '0', '0', '1', '0', '1', '0'}, {
 '0', '0', '0', '1', '1', '0', '0', '1', '0', '0', '0', '1', '1', '1', '0', '0', '1', '0', '0', '1'}, {
 '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'}, {
 '1', '0', '0', '0', '0', '1', '0', '1', '0', '1', '1', '0', '0', '0', '0', '0', '0', '1', '0', '1'}, {
 '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'}, {
 '0', '0', '0', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '1', '1', '0', '1', '1', '1', '0'}, {
 '0', '0', '0', '0', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1'}, {
 '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '1', '0'}, {
 '1', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '1', '0', '1', '0'}, {
 '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '1', '0', '1', '1', '1', '0', '1', '1', '0', '0'}, {
 '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1'}, {
 '0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '1', '1', '1', '1', '1', '0', '1', '0', '0', '0'}, {
 '0', '0', '1', '1', '1', '0', '0', '0', '1', '1', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0'}, {
 '1', '0', '0', '1', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '1'}, {
 '1', '0', '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0'}, {
 '0', '1', '1', '0', '0', '0', '1', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0'}, {
 '0', '1', '0', '0', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '0', '1', '0', '0', '1', '1'}, {
 '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1', '0', '0', '0', '1', '1', '0', '0', '0'}
 };
 System.out.println(new Question200().numIslands(ints));
 }

public int numIslands(char[][] grid) {
 int m = grid.length;
 int n = grid[0].length;
 UnionFind u = new UnionFind(n * m);
 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 if (grid[i][j] == '1') {
 int x = i * n + j;
 u.setP(x);
 if (x - 1 >= 0 && u.p[x - 1] >= 0) {
 if (x / n == (x - 1) / n) u.merge(x, x - 1);
 }
 if (x - n >= 0 && u.p[x - n] >= 0) u.merge(x, x - n);
 }
 }
 }
 return u.count;
 }

private static class UnionFind {
 int[] p;
 int count;

public UnionFind(int n) {
 p = new int[n];
 Arrays.fill(p, -1);
 count = 0;
 }

public int find(int x) {
 if (p[x] == x) return x;
 p[x] = find(p[x]);
 return p[x];
 }

public void merge(int x, int y) {
 x = find(x);
 y = find(y);
 if (x == y) return;
 p[x] = y;
 count--;
 }

public void setP(int x) {
 p[x] = x;
 count++;
 }
 }
}

一键复制编辑原始数据按行查看历史

Roderland 提交于 2021年04月04日 15:30 +08:00 . ====== roderland ======

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

package question;

import java.util.Arrays;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question200 {
 public static void main(String[] args) {
 char[][] ints = {
 {'1', '0', '0', '1', '1', '1', '0', '1', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'}, {
 '1', '0', '0', '1', '1', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '0', '1', '0'}, {
 '0', '0', '0', '1', '1', '1', '1', '0', '1', '0', '1', '1', '0', '0', '0', '0', '1', '0', '1', '0'}, {
 '0', '0', '0', '1', '1', '0', '0', '1', '0', '0', '0', '1', '1', '1', '0', '0', '1', '0', '0', '1'}, {
 '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'}, {
 '1', '0', '0', '0', '0', '1', '0', '1', '0', '1', '1', '0', '0', '0', '0', '0', '0', '1', '0', '1'}, {
 '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'}, {
 '0', '0', '0', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '1', '1', '0', '1', '1', '1', '0'}, {
 '0', '0', '0', '0', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1'}, {
 '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '1', '0'}, {
 '1', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '1', '0', '1', '0'}, {
 '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '1', '0', '1', '1', '1', '0', '1', '1', '0', '0'}, {
 '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1'}, {
 '0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '1', '1', '1', '1', '1', '0', '1', '0', '0', '0'}, {
 '0', '0', '1', '1', '1', '0', '0', '0', '1', '1', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0'}, {
 '1', '0', '0', '1', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '1'}, {
 '1', '0', '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0'}, {
 '0', '1', '1', '0', '0', '0', '1', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0'}, {
 '0', '1', '0', '0', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '0', '1', '0', '0', '1', '1'}, {
 '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1', '0', '0', '0', '1', '1', '0', '0', '0'}
 };
 System.out.println(new Question200().numIslands(ints));
 }

 public int numIslands(char[][] grid) {
 int m = grid.length;
 int n = grid[0].length;
 UnionFind u = new UnionFind(n * m);
 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 if (grid[i][j] == '1') {
 int x = i * n + j;
 u.setP(x);
 if (x - 1 >= 0 && u.p[x - 1] >= 0) {
 if (x / n == (x - 1) / n) u.merge(x, x - 1);
 }
 if (x - n >= 0 && u.p[x - n] >= 0) u.merge(x, x - n);
 }
 }
 }
 return u.count;
 }

 private static class UnionFind {
 int[] p;
 int count;

 public UnionFind(int n) {
 p = new int[n];
 Arrays.fill(p, -1);
 count = 0;
 }

 public int find(int x) {
 if (p[x] == x) return x;
 p[x] = find(p[x]);
 return p[x];
 }

 public void merge(int x, int y) {
 x = find(x);
 y = find(y);
 if (x == y) return;
 p[x] = y;
 count--;
 }

 public void setP(int x) {
 p[x] = x;
 count++;
 }
 }
}