2020-4-2

1267.统计参与通信的服务器

✒解题思路：

1. 统计每行和每列的服务器数量，只要grid[i][j]处，第i行和第j列存在的服务器数量>1就可以通信。

class Solution {
	public int countServers(int[][] grid) {
		int result = 0;
		int m = grid.length;
		int n = grid[0].length;
		int[] row = new int[m];
		int[] col = new int[n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 1) {
					row[i]++;
					col[j]++;
				}
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 1 && (row[i] > 1 || col[j] > 1)) {
					result++;
				}
			}
		}
		return result;
	}
}

841.钥匙和房间

✒解题思路：

1. BFS
2. DFS

//DFS
class Solution {
	public boolean canVisitAllRooms(List<List<Integer>> rooms) {
		boolean[] visited = new boolean[rooms.size()];
		visited[0] = true;
		Stack<List<Integer>> stack = new Stack<>();
		stack.push(rooms.get(0));
		while (!stack.isEmpty()) {
			List<Integer> list = stack.pop();
			for (int num : list) {
				if (!visited[num]) {
					visited[num] = true;
					stack.push(rooms.get(num));
				}
			}
		}
		for (boolean b : visited) {
			if (!b) {
				return false;
			}
		}
		return true;
	}
}
//BFS
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
		boolean[] visited = new boolean[rooms.size()];
		visited[0] = true;
		Queue<List<Integer>> queue = new LinkedList<>();
		queue.add(rooms.get(0));
		while (!queue.isEmpty()) {
			List<Integer> list = queue.poll();
			for (int num : list) {
				if (!visited[num]) {
					visited[num] = true;
					queue.add(rooms.get(num));
				}
			}
		}
		for (boolean b : visited) {
			if (!b) {
				return false;
			}
		}
		return true;
	}
}

289.生命游戏

✒解题思路：

1. 设置额外的状态
   • grid[i][j]==1并且sum<2||sum>3时，设置grid[i][j]=-1表示之前存活，现在死亡
   • grid[i][j]==0并且sum==3时，设置grid[i][j]=2表示之前死亡，现在存活
   • 每次遍历时要考虑grid[i][j]==1和grid[i][j]==-1的情况，因为这两种情况在上个状态是存活的

class Solution {
	public void gameOfLife(int[][] board) {
		int m = board.length;
		if (m == 0) {
			return;
		}
		int n = board[0].length;
		if (n == 0) {
			return;
		}
		int[][] directions = new int[][]{{-1, 0}, {-1, -1}, {-1, 1}, {0, 1}, {0, -1}, {1, 0}, {1, -1}, {1, 1}};
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int sum = 0;
				for (int k = 0; k < 8; k++) {
					int newX = i + directions[k][0];
					int newY = j + directions[k][1];
					if (newX >= 0 && newX < m && newY < n && newY >= 0 && (board[newX][newY] == 1||board[newX][newY] == -1)) {
						sum += 1;
					}
				}
				if (board[i][j] == 1 && (sum < 2 || sum > 3)) {
					board[i][j] = -1;//开始存活，后来死亡
				}
				if (board[i][j] == 0 && sum == 3) {
					board[i][j] = 2;//复活
				}
			}
		}

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] > 0) {
					board[i][j] = 1;
				} else {
					board[i][j] = 0;
				}
			}
		}
	}
}

990.等式方程的可满足性

✒解题思路：

1. 并查集

class Solution {
	public boolean equationsPossible(String[] equations) {
		UnionFind uf = new UnionFind(26);
		for (String s : equations) {
			if (s.charAt(1) == '=') {
				int p = s.charAt(0) - 'a';
				int q = s.charAt(3) - 'a';
				uf.union(p, q);
			}
		}
		for (String s : equations) {
			if (s.charAt(1) == '!') {
				int p = s.charAt(0) - 'a';
				int q = s.charAt(3) - 'a';
				if (uf.isConnected(p, q)) {
					return false;
				}
			}
		}
		return true;
	}
    class UnionFind {
		//存放第i节点的父节点索引
		private int[] parent;

		public UnionFind(int n) {
			parent = new int[n];
			for (int i = 0; i < n; i++) {
				parent[i] = i;
			}
		}

		public int find(int p) {
			while (parent[p] != p) {
   	  	       //两步一跳
    	        parent[p] = parent[parent[p]];
				p = parent[p];
			}
			return p;
		}

		public void union(int p, int q) {
			int pRoot = find(p);
			int qRoot = find(q);
			//此时已经在同一个分量中
			if (pRoot == qRoot) {
				return;
			}
			parent[pRoot] = qRoot;
			//或者parent[pRoot]=qRoot;
		}
        
		public boolean isConnected(int p, int q) {
			return find(p) == find(q);
		}
	}
}