Sheng – Page 24 – Code Says

Solution to Combination Sum II by LeetCode

18 May

Question: http://oj.leetcode.com/problems/combination-sum-ii/ Question Name: Combination Sum II

class Solution:

# @param candidates, a list of integers

# @param target, integer

# @return a list of lists of integers

def combinationSum2(self, candidates, target):

''' Convert this question into n-sum question, by adding 0s

'''

result = []

# Rule out the integers greater than target

candidates = [i for i in candidates if i <= target]

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

# The maximum number of items in one answer set

candidates.sort()

limit = target // candidates[0]

# Adjust the limit. The maximum number of items in one

# answer set must be equal to or less than the number

# of items in candidates

if limit > len(candidates): limit = len(candidates)

if limit == 0: return []

elif limit == 1:

if target in candidates: return [[target]]

else: return []

else:

# We add a 0 at the head of candidates. If the length of

# of original answer is M, the answer here will be length

# of "limit", with original answer M and additional heading

# (limit - M) 0s.

candidates= [0] * (limit - 1) + candidates

# The pointers used for n-sum. The time complexity is O(M^(n-1))

pointers = range(limit)

pointers[-1] = len(candidates) - 1

while pointers[0] < len(candidates) - (limit - 1):

# The innermost loop of n-sum solution

preSum = sum([candidates[i] for i in pointers[:-2]])

if preSum + candidates[pointers[-2]] + candidates[pointers[-2]] > target:

# All combinations in this round are too big

pass

elif preSum + candidates[pointers[-1]] + candidates[pointers[-1]] < target:

# All combinations in this round are too small

pass

else:

# These two pointers cannot point to one same cell, because each cell

# can be used once at most.

while pointers[-2] < pointers[-1]:

temp = preSum + candidates[pointers[-2]] + candidates[pointers[-1]]

moveAhead, moveBack = False, False

if temp > target:

moveBack = True

elif temp < target:

moveAhead = True

else:

# Found a qualified combination

result.append([candidates[i] for i in pointers if candidates[i] != 0])

moveAhead, moveBack = True, True

if moveBack:

pointers[-1] -= 1

while pointers[-2] <= pointers[-1] and

candidates[pointers[-1]] == candidates[pointers[-1]+1]:

pointers[-1] -= 1

if moveAhead:

pointers[-2] += 1

while pointers[-2] <= pointers[-1] and

candidates[pointers[-2]] == candidates[pointers[-2]-1]:

pointers[-2] += 1

# Adjust the pointers for next round n-sum trying

pointerIndex = limit - 3

while pointerIndex >= 0:

pointers[pointerIndex] += 1

while pointers[pointerIndex] < len(candidates) - (limit - (pointerIndex + 1)) and

candidates[pointers[pointerIndex]] == candidates[pointers[pointerIndex]-1]:

pointers[pointerIndex] += 1

if pointers[pointerIndex] == len(candidates) - (limit - (pointerIndex + 1)):

pointerIndex -= 1

else:

break

else: break

for i in xrange(pointerIndex+1, limit-1): pointers[i] = pointers[i-1] + 1

pointers[-1] = len(candidates) - 1

return result

Solution to Combination Sum by LeetCode

17 May

Question: http://oj.leetcode.com/problems/combination-sum/ Question Name: Combination Sum

class Solution:

# @param candidates, a list of integers

# @param target, integer

# @return a list of lists of integers

def combinationSum(self, candidates, target):

''' Convert this question into n-sum question, by adding 0s

'''

result = []

# We add a 0 at the head of candidates. If the length of

# of original answer is M, the answer here will be length

# of "limit", with original answer M and additional

# (limit - M) 0s.

candidates.append(0)

candidates.sort()

# The maximum number of items in one answer set

limit = target // candidates[1]

if limit == 0: return []

if limit == 1:

if target in candidates: return [[target]]

else: return []

# The pointers used for n-sum. The time complexity is O(M^(n-1))

pointers = [0] * limit

pointers[-1] = len(candidates) - 1

while pointers[0] < len(candidates):

preSum = sum([candidates[i] for i in pointers[:-2]])

if preSum + candidates[pointers[-2]] + candidates[pointers[-2]] > target:

# All combinations in this round are too big

pass

elif preSum + candidates[pointers[-1]] + candidates[pointers[-1]] < target:

# All combinations in this round are too small

pass

else:

while pointers[-2] <= pointers[-1]:

temp = preSum + candidates[pointers[-2]] + candidates[pointers[-1]]

moveAhead, moveBack = False, False

if temp > target:

moveBack = True

elif temp < target:

moveAhead = True

else:

# Found a qualified combination

result.append([candidates[i] for i in pointers if candidates[i] != 0])

moveAhead, moveBack = True, True

if moveBack:

pointers[-1] -= 1

while pointers[-2] <= pointers[-1] and

candidates[pointers[-1]] == candidates[pointers[-1]+1]:

pointers[-1] -= 1

if moveAhead:

pointers[-2] += 1

while pointers[-2] <= pointers[-1] and

candidates[pointers[-2]] == candidates[pointers[-2]-1]:

pointers[-2] += 1

# Adjust the pointers for the next round n-sum trying

pointerIndex = limit - 3

while pointerIndex >= 0:

pointers[pointerIndex] += 1

while pointers[pointerIndex] < len(candidates) and

candidates[pointers[pointerIndex]] == candidates[pointers[pointerIndex]-1]:

pointers[pointerIndex] += 1

if pointers[pointerIndex] == len(candidates): pointerIndex -= 1

else: break

for i in xrange(pointerIndex+1, limit-1): pointers[i] = pointers[pointerIndex]

pointers[-1] = len(candidates) - 1

return result

Solution to Count and Say by LeetCode

15 May

Question: http://oj.leetcode.com/problems/count-and-say/ Question Name: Count and Say

class Solution:

# @return a string

def countAndSay(self, n):

result = "1" # The result for n == 1

for _ in xrange(n-1):

temp = "" # The result for next round

current = result[0]

currentCount = 1

for item in result[1:]:

if item == current:

# Same value as previous

currentCount += 1

else:

# Meet with a new value, store the result of

# previous value

temp += str(currentCount) + current

#Reset these two variables

current = item

currentCount = 1

# Store the result for the last unique value

temp += str(currentCount) + current

result = temp

return result

Solution to Sudoku Solver by LeetCode

15 May

Question: http://oj.leetcode.com/problems/sudoku-solver/ Question Name: Sudoku Solver

class Solution:

class _State(object):

__slot__ = ("board", "row", "col", "usedRow", "usedCol", "usedBlock")

def __init__(self, board, row, col, usedRow, usedCol, usedBlock):

self.board = [line*1 for line in board] # The whole board

self.row = row # Next process position

self.col = col # Next process position

self.usedRow = usedRow # Appeared integers in rows

self.usedCol = usedCol # Appeared integers in columns

self.usedBlock = usedBlock # Appeared integers in blocks

# @param board, a 9x9 2D array

# Solve the Sudoku by modifying the input board in-place.

# Do not return any value.

def solveSudoku(self, board):

# Convert the input (array of strings) to 2D array of integer

char2int = {"1":1, "2":2, "3":4, "4":8, "5":16, "6":32, "7":64, "8":128, "9":256}

boardMatrix = [[char2int.get(item, 0) for item in line] for line in board]

stack = []

usedRow, usedCol, usedBlock = [0] * 9, [0] * 9, []

# Get the initially appeared integers in each row and column

for i in xrange(9):

usedRow[i] = sum(boardMatrix[i])

usedCol[i] = sum([line[i] for line in boardMatrix])

# Get the initially appeared integers in each block

for iBlock in xrange(3):

for jBlock in xrange(3):

usedBlock.append(0)

for i in xrange(3):

for j in xrange(3):

usedBlock[-1] = usedBlock[-1] | boardMatrix[iBlock*3+i][jBlock*3+j]

stack.append(self._State(boardMatrix, 0, 0, usedRow, usedCol, usedBlock))

current = None

# Do a DFS

while len(stack) != 0:

current = stack.pop()

# Find the next empty cell to fill

while current.row != 9 and current.board[current.row][current.col] != 0:

current.col += 1

if current.col == 9:

current.row += 1

current.col = 0

# Every cell is filled. It is a solution for the Sudoku

if current.row == 9: break

# Try to fill this cell with each integer

for toAdd in char2int.values():

# Check whether this integer appears in the row/column/block or not

if toAdd & current.usedRow[current.row] != 0: continue

if toAdd & current.usedCol[current.col] != 0: continue

if toAdd & current.usedBlock[(current.row//3)*3+current.col//3] != 0: continue

# Create a new State for this filling and push it to the stqck

current.board[current.row][current.col] = toAdd

newUsedRow = current.usedRow * 1

newUsedRow[current.row] |= toAdd

newUsedCol = current.usedCol * 1

newUsedCol[current.col] |= toAdd

newUsedBlock = current.usedBlock * 1

newUsedBlock[(current.row//3)*3+current.col//3] |= toAdd

stack.append(self._State(current.board, current.row, current.col,

newUsedRow, newUsedCol, newUsedBlock))

# Find the solution for this Sudoku

# Empty the input board

del board[:]

# Fill the board with the right solution

int2char = {0:".", 1:"1", 2:"2", 4:"3", 8:"4", 16:"5", 32:"6", 64:"7", 128:"8", 256:"9"}

result = ["".join([int2char[i] for i in line]) for line in current.board]

for line in result: board.append(line)

return

Solution to Search Insert Position by LeetCode

11 May

Question: http://oj.leetcode.com/problems/search-insert-position/ Question Name: Search Insert Position

class Solution:

# @param A, a list of integers

# @param target, an integer to be inserted

# @return integer

def searchInsert(self, A, target):

''' A variant of the binary search algorithm

If target is in A, return the position of its first

occurrence.

Otherwise, rethurn the position of the first element,

which is larger than target.

'''

begin = 0

end = len(A) - 1

insertPos = 0

while begin <= end:

mid = (begin + end) // 2

if A[mid] == target:

# Target found

return mid

elif A[mid] > target:

end = mid - 1

insertPos = mid

else:

begin = mid + 1

insertPos = mid + 1

return insertPos

Solution to Valid Sudoku by LeetCode

11 May

Question: http://oj.leetcode.com/problems/valid-sudoku/ Question Name: Valid Sudoku An example of bit manipulation.

class Solution:

# @param board, a 9x9 2D array

# @return a boolean

def isValidSudoku(self, board):

char2int = {".":0, "1":1, "2":2, "3":4, "4":8, "5":16, "6":32, "7":64, "8":128, "9":256}

board = [[char2int[item] for item in line] for line in board]

# Check each row

for i in xrange(9):

sum = 0

for value in board[i]:

if sum & value != 0: return False

sum = sum | value

# Check each column

for i in xrange(9):

sum = 0

for row in xrange(9):

if sum & board[row][i] != 0: return False

sum = sum | board[row][i]

# Check each block

for iBlock in xrange(3):

for jBlock in xrange(3):

sum = 0

for i in xrange(3):

for j in xrange(3):

if sum & board[iBlock*3+i][jBlock*3+j] != 0: return False

sum = sum | board[iBlock*3+i][jBlock*3+j]

return True

Solution to Search in Rotated Sorted Array by LeetCode

11 May

Question: http://oj.leetcode.com/problems/search-in-rotated-sorted-array/ Question Name: Search in Rotated Sorted Array

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @param begin, an integer to indicate the begin pos to search

# @param end, an integer to indicate the end pos to search

# @return an integer

def _searchHelper(self, A, target, begin, end):

''' Use a modified binary search algorithm to find the target

in a may-be-rotated array A from position begin to end.

'''

# Did not find the target

if begin > end: return -1

mid = (begin + end) // 2

if A[begin] < A[end]: rotated = False # Sorted and not rotated

else: rotated = True # Sorted and then rotated

if A[mid] == target:

# Target found

return mid

elif A[mid] < target:

# If array is not rotated, no need to search in the left part

if rotated:

# Target might be in the left part

temp = self._searchHelper(A, target, begin, mid - 1)

if temp != -1: return temp

# Search in the right part

return self._searchHelper(A, target, mid + 1, end)

else:

# If array is not rotated, no need to search in the right part

if rotated:

# Target might be in the right part

temp = self._searchHelper(A, target, mid + 1, end)

if temp != -1: return temp

# Search in the left part

return self._searchHelper(A, target, begin, mid - 1)

# @param A, a list of integers

# @param target, an integer to be searched

# @return an integer

def search(self, A, target):

return self._searchHelper(A, target, 0, len(A)-1)

Solution to Search for a Range by LeetCode

11 May

Question: http://oj.leetcode.com/problems/search-for-a-range/ Question Name: Search for a Range

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @return a list of length 2, [index1, index2]

def searchRange(self, A, target):

''' Use binary search to find the occurrence range

of target in array A.

'''

begin = -1

end = -1

# Find the first occurrence of target in A

front = len(A) - 1

back = 0

while back <= front:

mid = (front + back) // 2

if A[mid] > target:

front = mid - 1

elif A[mid] < target:

back = mid + 1

else:

front = mid - 1

begin = mid

# Target is not found in the array A

if begin == -1: return [-1, -1]

# Find the last occurrence of target in A

front = len(A) - 1

back = 0

while back <= front:

mid = (front + back) // 2

if A[mid] > target:

front = mid - 1

elif A[mid] < target:

back = mid + 1

else:

back = mid + 1

end = mid

return [begin, end]

Solution to Longest Valid Parentheses by LeetCode

1 May

Question: http://oj.leetcode.com/problems/longest-valid-parentheses/ Question Name: Longest Valid Parentheses

class Solution:

# @param s, a string

# @return an integer

def longestValidParentheses(self, s):

stack = []

# The leftmost ")"s are useless to form a valid parentheses

for item in s.lstrip(")"):

if item == "(":

stack.append(item)

else:

if stack[-1] == "(":

# A valid parentheses is found

stack.pop()

stack.append(2)

elif len(stack) > 1 and stack[-2] == "(":

# A valid parentheses is found

# stack[-1] != "(", otherwise the previous if block

# will be executed.

# stack[-1] != ")", otherwise, in the previous round,

# a valid parentheses is found, and ")" should not

# be in the stack

# So stack[-1] must be a number.

temp =stack.pop()

stack.pop()

stack.append(temp + 2)

else:

# We should start a new search for the remaining part.

# And any content in the remaining part can NOT form

# a valid parentheses with previous content.

stack.append(")")

continue

# Compress the previous valid parentheses

# For example, with "()()",after dealing with the last ")"

# the stack would be [2,2], we try to compress into one unit

# as [4].

# After compression, we could guarantee, if current procession

# letter is ")", and there is a previous matching "(", there

# will be only one or zero integer between them in the stack.

while len(stack) > 1 and isinstance(stack[-2], int):

temp = stack.pop()

temp += stack.pop()

stack.append(temp)

# Remove the non-number elements

stack = [item for item in stack if isinstance(item,int)]

if len(stack) == 0: return 0

else: return max(stack)

Solution to psi2012 (Wire-Burnouts) by codility

28 Apr

Question: https://codility.com/demo/take-sample-test/wire_burnouts Question Name: psi2012 or Wire-Burnouts or WireBurnouts A good application of weighted quick union algorithm.

class WeightedQuickUnion(object):

''' A class for weighted quick union data structure

Details: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

'''

ID = None # ID[i] = component identifier of i

weight = None # weight[i] = number of nodes in the subtree(component)

# with i being the root

def __init__(self, size):

assert size > 0

# Each individual cell is a component

self.ID = [i for i in xrange(size)]

# Each component has only one item initially

self.weight = [1 for i in xrange(size)]

return

def findRoot(self, cell):

''' Return the root of tree, to which cell belongs.

That is, the component identifier of cell.

'''

assert 0 <= cell < len(self.ID)

while cell != self.ID[cell]: cell = self.ID[cell]

return cell

def isConnected(self, p, q):

''' Check whether p and q belong to same component/tree.

'''

assert 0 <= p < len(self.ID) and 0 <= q < len(self.ID)

return self.findRoot(p) == self.findRoot(q)

def union(self, p, q):

''' Merge the components (trees), to which p and q belong

'''

assert 0 <= p < len(self.ID) and 0 <= q < len(self.ID)

rootP = self.findRoot(p)

rootQ = self.findRoot(q)

# Already the same component

if rootP == rootQ: return

if self.weight[rootP] >= self.weight[rootQ]:

self.ID[rootQ] = rootP

self.weight[rootP] += self.weight[rootQ]

else:

self.ID[rootP] = rootQ

self.weight[rootQ] += self.weight[rootP]

return

class Grid(object):

''' A wrapper class of WeightedQuickUnion for the current grid

'''

grid = None

size = -1

def __init__(self, size):

self.grid = WeightedQuickUnion(size*size)

# This is a size * size grid

self.size = size

return

def isConnected(self, x1, y1, x2, y2):

''' Check whether the nodes (x1, y1) and (x2, y2) in the grid

is connected or not.

'''

p = x1 * self.size + y1

q = x2 * self.size + y2

return self.grid.isConnected(p, q)

def union(self, x1, y1, x2, y2):

''' Connect two nodes (x1, y1) and (x2, y2) in the grid

'''

p = x1 * self.size + y1

q = x2 * self.size + y2

self.grid.union(p, q)

return

def solution(N, A, B, C):

# Not enough burn out wires to stop the current from flowing

if len(A) < N + N - 2: return -1

grid = Grid(N)

# Get all the wires, which will burn out.

removed = {}

for index in xrange(len(A)):

if C[index] == 0: removed[(A[index], B[index], A[index], B[index]+1)] = True

else: removed[(A[index], B[index], A[index]+1, B[index])] = True

# Add all the never-burn wires to the grid

for x in xrange(N):

for y in xrange(N):

if y + 1 < N and not (x, y, x, y+1) in removed:

grid.union(x, y, x, y+1)

if x + 1 < N and not (x, y, x+1, y) in removed:

grid.union(x, y, x+1, y)

# Even if all the wires in A, B, and C burn out, the current is still flowing

if grid.isConnected(0, 0, N-1, N-1): return -1

for index in xrange(len(A)-1, -1, -1):

# Recovery one burn-out wire

if C[index] == 0:

grid.union(A[index], B[index], A[index], B[index]+1)

else:

grid.union(A[index], B[index], A[index]+1, B[index])

# After recovery, the current could flow.

if grid.isConnected(0, 0, N-1, N-1): return index + 1

# Would never be here.

return -1

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