LeetCode – Page 11

Solution to Unique Binary Search Trees by LeetCode

1 Jul

Question: https://oj.leetcode.com/problems/unique-binary-search-trees/ Question Name: Unique Binary Search Trees

class Solution:

# @return an integer

def numTrees(self, n):

# numOfTrees[i] == j means for n is i, there are j unique

# binary search trees for it.

numOfTrees = [1, 1, 2]

nextTrying = len(numOfTrees)

while nextTrying <= n:

# Comptute how many unique binary search trees are there for

# n == nextTrying.

count = 0

for center in xrange(nextTrying):

# numOfTrees[center] is the number of unique binary search

# trees in the left son

# numOfTrees[nextTrying-center-1] is the number of unique

# binary search trees in the right son

# numOfTrees[center] * numOfTrees[nextTrying-center-1] is

# the number of unique binary search trees with "center"

# being the root.

count += numOfTrees[center] * numOfTrees[nextTrying-center-1]

numOfTrees.append(count)

nextTrying += 1

return numOfTrees[n]

Solution to Restore IP Addresses by LeetCode

30 Jun

Question: https://oj.leetcode.com/problems/restore-ip-addresses/ Question Name: Restore IP Addresses

class Solution:

# @param s, a string

# @return a boolean to indicate whether s is a valid IP address section.

def restoreIpAddressesHelper(self,s):

assert 0 < len(s) <= 3

if len(s) == 1: return True

elif len(s) == 2 and s[0] != "0": return True

else:

if s[0] == "1": return True

elif s[0] == "2":

if s[1] in "01234": return True

elif s[1] == "5":

if s[2] in "012345": return True

return False

# @param s, a string

# @return a list of strings

def restoreIpAddresses(self, s):

# Check the length of s. Too long or too short makes it impossible

# to be a valid IP address.

if not 4 <= len(s) <= 12: return []

result = []

for i in xrange(1, len(s)-2):

# The first section cannot be longer than 3.

if i > 3: break

for j in xrange(i+1, len(s)-1):

# THe second section cannot be longer than 3.

if j - i > 3: break

for k in xrange(j+1, len(s)):

# The third section cannot be longer than 3.

if k - j > 3: break

# The last section cannot be longer than 3.

if len(s) - k > 3: continue

# Validate the four sections one by one.

if not self.restoreIpAddressesHelper(s[:i]): continue

if not self.restoreIpAddressesHelper(s[i:j]): continue

if not self.restoreIpAddressesHelper(s[j:k]): continue

if not self.restoreIpAddressesHelper(s[k:]): continue

# All sections passed the validation. This is a valid

# IP address.

result.append(s[:i] + "." + s[i:j] + "." + s[j:k] +

"." + s[k:])

return result

Solution to Reverse Linked List II by LeetCode

30 Jun

Question: https://oj.leetcode.com/problems/reverse-linked-list-ii/ Question Name: Reverse Linked List II

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @param m, an integer

# @param n, an integer

# @return a ListNode

def reverseBetween(self, head, m, n):

# Actually, we do not need to reverse the nodes, when m == n.

if m == n: return head

# Add a pseudo head node, so that we can handle the case m == 1,

# in a same way as that m.

currentNode = pseoduHead = ListNode(-1)

pseoduHead.next = head

current = 0

# Find the last node before the to-reverse zone

while current < m - 1:

currentNode = currentNode.next

current += 1

beforeReverseZone = currentNode

# Push all the nodes in the reversing zone into one stack.

stack = []

for _ in xrange(m, n+1):

stack.append(currentNode.next)

currentNode = currentNode.next

# Find the first node after the to-reverse zone

afterReverseZone = currentNode.next

# Reverse the nodes in the stack. And record the begin and

# end nodes.

reverseListEnd = reverseListHead = stack.pop()

while len(stack) != 0:

reverseListEnd.next = stack.pop()

reverseListEnd = reverseListEnd.next

# Embed the reversed list into the original zone

beforeReverseZone.next = reverseListHead

reverseListEnd.next = afterReverseZone

# Skip the pseudo head node

return pseoduHead.next

Solution to Decode Ways by LeetCode

27 Jun

Question: https://oj.leetcode.com/problems/decode-ways/ Question Name: Decode Ways

class Solution:

# @param s, a string

# @return an integer

def numDecodings(self, s):

# Handle with special cases, string is empty or starting with "0".

if s == "" or s[0] == "0": return 0

numDecodingEndingHere = [0] * (len(s) + 1)

numDecodingEndingHere[0] = 1

index = 0

while index < len(s) - 1:

# We cannot decode one single "0"

if s[index] == "0": return 0

# We can decode current character and move to the next position.

numDecodingEndingHere[index+1] += numDecodingEndingHere[index]

# We can also decode current character and the next one at the smae

# time, and then move to the second next position.

if s[index] == "1" or

(s[index] == "2" and s[index+1] in "0123456"):

numDecodingEndingHere[index+2] += numDecodingEndingHere[index]

if s[index+1] == "0":

# In this case, if the next character is "0", we have to

# skip it, because one single "0" is unable to be decoded.

index += 1

if s[-1] != "0":

# The last character could be decoded.

numDecodingEndingHere[-1] += numDecodingEndingHere[-2]

return numDecodingEndingHere[-1]

Solution to Subsets II by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/subsets-ii/ Question Name: Subsets II

class Solution:

# @param num, a list of integer

# @return a list of lists of integer

def subsetsWithDup(self, S):

''' A problem to test the bit operation.

'''

S.sort() # Make sure the result is non-descending order.

used = set() # The used subset in result

limit = 1 << len(S)

current = 0 # In "current", the i(th) rightmost bit == 1

# means S[i] is chosen.

result = []

while current < limit:

# Construct the list for "current"

temp = []

for index in xrange(len(S)):

if (1 << index) & current != 0:

temp.append(S[index])

tempTuple = tuple(temp)

if not tempTuple in used:

result.append(temp)

used.add(tempTuple)

current += 1

return result

Solution to Merge Sorted Array by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/merge-sorted-array/ Question Name: Merge Sorted Array

class Solution:

# @param A a list of integers

# @param m an integer, length of A

# @param B a list of integers

# @param n an integer, length of B

# @return nothing

def merge(self, A, m, B, n):

lastA, lastB = m-1, n-1 # Travel A and B from right to left

last2Write = m + n -1 # Write the integers from the rightmost

# position to the leftmost position of A

while lastA != -1 and lastB != -1:

if A[lastA] >= B[lastB]:

A[last2Write] = A[lastA]

lastA -= 1

else:

A[last2Write] = B[lastB]

lastB -= 1

last2Write -= 1

# If A list has some remaining items to process, they are already in

# their to-be position. No operation is needed.

# Otherwise, if B list has some remaining items, copy them to the head

# of A.

if lastB != -1: A[:lastB+1] = B[:lastB+1]

return

Solution to Gray Code by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/gray-code/ Question Name: Gray Code At the beginning, I have no idea other than brute force. But thanks to Wikipedia, the perfect solution is found.

class Solution:

# @return a list of integers

def grayCode(self, n):

result = []

for item in xrange(1<<n):

result.append(item ^ (item>>1))

return result

Solution to Partition List by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/partition-list/ Question Name: Partition List

class Solution:

# @param head, a ListNode

# @param x, an integer

# @return a ListNode

def partition(self, head, x):

smaller = ListNode(-1) # A pseudo head node to link all nodes, whose

# value is less than x

others = ListNode(-1) # A pseudo head node to link all nodes, whose

# value is greater than or equal to x

# Record the last nodes in "smaller" and "others" lists respectively.

smallerLast, othersLast = smaller, others

while head != None:

if head.val < x:

# Append to the end of "smaller" list

smallerLast.next = head

smallerLast = smallerLast.next

else:

# Append to the end of "others" list

othersLast.next = head

othersLast = othersLast.next

head = head.next

smallerLast.next = others.next # Append the "others" list to the end

# of "smaller"

othersLast.next = None # Close the whole list

return smaller.next # Skip the pseudo head node.

Solution to Scramble String by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/scramble-string/ Question Name: Scramble String

class Solution:

# @return a boolean

def isScramble(self, s1, s2):

if len(s1) != len(s2): return False

if s1 == s2: return True

# Check their char distribution before trying to swap it.

charDis = {}

for index in xrange(len(s1)): # Gather char distribution

charDis[s1[index]] = charDis.get(s1[index], 0) + 1

charDis[s2[index]] = charDis.get(s2[index], 0) - 1

for index in xrange(len(s1)): # Check char distribution

if charDis[s1[index]] != 0: return False

# Try to divide the strings into two part, and may swap parts.

for index in xrange(1, len(s1)):

# Divided, but did not swap the parts

if self.isScramble(s1[:index], s2[:index]) and

self.isScramble(s1[index:], s2[index:]):

return True

# Divided, and swapped the parts

if self.isScramble(s1[:index], s2[-index:]) and

self.isScramble(s1[index:], s2[:len(s2)-index]):

return True

return False

Solution to Maximal Rectangle by LeetCode

24 Jun

Question: https://oj.leetcode.com/problems/maximal-rectangle/ Question Name: Maximal Rectangle

class Solution:

# @param height, a list of integer

# @return an integer

def largestRectangleArea(self, height):

stack = [] # Store the position of bars with non-decreasing height

maxArea = 0

height.append(-1) # Append a pseudo bar at the end so that, after

# the while loop, the one and the only on bar

# left in the stack will definitely be this

# pseudo bar.

index = 0

# In this loop, we are using the stack to find out the largest zone

# for each bar (to say i), in which bar i is the shortest one.

while index < len(height):

if len(stack) == 0:

# This is the first bar. OR all of its previous bars are

# higher than this one.

stack.append(index)

index += 1

elif height[index] >= height[stack[-1]]:

stack.append(index)

index += 1

else:

preBasin = stack.pop()

if len(stack) == 0:

# From beginning to index-1 position, the preBasin has

# the shortest bar.

maxArea = max(maxArea, height[preBasin] * index)

else:

# From stack[-1] position to index-1 position, the

# preBasin has the shortest bar.

maxArea = max(maxArea, height[preBasin] *

(index-stack[-1]-1) )

return maxArea

# @param matrix, a list of lists of 1 length string

# @return an integer

def maximalRectangle(self, matrix):

# Handle the special case that the matrix is empty

if len(matrix) == 0: return 0

# heights[i][j] means on the i(th) row, begin with j(th) position,

# how many consecutive one(s) are there.

heights = [[0] * len(matrix[0]) for _ in xrange(len(matrix))]

for row in xrange(len(matrix)):

# We are going to travel the row from the end to the beginning

if matrix[row][-1] == "1": heights[row][-1] = 1

for col in xrange(len(matrix[0])-2, -1, -1):

if matrix[row][col] == "0":

heights[row][col] = 0

else:

heights[row][col] = heights[row][col+1] + 1

# We transfer the original challenge into an old question: Largest

# Rectangle in Histogram. We compute the largest rectangle on each

# column (towards right). And then choose the maximum among them.

maxArea = 0

for x in xrange(len(matrix[0])):

maxArea = max(maxArea,

self.largestRectangleArea(

[heights[y][x] for y in xrange(len(matrix))]))

return maxArea

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...