C code. C code run. Run code run… please!
Question: https://leetcode.com/problems/shortest-palindrome/ Question Name: Shortest Palindrome This is a variant of Longest Palindromic Substring. The key point is to convert the original question as following: 1. Shortest Palindrome by adding any characters in the head. Therefore the original string “original” is going … Read More »
Question: https://codility.com/demo/take-sample-test/cyclic_rotation/ Question Name: Cyclic-Rotation or CyclicRotation With Python’s syntactic sugar, the solution is pretty short.
1 2 3 4 5 6 | def solution(A, K): # write your code in Python 2.7 if len(A) == 0: return A K = K % len(A) return A[-K:] + A[:-K] |
Well, kind of too easy. Let’s try a C++ solution to demo the details better. Thanks to @micropentium6, the original C++ solution is … Read More »
Question: https://leetcode.com/problems/house-robber-ii/ Question Name: House Robber II This is a variant of House Robber. We need to apply the previous solution to two sub-arrays and return the maximum of the two results: 1. Do not use the first element, and … Read More »
Question: https://leetcode.com/problems/word-search-ii/ Question Name: Word Search II In general, this is a question with DFS/BFS of graph. Additionally, we need some optimizations: Use prefix tree to terminate the search early; Remove the found word in the prefix tree; Use bigrams … Read More »
Question: https://leetcode.com/problems/add-and-search-word-data-structure-design/ Question Name: Add and Search Word – Data Structure Design This is a variant of prefix tree (trie).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | class TrieNode(object): def __init__(self): """ Initialize your data structure here. """ self.isWord = False self.sons = {} class WordDictionary(object): def __init__(self): """ initialize your data structure here. """ self.root = TrieNode() def addWord(self, word): """ Adds a word into the data structure. :type word: str :rtype: void """ current = self.root for letter in word: if letter not in current.sons: current.sons[letter] = TrieNode() current = current.sons[letter] current.isWord = True return def search(self, word): """ Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. :type word: str :rtype: bool """ return self.search_helper(word, self.root) def search_helper(self, word, node): """ Returns if the word is in current trie. A word could contain the dot character '.' to represent any one letter. :type word: str :type node: TrieNode :rtype: bool """ if len(word) == 0: return node.isWord elif word[0] == ".": for candidate in node.sons: if self.search_helper(word[1:], node.sons[candidate]): return True else: return False else: if word[0] in node.sons: return self.search_helper(word[1:], node.sons[word[0]]) else: return False # Your WordDictionary object will be instantiated and called as such: # wordDictionary = WordDictionary() # wordDictionary.addWord("word") # wordDictionary.search("pattern") |
Question: https://leetcode.com/problems/course-schedule-ii/ Question Name: Course Schedule II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | class Course(object): def __init__(self): self.prerequisites = set() self.descendants = set() class Solution(object): def findOrder(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: List[int] """ ready_to_take = {CourseID:Course() for CourseID in xrange(numCourses)} waiting_for_prerequisite = {} # Build a graph to represent the courses dependence. for course, prerequisite in prerequisites: if course in ready_to_take: waiting_for_prerequisite[course] = ready_to_take[course] del ready_to_take[course] waiting_for_prerequisite[course].prerequisites.add(prerequisite) if prerequisite in ready_to_take: ready_to_take[prerequisite].descendants.add(course) else: waiting_for_prerequisite[prerequisite].descendants.add(course) # Travel the graph to get a course schedule. courses_order = [] while len(ready_to_take) != 0: courseID, courseInfo = ready_to_take.popitem() courses_order.append(courseID) for descendant in courseInfo.descendants: waiting_for_prerequisite[descendant].prerequisites.remove(courseID) if len(waiting_for_prerequisite[descendant].prerequisites) == 0: ready_to_take[descendant] = waiting_for_prerequisite[descendant] del waiting_for_prerequisite[descendant] if len(waiting_for_prerequisite) == 0: return courses_order else: return [] |
Question: https://leetcode.com/problems/minimum-size-subarray-sum/ Question Name: Minimum Size Subarray Sum This question is very similar with Longest Substring Without Repeating Characters and Minimum Window Substring.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | class Solution(object): def minSubArrayLen(self, s, nums): """ :type s: int :type nums: List[int] :rtype: int """ begin = 0 # Inclusive end = 0 # Exclusive. It is always different from "begin" # after the first move. window_sum = 0 result = 0 # Find candidate windows, whose sum is >= s. while end < len(nums): # Prepare for this window. window_sum += nums[end] end += 1 # Extend the window by moving the "end". # For the first window, it may be extended by multiple steps. # Otherwise, it is always extended by one step. while end < len(nums) and window_sum < s: window_sum += nums[end] end += 1 if window_sum < s: break # Shrink the window by moving the "begin". while window_sum - nums[begin] >= s: window_sum -= nums[begin] begin += 1 # Update the result if this window is shorter. if result == 0 or end - begin < result: result = end - begin return result |
Question: https://leetcode.com/problems/implement-trie-prefix-tree/ Question Name: Implement Trie (Prefix Tree) Not a full implementation. The delete function is not required.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | class TrieNode(object): def __init__(self): """ Initialize your data structure here. """ self.isWord = False self.sons = {} class Trie(object): def __init__(self): self.root = TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ current = self.root for letter in word: if letter not in current.sons: current.sons[letter] = TrieNode() current = current.sons[letter] current.isWord = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ current = self.root for letter in word: if letter not in current.sons: return False else: current = current.sons[letter] return current.isWord def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ current = self.root for letter in prefix: if letter not in current.sons: return False else: current = current.sons[letter] return True # Your Trie object will be instantiated and called as such: # trie = Trie() # trie.insert("somestring") # trie.search("key") |
Question: https://leetcode.com/problems/course-schedule/ Question Name: Course Schedule
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | class Solution(object): def _hasLoop(self, courseID, adjacencySet, reachableNodes, currentPath): """ :type numCourses: int :type adjacencySet: List[set(int)] :type: reachableNodes: mutable, set(int) :type: current_path: mutalbe, set(int) :rtype: bool """ if courseID in currentPath: return True currentPath.add(courseID) reachableNodes.add(courseID) for prerequisite in adjacencySet[courseID]: if self._hasLoop(prerequisite, adjacencySet, reachableNodes, currentPath): return True currentPath.remove(courseID) return False def _buildAdjacencySet(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: List[set(int)] """ adj_set = [set() for _ in xrange(numCourses)] for prerequisite in prerequisites: adj_set[prerequisite[0]].add(prerequisite[1]) return adj_set def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ # Find out the courses, which are not prerequisite of others. is_prerequisite = [False for _ in xrange(numCourses)] for prerequisite in prerequisites: is_prerequisite[prerequisite[1]] = True adjacency_set = self._buildAdjacencySet(numCourses, prerequisites) is_doable = [False for _ in xrange(numCourses)] for courseID in xrange(numCourses): if is_prerequisite[courseID]: continue # Check whether it is possible to finish this course. # If it is, all its direct/indirect prerequisites are also doable. reachable_nodes = set() current_path = set() if self._hasLoop(courseID, adjacency_set, reachable_nodes, current_path): return False for courseID in reachable_nodes: is_doable[courseID] = True return all(is_doable) |
Question: https://codility.com/demo/take-sample-test/polygon_concavity_index/ Question Name: Polygon-Concavity-Index or PolygonConcavityIndex Thanks to Robert Sedgewick, the Youtube video (Algorithms, Part I – Convex Hull) tells everything about this problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | def _IsClockwise(point_A, point_B, point_C): ''' Return the direction from points A -> B -> C. ''' result = (point_B.x - point_A.x) * (point_C.y - point_A.y) - (point_B.y - point_A.y) * (point_C.x - point_A.x) # The direction of a->b->c is: if result > 0: return 1 # counter-clockwise elif result < 0: return -1 # clockwise else: return 0 # a staight line def solution(A): ''' The solution refers to: https://www.youtube.com/watch?v=0HZaRu5IupM ''' # Find the lowest point(s) in y-axis. lowest_y = A[0].y lowest_y_index = [] for i in xrange(len(A)): if A[i].y < lowest_y: lowest_y = A[i].y lowest_y_index = [i] elif A[i].y == lowest_y: lowest_y_index.append(i) else: continue # Find a point, which is not the lowest in y-axis and immediately # after a lowest-in-y-axis point. start_point = lowest_y_index[0] lowest_y_array = [False] * len(A) for i in lowest_y_index: lowest_y_array[i] = True while lowest_y_array[start_point] == True: start_point = (start_point + 1) % len(A) start_point = (start_point - 1 + len(A)) % len(A) # Re-organize the points so that, it is easier to check every three # consecutive points in one loop (without module operation %). rotated_A = A[start_point : ] + A[ : start_point] # We find the start point such that, the direction is non-zero. direction = _IsClockwise(rotated_A[-1], rotated_A[0], rotated_A[1]) extened_A = rotated_A + rotated_A[:2] for i in xrange(len(A)): temp = _IsClockwise(extened_A[i], extened_A[i+1], extened_A[i+2]) if temp * direction < 0: # Compute the original index and return return (i + 1 + start_point)%len(A) # Every point is on the convex hull. return -1 |