C code. C code run. Run code run… please!
This question is available on both Leetcode (No. 270) and Lintcode (No. 901). The question is not too hard, if we do not chase the best time complexity. For example, we can traversal all the nodes and book-keep the closest … Read More »
Question: https://leetcode.com/problems/contains-duplicate/ Question Name: Contains Duplicate In general, I found two solutions. The first solution is using hash set:
1 2 3 4 5 6 7 8 | class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ deduplicated = set(nums) return len(deduplicated) != len(nums) |
The second solution is using sorting. We could sort the input and check each pair of adjacent items. Or we could early … Read More »
Question: https://leetcode.com/problems/combination-sum-iii/ Question Name: Combination Sum III This is a typical recursion problem. Find out the base case and recursive cases, and that’s the right solution.
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 | class Solution(object): def _combinationSum3Helper(self, remaining, candidates, next_value, partial_sum, target): """ :type remaining: int. It's the count of additional numbers could be used. :type candidates: list[bool]. candidates[i] is True, if the number i is\ used. :type next_value: int. It's the next number to consider. :type partial_sum: int. The sum of used candidates so far. :type target : int. It's the target sum. :rtype: List[List[int]] """ result = [] if remaining == 0: if partial_sum == target: # Found one combination. combination = [] for i in xrange(1, next_value): if candidates[i] == True: combination.append(i) result.append(combination) return result else: # This combination is not valid. return result elif partial_sum + next_value > target or next_value > 9: # It's impossbile to have any valid combination with current # prefix. return result else: # It does not take the next_value. result.extend(self._combinationSum3Helper( remaining, candidates, next_value + 1, partial_sum, target)) # It does take the next_value. candidates[next_value] = True result.extend(self._combinationSum3Helper( remaining - 1, candidates, next_value + 1, partial_sum + next_value, target)) candidates[next_value] = False return result def combinationSum3(self, k, n): """ :type k: int :type n: int :rtype: List[List[int]] """ candidates = [False for _ in xrange(10)] # 0 is never used. return self._combinationSum3Helper(k, candidates, 1, 0, n) |
Question: https://leetcode.com/problems/kth-largest-element-in-an-array/ Question Name: Kth Largest Element in an Array This is exactly the quick-select.
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 | class Solution(object): def _quickSortHelper(self, nums, begin, end): """ :type nums: List[int] :type begin: int :type end: int :rtype: int (the index of nums[begin] after quick-select) """ next_smaller_pos = begin + 1 next_bigger_pos = end while next_smaller_pos <= next_bigger_pos: if nums[next_smaller_pos] <= nums[begin]: next_smaller_pos += 1 elif nums[begin] <= nums[next_bigger_pos]: next_bigger_pos -= 1 else: nums[next_smaller_pos] ^= nums[next_bigger_pos] nums[next_bigger_pos] ^= nums[next_smaller_pos] nums[next_smaller_pos] ^= nums[next_bigger_pos] next_smaller_pos += 1 nums[begin], nums[next_bigger_pos] = nums[next_bigger_pos], nums[begin] return next_bigger_pos def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ k = len(nums) - k begin, end = 0, len(nums) - 1 while True: position = self._quickSortHelper(nums, begin, end) if position == k: return nums[k] elif position < k: begin = position + 1 else: end = position - 1 # Should never be here. return 0 |
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://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 |