C code. C code run. Run code run… please!
Question: https://leetcode.com/problems/maximum-gap/ Question Name: Maximum Gap The solution uses the bucket sorting and Pigeonhole principle. We divide the input range into bucketCount ranges. Each sub-section has the same length, and the sum of all the sub-sections covers the whole input … Read More »
Sometimes, the visitors posted their code in the comment section. That is an awesome way to share and communicate. However, in some cases, partial of the code inside pre/code section is missing. This unexpected feature bothered me for a long … Read More »
Question: https://oj.leetcode.com/problems/combine-two-tables/ Question Name: Combine Two Tables This problem is used to check our knowledge in JOIN. LEFT JOIN is used here. But we should also know about the others like INNER JOIN, RIGHT JOIN and OUTER JOIN.
1 2 3 4 | # Write your MySQL query statement below SELECT FirstName, LastName, City, State FROM Person LEFT JOIN Address ON Person.PersonId = Address.PersonId |
Question: https://oj.leetcode.com/problems/find-peak-element/ Question Name: Find Peak Element The key point is: return the index to ANY ONE of the peaks. So O(logN) is 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 | class Solution: # @param num, a list of integer # @base, the base index for tail recursion. # @return an integer def findPeakElement(self, num, base = 0): # Refer to www.geeksforgeeks.org/find-a-peak-in-a-given-array/ # Because num[-1] = num[n] = negative infinity, if there is only # one element in the list, it is a peak. if len(num) == 1: return base # If there are two two elements in the list, the greater one is # the peak. if len(num) == 2: if num[0] > num[1]: return base else: return base + 1 mid = (len(num) - 1) // 2 if num[mid-1] < num[mid] and num[mid+1] < num[mid]: # The middle element is a peak. return mid + base elif num[mid] < num[mid-1]: # There must be one or more peak(s) in the left part. return self.findPeakElement(num[:mid], base) else: # There must be one or more peak(s) in the right part. return self.findPeakElement(num[mid+1:], mid + 1 + base) |
Question: https://oj.leetcode.com/problems/intersection-of-two-linked-lists/ Question Name: Intersection of Two Linked 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 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # Get the length of the given linked list # @param ListNodes # @return the length of the linked list def _length(self, head): current = head length = 0 while current != None: current = current.next length += 1 return length # Find the intersection node of two linked list, if it exists. # @param two ListNodes # @return the intersected ListNode or None def getIntersectionNode(self, headA, headB): lenA = self._length(headA) lenB = self._length(headB) # Make sure the list A is no longer that list B. if lenA > lenB: lenA, lenB = lenB, lenA headA, headB = headB, headA # Handle with the special case. if lenA == 0 or lenB == 0: return None # Skip the leading nodes in list B, which is impossible to be # the intersection node. currentA = headA currentB = headB for _ in xrange(lenB - lenA): currentB = currentB.next # Try to find the intersection node while currentA != None and id(currentA) != id(currentB): currentA = currentA.next currentB = currentB.next return currentA |
Question: https://oj.leetcode.com/problems/min-stack/ Question Name: Min Stack
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 | class MinStack: def __init__(self): self.data = [] # Store all the data self.minData = [] # Store the minimum element so far # @param x, an integer # @return nothing def push(self, x): self.data.append(x) # Check if we need to update the minimum value if len(self.minData) == 0 or x <= self.minData[-1]: self.minData.append(x) # @return an integer def pop(self): if len(self.data) == 0: # Empty stack return None else: if self.data[-1] == self.minData[-1]: self.minData.pop() return self.data.pop() # @return an integer def top(self): if len(self.data) == 0: return None # Empty stack else: return self.data[-1] # @return an integer def getMin(self): if len(self.minData) == 0: return None # Empty stack else: return self.minData[-1] |
Question: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ Question Name: Find Minimum in Rotated Sorted Array II This question is essentially the same as the prevous one.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: # @param num, a list of integer # @return an integer def findMin(self, num): if num[0] < num[-1]: # Completely sorted return num[0] elif len(num) < 5: # The input is small enough to do a linear search. return min(num) else: # The length of input is greater than 2. So the division won't get # an empty list. # The input may be or may be not sorted. mid = (len(num) - 1) // 2 return min(self.findMin(num[:mid]), self.findMin(num[mid:])) |
Question: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Question Name: Find Minimum in Rotated Sorted Array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: # @param num, a list of integer # @return an integer def findMin(self, num): if num[0] < num[-1]: # Completely sorted return num[0] elif len(num) < 3: # The input is small enough to do a linear search. return min(num) else: # The length of input is greater than 2. So the division won't get # an empty list. mid = (len(num) - 1) // 2 return min(self.findMin(num[:mid]), self.findMin(num[mid:])) |
Question: https://oj.leetcode.com/problems/maximum-product-subarray/ Question Name: Maximum Product Subarray The following solution is not the optimal. Because the recursion is not necessary. But recursion does make the coding easier.
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 | class Solution: # @param A, a list of non-zero integers # @return an integer def maxProductWithoutZero(self, A): # Two base cases for this recursive method. if len(A) == 0: return 0 if len(A) == 1: return A[0] negativeCount = len([i for i in A if i < 0]) if negativeCount % 2 == 0: # There are even number of negative integers. The product of all them # is a positive integer as the maximum product among all subarrays. return reduce(lambda x, y: x * y, A, 1) else: # There are odd number of negative integers. We divide the array into # two subarray: one without the first negative integer, and the other # without the last negative integer. firstNeg = 0 while firstNeg < len(A): if A[firstNeg] < 0: break firstNeg += 1 lastNeg = len(A) - 1 while lastNeg >= 0: if A[lastNeg] < 0: break lastNeg -= 1 return max(self.maxProductWithoutZero(A[:lastNeg]), self.maxProductWithoutZero(A[firstNeg + 1:])) # @param A, a list of integers # @return an integer def maxProduct(self, A): begin, end = 0, 0 if A.count(0) != 0: maxProd = 0 else: maxProd = A[0] # Use 0 (zero) as delimiter to split the original array into small ones, # which do not contain 0. while end < len(A): if A[end] != 0: end += 1 else: maxProd = max(maxProd, self.maxProductWithoutZero(A[begin : end])) end += 1 begin = end return max(maxProd, self.maxProductWithoutZero(A[begin : end])) |
Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1509 Question Name: Lowest Common Ancestor Question Description: Find the lowest common ancestor of two nodes in a binary tree. Input: the input might contain multiple test cases. Globally the first line includes one interger N (0 … Read More »