2020-3-27

914.卡牌分组

✒解题思路：

1. 使用Hash表记录每个数字的次数，当次数大于1时，最大公因数

class Solution {
	public boolean hasGroupsSizeX(int[] deck) {
		int len = deck.length;
		if (len < 2) {
			return false;
		}
		int[] heap = new int[10000];
		for (int i = 0; i < len; i++) {
			heap[deck[i]]++;
		}
		int x = heap[deck[0]];
		for (int i = 0; i < 10000; i++) {
			if (heap[i] == 1) {
				return false;
			}
			if (heap[i] > 1) {
				x = gcd(x, heap[i]);
				if (x == 1) {
					return false;
				}
			}
		}
		return true;
	}
    	int gcd(int m, int n) {
		if (m < n) {
			int t = m;
			m = n;
			n = t;
		}
		if (m % n == 0) {
			return n;
		} else {
			return gcd(n, m % n);
		}
	}
}

210.课程表II

✒解题思路：

1. 在课程表I的基础上，将每个出队列的数字添加进数组中

class Solution {
	public int[] findOrder(int numCourses, int[][] prerequisites) {
		int[] inDegree = new int[numCourses];
		List<List<Integer>> courses = new ArrayList<>();
		for (int i = 0; i < numCourses; i++) {
			courses.add(new ArrayList<>());
		}
		for (int[] cour : prerequisites) {
			inDegree[cour[0]]++;
			courses.get(cour[1]).add(cour[0]);
		}
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < numCourses; i++) {
			if (inDegree[i] == 0) {
				queue.add(i);
			}
		}
		int[] result = new int[numCourses];
		int i = 0;
		while (!queue.isEmpty()) {
			int num = queue.poll();
			result[i] = num;
			i++;
			numCourses--;
			for (int c : courses.get(num)) {
				if (--inDegree[c] == 0) {
					queue.add(c);
				}
			}
		}
		return numCourses == 0 ? result : new int[0];
	}
}

337.打家劫舍III

✒解题思路：

1. DP $$int x = root.val+rob(root.left.left)+rob(root.left.right)+rob(root.right.left)+rob(root.right.right) int y = rob(root.left)+rob(root.right) return max(x,y)$$

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	private Map<TreeNode, Integer> map = new HashMap<>();

	public int rob(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (map.containsKey(root)) {
			return map.get(root);
		}
		int doIt = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) +
				(root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
		int notDoIt = rob(root.left) + rob(root.right);
		int result = Math.max(doIt, notDoIt);
		map.put(root, result);
		return result;
	}
}

394.字符串解码

✒解题思路：

1. 使用两个栈

class Solution {
	public String decodeString(String s) {
		StringBuilder result = new StringBuilder();
		Stack<Integer> num = new Stack<>();
		Stack<String> str = new Stack<>();
		int multi = 0;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c >= '0' && c <= '9') {
				multi = multi * 10 + Integer.parseInt(c + "");
			} else if (c == '[') {
				num.push(multi);
				str.push(result.toString());
				multi = 0;
				result = new StringBuilder();
			} else if (c == ']') {
				int n = num.pop();
				StringBuilder temp = new StringBuilder();
				for (int j = 0; j < n; j++) {
					temp.append(result);
				}
				result = new StringBuilder(str.pop() + temp);
			} else {
				result.append(c);
			}
		}
		return result.toString();
	}
}

547.朋友圈

✒解题思路：

1. 深度优先遍历
2. 广度优先遍历
3. 并查集

//1.DFS
class Solution {
	public int findCircleNum(int[][] M) {
		int result = 0;
		boolean[] visited = new boolean[M.length];
		for (int i = 0; i < M.length; i++) {
			if (visited[i] == false) {
				dfs(M, visited, i);
				result++;
			}
		}
		return result;
	}

	private void dfs(int[][] M, boolean[] visited, int start) {
		for (int i = 0; i < M.length; i++) {
			if (M[i][start] == 1 && visited[i] == false) {
				visited[i] = true;
				dfs(M, visited, i);
			}
		}
	}
}
//2.BFS
class Solution {
    public int findCircleNum(int[][] M) {
		int result = 0;
		boolean[] visited = new boolean[M.length];
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < M.length; i++) {
			if (visited[i] == false) {
				queue.add(i);
				while (!queue.isEmpty()) {
					int num = queue.remove();
                    visited[num]=true;
					for (int j = 0; j < M.length; j++) {
						if (M[num][j] == 1 && visited[j] == false) {
							queue.add(j);
						}
					}
				}
				result++;
			}
		}
		return result;
	}
}
//3.并查集
class Solution {
    public int findCircleNum(int[][] M) {
		int result = 0;
		int[] parent = new int[M.length];
		Arrays.fill(parent, -1);
		for (int i = 0; i < M.length; i++) {
			for (int j = 0; j < M.length; j++) {
				if (M[i][j] == 1 && i != j) {
					union(parent, i, j);
				}
			}
		}
		for (int i = 0; i < M.length; i++) {
			if (parent[i] == -1) {
				result++;
			}
		}
		return result;
	}

	private void union(int[] parent, int i, int j) {
		int fX = find(parent, i);
		int fY = find(parent, j);
		if (fX != fY) {
			parent[fX] = fY;
		}
	}

	private int find(int[] parent, int x) {
		if (parent[x] == -1) {
			return x;
		}
		return find(parent, parent[x]);
	}
}

515.在每个树行中找最大值

✒解题思路：

1. 简单层次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<Integer> largestValues(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			int max = Integer.MIN_VALUE;
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (max < node.val) {
					max = node.val;
				}
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			result.add(max);
		}
		return result;
	}
}