Sheng – Page 22 – Code Says

Solution to Length of Last Word by LeetCode

11 Jun

Question: https://oj.leetcode.com/problems/length-of-last-word/ Question Name: Length of Last Word

class Solution:

# @param s, a string

# @return an integer

def lengthOfLastWord(self, s):

s = s.strip() # Remove the spaces at the beginning and end

length = 0

for letter in s:

if letter == " ": length = 0 # Waiting for the next word

else: length += 1 # Inside one word

return length

If strip() method is forbidden or unusable, we could do it like:

class Solution:

# @param s, a string

# @return an integer

def lengthOfLastWord(self, s):

preLength = 0 # Length of previous word

length = 0 # Length of current word

for letter in s:

if letter == " ": # Waiting for the next word

if length != 0: # This is a single zero or

# leading one in zeros

preLength = length

length = 0

else: # A following zero in zeros

pass

else:

# Inside one word

length += 1

if length == 0: return preLength # s ends with zero(s)

else: return length # s ends with word

Solution to Spiral Matrix II by LeetCode

11 Jun

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

class Solution:

# @return a list of lists of integer

def generateMatrix(self, n):

if n == 0: return []

result = [[0]*n for _ in xrange(n)]

current = 1

for layer in xrange(n//2):

# Fill the top line

for i in xrange(layer, n-layer-1):

result[layer][i] = current

current += 1

# Fill the right line

for i in xrange(layer,n-layer-1):

result[i][n-layer-1] = current

current += 1

# Fill the bottom line

for i in xrange(n-layer-1,layer,-1):

result[n-layer-1][i] = current

current += 1

# Fill the left line

for i in xrange(n-layer-1,layer,-1):

result[i][layer] = current

current += 1

# Fill the center

if n % 2 == 1: result[n//2][n//2] = current

return result

Solution to Permutation Sequence by LeetCode

11 Jun

Question: https://oj.leetcode.com/problems/permutation-sequence/ Question Name: Permutation Sequence

class Solution:

# @return a string

def getPermutation(self, n, k):

assert 1 <= n <= 9

# Get the total number of permutations

total = 1

for i in xrange(n): total *= i + 1

# Adjust k to zero-based index

k = k - 1

assert 0 <= k < total

result = [] # The sequence o result permutation

candidates = range(1, n+1) # The numbers to form the permutation

remaining = total # How many possible permutations are there in

# the remaining part?

for position in xrange(n, 0, -1):

remaining = remaining // position

# Use the (k//remaining)th element and remove it from candidates

result.append(str(candidates[k//remaining]))

candidates.remove(candidates[k//remaining])

k %= remaining

return "".join(result)

Solution to Rotate List by LeetCode

10 Jun

Question: https://oj.leetcode.com/problems/rotate-list/ Question Name: Rotate List

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @param k, an integer

# @return a ListNode

def rotateRight(self, head, k):

assert k >= 0

# Empty list

if head == None: return head

# Compute the length of the list

listLen = 0

temp = head

while temp != None:

temp = temp.next

listLen += 1

k = k % listLen

# No need to rotate

if k == 0: return head

# Find the last node, and the last (k+1)th node

former = latter = head

for _ in xrange(k):

latter = latter.next

while latter.next != None:

latter = latter.next

former = former.next

# Rotate the list

newHead = former.next

latter.next = head

former.next = None

return newHead

Solution to Merge Intervals by LeetCode

10 Jun

Question: https://oj.leetcode.com/problems/merge-intervals/ Question Name: Merge Intervals

# Definition for an interval.

# class Interval:

# def __init__(self, s=0, e=0):

# self.start = s

# self.end = e

class Solution:

# @param intervals, a list of Interval

# @return a list of Interval

def merge(self, intervals):

if len(intervals) == 0: return [] # Empty input

# Sort the input according to the start position

intervals.sort(key = lambda x:x.start)

previous = Interval(intervals[0].start, intervals[0].end)

result = []

for interval in intervals[1:]:

if interval.start > previous.end:

# Cannot merge the current interval with the previous one

result.append(previous)

previous = Interval(interval.start, interval.end)

else:

# Merge the current interval with the previous one, by

# extending the end position if possible

previous.end = max(interval.end, previous.end)

# Record the last one interval

result.append(previous)

return result

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

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