C code. C code run. Run code run… please!
Question: https://codility.com/demo/take-sample-test/count_div Question Name: Count-Div or CountDiv It is completely a mathematic question. Not qualified for a 2-star problem.
1 2 3 | def solution(A, B, K): if A % K == 0: return (B - A) // K + 1 else: return (B - (A - A % K )) // K |
Question: http://oj.leetcode.com/problems/swap-nodes-in-pairs/ Question Name: Swap Nodes in Pairs
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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param a ListNode # @return a ListNode def swapPairs(self, head): # If it is empty list or one-element list, no need to process if head == None or head.next == None: return head # Record the head node of the new list newHead = head.next # We are going to travel the list with two nodes each time. current = head previous = None while current != None and current.next != None: # If there is, we need to adjust the previous node so # that it links to the adjusted remaining list in a # right way. if previous != None: previous.next = current.next previous = current # Adjust the current two nodes temp = current.next.next current.next.next = current current.next = temp # Move to the next round current = current.next return newHead |
Question: http://oj.leetcode.com/problems/merge-k-sorted-lists/ Question Name: Merge k Sorted Lists
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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # Definition and implement of a min heap class _Heap: # Make it 1-based index heap = [None] def __init__(self): return def size(self): return len(self.heap) - 1 def _swin(self, K): while (K > 1 and self.heap[K//2].val > self.heap[K].val): self.heap[K//2], self.heap[K] = self.heap[K], self.heap[K//2] K = K//2 return def _sink(self, K): N = len(self.heap) while 2 * K < N: tempIndex = 2 * K if tempIndex + 1 < N and self.heap[tempIndex + 1].val < self.heap[tempIndex].val: tempIndex += 1 if self.heap[K].val <= self.heap[tempIndex].val: break self.heap[tempIndex], self.heap[K] = self.heap[K], self.heap[tempIndex] K = tempIndex return def add(self, item): self.heap.append(item) self._swin(len(self.heap)-1) return def delMin(self): if len(self.heap) == 2: return self.heap.pop() self.heap[1], self.heap[-1] = self.heap[-1], self.heap[1] temp = self.heap.pop() self._sink(1) return temp class Solution: # @param a list of ListNode # @return a ListNode def mergeKLists(self, lists): # Handle the special case: empty input if len(lists) == 0: return None # Initial our heap with the first node in each list heap = _Heap() for singleList in lists: if singleList != None: heap.add(singleList) # Actually empty input if heap.size() == 0: return None # Build the head of the result list head = heap.delMin() if head.next != None: heap.add(head.next) # Merge the remaining part of all the lists current = head while heap.size() != 0: current.next = heap.delMin() current = current.next if current.next != None: heap.add(current.next) return head |
Question: http://oj.leetcode.com/problems/generate-parentheses/ Question Name: Generate Parentheses A good question to show the good side of recursion. Memorization could improve the performance.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: # @param two integer: the number of remaining "(" and ")" # @return a list of string def _generateParenthesis(self, n, m): if n == 0: return [")"*m] elif n == m: return ["("+i for i in self._generateParenthesis(n-1, m)] else: return ["("+i for i in self._generateParenthesis(n-1, m)] + [")"+i for i in self._generateParenthesis(n, m-1)] # @param an integer # @return a list of string def generateParenthesis(self, n): return self._generateParenthesis(n, n) |
Question: http://oj.leetcode.com/problems/valid-parentheses/ Question Name: Valid Parentheses
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: # @return a boolean def isValid(self, s): stack = [] matchingTable = {"(":")", "[":"]", "{":"}"} for letter in s: if letter == "(" or letter == "[" or letter == "{": stack.append(letter) elif letter == ")" or letter == "]" or letter == "}": if len(stack) == 0 or letter != matchingTable[stack.pop()]: # Unmatched parentheses found return False else: # Only valid parentheses. pass return len(stack) == 0 |
Question: http://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/ Question Name: Remove Nth Node From End of 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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @return a ListNode def removeNthFromEnd(self, head, n): former = head latter = head # Skip n-1 nodes with latter for _ in xrange(n-1): latter = latter.next if latter.next == None: # There are totally n nodes. And we are # removing the head node. head = head.next else: # There are more than n nodes. latter = latter.next # Totally skip n nodes # Find the previous node to the nth node from end while latter.next != None: former = former.next latter = latter.next # Remove the nth node from end former.next = former.next.next return head |
Quesion: http://oj.leetcode.com/problems/4sum/ Question Name: 4Sum or 4-sum The key point is to prune when further qualified combination is not possible.
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 | class Solution: # @return a list of lists of length 4, [[val1,val2,val3,val4]] def fourSum(self, num, target): result = [] num.sort() firstIndex = 0 while firstIndex < len(num)-3: secondIndex = firstIndex + 1 while secondIndex < len(num)-2: thirdIndex = secondIndex + 1 fourthIndex = len(num) - 1 while thirdIndex < fourthIndex: if num[firstIndex] + num[secondIndex] + num[thirdIndex] + num[thirdIndex] > target: # Already too larger, not possible to find any qualified # list afterwards break if num[firstIndex] + num[secondIndex] + num[fourthIndex] + num[fourthIndex] < target: # Already too small, not possible to find any qualified # list forwards break temp = num[firstIndex] + num[secondIndex] + num[thirdIndex] + num[fourthIndex] if temp == target: result.append([num[firstIndex], num[secondIndex], num[thirdIndex], num[fourthIndex]]) # Skip the duplicate numbers as num[thirdIndex] thirdIndex += 1 while thirdIndex < fourthIndex + 1 and num[thirdIndex] == num[thirdIndex-1]: thirdIndex += 1 # Skip the duplicate numbers as num[fourthIndex] fourthIndex -= 1 while fourthIndex > thirdIndex -1 and num[fourthIndex] == num[fourthIndex+1]: fourthIndex -= 1 elif temp > target: # Skip the duplicate numbers as num[fourthIndex] fourthIndex -= 1 while fourthIndex > thirdIndex -1 and num[fourthIndex] == num[fourthIndex+1]: fourthIndex -= 1 else: # Skip the duplicate numbers as num[thirdIndex] thirdIndex += 1 while thirdIndex < fourthIndex + 1 and num[thirdIndex] == num[thirdIndex-1]: thirdIndex += 1 # Skip the duplicate numbers as num[secondIndex] secondIndex += 1 while secondIndex < len(num)-1 and num[secondIndex] == num[secondIndex-1]: secondIndex += 1 # Skip the duplicate numbers as num[firstIndex] firstIndex += 1 while firstIndex < len(num) - 2 and num[firstIndex] == num[firstIndex-1]: firstIndex += 1 return result |
Question: https://codility.com/demo/take-sample-test/nailing_planks Question Name: Nailing Planks or NailingPlanks This question is designed to be solved with binary search method (BUT there is a better solution! It is updated at the end of this post.). And the binary solution is as … Read More »
Question: https://codility.com/demo/take-sample-test/min_max_division Question Name: Min-Max-Division or MinMaxDivision Logically, it seems to be similar with the boron2013 (Flags) challenge by Codility. And the following is my Python solution. UPDATE – 2014/09/19: thanks to Martin Kysel. The function signature is changed to: … Read More »
Question: http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/ Question Name: Letter Combinations of a Phone Number
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution: # @return a list of strings, [s1, s2] def letterCombinations(self, digits): # Mapping table for translating number to letters num2letter = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"} # The result for an empty string is an empty string. if len(digits) == 0: return [""] # We are only handling numbers from 2 to 9. if not digits[0] in num2letter: raise LookupError("Unacceptable input.") # Terminate case for recursion if len(digits) == 1: return [i for i in num2letter[digits[0]]] # The strings for the current digit. temp = [i for i in num2letter[digits[0]]] result = [] # Recursion case. Append the recursion result to each string for current digit. for tail in self.letterCombinations(digits[1:]): result.extend([i+tail for i in temp]) return result |