LeetCode – Page 14

Solution to Merge Two Sorted Lists by LeetCode

14 Jun

Question: https://oj.leetcode.com/problems/merge-two-sorted-lists/ Question Name: Merge Two Sorted Lists

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param two ListNodes

# @return a ListNode

def mergeTwoLists(self, l1, l2):

head = ListNode(-1) # A pseudo head node

current = head

while l1 != None and l2 != None:

if l1.val <= l2.val:

# Append l1's current node

current.next = l1

l1 = l1.next

current = current.next

else:

# Append l2's current node

current.next = l2

l2 = l2.next

current = current.next

if l1 != None: current.next = l1 # Extend the remaining node(s) in l1

else: current.next = l2 # Extend the remaining node(s) in l2

head = head.next # Remove the pseudo head node

return head

Solution to Unique Paths II by LeetCode

14 Jun

Question: https://oj.leetcode.com/problems/unique-paths-ii/ Question Name: Unique Paths II Similar with these questions: Minimum Path Sum and minimum edit distance.

class Solution:

# @param obstacleGrid, a list of lists of integers

# @return an integer

def uniquePathsWithObstacles(self, obstacleGrid):

# COmpute the dimensions

rowLen = len(obstacleGrid)

colLen = len(obstacleGrid[0])

# Compute the number of possible path in the first column

possiblePathCount = [0] * rowLen

possiblePathCount[0] = 1

# Compute the number of possible path in the remaining column

for colIndex in xrange(colLen):

if obstacleGrid[0][colIndex] == 1:

# This cell is obstacle. Impossible to reach here.

possiblePathCount[0] = 0

for rowIndex in xrange(1, rowLen):

if obstacleGrid[rowIndex][colIndex] == 1:

# This cell is obstacle. Impossible to reach here.

possiblePathCount[rowIndex] = 0

else:

# We may reach here by moving from either left or upper cell.

possiblePathCount[rowIndex] += possiblePathCount[rowIndex-1]

return possiblePathCount[-1]

Solution to Unique Paths by LeetCode

13 Jun

Question: https://oj.leetcode.com/problems/unique-paths/ Question Name: Unique Paths

class Solution:

# @return an integer

def uniquePaths(self, m, n):

# From the top-left cell to bottom-right cell, there are

# totally m+n-2 moves. Among these moves, m-1 is moving

# downwards, and n-1 is moving to right. So the number of

# possible unique paths = C(m+n-2, m-1) = C(m+n-2, n-1).

result = 1

# Because C(m+n-2, m-1) = C(m+n-2, n-1), we are going to

# do one with less steps.

total = m + n - 2

chosen = min(m, n) - 1

# http://en.wikipedia.org/wiki/Binomial_coefficient

for i in xrange(total, total-chosen, -1): result *= i

for i in xrange(chosen): result //= (i+1)

return result

Solution to Minimum Path Sum by LeetCode

12 Jun

Question: https://oj.leetcode.com/problems/minimum-path-sum/ Question Name: Minimum Path Sum

class Solution:

# @param grid, a list of lists of integers

# @return an integer

def minPathSum(self, grid):

# Similar with the minimum edit distance algorithm

colLen = len(grid)

column = [-1] * colLen

# Go through the first column

column[0] = grid[0][0]

for index in xrange(1, colLen):

column[index] = grid[index][0] + column[index-1]

# Go through the remaining cells column by column

for colIndex in xrange(1, len(grid[0])):

column[0] += grid[0][colIndex]

for rowIndex in xrange(1, colLen):

column[rowIndex] = min(column[rowIndex], column[rowIndex-1])

+ grid[rowIndex][colIndex]

return column[-1]

Solution to Insert Interval by LeetCode

12 Jun

Question: https://oj.leetcode.com/problems/insert-interval/ Question Name: Insert Interval

# 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 Intervals

# @param newInterval, a Interval

# @return a list of Interval

def insert(self, intervals, newInterval):

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

# Insert the newInterval according to its start position.

# Actually, we could only find out where to insert, and then

# divide the following merge code into three parts to avoid insertion.

# But the non-insert version would be long code.

# Find the insert position with binary method.

begin, end = 0, len(intervals) - 1

while begin <= end:

mid = (begin + end) // 2

if newInterval.start > intervals[mid].start:

begin = mid + 1

elif newInterval.start < intervals[mid].start:

end = mid - 1

else:

begin = mid

break

# Insert the new interval into the old list.

intervals = intervals[:begin] + [newInterval] + intervals[begin:]

# Do merge if we could

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

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