126. 单词接龙 II
先使用bfs记录每个结点的前驱，然后使用dfs获得所有最短路径。
class Solution {
Map<String, Set<String>> pre = new HashMap<>();//存放每个单词的前驱
List<List<String>> res = new ArrayList<>();//最终结果
List<String> temp = new ArrayList<>();//临时路径
public void dfs(String endWord, String beginWord) {
if (endWord.equals(beginWord)) {
Collections.reverse(temp);
res.add(new ArrayList<>(temp));
Collections.reverse(temp);//还得转回来，不然会影响后面的结果
return;
}
Set<String> set = pre.get(endWord);
for (String s : set) {
temp.add(s);
dfs(s, beginWord);
temp.remove(temp.size() - 1);
}
}
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);//使用set加快搜索
if (set.isEmpty() || !set.contains(endWord)) {
return new ArrayList<>();
}
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(beginWord);
visited.add(beginWord);
set.add(beginWord);
boolean finish = false;
while (!q.isEmpty()) {
int size = q.size();
Set<String> s = new HashSet<>();//关键点，每一层遍历完之后才能把这一层加到已访问中
for (int i = 0; i < size; i++) {
String front = q.poll();
char[] array = front.toCharArray();
for (int j = 0; j < array.length; j++) {
char temp = array[j];
for (char k = 'a'; k <= 'z'; k++) {
array[j] = k;
String word = String.valueOf(array);
if (word.equals(endWord)) {
finish = true;
}
if (!visited.contains(word) && set.contains(word)) {
if (pre.containsKey(word)) {
Set<String> se = pre.get(word);
se.add(front);
pre.put(word, se);
} else {
Set<String> se = new HashSet<>();
se.add(front);
pre.put(word, se);
}
s.add(word);
q.add(word);
}
array[j] = temp;
}
}
}
visited.addAll(s);
if (finish == true) {
break;
}
}
if (pre.isEmpty()) {
return new ArrayList<>();
}
temp.add(endWord);
dfs(endWord, beginWord);
return res;
}
}
127. 单词接龙
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (set.size() == 0 || !set.contains(endWord)) {
return 0;
}
set.remove(beginWord);
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
int step = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String front = q.poll();
char[] charArray = front.toCharArray();
for (int j = 0; j < charArray.length; j++) {
char temp = charArray[j];
for (char k = 'a'; k <= 'z'; k++) {
if (k == charArray[j]) {
continue;
}
charArray[j] = k;
String word = String.valueOf(charArray);
if (word.equals(endWord)) {
return step + 1;
}
if (set.contains(word) && !visited.contains(word)) {
q.add(word);
visited.add(word);
}
}
charArray[j] = temp;
}
}
step++;
}
return 0;
}
}
128. 最长连续序列
class Solution {
int[] father, size;
int res = 1;
public void init() {
for (int i = 0; i < father.length; i++) {
father[i] = i;
size[i] = 1;
}
}
//没有写路径压缩
public int findFather(int x) {
while (father[x] != x) {
x = father[x];
}
return x;
}
public void merge(int a, int b) {
int faA = findFather(a), faB = findFather(b);
if (faA != faB) {
father[faA] = faB;
size[faB] += size[faA];
res = Math.max(res, size[faB]);
}
}
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
father = new int[nums.length];
size = new int[nums.length];
init();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (Integer key : map.keySet()) {
if (map.containsKey(key + 1)) {
merge(map.get(key), map.get(key + 1));
}
}
return res;
}
}
129. 求根到叶子节点数字之和
class Solution {
int res = 0;
public void dfs(TreeNode root, int num) {
if (root == null) {
return;
}
num *= 10;
num += root.val;
if (root.left == null && root.right == null) {
res += num;
}
dfs(root.left, num);
dfs(root.right, num);
}
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return res;
}
}
class Solution {
public int sumNumbers(TreeNode root) {
return helper(root, 0);
}
public int helper(TreeNode root, int i) {
if (root == null) return 0;
int temp = i * 10 + root.val;
if (root.left == null && root.right == null)
return temp;
return helper(root.left, temp) + helper(root.right, temp);
}
}
130. 被围绕的区域
首先对边界上每一个'O'做深度优先搜索，将与其相连的所有'O'改为'-'。然后遍历矩阵，将矩阵中所有'O'改为'X',将矩阵中所有'-'变为'O'
class Solution {
int row, col;
public void dfs(char[][] board, int i, int j) {
if (i < 0 || j < 0 || i >= row || j >= col || board[i][j] != 'O') {
return;
}
board[i][j] = '-';
dfs(board, i - 1, j);
dfs(board, i + 1, j);
dfs(board, i, j - 1);
dfs(board, i, j + 1);
}
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
row = board.length;
col = board[0].length;
for (int i = 0; i < row; i++) {
dfs(board, i, 0);
dfs(board, i, col - 1);
}
for (int j = 0; j < col; j++) {
dfs(board, 0, j);
dfs(board, row - 1, j);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '-') {
board[i][j] = 'O';
}
}
}
}
}
网友评论