LeetCode – Page 15

Solution to Spiral Matrix by LeetCode

10 Jun

Question: https://oj.leetcode.com/problems/spiral-matrix/ Question Name: Spiral Matrix

class Solution:

# @param matrix, a list of lists of integers

# @return a list of integers

def spiralOrder(self, matrix):

rowLen = len(matrix)

if rowLen == 0: return [] # Empty list

colLen = len(matrix[0])

result = []

bound = min(rowLen, colLen)

for layer in xrange(bound//2):

# Access the top line

result.extend(matrix[layer][layer:colLen-layer-1])

# Access the right line

result.extend([matrix[i][colLen-layer-1] for i in xrange(layer,rowLen-layer-1)])

# Access the bottom line

result.extend(matrix[rowLen-layer-1][colLen-layer-1:layer:-1])

# Access the left line

result.extend([matrix[i][layer] for i in xrange(rowLen-layer-1,layer,-1)])

# Maybe one line is remaining for access

if bound % 2 == 1:

if bound == rowLen:

# The last horizontal line

result.extend(matrix[bound//2][bound//2:colLen-bound//2])

else:

# The last vertical line

result.extend([matrix[i][bound//2] for i in xrange(bound//2,rowLen-bound//2)])

return result

Solution to Jump Game by LeetCode

9 Jun

Question: https://oj.leetcode.com/problems/jump-game/ Question Name: Jump Game

class Solution:

# @param A, a list of integers

# @return a boolean

def canJump(self, A):

# Initially we can only access the first position

reachable = [False] * len(A)

reachable[0] = True

for index in xrange(len(A)):

# Not reachable to current position

if reachable[index] == False: break

for step in xrange(A[index], 0, -1):

# Out of range

if index+step >= len(A): continue

# Already reached

if reachable[index+step] == True: break

reachable[index+step] = True

return reachable[-1]

Solution to Maximum Subarray by LeetCode

9 Jun

Question: https://oj.leetcode.com/problems/maximum-subarray/ Question Name: Maximum Subarray This problem is a classic one.

class Solution:

# @param A, a list of integers

# @return an integer

def maxSubArray(self, A):

max_so_far = max_ending_here = A[0]

for item in A[1:]:

max_ending_here = max(item, max_ending_here + item)

max_so_far = max(max_ending_here, max_so_far)

return max_so_far

Solution to N-Queens II by LeetCode

9 Jun

Question: https://oj.leetcode.com/problems/n-queens-ii/ Question Name: N-Queens II Same method as that in N-Queens problem. But we could save some time and space by not recording the chessboard.

class QueenSolution(object):

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

N-Queen solutions

'''

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

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

self.col = col # Used columns

self.diagF = diagF # Used forward diagonal

self.diagB = diagB # Used backward diagonal

return

class Solution:

# @return an integer

def totalNQueens(self, n):

# Handle some special cases

if n == 1: return 1

if n == 2 or n == 3: return 0

result = [QueenSolution(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

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

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

result = temp # Prepare for working with the next row

return len(result)

Solution to Anagrams by LeetCode

7 Jun

Question: https://oj.leetcode.com/problems/anagrams/ Question Name: Anagrams

class Solution:

# @param strs, a list of strings

# @return a list of strings

def anagrams(self, strs):

records = {}

for string in strs:

signature = "".join(sorted([i for i in string]))

bucket = records.get(signature, [])

bucket.append(string)

records[signature] = bucket

result = []

for bucket in records.values():

if len(bucket) > 1:

# There are two or more strings, having the same

# letter distribution. They are anagrams.

result.extend(bucket)

return result

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

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