C code. C code run. Run code run… please!
Question: https://leetcode.com/problems/factorial-trailing-zeroes/ Question Name: Factorial Trailing Zeroes I firstly saw this question on CTCI. The key points of the solution are: Every interger could be represented as (2^i)*(5^j)*x, where i, j >= 0 and x cannot be evenly divided by … Read More »
Question: https://leetcode.com/problems/excel-sheet-column-number/ Question Name: Excel Sheet Column Number This tiny website is hosted on a free provider. Therefore it is not as strong as the big guys. SORRY for any inconvenience recently.
1 2 3 4 5 6 7 8 | class Solution: # @param {string} s # @return {integer} def titleToNumber(self, s): result = 0 for letter in s: result = result * 26 + (ord(letter) - ord("A") + 1) return result |
Question: https://leetcode.com/problems/majority-element/ Question Name: Majority Element We can do it with a dictionary (O(N) time, O(N) space). For a better solution with O(N) time and O(1) space, we can remove pairs of different elements as many as possible, and the … Read More »
Question: https://leetcode.com/problems/excel-sheet-column-title/ Question Name: Excel Sheet Column
1 2 3 4 5 6 7 8 9 | class Solution: # @return a string def convertToTitle(self, num): result = [] while num != 0: num -= 1 result.append(chr(ord("A") + (num % 26))) num //= 26 return "".join(result[::-1]) |
Question: https://leetcode.com/problems/fraction-to-recurring-decimal/ Question Name: Fraction to Recurring Decimal Again, a little mathematical puzzle. Pay attention to some corner cases.
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 | class Solution: # @return a string def fractionToDecimal(self, numerator, denominator): # Adjust the sign of the input. sign = "" if numerator < 0 and denominator > 0: numerator = -numerator sign = "-" if numerator > 0 and denominator < 0: denominator = -denominator sign = "-" # Check the case when numerator is divisible by denominator remaining = numerator % denominator if remaining == 0: return sign + str(numerator // denominator) # Process the fractional part. It is a mathematical story: balala... result = [sign, str(numerator // denominator), "."] position = {} # A dictionary of dictionary current = 3 while remaining != 0: remaining *= 10 newvalue = remaining // denominator if not newvalue in position: position[newvalue] = {} newRemaining = remaining % denominator if newRemaining == 0: # Division finished. result.append(str(newvalue)) break elif newRemaining in position[newvalue]: # Loop is found. result.insert(position[newvalue][newRemaining], "(") result.append(")") break result.append(str(newvalue)) position[newvalue][newRemaining] = current # Prepare the next digit. remaining = remaining % denominator current += 1 return "".join(result) |
Â
Question: https://leetcode.com/problems/compare-version-numbers/ Question Name: Compare Version Numbers Clean up the tailing 0(s), and the right answer is there.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution: # @param version1, a string # @param version2, a string # @return an integer def compareVersion(self, version1, version2): # Split the version number with dot, and clear the tailing 0(s) versionList1 = [int(ver) for ver in version1.split(".")] while len(versionList1) > 1 and versionList1[-1] == 0: versionList1.pop() versionList2 = [int(ver) for ver in version2.split(".")] while len(versionList2) > 1 and versionList2[-1] == 0: versionList2.pop() shorterVersion = min(len(versionList1), len(versionList2)) # Compare the common part of version numbers. for i in xrange(shorterVersion): if versionList1[i] > versionList2[i]: return 1 elif versionList1[i] < versionList2[i]: return -1 # Check the remaining part of version number. if len(versionList1) != shorterVersion: return 1 elif len(versionList2) != shorterVersion: return -1 else: return 0 |
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 »
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] |