Sheng – Page 14 – Code Says

Solution to Word Break by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/word-break/ Question Name: Word Break Similar with Palindrome Partitioning II by LeetCode. Dynamic programming is suitable here.

class Solution:

# @param s, a string

# @param dict, a set of string

# @return a boolean

def wordBreak(self, s, dict):

''' Solve it with dynamic programming.

'''

couldBreak = [False] * len(s)

for breakAfterCurrent in xrange(len(s)):

if s[: breakAfterCurrent+1] in dict:

# The substring from beginning to here is in the dict.

# We can make the substring with zero break.

couldBreak[breakAfterCurrent] = True

continue

# Otherwise, we will try to check, whether this substring

# s[:breakAfterCurrent+1] could be composed by a breakable

# head and a tail, which is in the dict.

for preBreak in xrange(breakAfterCurrent):

if couldBreak[preBreak] == False:

# The head is not breakable

continue

elif s[preBreak+1: breakAfterCurrent+1] not in dict:

# The tail is not in the dict.

continue

else:

# As long as we know it's breakable, no need to

# continue the search for current position.

couldBreak[breakAfterCurrent] = True

break

return couldBreak[-1]

Solution to Copy List with Random Pointer by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/copy-list-with-random-pointer/ Question Name: Copy List with Random Pointer Quite similar with the Clone Graph by LeetCode.

# Definition for singly-linked list with a random pointer.

# class RandomListNode:

# def __init__(self, x):

# self.label = x

# self.next = None

# self.random = None

class Solution:

# @param head, a RandomListNode

# @return a RandomListNode

def copyRandomList(self, head):

# Store the mapping between old nodes and new nodes

mapOldToNew ={None:None}

# Clone all the old nodes with only labels.

current = head

while current != None:

mapOldToNew[current] = RandomListNode(current.label)

current = current.next

# Assign the next and random of new cloned nodes.

current = head

while current != None:

mapOldToNew[current].next = mapOldToNew[current.next]

mapOldToNew[current].random = mapOldToNew[current.random]

current = current.next

# Return the cloned head

return mapOldToNew[head]

Solution to Single Number II by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/single-number-ii/ Question Name: Single Number II Follow Up: Every element appears N times except one for M time (N != M): If N > M: If N % M == 0: use dictionary to count the appearance; If N … Read More »

Solution to Single Number by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/single-number/ Question Name: Single Number

class Solution:

# @param A, a list of integer

# @return an integer

def singleNumber(self, A):

''' Basic knowledge for cryptography: XOR operation

'''

result = 0

for item in A: result ^= item

return result

Solution to Candy by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/candy/ Question Name: Candy

class Solution:

# @param ratings, a list of integer

# @return an integer

def candy(self, ratings):

sortedRatings = enumerate(ratings)

sortedRatings = sorted(sortedRatings, key = lambda x: x[1])

candyCount = [-1] * len(ratings)

# Lowest rating, First service.

for child in sortedRatings:

position = child[0]

# Each child must have at least one candy.

candyForThisChild = 1

# Children with a higher rating get more candies than their

# neighbors.

# Check its left neighbor, if exists.

if position != 0 and ratings[position-1] < ratings[position]:

candyForThisChild = max(candyForThisChild,

candyCount[position-1] + 1)

# Check its right neighbor, if exists.

if position != len(ratings)-1 and

ratings[position+1] < ratings[position]:

candyForThisChild = max(candyForThisChild,

candyCount[position+1] + 1)

candyCount[position] = candyForThisChild

return sum(candyCount)

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

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