Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.
Your algorithm should run in O(n) complexity.
给定一个整形数组，求出最长的连续序列。例如数组[100,4,200,1,3,2]，最长的连续序列长度为[1,2,3,4]，长度为4。要求时间复杂度为O(n)。
排序的话至少要O(nlgn) 的复杂度。O(n)的复杂度，目前只找到了使用hash来解决的方案，add, remove, contains 等方法的复杂度都是 O(1)，因此两次遍历的操作复杂度为 O(n)。
public static int longestConsecutive(int[] num) { // if array is empty, return 0 if (num.length == 0) { return 0; } Set<Integer> set = new HashSet<Integer>(); int max = 1; for (int e : num) set.add(e); for (int e : num) { int left = e - 1; int right = e + 1; int count = 1; while (set.contains(left)) { count++; set.remove(left); left--; } while (set.contains(right)) { count++; set.remove(right); right++; } max = Math.max(count, max); } return max; }
Given a 2D board containing‘X‘and‘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
典型的BFS题目。遍历每个字符，如果是“O”，则从当前字符开始BFS遍历，如果周围也是“O”则加入当前遍历的队列，知道遍历完所有相邻的“O”，于此同时，判断每个O是否是被包围的，只有由一个O是没有被包围的，则当前遍历的O的集合都是没有被包围的，因为这些O都是相连的。
当然，此题使用DFS也可以，只是测试数据过大，提交时StackOverFlow.
1）BFS 广度优先搜索
public class Solution { // use a queue to do BFS private Queue<Integer> queue = new LinkedList<Integer>(); public void solve(char[][] board) { if (board == null || board.length == 0) return; int m = board.length; int n = board[0].length; // merge O‘s on left & right boarder for (int i = 0; i < m; i++) { if (board[i][0] == ‘O‘) { bfs(board, i, 0); } if (board[i][n - 1] == ‘O‘) { bfs(board, i, n - 1); } } // merge O‘s on top & bottom boarder for (int j = 0; j < n; j++) { if (board[0][j] == ‘O‘) { bfs(board, 0, j); } if (board[m - 1][j] == ‘O‘) { bfs(board, m - 1, j); } } // process the board for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == ‘O‘) { board[i][j] = ‘X‘; } else if (board[i][j] == ‘#‘) { board[i][j] = ‘O‘; } } } } private void bfs(char[][] board, int i, int j) { int n = board[0].length; // fill current first and then its neighbors fillCell(board, i, j); while (!queue.isEmpty()) { int cur = queue.poll(); int x = cur / n; int y = cur % n; fillCell(board, x - 1, y); fillCell(board, x + 1, y); fillCell(board, x, y - 1); fillCell(board, x, y + 1); } } private void fillCell(char[][] board, int i, int j) { int m = board.length; int n = board[0].length; if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != ‘O‘) return; // add current cell is queue & then process its neighbors in bfs queue.offer(i * n + j); board[i][j] = ‘#‘; // 用#标识要保留的O } }
2）DFS深度优先搜索
public void solve(char[][] board) { if(board == null || board.length==0) return; int m = board.length; int n = board[0].length; //merge O‘s on left & right boarder for(int i=0;i<m;i++){ if(board[i][0] == ‘O‘){ merge(board, i, 0); } if(board[i][n-1] == ‘O‘){ merge(board, i,n-1); } } //merge O‘s on top & bottom boarder for(int j=0; j<n; j++){ if(board[0][j] == ‘O‘){ merge(board, 0,j); } if(board[m-1][j] == ‘O‘){ merge(board, m-1,j); } } //process the board for(int i=0;i<m;i++){ for(int j=0; j<n; j++){ if(board[i][j] == ‘O‘){ board[i][j] = ‘X‘; }else if(board[i][j] == ‘#‘){ board[i][j] = ‘O‘; } } } } public void merge(char[][] board, int i, int j){ if(i<0 || i>=board.length || j<0 || j>=board[0].length) return; if(board[i][j] != ‘O‘) return; board[i][j] = ‘#‘; // 递归实现深度优先搜索 merge(board, i-1, j); merge(board, i+1, j); merge(board, i, j-1); merge(board, i, j+1); }
原文：http://www.cnblogs.com/zxqstrong/p/5358966.html
