C code. C code run. Run code run… please!
Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1384 Question Name: Find an Integer in 2D Array Question Description: in a 2D array, independently every row/column is already sorted in ascending order. Given a such 2D array and an integer, write a function to check … Read More »
Question: https://codility.com/demo/take-sample-test/delta2011 Question Name: Delta2011 or Min-Abs-Sum or MinAbsSum I did not solve it in a golden way. The official solution is so elegant.
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 | def solution(A): # Since S could be 1 or -1, it does not matter that # each element in A is positive or negative. A = [abs(item) for item in A] sumOfA = sum(A) # Get the number distribution. So we do not need to try # each number for multiple times. numbers = {} for item in A: numbers[item] = numbers.get(item, 0) + 1 # This is the KEY point. # Typically, we will use possible = [False] * len to track, which numbers # could be the result by summing up subsets of A. # For a number, appeared for many times, there will be multiple attempts # for it. But in this way, when we are trying number n, # possible[i] == -1 means it is impossible. # possible[i] == i >= 0 means it is possible and there are i n(s) left to use. # So for ALL number n(s), we only need ONE scan over the record. possible = [-1] * (sumOfA // 2 + 1) possible[0] = 0 for number in numbers: # Try each distinct number for trying in xrange(sumOfA//2+1): if possible[trying] >= 0: # Can be reached with previous numbers possible[trying] = numbers[number] elif trying >= number and possible[trying-number] > 0: # Cannot be reached with only previous numbers. # But could be achieved with previous numbers AND current one. possible[trying] = possible[trying-number] - 1 # Divide the A into two parts: P and Q, with restriction P <= Q. # So P <= sumOfA // 2 <= Q. We want the largest possible P, so that # Q-P is minimized. for halfSum in xrange(sumOfA//2, -1, -1): if possible[halfSum] >= 0: return sumOfA - halfSum - halfSum raise Exception("Should never be here!") return 0 |
Question: https://codility.com/demo/take-sample-test/str_symmetry_point Question Name: Str-Symmetry-Point or StrSymmetryPoint
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def solution(S): sLen = len(S) # Symmetry point is possible, when and only when the # string's length is odd. if sLen % 2 == 0: return -1 # With a odd-length string, the only possible symmetry # point is the middle point. mid = sLen // 2 begin, end = 0, sLen-1 # The middle point of an odd-length string is symmetry # point, only when the string is symmetry. while begin < mid: if S[begin] != S[end]: return -1 begin += 1 end -= 1 return mid |
Question: https://codility.com/demo/take-sample-test/tie_ropes Question Name: Tie-Ropes or TieRopes
1 2 3 4 5 6 7 8 9 10 11 12 | def solution(K, A): # The number of tied ropes, whose lengths # are greater than or equal to K. count = 0 # The length of current rope (might be a tied one). length = 0 for rope in A: length += rope # Tied with the previous one. # Find a qualified rope. Prepare to find the # next one. if length >= K: count += 1; length = 0 return count |
Question: https://codility.com/demo/take-sample-test/count_factors Question Name: Count-Factors or CountFactors
1 2 3 4 5 6 7 8 9 10 | def solution(N): candidate = 1 result = 0 while candidate * candidate < N: # N has two factors: candidate and N // candidate if N % candidate == 0: result += 2 candidate += 1 # If N is square of some value. if candidate * candidate == N: result += 1 return result |
Question: https://codility.com/demo/take-sample-test/missing_integer Question Name: Missing-Integer or MissingInteger
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def solution(A): ''' Solve it with Pigeonhole principle. There are N integers in the input. So for the first N+1 positive integers, at least one of them must be missing. ''' # We only care about the first N+1 positive integers. # occurrence[i] is for the integer i+1. occurrence = [False] * (len(A) + 1) for item in A: if 1 <= item <= len(A) + 1: occurrence[item-1] = True # Find out the missing minimal positive integer. for index in xrange(len(A) + 1): if occurrence[index] == False: return index + 1 raise Exception("Should never be here.") return -1 |
Question: https://oj.leetcode.com/problems/reverse-words-in-a-string/ Question Name: Reverse Words in a String To solve it with Python, it is as simple as one statement.
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 | class Solution: # @param s, a string # @return a string def reverseWords(self, s, method = "Stack"): methodDic = { "Pythonic" : self.reverseWordsPythonic, "Recursive" : self.reverseWordsRec, "Stack" : self.reverseWordsStack, } methodFun = methodDic.get(method, None) if methodFun == None: raise Exception("Require unknown method: " + method) else: return methodFun(s) # @param s, a string # @return a string def reverseWordsStack(self, s): ''' Solve it with a stack ''' stack = [] index = 0 while index < len(s): nextWord = "" # Skip the spaces while index < len(s) and s[index] == " ": index += 1 # Extract the next non-space word while index < len(s) and s[index] != " ": nextWord += s[index] index += 1 # Push the word into stack. So that when we pop them out later, # the order is reversed. if nextWord != "": stack.append(nextWord) if len(stack) == 0: # No word is in the s return "" else: result = stack.pop() while len(stack) != 0: result += " " + stack.pop() return result # @param s, a string # @return a string def reverseWordsRec(self, s): ''' Solve it in a recursive method ''' # Reach the end. if s == "": return "" firstWord = "" # Find the first word in the remaining content. index = 0 # Skip the heading spaces. while index < len(s) and s[index] == " ": index += 1 # Extract the first non-space word. while index < len(s) and s[index] != " ": firstWord += s[index] index += 1 # Recursively get the result for the remaining part. remaining = self.reverseWordsRec(s[index:]) # This is the last word or the tailing spaces. if remaining == "": return firstWord # THis word is not in the last position. else: return remaining + " " + firstWord # @param s, a string # @return a string def reverseWordsPythonic(self, s): ''' Solve it in a Pythonic way. ''' return " ".join(s.split()[::-1]) |
But is there a better way? Anyone, who read the excellent book Programming Pearls before, might remember Doug McIlroy’s … Read More »
Question: https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/ Question Name: Evaluate Reverse Polish Notation
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 | class Solution: # @param tokens, a list of string # @return an integer def evalRPN(self, tokens, method = "Ite"): if method == "Ite": return self.evalRPNIte(tokens) elif method == "Rec": return self.evalRPNRec(tokens) else: raise Exception("Invalid method.") # @param tokens, a list of string # @return an integer def evalRPNIte(self, tokens): ''' Eval the RPN in an iterative method. ''' waiting = [] while len(tokens) != 0: token = tokens.pop() if not token in set(["+", "-", "*", "/"]): # This is an operand. token = int(token) while len(waiting) != 0 and type(waiting[-1]) == int: otherOperand = waiting.pop() operator = waiting.pop() if operator == "+": token += otherOperand elif operator == "-": token -= otherOperand elif operator == "*": token *= otherOperand elif operator == "/": # http://stackoverflow.com/questions/5535206/python-negative-integer-division-surprising-result # Because Python uses floor division. (-6) / 7 = -1, and -(6 / 7) = 0. if (token > 0 and otherOperand > 0) or (token < 0 and otherOperand < 0): token = abs(token) // abs(otherOperand) else: token = - (abs(token) // abs(otherOperand)) else: raise Exception("Unknown Token.") waiting.append(token) else: # This is an operator. waiting.append(token) return waiting[-1] # @param tokens, a list of string # @return an integer def evalRPNRec(self, tokens): ''' Eval the RPN in a recursive method. ''' assert len(tokens) != 0 token = tokens.pop() if not token in set(["+", "-", "*", "/"]): # This is an operand. return int(token) else: # This is an operator. # The corresponding operands are in the stack. So the second # operand is on the top of the first one. secondParameter = self.evalRPN(tokens) firstParameter = self.evalRPN(tokens) if token == "+": return firstParameter + secondParameter elif token == "-": return firstParameter - secondParameter elif token == "*": return firstParameter * secondParameter elif token == "/": # http://stackoverflow.com/questions/5535206/python-negative-integer-division-surprising-result # Because Python uses floor division. (-6) / 7 = -1, and -(6 / 7) = 0. if secondParameter == 0: raise ZeroDivisionError() elif firstParameter > 0 and secondParameter > 0: return firstParameter // secondParameter elif firstParameter < 0 and secondParameter > 0: return - ((-firstParameter) // secondParameter) elif firstParameter > 0 and secondParameter < 0: return - (firstParameter // (-secondParameter)) else: return (-firstParameter) // (-secondParameter) else: raise Exception("Unknown Token.") |
Question: https://oj.leetcode.com/problems/max-points-on-a-line/ Question Name: Max Points on a Line
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 | # Definition for a point # class Point: # def __init__(self, a=0, b=0): # self.x = a # self.y = b class Solution: # @param a, an integer # @param b, an integer # @return an integer, the Greatest Common Divisor of a and b. def _getGCD(self, a, b): ''' Compute the Greatest Common Divisor of a and b. ''' if a < b: a, b = b, a if a % b != 0: return self._getGCD(b, a%b) else: return b # @param points, a list of Points # @return an integer def maxPoints(self, points): if len(points) == 0: return 0 maxCount = 1 # For a single point for index in xrange(len(points)-1): point = points[index] maxCountForThisPoint = 0 # Each to-compare point must fall into one of the following # four cases. vertical = 0 # The two points are on one vertical line. horizontal = 0 # The two points are on one horizontal line. samePos = 1 # The points are in one completely same position. # At least it has the same position as itself. slop = {} # For all the other cases. for toCmp in points[index+1:]: diffX = toCmp.x - point.x diffY = toCmp.y - point.y if diffX == 0 and diffY == 0: samePos += 1 elif diffX == 0: vertical += 1 elif diffY == 0: horizontal += 1 else: # Make sure either: # Both diffX and diffY are positive; # OR # diffX is negative while diffY positive. # So that we can get slop(-5,3) == slop(5,-3). if diffX < 0 and diffY < 0: diffX, diffY = -diffX, -diffY elif diffX < 0 or diffY < 0: diffX, diffY = -abs(diffX), abs(diffY) # Simplify the diffX and diffY. So that we could # get slop(5, 10) == slop(1,2). gcd = self._getGCD(abs(diffX), diffY) diffX //= gcd diffY //= gcd slop[(diffX, diffY)] = slop.get((diffX, diffY), 0) + 1 # Find the maximum number of points that lie on the same straight line, # which cross the current point. if len(slop) != 0: maxCountForThisPoint = max(slop.values()) maxCountForThisPoint = max(vertical, horizontal, maxCountForThisPoint) maxCountForThisPoint += samePos maxCount = max(maxCount, maxCountForThisPoint) return maxCount |
Question: https://oj.leetcode.com/problems/sort-list/ Question Name: 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 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 | # 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 sortList(self, head): ''' In the common sorting algorithms, there are only two, which can guarantee Nlog(N) in the worst case. The two are merge sorting and heap sorting. Heap sorting is apparently not suitable for this challenge, because it requires array to store the elements. We are going to solve this challenge with bottom-up merge sorting. ''' if head == None: return None mergeSize = 1 # Bottom-up merge sorting. finishSort = False # Add a pseudo head node to make the process uniform. # In the original list, during the merging, the head node might change. # But after adding this pseudo head node, the head node never changes. pseudoHead = ListNode(-1) pseudoHead.next = head while not finishSort: # Start a new round of merging. endOfSorted = pseudoHead while endOfSorted.next != None: # The start position of the first merged list. firstToSort = endOfSorted.next # The start position of the second merged list. secondToSort = firstToSort for _ in xrange(mergeSize): secondToSort = secondToSort.next if secondToSort == None: break if secondToSort == None: # Reach the end of the whole list. No need to # merge anymore. if firstToSort == pseudoHead.next: # Did not merge anything in this round, because # mergeSize >= listSize. Whole list is sorted. finishSort = True break # Record how many nodes in first and second list are # merged. firstListCount will finally be mergeSize. # secondListCount might be either less than or equal # to mergeSize. firstListCount, secondListCount = 0, 0 # Merge the firstToSort and secondToSort. # # Actually we do NOT need to get the end positions of # lists. We can determine their end during the merge # process with two counters. # # In my first answer, I found the end positions of # both to-merge lists. It leads to Time Limit Exceeded. while firstListCount < mergeSize and secondListCount < mergeSize and secondToSort != None: if firstToSort.val <= secondToSort.val: endOfSorted.next = firstToSort endOfSorted = endOfSorted.next firstToSort = firstToSort.next firstListCount += 1 else: endOfSorted.next = secondToSort endOfSorted = endOfSorted.next secondToSort = secondToSort.next secondListCount += 1 if firstListCount == mergeSize: # THere may be some left nodes in second to-sort list. while secondListCount < mergeSize and secondToSort != None: endOfSorted.next = secondToSort endOfSorted = endOfSorted.next secondToSort = secondToSort.next secondListCount += 1 else: # THere may be some left nodes in first to-sort list. while firstListCount < mergeSize: endOfSorted.next = firstToSort endOfSorted = endOfSorted.next firstToSort = firstToSort.next firstListCount += 1 endOfSorted.next = secondToSort # Double the mergeSize for the next round. mergeSize = mergeSize << 1 # Skip the pseudo head node. return pseudoHead.next |