Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
publicclassSolution{ int[] dx = {0, 0, 1, -1}; int[] dy = {1, -1, 0, 0}; publicintnumIslands(char[][] grid){ if (grid == null || grid.length == 0) return0; int numberOfLands = 0; int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { _dfs(grid, i, j, m, n); numberOfLands ++; } } }
return numberOfLands; }
privatevoid_dfs(char[][] grid, int i, int j, int maxRow, int maxCol){ if (i >= 0 && i < maxRow && j >= 0 && j < maxCol && grid[i][j] == '1') { grid[i][j] = 'm'; for (int k = 0; k < 4; k++) { _dfs(grid, i+dx[k], j+dy[k], maxRow, maxCol); } } } }
classSolution(object): defnumIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ """ Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. """ if grid isNoneorlen(grid) == 0:return0
m, n = len(grid), len(grid[0]) result = 0 for i inrange(m): for j inrange(n): if grid[i][j] == '1': self._dfs(grid, i, j, m, n) result += 1 return result
def_dfs(self, grid, i, j, m, n): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] if0 <= i < m and0 <= j < n and grid[i][j] == '1': grid[i][j] = '0' for k inrange(4): self._dfs(grid, i + dx[k], j + dy[k], m, n)
classSolution(object): defnumIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ """ Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. """ if grid isNoneorlen(grid) == 0:return0
m, n = len(grid), len(grid[0]) result = 0 for i inrange(m): for j inrange(n): if grid[i][j] == '1': self._dfs(grid, i, j, m, n) result += 1 # recover the scene for i inrange(m): for j inrange(n): if grid[i][j] == 'm': grid[i][j] = '1'
return result
def_dfs(self, grid, i, j, m, n): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] if0 <= i < m and0 <= j < n and grid[i][j] == '1': grid[i][j] = 'm' for k inrange(4): self._dfs(grid, i + dx[k], j + dy[k], m, n)
classSolution(object): defnumIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ """ Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. """ if grid isNoneorlen(grid) == 0:return0
m, n = len(grid), len(grid[0]) visited, result = [[0for _ inrange(n)] for _ inrange(m)], 0 for i inrange(m): for j inrange(n): if grid[i][j] == '1'and visited[i][j] == 0: self._dfs(grid, visited, i, j, m, n) result += 1 return result
def_dfs(self, grid, visited, i, j, m, n): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] if0 <= i < m and0 <= j < n and grid[i][j] == '1'and visited[i][j] == 0: visited[i][j] = 1 for k inrange(4): self._dfs(grid, visited, i + dx[k], j + dy[k], m, n)
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
int m = board.length; int n = board[0].length; Queue<Pair<Integer, Integer>> queue = new LinkedList<>(); HashSet<Pair<Integer, Integer>> visited = new HashSet<Pair<Integer, Integer>>(); // find the edge not surrounded elements. for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') { queue.offer(new Pair<Integer, Integer>(i, j)); } } }
while (!queue.isEmpty()) { Pair<Integer, Integer> position = queue.poll(); int x = position.getKey(); int y = position.getValue(); if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !visited.contains(position)) { board[x][y] = 'm'; visited.add(position);
for (int k = 0; k < 4; k++) { queue.offer(new Pair<Integer, Integer>(x + dx[k], y + dy[k])); } } }
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; } elseif (board[i][j] == 'm') { board[i][j] = 'O'; } } } } }
queue = deque() visited = set() # queue.append([0, 0]) for i inrange(m): for j inrange(n): if (i in [0, m - 1] or j in [0, n - 1]) and board[i][j] == 'O': queue.append((i, j))
while queue: position = queue.popleft() visited.add(position) # do something
if0 <= position[0] < m and0 <= position[1] < n and board[position[0]][position[1]] == 'O': board[position[0]][position[1]] = 'm' for i inrange(4): p = (position[0] + dx[i], position[1] + dy[i]) queue.append(p)
# loop the board and mark the none-surrounded area, and mark back 'm' area for i inrange(m): for j inrange(n): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == 'm': board[i][j] = 'O'
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ publicclassSolution{ public List<Integer> largestValues(TreeNode root){ List<Integer> result = new ArrayList<>(); if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root);
while (!queue.isEmpty()) { int queueSize = queue.size(); int levelMaxValue = Integer.MIN_VALUE; for (int i = 0; i < queueSize; i++) { TreeNode node = queue.poll(); levelMaxValue = Math.max(levelMaxValue, node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); }
while queue: queue_size = len(queue) level_max_value = -sys.maxsize for i inrange(queue_size): node = queue.popleft() visited.add(node) level_max_value = max(level_max_value, node.val)
if node.left and node.left notin visited: queue.append(node.left) if node.right and node.right notin visited: queue.append(node.right) result.append(level_max_value) return result