C code. C code run. Run code run… please!
Questioin Name: Count Visible Nodes in Binary Tree Question: In a binary tree, if in the path from root to the node A, there is no node with greater value than A’s, this node A is visible. We need to … Read More »
Question Name: Print Tree By Columns Question: print tree by columns, from leftmost column to rightmost column. For each node in i(th) column, if son(s) exist, its left son is in the (i-1)th column, and right son in the (i+1)th … Read More »
Question: https://oj.leetcode.com/problems/insertion-sort-list/ Question Name: Insertion Sort List
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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return a ListNode def insertionSortList(self, head): if head == None: return None # Cut the list into two part: sorted and to-sort. pseudoHead = ListNode(-1) # Sorted list pseudoHead.next = head current = head.next # To-sort list head.next = None # Cut the two lists sortedEnd = head # Optimization for sorted input while current != None: # Store the current's next for later use. nextCurrent = current.next if sortedEnd.val <= current.val: # Append the current node at the end. sortedEnd.next = current current.next = None # The node at the end of sorted list is changed. sortedEnd = current else: # Insert to some place in the middle of sorted list headOfSorted = pseudoHead # Find the insert position. If space permitted, we could use # a binary tree to record the sorted node. So that we could # find the insert position with O(logN) instead of O(N). # # Because this current node will not be added at the end, we # do not need to check the bound. while headOfSorted.next.val < current.val: headOfSorted = headOfSorted.next # Insert the node current.next = headOfSorted.next headOfSorted.next = current current = nextCurrent return pseudoHead.next |
Question: https://oj.leetcode.com/problems/lru-cache/ Question Name: LRU Cache
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | class LRUCache: # The following support functions for priority queue is unnecessary, if we can # import and use Python build-in lib heapq. # @param pos, an integer # @return None def _swinm(self, pos): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' while pos > 0 and self.heap[(pos-1)//2][2] > self.heap[pos][2]: # Update the position dict. self.position[self.heap[(pos-1)//2][0]] = pos self.position[self.heap[pos][0]] = (pos-1)//2 # Swap these two records in heap self.heap[(pos-1)//2], self.heap[pos] = self.heap[pos], self.heap[(pos-1)//2] pos = (pos-1)//2 return # @param pos, an integer # @return None def _sink(self, pos): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' while 2*pos + 1 < self.count: earlierSon = 2*pos + 1 # Check the time of its right son, if it exists. if earlierSon+1 < self.count and self.heap[earlierSon][2] > self.heap[earlierSon+1][2]: earlierSon += 1 # Has earlier timestamp than son(s). Finish sinking. if self.heap[earlierSon][2] > self.heap[pos][2]: break # Swap the records in heap and position dict. self.position[self.heap[pos][0]] = earlierSon self.position[self.heap[earlierSon][0]] = pos self.heap[pos], self.heap[earlierSon] = self.heap[earlierSon], self.heap[pos] pos = earlierSon return # @return an array for the least recent used record, in form of [key, value, time] def _popLRU(self): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' # Nothing to pop. if self.count == 0: return None # Keep the to-pop record, and delete it from position dict. result = self.heap[0] del self.position[result[0]] # Delete the record in the heap. if self.count > 1: self.heap[0] = self.heap[self.count-1] self.count -= 1 self.position[self.heap[0][0]] = 0 self._sink(0) else: self.count -= 1 return result # @param key, an integer # @param value, an integer # @param time, an integer # @return None def _addNew(self, key, value, time): ''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf Support function for priority queue ''' if self.count == self.capacity: # Heap is full. Make some space. self._popLRU() self.heap[self.count] = [key, value, time] self.position[key] = self.count self.count += 1 self._swinm(self.count - 1) return # @param capacity, an integer def __init__(self, capacity): # Use min heap to do find and remove the least recent used record. self.heap = [None] * capacity # Each element: [key, value, time] self.count = 0 self.capacity = capacity # Used to store the mapping between key and the corresponding record's # position in self.heap. self.position = {} # Record the current time self.time = 0 # @param key, an integer # @return an integer def get(self, key): self.time += 1 if key not in self.position: # Not found in our db. return -1 else: # Update the used time for the record posInHeap = self.position[key] self.heap[posInHeap][2] = self.time self._sink(posInHeap) return self.heap[self.position[key]][1] # @param key, an integer # @param value, an integer # @return nothing def set(self, key, value): self.time += 1 if key not in self.position: # Add a new record. self._addNew(key, value, self.time) else: # Update the used time and value of the existing record. self.heap[self.position[key]][2] = self.time self.heap[self.position[key]][1] = value self._sink(self.position[key]) |
Question: https://oj.leetcode.com/problems/binary-tree-postorder-traversal/ Question Name: Binary Tree Postorder Traversal
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 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a list of integers def postorderTraversal(self, root): # Handle with the special cast (empty input) if root == None: return [] # Every node will be accessed twice in the stacks. # # As post order traversal required: # The first time, we will pop and check its son(s). # The second time, we will check its value. # # So we are using two stacks here. One for the nodes to be accessed # for the first time. The other is used for the nodes, waiting for # the second access. stackPrepare = [root] stackReady = [] result = [] while len(stackPrepare) != 0 : current = stackPrepare.pop() # Current node is finally read after reading its son(s). So # it is pushed firstly. stackReady.append(current) # The sons are going to travel tow stacks, which are FILO. # We want to read left son first, if it exists. # So we push the left son first. Please notice that, in the # first stack, it would be left -> right # When in the second stack, it would be root -> right -> left # And final when reading the value into result, the order is: # left -> right -> root, as post order traversal. if current.left != None: stackPrepare.append(current.left) if current.right != None: stackPrepare.append(current.right) while len(stackReady) != 0: result.append(stackReady.pop().val) return result |
Question: https://oj.leetcode.com/problems/binary-tree-preorder-traversal/ Question Name: Binary Tree Preorder Traversal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a list of integers def preorderTraversal(self, root): # Empty tree if root == None: return [] result = [] stack = [root] while len(stack) != 0: # Access the root firstly current = stack.pop() result.append(current.val) # Then we are going to access its left son and right son. if current.right != None: stack.append(current.right) if current.left != None: stack.append(current.left) return result |
Question: https://oj.leetcode.com/problems/reorder-list/ Question Name: Reorder List
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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return nothing def reorderList(self, head): listInArray = [] # Store all the nodes in the list into an array. current = head while current != None: listInArray.append(current) current = current.next # Check whether it's an empty list. listLen = len(listInArray) if listLen == 0: return # Reorder the List as required for index in xrange(listLen // 2): listInArray[index].next = listInArray[listLen-1-index] listInArray[listLen-1-index].next = listInArray[index+1] # End the list listInArray[listLen // 2].next = None return |
Question: https://oj.leetcode.com/problems/linked-list-cycle-ii/ Question Name: Linked List Cycle II Same as the problem in Cracking the Coding Interview.
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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return a boolean def detectCycle(self, head): if head == None: return None slower = head # Move one step each time quicker = head # Move two steps each time while quicker.next != None and quicker.next.next != None: slower = slower.next quicker = quicker.next.next # The slower and quicker meet with each other. There is a cycle. if slower == quicker: break else: # quicker reach the end. Limited list never have cycle. return None # Both latter and former move one step in each round, until they meet. # The meeting place is the entry point of cycle. latter, former = head, quicker while latter != former: latter = latter.next former = former.next return former |
Question: https://oj.leetcode.com/problems/linked-list-cycle/ Question Name: Linked List Cycle Same as the problem in Cracking the Coding Interview.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return a boolean def hasCycle(self, head): if head == None: return False slower = head # Move one step each time quicker = head # Move two steps each time while quicker.next != None and quicker.next.next != None: slower = slower.next quicker = quicker.next.next if slower == quicker: return True # quicker reach the end. Limited list never have cycle. return False |
Question: https://oj.leetcode.com/problems/word-break-ii/ Question Name: Word Break 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | class Solution: # @param s, a string # @param dict, a set of string # @return a boolean def _isBreakable(self, s, dict): ''' Solve it with dynamic programming. ''' couldBreak = [False] * len(s) for breakAfterCurrent in xrange(len(s)): if s[: breakAfterCurrent+1] in dict: # The substring from beginning to here is in the dict. # We can make a break between this position and its # next position. couldBreak[breakAfterCurrent] = True continue # Otherwise, we will try to check, whether this substring # s[:breakAfterCurrent+1] could be composed by breakable # head and a tail, which is in the dict. for preBreak in xrange(breakAfterCurrent): if couldBreak[preBreak] == False: # The head is not breakable continue elif s[preBreak+1: breakAfterCurrent+1] not in dict: # The tail is not in the dict. continue else: # As long as we know it's breakable, no need to # continue the search for current position. couldBreak[breakAfterCurrent] = True break return couldBreak[-1] # @param s, a string # @param dict, a set of string # @return a list of strings def wordBreak(self, s, dict): ''' Solve it with dynamic programming. ''' # First of all, use a much-less-time-consuming method to check # whether the answer is an empty list. # It is important to pass some unbreakable tests. if not self._isBreakable(s, dict): return [] sLen = len(s) couldBreak = [[] for _ in xrange(sLen)] # There may be multiple candidates in dict, having the same length. # So we are using set to find out the unique ones. # This is an optimization. Without this, we can still pass all # the tests by trying all lengths. candidateLen = set([len(item) for item in dict]) for breakAfterCurrent in xrange(sLen): if s[: breakAfterCurrent+1] in dict: # The substring from beginning to here is in the dict. # We can make a break between this position and its # next position. couldBreak[breakAfterCurrent].append([s[: breakAfterCurrent+1]]) # Otherwise, we will try to check, whether this substring # s[:breakAfterCurrent+1] could be composed by breakable # head and a tail, which is in the dict. for preBreak in candidateLen: preBreak = breakAfterCurrent - preBreak if preBreak < 0: # Not enough characters. continue elif couldBreak[preBreak] == []: # The head is not breakable continue elif s[preBreak+1: breakAfterCurrent+1] not in dict: # The tail is not in the dict. continue else: combinations = [item +[s[preBreak+1: breakAfterCurrent+1]] for item in couldBreak[preBreak]] couldBreak[breakAfterCurrent].extend(combinations) return [" ".join(combination) for combination in couldBreak[-1]] |