In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].
A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.
Example 1:
<pre>Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]
</pre>
Because x and y are constrained to be in range[-300, 300], we can use BFS to find the minimum steps needed to reach target(x, y). Furthermore, we can only consider the case that x >=0 && y >=0 since the chess board is symmetric. The bfs implementation is pretty straightforward. There are two important points you need to be careful with.
1. Pruning. We can limit the search dimension within 310 * 310. Any moves that lead to a position that is outside this box will not yield an optimal result.
2. Initially, you used a Set of type int[] to track visited positions. This caused TLE because you didn't overwrite the hashCode and equals methods for int[]. As a result, Set uses the default hashCode and equals method when checking if an element is already in the set. For equals(), The default implementation provided by the JDK is based on memory location — two objects are equal if and only if they are stored in the same memory address. For a comprehensive reading, refer to https://dzone.com/articles/working-with-hashcode-and-equals-in-java
for direction in directions: neighbor = (node[0] + direction[0], node[1] + direction[1]) if neighbor in visited: continue queue.append(neighbor) visited.add(neighbor) distance[neighbor] = distance[node] + 1
Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
<pre>class Node {
public int val;
public List<Node> neighbors;
}
</pre>
Test case format:
For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.
Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
<pre>Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
</pre>
Example 2:
<pre>Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
</pre>
Example 3:
<pre>Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
</pre>
defcloneGraph(self, node: 'Node') -> 'Node': ifnot node: returnNone di = {} node_list = self.bfs(node) for n in node_list: di[n] = Node(n.val) for n in node_list: for n2 in n.neighbors: di[n].neighbors.append(di[n2]) return di[node]
defbfs(self, input): queue = deque([input]) visited = {input} # graph = collections.defaultdict(list) res = [] while queue: node = queue.popleft() # graph[node] = [] res.append(node) for neighbor in node.neighbors: if neighbor in visited: continue queue.append(neighbor) visited.add(neighbor) # graph[node].append(neighbor) return res
// another bfs3 method uses 3 steps, convert graph to adjacent list by bfs (flatten the graph), //clone vertices, clone edges publicvoidbfs3(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map) { ArrayList<UndirectedGraphNode> nodes = getNodes(node); // Copy vertices for(UndirectedGraphNode old : nodes) { UndirectedGraphNodenewNode=newUndirectedGraphNode(old.label); map.put(old, newNode); } // Copy edges for(UndirectedGraphNode old : nodes) { for(UndirectedGraphNode neighbor : old.neighbors) { map.get(old).neighbors.add(map.get(neighbor)); } } }
public ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) { Queue<UndirectedGraphNode> q = newLinkedList<>(); Set<UndirectedGraphNode> result = newHashSet<>(); q.offer(node); result.add(node); // Use result set so we can save the visited set while(!q.isEmpty()) { UndirectedGraphNoden= q.poll(); for(UndirectedGraphNode neighbor : n.neighbors) { if(result.contains(neighbor)) continue; q.offer(neighbor); result.add(neighbor); } } ArrayList<UndirectedGraphNode> reList = newArrayList<UndirectedGraphNode>(); reList.addAll(result); return reList; }
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
deffindLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[int]]: ifnot beginWord ornot endWord: return0 distance, graph = {}, defaultdict(list) for word in wordList: distance[word] = 0 distance[beginWord] = 1 self.bfs(beginWord, endWord, distance, graph, set()) result = [] self.dfs(graph, beginWord, endWord, [beginWord], result, distance) # remember [beginWord] return result
defdfs(self, graph, startWord, endWord, path, res, dict): if startWord == endWord: res.append(list(path)) return '''if startWord in visited: # remember return visited.add(startWord)''' for neighbor in graph[startWord]: ifdict[neighbor] == dict[startWord] + 1: path.append(neighbor) self.dfs(graph, neighbor, endWord, path, res, dict) path.pop()
defbfs(self, beginWord, endWord, dict, graph, visited): queue = deque([beginWord]) visited.add(beginWord) # for key in dict.keys(): # remember # graph[key] = [] while queue: word = queue.popleft() if word == endWord: returndict[word]
neighbors = self.get_next_words(word, dict) graph[word] = neighbors for neighbor in neighbors: if neighbor notin visited: queue.append(neighbor) visited.add(neighbor) dict[neighbor] = dict[word] + 1 return0
defget_next_words(self, word, dict): res = [] for i inrange(len(word)): for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz' if c == word[i]: continue new_word = word[:i] + c + word[i + 1:] if new_word indict: res.append(new_word) return res
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { List<String> path = newArrayList<>(); List<List<String>> res = newArrayList<>(); if(beginWord == null || endWord == null) return res; // This is a dict and also keeps track of distance Map<String, Integer> dict = getDict(wordList); // Make sure endWord is in the dict and can be the next word //dict.put(endWord, 0); dict.put(beginWord, 1); HashMap<String, List<String>> graph = newHashMap<String, List<String>>(); ladderLength(beginWord, endWord, dict, graph); path.add(beginWord); dfs(beginWord, endWord, dict, graph, path, res); return res; }
voiddfs(String cur, String endWord, Map<String, Integer> distance, HashMap<String, List<String>> graph, List<String> path, List<List<String>> res) { if(endWord.equals(cur)) { res.add(newArrayList<>(path)); return; } for(String word : graph.get(cur)) { path.add(word); if(distance.get(word) - 1 == distance.get(cur)) // use distance, resolve LTE the most important dfs(word, endWord, distance, graph, path, res); path.remove(path.size() - 1); } }
Given a set of distinct positive integers, find the largest subset such that every pair (S<sub>i</sub>, S<sub>j</sub>) of elements in this subset satisfies:
