Sheng – Page 23 – Code Says

Solution to Pow(x, n) by LeetCode

5 Jun

Question: https://oj.leetcode.com/problems/powx-n/ Question Name: Pow(x, n) The simplest solution is to use the build-in function “pow” or build-in operation “**” of Python.

class Solution:

# @param x, a float

# @param n, a integer

# @return a float

def pow(self, x, n):

return x**n

A second simple solution is recursive.

class Solution:

# @param x, a float

# @param n, a integer

# @return a float

def pow(self, x, n):

if n == 0: return 1 # Handle with special case

elif n < 0: return 1.0 / self.pow(x, -n) # Handle with negative n

elif n == 1: return x # Termination condition

else:

# Recursive condition

if n % 2 == 0: return self.pow(x*x, n//2)

else: return self.pow(x*x, n//2)*x

Finally, a iterative solution works here.

class Solution:

# @param x, a float

# @param n, a integer

# @return a float

def pow(self, x, n):

if n == 0: return 1

if n < 0: div = True; n = -n

else: div = False

stack = []

while n != 1 and n != -1:

if n % 2 == 0: stack.append(1)

else: stack.append(x)

n //= 2

result = x

while len(stack) != 0:

result = result * result * stack.pop()

if div: return 1.0 / result

else: return result

Solution to N-Queens by LeetCode

4 Jun

Question: https://oj.leetcode.com/problems/n-queens/ Question Name: N-Queens

class QueenSolution(object):

''' A class to store the intermediate status towards the

N-Queen solutions

'''

__slots__ = ("board","col","diagF", "diagB")

def __init__(self, board, col, diagF, diagB):

self.board = board * 1 # Board contents, board[i] means there is

# a queen in position (i, board[i[)

self.col = col # Used columns

self.diagF = diagF # Used forward diagonal

self.diagB = diagB # Used backward diagonal

return

def toForm(self):

''' Transfer the board from the class-inside formation to the required

form.

'''

res = []

size = len(self.board)

for i in self.board:

if i == -1: res.append("."*size)

else: res.append("."*i + "Q" + "."*(size - i - 1))

return res

class Solution:

# @return a list of lists of string

def solveNQueens(self, n):

# Handle some special cases

if n == 1: return [["Q"]]

if n == 2 or n == 3: return []

result = [QueenSolution([-1]*n, 0, 0, 0)]

for row in xrange(n): # Add the queens row by row

temp = []

for preState in result:

for col in xrange(n): # Try each position

# Column conflicts

if (1<<col) & preState.col != 0: continue

diagF = 1 << (col - row + (n-1))

# Forward diagonal conflicts

if diagF & preState.diagF != 0: continue

diagB = 1 << (row + col)

# Backward diagonal conflicts

if diagB & preState.diagB != 0: continue

# Find a valid intermediate status

preState.board[row] = col

temp.append(QueenSolution(preState.board, (1<<col) | preState.col,

diagF | preState.diagF, diagB | preState.diagB))

result = temp # Prepare for working with the next row

return [record.toForm() for record in result]

Solution to Rotate Image by LeetCode

24 May

Question: https://oj.leetcode.com/problems/rotate-image/ Question Name: Rotate Image A same question as this one from CTCI.

class Solution:

# @param matrix, a list of lists of integers

# @return a list of lists of integers

def rotate(self, matrix):

mLen = len(matrix) # The dimensions of the matrix

# Determine the block size to rotate

iLen = mLen // 2

if mLen % 2 == 0: jLen = mLen // 2

else: jLen = mLen // 2 + 1

for i in xrange(iLen):

for j in xrange(jLen):

# Swap the four elements

matrix[i][j], matrix[j][mLen-i-1], matrix[mLen-i-1][mLen-j-1], matrix[mLen-j-1][i] =

matrix[mLen-j-1][i], matrix[i][j], matrix[j][mLen-i-1], matrix[mLen-i-1][mLen-j-1]

return matrix

Solution to Jump Game II by LeetCode

23 May

Question: https://oj.leetcode.com/problems/jump-game-ii/ Question Name: Jump Game II A similar problem with Fib-Frog by codility. But this one is much simpler.

class Solution:

# @param A, a list of integers

# @return an integer

def jump(self, A):

# steps[i] means the minimum number of jumps needed to reach the position i.

steps = [0] * len(A)

for index in xrange(len(A)):

preSteps = steps[index] # Minimum jumps needing to reach position index

step = A[index] # Maximum jump length at position index

# Try to jump with steps of "step" to 1

for jump in xrange(step, 0, -1):

if index + jump >= len(steps): continue # Out of range

if steps[index + jump] != 0: break # Reached before

steps[index + jump] = preSteps + 1

return steps[-1]

Solution to Multiply Strings by LeetCode

22 May

Question: https://oj.leetcode.com/problems/multiply-strings/ Question Name: Multiply Strings

class Solution:

# @param num1, a string

# @param num2, a string

# @return a string

def multiply(self, num1, num2):

# Handle with the special case that, at least of the input is 0.

if num1 == "0" or num2 == "0": return "0"

result = [0] * (len(num1) + len(num2))

num1 = [int(i) for i in num1]

num2 = [int(i) for i in num2]

for index1 in xrange(len(num1)):

multiplier = num1[index1]

temp = [i*multiplier for i in num2] # Multiply

temp.extend([0] * (len(num1) - index1 - 1)) # Shift

# Add to the final result

for resIndex in xrange(1, len(temp) + 1):

result[-resIndex] += temp[-resIndex]

# Normalize the final result.

# We do not need to consider the first element.

# For a m-length integer multiply n-length integer, the result

# is at most with length of m+n. Thus the first element in array

# "result" will never be more than 9.

for resIndex in xrange(len(result)-1, 0, -1):

result[resIndex-1] += result[resIndex] // 10

result[resIndex] %= 10

# Convert the final result into string

result = "".join([str(i) for i in result]).lstrip("0")

return result

Solution to Permutations II by LeetCode

21 May

Question: https://oj.leetcode.com/problems/permutations-ii/ Question Name: Permutations II

class Solution:

# @param num, a list of integer

# @return a list of lists of integers

def permuteUnique(self, num):

stack = [] # The temporary lists for result

used = [] # For stack[i], used[i] means the used

# items' position in "num"

appeared = set() # The appeared combination

result = [] # Final result permutations

fullFlag = (1 << len(num)) - 1 # The value of used[i], when

# stack[i] is a full permutation

# Initialize the stack and used, with a single integer in "num"

for index in xrange(len(num)):

if not (num[index],) in appeared: # Never appeared

stack.append((num[index],))

used.append(1<<index)

appeared.add((num[index],))

while len(stack) != 0:

temp = stack.pop()

usedState = used.pop()

if usedState == fullFlag:

# This is a final permutation

result.append(list(temp))

else:

# Try to append one unused integer

for index in xrange(len(num)):

# This integer is not used

if usedState & (1<<index) == 0:

nextState = temp + (num[index],)

# This combination does not appear in previous rounds

if not nextState in appeared:

stack.append(nextState)

used.append(usedState | (1<<index))

appeared.add(nextState)

return result

Solution to Permutations by LeetCode

21 May

Question: https://oj.leetcode.com/problems/permutations/ Question Name: Permutations

class Solution:

# @param num, a list of integer

# @return a list of lists of integers

def permute(self, num):

stack = [] # The temporary lists for result

used = [] # For stack[i], used[i] means the used

# items' position in "num"

result = [] # Final result permutations

fullFlag = (1 << len(num)) - 1 # The value of used[i], when

# stack[i] is a full permutation

# Initialize the stack and used, with a single integer in "num"

for index in xrange(len(num)):

stack.append([num[index]])

used.append(1<<index)

while len(stack) != 0:

temp = stack.pop()

usedState = used.pop()

if usedState == fullFlag:

# This is a final permutation

result.append(temp)

else:

# Try to append one unused integer

for index in xrange(len(num)):

# This integer is not used

if usedState & (1<<index) == 0:

stack.append(temp + [num[index]])

used.append(usedState | (1<<index))

return result

Solution to Wildcard Matching by LeetCode

21 May

Question: https://oj.leetcode.com/problems/wildcard-matching/ Question Name: Wildcard Matching

class Solution:

# @param p, the original pattern string

# @return, a compressed pattern string, and the minimal number of characters

# in a matching string.

def _compile(self, p):

# Handle with a special case that the pattern string is empty

if len(p) == 0: return "", 0

result = p[0] # Compressed pattern

minimal = 0 # Minimal number of chars in any matching string

for i in p[1:]:

# Count the minimal number of chars

if i!= "*": minimal += 1

# Compress consecutive stars into one

if i == "*" and i == result[-1]: continue

else: result += i

return result, minimal

# @param s, an input string

# @param sIndex, the begin position of s to check

# @param p, a pattern string

# @param pIndex, the begin position of p to match

# @return a boolean

def _isMatchHelper(self, s, sIndex, p, pIndex, tried):

while True:

# Cache the previous failure

if tried[sIndex] & (1<<pIndex) != 0: return False

else: tried[sIndex] |= (1<<pIndex)

# Both input and pattern have nothing left. Match success!

if sIndex == len(s) and pIndex == len(p):

return True

# Either the input has something unmatched

elif pIndex == len(p):

return False

# In the pattern, only one star is left. It matches every string.

elif pIndex == len(p) - 1 and p[pIndex] == "*":

return True

# Single character matches.

elif sIndex != len(s) and (p[pIndex] == "?" or s[sIndex] == p[pIndex]):

sIndex += 1

pIndex += 1

# Deal with star match

elif p[pIndex] == "*":

# "*" means empty string

if self._isMatchHelper(s, sIndex, p, pIndex+1, tried):

return True

# "*" consume one character

elif sIndex != len(s) and self._isMatchHelper(s, sIndex+1, p, pIndex, tried):

return True

# No way to match "*"

else:

return False

# input and pattern do not match for current position. Fails.

else:

return False

# @param s, an input string

# @param p, a pattern string

# @return a boolean

def isMatch(self, s, p):

p, mininal = self._compile(p)

# Not enough characters in s to be matched for pattern p

if mininal > len(s):

return False

else:

tried = [0 for _ in xrange(len(s)+1)]

return self._isMatchHelper(s, 0, p, 0, tried)

Solution to Trapping Rain Water by LeetCode

20 May

Question: http://oj.leetcode.com/problems/trapping-rain-water/ Question Name: Trapping Rain Water

class Solution:

# @param A, a list of integers

# @return an integer

def trap(self, A):

water = 0 # The total number of water

# The the first decreasing point

begin = 0

while begin < len(A) - 1 and A[begin] <= A[begin + 1]:

begin += 1

# The array A is always non-decreasing. No where to store water

if begin >= len(A) - 1: return 0

stack = [(begin, A[begin])]

for wall in enumerate(A[begin+1:], begin+1):

# Does not make additional space to store water. AND does not

# change the landscape

if wall[1] == stack[-1][1]: continue

# Does not make additional space to store water. BUT does

# change the landscape

elif wall[1] < stack[-1][1]:

stack.append(wall)

# Add some additional space to store water.

# We need to adjust the landscape. For example, the previous

# landscape is:# , with a new #. Firstly, we will fill the gap

# ## #

# ### #

# like # # to # # to #++# and finally compress to #

# ## # ##+# ##+# #

# #### #### #### #

else:

adjustIndex = -1

while len(stack) > 1 and wall[1] > stack[-1][1]:

preWall = stack.pop()

# Fill with water

water += (min(wall[1], stack[-1][1]) - preWall[1]) * (wall[0]-preWall[0])

# Compress the walls with the same height

adjustIndex = preWall[0]

# Left guard wall is abandoned, because we have a new one

if len(stack) == 1 and stack[-1][1] <= wall[1]:

stack.pop()

stack.append((adjustIndex, wall[1]))

return water

Solution to First Missing Positive by LeetCode

18 May

Question: http://oj.leetcode.com/problems/first-missing-positive/ Question Name: First Missing Positive

class Solution:

# @param A, a list of integers

# @return an integer

def firstMissingPositive(self, A):

# Place number i in the place A[i-1]

index = 0

while index < len(A):

# Already in the place

if index + 1 == A[index]: index += 1

# Nowhere to swap

elif A[index] <= 0: index += 1

# Nowhere to swap

elif A[index] > len(A): index += 1

# No effect to swap

elif A[index] == A[A[index]-1]: index += 1

else:

swapI, swapJ = index, A[index]-1

A[swapI], A[swapJ] = A[swapJ], A[swapI]

# Try to find the first i, such that i + 1 != A[i]

for index in xrange(len(A)):

if index + 1 != A[index]: return index + 1

# If all positive integers appears, the first missing

# one would be the next integer

return len(A) + 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 /...