Sheng – Page 15 – Code Says

Solution to Sum Root to Leaf Numbers by LeetCode

13 Jul

Question: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ Question Name: Sum Root to Leaf Numbers

# 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 an array of two integers.

# The first integer is the value

# The second one is the number of digits

def sumNumbersHelper(self, root):

if root.left == None and root.right == None:

return [[root.val, 1]]

temp = []

if root.left != None:

temp.extend(self.sumNumbersHelper(root.left))

if root.right != None:

temp.extend(self.sumNumbersHelper(root.right))

result = []

for item in temp:

result.append([(10**item[1])*root.val+item[0], item[1]+1])

return result

# @param root, a tree node

# @return an integer

def sumNumbers(self, root):

if root == None:

return 0

else:

# Generate all the numbers, represented by each root-to-leaf path.

# Then compute their sum.

return sum([item[0] for item in self.sumNumbersHelper(root)])

Solution to Longest Consecutive Sequence by LeetCode

13 Jul

Question: https://oj.leetcode.com/problems/longest-consecutive-sequence/ Question Name: Longest Consecutive Sequence The requirement should be more accurate: your algorithm should run in O(n) complexity in average condition. I googled the other solutions. All of them used the hash table. But hash table’s time complexity … Read More »

Solution to Word Ladder II by LeetCode

12 Jul

Question: https://oj.leetcode.com/problems/word-ladder-ii/ Question Name: Word Ladder II

class Solution:

# @param start, a set of string

# @return two dictionaries

def _buildSig(self, contents):

sig = {} # Records the signatures for each string

bucket = {} # Records the strings with each signature

for string in contents:

sig[string] = []

for index in xrange(len(string)):

tempSig = string[:index] + "*" + string[index+1:]

sig[string].append(tempSig)

if tempSig not in bucket: bucket[tempSig] = []

bucket[tempSig].append(string)

return sig, bucket

# @param start, a string

# @param end, a string

# @param dict, a set of string

# @return a list of lists of string

def findLadders(self, start, end, dict):

# Build the graph.

# Two nodes (whose value is the string in dict), are connected if

# they have one same signature or more.

sig, bucket = self._buildSig(set([start, end]) | dict)

result = []

accessed = {}

for string in dict: accessed[string] = False

accessed[start] = True

# Travel the graph in breadth-first search.

currentLayer = [[start]]

steps = 1

while len(currentLayer) != 0 and len(result) == 0:

steps += 1

nextLayer = []

accessedTemp = []

for intermediate in currentLayer:

signatures = sig[intermediate[-1]]

for signature in signatures:

for nextLayerCandidate in bucket[signature]:

# Transformation from start to end finished.

if nextLayerCandidate == end:

result.append(intermediate + [end])

continue

# Accessed before. Not to access again.

if accessed[nextLayerCandidate]:

continue

# We cannot set the accessed flag instantly here.

# The other same-deep nodes(stirng) also have the

# right to jump to this node(string).

accessedTemp.append(nextLayerCandidate)

nextLayer.append(intermediate + [nextLayerCandidate])

for item in accessedTemp: accessed[item] = True

currentLayer = nextLayer

return result

Solution to Word Ladder by LeetCode

12 Jul

Question: https://oj.leetcode.com/problems/word-ladder/ Question Name: Word Ladder

class Solution:

# @param start, a set of string

# @return two dictionaries

def _buildSig(self, contents):

sig = {} # Records the signatures for each string

bucket = {} # Records the strings with each signature

for string in contents:

sig[string] = []

for index in xrange(len(string)):

tempSig = string[:index] + "*" + string[index+1:]

sig[string].append(tempSig)

if tempSig not in bucket: bucket[tempSig] = []

bucket[tempSig].append(string)

return sig, bucket

# @param start, a string

# @param end, a string

# @param dict, a set of string

# @return an integer

def ladderLength(self, start, end, dict):

# Build the graph.

# Two nodes (whose value is the string in dict), are connected if

# they have one same signature or more.

sig, bucket = self._buildSig(set([start, end]) | dict)

accessed = {}

for string in dict: accessed[string] = False

accessed[start] = True

# Travel the graph in breadth-first search.

currentLayer = [start]

steps = 1

while len(currentLayer) != 0:

steps += 1

nextLayer = []

for intermediate in currentLayer:

signatures = sig[intermediate]

for signature in signatures:

for nextLayerCandidate in bucket[signature]:

# Transformation from start to end finished.

if nextLayerCandidate == end: return steps

# Accessed before. Not to access again.

if accessed[nextLayerCandidate]: continue

accessed[nextLayerCandidate] = True

nextLayer.append(nextLayerCandidate)

currentLayer = nextLayer

return 0

Solution to Valid Palindrome by LeetCode

11 Jul

Question: https://oj.leetcode.com/problems/valid-palindrome/ Question Name: Valid Palindrome

class Solution:

# @param s, a string

# @return a boolean

def isPalindrome(self, s):

if len(s) < 2: return True

head, tail = 0, len(s)-1

while head < tail:

if not s[head].isalnum():

head += 1

elif not s[tail].isalnum():

tail -= 1

else:

if s[head].lower() == s[tail].lower():

head += 1

tail -= 1

else:

return False

return True

Solution to Best Time to Buy and Sell Stock III by LeetCode

11 Jul

Question: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ Question Name: Best Time to Buy and Sell Stock III This problem is a simplified version of the challenge from Codility.

class Solution:

# @param prices, a list of integer

# @return an integer

def maxProfit(self, prices):

if len(prices) <= 1: return 0

# maxProfitEndingHere records the maximum profit, until here (inclusive)

# with zero or one transaction.

maxProfitEndingHere = [0] * len(prices)

lowestEndingHere = prices[0]

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

lowestEndingHere = min(lowestEndingHere, prices[index])

maxProfitEndingHere[index] = max(maxProfitEndingHere[index-1],

prices[index] - lowestEndingHere)

# maxProfitEndingHere records the maximum profit, after here (inclusive)

# with zero or one transaction.

maxProfitFromHere = [0] * len(prices)

highestFromHere = prices[-1]

for index in xrange(len(prices)-2, -1, -1):

highestFromHere = max(highestFromHere, prices[index])

maxProfitFromHere[index] = max(maxProfitFromHere[index+1],

highestFromHere - prices[index])

# Find the maximum profit, with zeor or one or two transactions.

maxProfit = maxProfitEndingHere[-1]

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

profit = maxProfitEndingHere[index] + maxProfitFromHere[index+1]

maxProfit = max(maxProfit, profit)

return maxProfit

Solution to Binary Tree Maximum Path Sum by LeetCode

10 Jul

Question: https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/ Question Name: Binary Tree Maximum Path Sum

# 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 tuple

def maxPathSumHelper(self, root):

maxPathSumInThisSubTree = root.val

maxPathSumToUpper = root.val # The maximum path sum, which could

# be used by its ancestors.

left, right = None, None

if root.left != None:

left = self.maxPathSumHelper(root.left)

# Any path, who has both the nodes of root's son(s) AND root's

# ancestors, must have the node "root" of this subtree.

maxPathSumToUpper = max(maxPathSumToUpper, root.val + left[1])

# The maximum path of current subtree may not cross its root.

maxPathSumInThisSubTree = max(maxPathSumInThisSubTree,

maxPathSumToUpper,

left[0]

)

if root.right != None:

# Same as the left son.

right = self.maxPathSumHelper(root.right)

maxPathSumToUpper = max(maxPathSumToUpper, root.val + right[1])

maxPathSumInThisSubTree = max(maxPathSumInThisSubTree,

maxPathSumToUpper,

right[0]

)

# If both the left son and right son exist, the maximum path of this

# subtree may across the left subtree, current root and the right

# substree.

if left != None and right != None:

maxPathSumInThisSubTree = max(maxPathSumInThisSubTree,

root.val + left[1] + right[1]

)

return maxPathSumInThisSubTree, maxPathSumToUpper

# @param root, a tree node

# @return an integer

def maxPathSum(self, root):

return self.maxPathSumHelper(root)[0]

Solution to Best Time to Buy and Sell Stock II by LeetCode

10 Jul

Question: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ Question Name: Best Time to Buy and Sell Stock II

class Solution:

# @param prices, a list of integer

# @return an integer

def maxProfit(self, prices):

maxProfit = 0

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

if prices[index+1] > prices[index]:

# As long as we can earn money, do the transaction.

maxProfit += prices[index+1] - prices[index]

return maxProfit

Solution to Best Time to Buy and Sell Stock by LeetCode

9 Jul

Question: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/ Question Name: Best Time to Buy and Sell Stock

lass Solution:

# @param prices, a list of integer

# @return an integer

def maxProfit(self, prices):

# Not enough time to earn profit

if len(prices) < 2: return 0

# The maximum price from here to the end

maxFromHere = prices[-1]

# The maximum profit, we could earn.

# Could initialize it with any valid profit.

maxProfit = prices[1] - prices[0]

for index in xrange(len(prices)-2, -1, -1):

price = prices[index]

# The maximum profit, if we buy it here.

profit = maxFromHere - price

maxProfit = max(maxProfit, profit)

maxFromHere = max(maxFromHere, price)

# If maxProfit is negative, we would not take

# any transaction.

# If we initialize the maxProfit with 0, this

# step is not necessary.

maxProfit = max(0, maxProfit)

return maxProfit

Solution to Triangle by LeetCode

9 Jul

Question: https://oj.leetcode.com/problems/triangle/ Question Name: Triangle

class Solution:

# @param triangle, a list of lists of integers

# @return an integer

def minimumTotal(self, triangle):

# Empty triangle

if len(triangle) == 0: return 0

# The length of triangle is equal to the length of its last row.

pathSum = [0] * len(triangle)

# Initialize the pathSum with the first row

pathSum[0] = triangle[0][0]

# Compute the remaining rows

for row in xrange(1, len(triangle)):

# The last element of current row can only be reached from the

# last element of previous row.

pathSum[row] = pathSum[row-1] + triangle[row][row]

# Each element can be reached from two adjacent nodes in the

# previous row.

for column in xrange(row-1, 0, -1):

pathSum[column] = min(pathSum[column], pathSum[column-1]) +

triangle[row][column]

# The first element of current row can only be reached from the

# first element of previous row.

pathSum[0] += triangle[row][0]

# Return the length of the shortest path.

return min(pathSum)

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