前言
本文隶属于专栏《LeetCode 刷题汇总》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！
本专栏目录结构请见LeetCode 刷题汇总
Github 配套工程
正文
幕布
126. 单词接龙 II
题解
My concise JAVA solution based on BFS and DFS
BFS+DFS
package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode126.solution1;
import java.util.*;
/**
* @author Shockang
*/
public class Solution {
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
HashSet<String> dict = new HashSet<>(wordList);
List<List<String>> res = new ArrayList<>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<>();// Neighbors for every node
HashMap<String, Integer> distance = new HashMap<>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<>();
dict.add(start);
bfs(start, end, dict, nodeNeighbors, distance);
dfs(start, end, dict, nodeNeighbors, distance, solution, res);
return res;
}
// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
for (String str : dict)
nodeNeighbors.put(str, new ArrayList<>());
Queue<String> queue = new LinkedList<>();
queue.offer(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
ArrayList<String> neighbors = getNeighbors(cur, dict);
for (String neighbor : neighbors) {
nodeNeighbors.get(cur).add(neighbor);
if (!distance.containsKey(neighbor)) {// Check if visited
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else queue.offer(neighbor);
}
}
}
if (foundEnd) break;
}
}
// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<>();
char chs[] = node.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch) continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
solution.add(cur);
if (end.equals(cur)) {
res.add(new ArrayList<>(solution));
} else {
for (String next : nodeNeighbors.get(cur)) {
if (distance.get(next) == distance.get(cur) + 1) {
dfs(next, end, dict, nodeNeighbors, distance, solution, res);
}
}
}
solution.remove(solution.size() - 1);
}
}
127. 单词接龙
题解
4个 set
package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode127.solution1;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* @author Shockang
*/
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList), qs = new HashSet<>(), qe = new HashSet<>(), vis = new HashSet<>();
qs.add(beginWord);
if (dict.contains(endWord)) qe.add(endWord); // all transformed words must be in dict (including endWord)
for (int len = 2; !qs.isEmpty(); len++) {
Set<String> nq = new HashSet<>();
for (String w : qs) {
for (int j = 0; j < w.length(); j++) {
char[] ch = w.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
if (c == w.charAt(j)) continue; // beginWord and endWord not the same, so bypass itself
ch[j] = c;
String nb = String.valueOf(ch);
if (qe.contains(nb)) return len; // meet from two ends
if (dict.contains(nb) && vis.add(nb)) nq.add(nb); // not meet yet, vis is safe to use
}
}
}
qs = (nq.size() < qe.size()) ? nq : qe; // switch to small one to traverse from other end
qe = (qs == nq) ? qe : nq;
}
return 0;
}
}
128. 最长连续序列
题解
官方题解?
哈希表
package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode128.solution1;
import java.util.HashSet;
import java.util.Set;
/**
* @author Shockang
*/
public class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int res = 0;
for (int num : numSet) {
if (!numSet.contains(num - 1)) {
int currentNum = num;
int cur = 1;
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
cur += 1;
}
res = Math.max(res, cur);
}
}
return res;
}
}
129. 求根节点到叶节点数字之和
题解
官方题解?
DFS
package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode129.solution1;
import com.shockang.study.algorithm.java.leetcode.common.TreeNode;
/**
* @author Shockang
*/
public class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int prevSum) {
if (root == null) {
return 0;
}
int sum = prevSum * 10 + root.val;
if (root.left == null && root.right == null) {
return sum;
} else {
return dfs(root.left, sum) + dfs(root.right, sum);
}
}
}
BFS
package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode129.solution2;
import com.shockang.study.algorithm.java.leetcode.common.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author Shockang
*/
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
Queue<TreeNode> nodeQueue = new LinkedList<>();
Queue<Integer> numQueue = new LinkedList<>();
nodeQueue.offer(root);
numQueue.offer(root.val);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
int num = numQueue.poll();
TreeNode left = node.left, right = node.right;
if (left == null && right == null) {
sum += num;
} else {
if (left != null) {
nodeQueue.offer(left);
numQueue.offer(num * 10 + left.val);
}
if (right != null) {
nodeQueue.offer(right);
numQueue.offer(num * 10 + right.val);
}
}
}
return sum;
}
}
130. 被围绕的区域
题解
官方题解?
小岛沉没
package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode130.solution1;
/**
* @author Shockang
*/
public class Solution {
int n, m;
public void solve(char[][] board) {
n = board.length;
if (n == 0) {
return;
}
m = board[0].length;
for (int i = 0; i < n; i++) {
dfs(board, i, 0);
dfs(board, i, m - 1);
}
for (int i = 1; i < m - 1; i++) {
dfs(board, 0, i);
dfs(board, n - 1, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
public void dfs(char[][] board, int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
return;
}
board[x][y] = 'A';
dfs(board, x + 1, y);
dfs(board, x - 1, y);
dfs(board, x, y + 1);
dfs(board, x, y - 1);
}
}