Sheng – Page 18 – Code Says

Solution to Same Tree by LeetCode

2 Jul

Question: https://oj.leetcode.com/problems/same-tree/ Question Name: Same Tree

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param p, a tree node

# @param q, a tree node

# @return a boolean

def isSameTree(self, p, q):

if p == None and q == None:

return True

elif p == None or q == None:

return False

elif p.val == q.val:

return self.isSameTree(p.left, q.left) and

self.isSameTree(p.right, q.right)

else:

return False

Solution to Validate Binary Search Tree by LeetCode

2 Jul

Question: https://oj.leetcode.com/problems/validate-binary-search-tree/ Question Name: Validate Binary Search Tree This is an extension of an older question Binary Tree Inorder Traversal.

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return a list of integers

def inorderTraversal(self, root):

# Handle with the special cast (empty input)

if root == None: return []

stack = [root]

current = root.left

result = []

while len(stack) != 0 or current != None:

# Find the leftmost node among all the un-accessed ones.

while current != None:

stack.append(current)

current = current.left

# Fetch the value in currently leftmost node

current = stack.pop()

result.append(current.val)

# Try the right son of current node

current = current.right

return result

# @param root, a tree node

# @return a boolean

def isValidBST(self, root):

inOrder = self.inorderTraversal(root)

# If root is a binary search tree, the result of in order

# travle will be strickly increasing.

for index in xrange(len(inOrder)-1):

if inOrder[index] >= inOrder[index+1]:

return False

return True

Solution to Interleaving String by LeetCode

2 Jul

Question: https://oj.leetcode.com/problems/interleaving-string/ Question Name: Interleaving String

class Solution:

# @return a boolean

def isInterleaveHelper(self, s1, s1Index, s2, s2Index, s3, s3Index,

accessed):

if (s1Index, s2Index) in accessed:

# Have tried. Did not success. Wont success.

return False

else:

accessed.add((s1Index, s2Index))

# Checked all contents in s3. s3 is formed by the interleaving of

# s1 and s2

if s3Index == len(s3):

return True

# Try to use the next character in s1

if s1Index != len(s1) and s1[s1Index] == s3[s3Index]:

if self.isInterleaveHelper(s1, s1Index+1, s2, s2Index, s3,

s3Index+1, accessed):

return True

# Try to use the next character in s2

if s2Index != len(s2) and s2[s2Index] == s3[s3Index]:

if self.isInterleaveHelper(s1, s1Index, s2, s2Index+1, s3,

s3Index+1, accessed):

return True

return False

# @return a boolean

def isInterleave(self, s1, s2, s3):

# Check length firstly.

if len(s1) + len(s2) != len(s3):

return False

# Then check the character count.

charDis = {}

for item in s1: charDis[item] = charDis.get(item, 0) + 1

for item in s2: charDis[item] = charDis.get(item, 0) + 1

for item in s3: charDis[item] = charDis.get(item, 0) - 1

for item in charDis:

if charDis[item] != 0: return False

# Finally check overleaving

return self.isInterleaveHelper(s1, 0, s2, 0, s3, 0, set())

Solution to Binary Tree Inorder Traversal by LeetCode

1 Jul

Question: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/ Question Name: Binary Tree Inorder Traversal

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return a list of integers

def inorderTraversal(self, root):

# Handle with the special cast (empty input)

if root == None: return []

stack = [root]

current = root.left

result = []

while len(stack) != 0 or current != None:

# Find the leftmost node among all the un-accessed ones.

while current != None:

stack.append(current)

current = current.left

# Fetch the value in currently leftmost node

current = stack.pop()

result.append(current.val)

# Try the right son of current node

current = current.right

return result

Solution to Unique Binary Search Trees II by LeetCode

1 Jul

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

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param a list(representing trees)

# @return the root node the tree

def convertArray2Trees(self, array):

result = [TreeNode(i+1) for i in xrange(len(array))]

root = None

for index in xrange(len(array)):

if array[index] == -1:

# This node has no father. It is the root node.

root = result[index]

else:

if array[index] > index:

# Its father is on the right side. Thus it is

# father's left son.

result[array[index]].left = result[index]

else:

# Its father is no the left side.

result[array[index]].right = result[index]

return root

# @return a list of lists(representing trees)

def generateArray(self, array, current, left, right):

result = []

resultTemp = []

# Not possible to have any son.

if left >= current and current >= right:

return [array]

# Fill the left son

if left >= current:

resultTemp = [array]

else:

for son in xrange(left, current):

temp = array * 1

temp[son] = current

resultTemp.extend(self.generateArray(temp, son, left, current-1))

# Fill the right son

if current >= right:

result = resultTemp

else:

for tempStatus in resultTemp:

for son in xrange(current+1, right+1):

temp = tempStatus * 1

temp[son] = current

result.extend(self.generateArray(temp, son, current+1, right))

return result

# @return a list of tree node

def generateTrees(self, n):

# Handle the special case.

if n == 0: return [None]

result = []

# We firstly generate the trees in form of array.

# array[i] == j means, the i(th) node's father is j(th) node. (0-based)

for root in xrange(n):

temp = [-1] * n

tempRes = self.generateArray(temp, root, 0, n-1)

result.extend(tempRes)

# Convert the arrays into trees.

return [self.convertArray2Trees(array) for array in result]

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

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

Fabien November 7, 2024 at 4:42 am on Unofficial Solutions to the Training by CodilitySimilar but more compact solution using C++17 or later: #include <stack> #include <vector> using namespace std; using point = pair<int, int>; stack<point> pending; void explore(const...
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 /...