LeetCode – Page 4

Solution to Excel Sheet Column Number by LeetCode

23 Apr

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.

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

Solution to Majority Element by LeetCode

9 Apr

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 »

Solution to Excel Sheet Column Title by LeetCode

9 Apr

Question: https://leetcode.com/problems/excel-sheet-column-title/ Question Name: Excel Sheet Column

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])

Solution to Fraction to Recurring Decimal by LeetCode

8 Apr

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.

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)

Solution to Compare Version Numbers by LeetCode

7 Apr

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.

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

Solution to Maximum Gap by LeetCode

6 Apr

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 »

Solution to Combine Two Tables by LeetCode

28 Feb

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.

# Write your MySQL query statement below

SELECT FirstName, LastName, City, State

FROM Person LEFT JOIN Address

ON Person.PersonId = Address.PersonId

Solution to Find Peak Element by LeetCode

26 Dec

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.

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)

Solution to Intersection of Two Linked Lists by LeetCode

25 Dec

Question: https://oj.leetcode.com/problems/intersection-of-two-linked-lists/ Question Name: Intersection of Two Linked Lists

# 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

Solution to Min Stack by LeetCode

21 Dec

Question: https://oj.leetcode.com/problems/min-stack/ Question Name: Min Stack

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]

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...