1 Clone Graph 1 copy ervery nodes by bfs 2 add neighbors
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node)
{
if (node == null) {
return node;
} List<UndirectedGraphNode> nodes = new ArrayList<>();
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
nodes.add(node);
map.put(node, new UndirectedGraphNode(node.label)); int start = ;
while (start < nodes.size()) {
UndirectedGraphNode head = nodes.get(start++);
for (int i = ; i < head.neighbors.size(); i++) {
UndirectedGraphNode neighbor = head.neighbors.get(i);
if (!map.containsKey(neighbor)) {
nodes.add(neighbor);
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
}
}
} for (int i = ; i < nodes.size(); i++) {
UndirectedGraphNode newNode = map.get(nodes.get(i));
for (int j = ; j < nodes.get(i).neighbors.size(); j++) {
newNode.neighbors.add(map.get(nodes.get(i).neighbors.get(j)));
}
} return map.get(node);
}
2 Topological Sorting 1 store nodes and rudu 2 find nodes has 0 rudu 3 bfs
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
ArrayList<DirectedGraphNode> result = new ArrayList<>();
Map<DirectedGraphNode, Integer> map = new HashMap<>();
for (DirectedGraphNode node : graph) {
for (DirectedGraphNode neighbor : node.neighbors) {
if (map.containsKey(neighbor)) {
map.put(neighbor, map.get(neighbor) + );
} else {
map.put(neighbor, );
}
}
}
for (DirectedGraphNode node : graph) {
if (!map.containsKey(node)) {
result.add(node);
}
}
int start = ;
while (start < result.size()) {
DirectedGraphNode node = result.get(start++);
for (DirectedGraphNode neighbor : node.neighbors) {
map.put(neighbor, map.get(neighbor) - );
if (map.get(neighbor) == ) {
result.add(neighbor);
}
}
}
return result;
}
3 Route Between Two Nodes in Graph bfs 1 hold visited and queue 2 bfs
public boolean hasRoute(ArrayList<DirectedGraphNode> graph,
DirectedGraphNode s, DirectedGraphNode t) {
if (s == t) {
return true;
} Queue<DirectedGraphNode> queue = new LinkedList<>();
Set<DirectedGraphNode> visited = new HashSet<>();
queue.add(s);
visited.add(s); while (!queue.isEmpty()){
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode neighbor : node.neighbors) {
if (visited.contains(neighbor)) {
continue;
}
queue.add(neighbor);
visited.add(neighbor);
if (neighbor == t) {
return true;
}
}
} return false;
}
4 N-Queens
public ArrayList<ArrayList<String>> solveNQueens(int n)
{
// write your code here
ArrayList<ArrayList<String>> res = new ArrayList<>();
search(res, new ArrayList<Integer>(), n);
return res;
}
void search(ArrayList<ArrayList<String>> res, ArrayList<Integer> cols, int n) {
if (cols.size() == n) {
res.add(drawChessboard(cols));
return;
} for (int i = ; i < n; i++) {
if (!isValid(cols, i)) {
continue;
}
cols.add(i);
search(res, cols, n);
cols.remove(cols.size() - );
}
} ArrayList<String> drawChessboard(List<Integer> cols) {
ArrayList<String> result = new ArrayList<>();
for (int i = ; i < cols.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = ; j < cols.size(); j++) {
sb.append(cols.get(i) == j ? "Q" : ".");
}
result.add(sb.toString());
}
return result;
} boolean isValid(List<Integer> cols, int colIndex) {
int row = cols.size();
for (int i = ; i < cols.size(); i++) {
if (cols.get(i) == colIndex) {
return false;
} if (i + cols.get(i) == row + colIndex) {
return false;
} if (i - cols.get(i) == row - colIndex) {
return false;
}
}
return true;
}
5 Word Ladder
public int ladderLength(String start, String end, Set<String> dict)
{
if (dict == null) {
return ;
} if (start.equals(end)) {
return ;
} dict.add(end);
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.add(start);
int length = ; while (!queue.isEmpty()) {
length++;
int size = queue.size();
for (int i = ; i < size; i++) {
String word = queue.poll();
for (String newWord: getNextWords(word, dict)) {
if (visited.contains(newWord)) {
continue;
} if (newWord.equals(end)) {
return length;
} visited.add(newWord);
queue.add(newWord);
}
}
}
return ;
} List<String> getNextWords(String word, Set<String> dict) {
List<String> result = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++) {
for (int i = ; i < word.length(); i++) {
if (c == word.charAt(i)) {
continue;
}
String newWord = replace(word, i, c);
if (dict.contains(newWord)) {
result.add(newWord);
}
}
}
return result;
} String replace(String word, int i, char c) {
char[] arr = word.toCharArray();
arr[i] = c;
return new String(arr);
}
6 Word Ladder
public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return a list of lists of string
*/
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> result = new ArrayList<>();
Map<String, Integer> distance = new HashMap<>();
Map<String, List<String>> map = new HashMap<>();
dict.add(start);
dict.add(end);
bfs(start, end, dict, distance, map);
List<String> path = new ArrayList<>();
dfs(start, end, result, distance, map, path);
return result;
}
void dfs(String start, String cur, List<List<String>> result, Map<String, Integer> distance,
Map<String, List<String>> map, List<String> path) {
path.add(cur);
if (cur.equals(start)) {
Collections.reverse(path);
result.add(new ArrayList<>(path));
Collections.reverse(path);
} else {
for (String word : map.get(cur)) {
if (distance.containsKey(word) && distance.get(word) + == distance.get(cur)) {
dfs(start, word, result, distance, map, path);
}
}
}
path.remove(path.size() - );
}
void bfs(String start, String end, Set<String> dict, Map<String, Integer> distance,
Map<String, List<String>> map) {
Queue<String> queue = new LinkedList<>();
queue.offer(start);
distance.put(start, );
for(String word : dict) {
map.put(word, new ArrayList<String>());
}
while (!queue.isEmpty()) {
String word = queue.poll();
for (String newWord: getNextWords(word, dict)) {
map.get(newWord).add(word);
if (!distance.containsKey(newWord)) {
distance.put(newWord, distance.get(word) + );
queue.offer(newWord);
}
}
}
}
List<String> getNextWords(String word, Set<String> dict) {
List<String> result = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++) {
for (int i = ; i < word.length(); i++) {
if (c == word.charAt(i)) {
continue;
}
String newWord = replace(word, i, c);
if (dict.contains(newWord)) {
result.add(newWord);
}
}
}
return result;
}
String replace(String word, int i, char c) {
char[] arr = word.toCharArray();
arr[i] = c;
return new String(arr);
}
}
7 Palindrome Partitioning
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> res = new ArrayList<>();
ArrayList<String> path = new ArrayList<>();
dfs(s, , path, res);
return res;
}
void dfs(String s, int start, ArrayList<String> path, ArrayList<ArrayList<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
if (isValid(s, start, i)){
path.add(s.substring(start, i + ));
dfs(s, i + , path, res);
path.remove(path.size() - );
}
}
}
boolean isValid(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}