LeetCode – Page 7

Solution to Gas Station by LeetCode

17 Jul

Question: https://oj.leetcode.com/problems/gas-station/ Question Name: Gas Station

class Solution:

# @param gas, a list of integers

# @param cost, a list of integers

# @return an integer

def canCompleteCircuit(self, gas, cost):

# The change of gas, if we move from one station to the next.

gasChange = [gas[index]-cost[index] for index in xrange(len(gas))]

# Double the array to avoid the mod operation for circular route.

gasChange = gasChange + gasChange

# Try to start our trip at each statioin.

start = 0

while start < len(gas):

left = 0 # Remaining gas in current trip.

station = 0 # The current station during this trip.

while station < len(gas):

left += gasChange[start + station]

if left < 0:

# No enough gas to continue our trip.

break

station += 1

else:

# Finished the trip successfully.

return start

# Let start be i, start + station be j. We know that sum of

# gasChange[i : j+1] is negative. And for ANY m and n, if the

# sum of gasChange[m : n+1] is nagative, we will break the while

# loop. So as long as we COULD travel from i to j station, for

# ALL k in range [i+1, j), we know that the remaining gas, or

# say the sum of gasChange[i, k+1], is zero or positive.

# sum(gasChange[i, k+1]) + sum(gasChange[k+1, j+1])

# = sum(gasChange[i, j+1]) < 0

# AND

# sum(gasChange[i, k+1]) >= 0

# Thus

# sum(gasChange[k+1, j+1]) < 0 ( For ALL k in [i+1,j) )

# Considering the i(th) and j(th) item, we can easily get that:

# sum(gasChange[k+1, j+1]) < 0 ( For ALL k in [i,j] )

# So no station in the range [i, j+1) could be the start position.

start += station + 1

return -1

Solution to Clone Graph by LeetCode

17 Jul

Question: https://oj.leetcode.com/problems/clone-graph/ Question Name: Clone Graph

# Definition for a undirected graph node

# class UndirectedGraphNode:

# def __init__(self, x):

# self.label = x

# self.neighbors = []

class Solution:

# @param node, a undirected graph node

# @return a undirected graph node

def cloneGraph(self, node):

# Empty graph

if node == None: return

# Do the work in two rounds. In the first round, we clone all the

# new nodes only with label. And let their neighbors array empty.

# In the second round, we will assign the neighbors of cloned

# node with the reference to new cloned ones.

# Clone nodes only with label

cloned = {}

currentLayer = [node]

while len(currentLayer) != 0:

nextLayer = []

for toClone in currentLayer:

if toClone in cloned: continue

temp = UndirectedGraphNode(toClone.label)

nextLayer.extend(toClone.neighbors)

cloned[toClone] = temp

currentLayer = nextLayer

# Assign the neighbors of new cloned nodes.

for oldNode in cloned:

newNode = cloned[oldNode]

newNode.neighbors = [cloned[neighbor] for neighbor

in oldNode.neighbors]

return cloned[node]

Solution to Palindrome Partitioning II by LeetCode

17 Jul

Question: https://oj.leetcode.com/problems/palindrome-partitioning-ii/ Question Name: Palindrome Partitioning II

class Solution:

# @param s, s string

# @return an array

def _buildPalindromeCache(self, s):

''' http://en.wikipedia.org/wiki/Longest_palindromic_substring

Method: Manacher's algorithm

'''

transformed = "#" + "#".join(s) + "#"

palindrome_len = [1] * len(transformed)

center = 0

farest = 0

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

if farest <= index:

tryingLen = 1

else:

preComputedLen = palindrome_len[2*center-index]

if preComputedLen + index > farest:

tryingLen = farest + 1 - index

else:

palindrome_len[index] = preComputedLen

continue

while index + tryingLen < len(transformed) and

index - tryingLen >= 0:

if transformed[index + tryingLen] ==

transformed[index - tryingLen]:

tryingLen += 1

else:

break

if index + tryingLen -1 > farest:

farest = index + tryingLen -1

center = index

palindrome_len[index] = tryingLen

return palindrome_len

# @param begin, an integer

# @param end, an integer

# @param palindromeCache, an array

# @return a boolean

def _isPalindrome(self, begin, end, palindromeCache):

''' In palindromeCache, the index for s[index] and s[end] are

index*2+1 and end*2+1 respectively. So in palindromeCache, the

middle point of s[index] and s[end] is (index*2+1 + end*2+1) // 2,

that is (index + end + 1).

IF you remove this function and use a single statement instead, you

could get a 30%-40% performance improvement or even more.

'''

return palindromeCache[begin + end + 1] - 1 >= (end - begin + 1)

# @param s, a string

# @return an integer

def minCut(self, s):

''' Solve it in a dynamic programming method.

'''

if len(s) == 0: return 0

palindromeCache = self._buildPalindromeCache(s)

minCutEndingHere = [0] * len(s)

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

if self._isPalindrome(0, index, palindromeCache):

# The substring from beginning to here is a palindrome. No

# cut is needed.

minCut = 0

else:

# We could add a cut between index and index - 1.

minCut = 1 + minCutEndingHere[index-1]

# Or the cut could be tried between tryingToCut and

# tryingToCut - 1.

for tryingToCut in xrange(1, index):

# Only when s[tryingToCut : index+1] is palindrome, the

# cut could be done.

if self._isPalindrome(tryingToCut, index, palindromeCache):

minCut = min(minCut,

1 + minCutEndingHere[tryingToCut-1])

minCutEndingHere[index] = minCut

return minCutEndingHere[-1]

Solution to Palindrome Partitioning by LeetCode

15 Jul

Question: https://oj.leetcode.com/problems/palindrome-partitioning/ Question Name: Palindrome Partitioning One simple solution is as following. It is easy to understand. And it passed all the tests.

class Solution:

# @param s, a string

# @return a boolean

def _isPalindrome(self, s):

begin, end = 0, len(s)-1

while begin < end:

if s[begin] != s[end]:

return False

else:

begin += 1

end -= 1

return True

# @param s, a string

# @return a list of lists of string

def partition(self, s):

if len(s) == 0: return []

if len(s) == 1: return [[s]]

result = []

if self._isPalindrome(s): result.append([s])

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

head = s[:i]

if not self._isPalindrome(head):

continue

tailPartition = self.partition(s[i:])

result.extend([[head] + item for item in tailPartition])

return result

We could do it better! Do it! Do it better with Manacher’s algorithm! BUT K.I.S.S.

Solution to Surrounded Regions by LeetCode

13 Jul

Question: https://oj.leetcode.com/problems/surrounded-regions/ Question Name: Surrounded Regions

class Solution:

# @param board, a 2D array

# Capture all regions by modifying the input board in-place.

# Do not return any value.

def solve(self, board):

''' We need to flip all 'O's into 'X's in these surrounded region.

If we solve this challenge directly by finding out the surrounded

region, it is difficult. So we might consider this question from

another direction: which "O" nodes should be kept?

'''

if len(board) == 0: return

toKeep = [[False] * len(board[0]) for _ in xrange(len(board))]

# Treat the board as a graph. Assume the adjacent nodes are

# connected in the graph. Then we are going to do a BFS traversal

# to find out all the nodes, which are connecting to periphery

# "O" nodes.

layer = []

# We initialize the layer with the periphery "O" nodes to do a

# BFS traversal.

for column in xrange(len(board[0])):

if board[0][column] == "O":

toKeep[0][column] = True

layer.append([0, column])

if board[-1][column] == "O":

toKeep[-1][column] = True

layer.append([len(board)-1, column])

for row in xrange(len(board)):

if board[row][0] == "O":

toKeep[row][0] = True

layer.append([row, 0])

if board[row][-1] == "O":

toKeep[row][-1] = True

layer.append([row, len(board[0])-1])

# Going to fished the BFS

while len(layer) != 0:

temp = []

for keptNode in layer:

# Try the upper node

if keptNode[0] != 0 and

board[keptNode[0]-1][keptNode[1]] == "O" and

toKeep[keptNode[0]-1][keptNode[1]] == False:

toKeep[keptNode[0]-1][keptNode[1]] = True

temp.append([keptNode[0]-1, keptNode[1]])

# Try the lower node

if keptNode[0] != len(board)-1 and

board[keptNode[0]+1][keptNode[1]] == "O" and

toKeep[keptNode[0]+1][keptNode[1]] == False:

toKeep[keptNode[0]+1][keptNode[1]] = True

temp.append([keptNode[0]+1, keptNode[1]])

# Try the left node

if keptNode[1] != 0 and

board[keptNode[0]][keptNode[1]-1] == "O" and

toKeep[keptNode[0]][keptNode[1]-1] == False:

toKeep[keptNode[0]][keptNode[1]-1] = True

temp.append([keptNode[0], keptNode[1]-1])

# Try the right node

if keptNode[1] != len(board[0])-1 and

board[keptNode[0]][keptNode[1]+1] == "O" and

toKeep[keptNode[0]][keptNode[1]+1] == False:

toKeep[keptNode[0]][keptNode[1]+1] = True

temp.append([keptNode[0], keptNode[1]+1])

layer = temp

# Change the contents in boards according to the flags in toKeep.

for row in xrange(len(board)):

for column in xrange(len(board[0])):

if board[row][column] == "X":

continue

if toKeep[row][column] == False:

board[row][column] = "X"

return

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

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