Sheng – Page 19 – Code Says

Solution to Merge Sorted Array by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/merge-sorted-array/ Question Name: Merge Sorted Array

class Solution:

# @param A a list of integers

# @param m an integer, length of A

# @param B a list of integers

# @param n an integer, length of B

# @return nothing

def merge(self, A, m, B, n):

lastA, lastB = m-1, n-1 # Travel A and B from right to left

last2Write = m + n -1 # Write the integers from the rightmost

# position to the leftmost position of A

while lastA != -1 and lastB != -1:

if A[lastA] >= B[lastB]:

A[last2Write] = A[lastA]

lastA -= 1

else:

A[last2Write] = B[lastB]

lastB -= 1

last2Write -= 1

# If A list has some remaining items to process, they are already in

# their to-be position. No operation is needed.

# Otherwise, if B list has some remaining items, copy them to the head

# of A.

if lastB != -1: A[:lastB+1] = B[:lastB+1]

return

Solution to Gray Code by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/gray-code/ Question Name: Gray Code At the beginning, I have no idea other than brute force. But thanks to Wikipedia, the perfect solution is found.

class Solution:

# @return a list of integers

def grayCode(self, n):

result = []

for item in xrange(1<<n):

result.append(item ^ (item>>1))

return result

Solution to Partition List by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/partition-list/ Question Name: Partition List

class Solution:

# @param head, a ListNode

# @param x, an integer

# @return a ListNode

def partition(self, head, x):

smaller = ListNode(-1) # A pseudo head node to link all nodes, whose

# value is less than x

others = ListNode(-1) # A pseudo head node to link all nodes, whose

# value is greater than or equal to x

# Record the last nodes in "smaller" and "others" lists respectively.

smallerLast, othersLast = smaller, others

while head != None:

if head.val < x:

# Append to the end of "smaller" list

smallerLast.next = head

smallerLast = smallerLast.next

else:

# Append to the end of "others" list

othersLast.next = head

othersLast = othersLast.next

head = head.next

smallerLast.next = others.next # Append the "others" list to the end

# of "smaller"

othersLast.next = None # Close the whole list

return smaller.next # Skip the pseudo head node.

Solution to Scramble String by LeetCode

26 Jun

Question: https://oj.leetcode.com/problems/scramble-string/ Question Name: Scramble String

class Solution:

# @return a boolean

def isScramble(self, s1, s2):

if len(s1) != len(s2): return False

if s1 == s2: return True

# Check their char distribution before trying to swap it.

charDis = {}

for index in xrange(len(s1)): # Gather char distribution

charDis[s1[index]] = charDis.get(s1[index], 0) + 1

charDis[s2[index]] = charDis.get(s2[index], 0) - 1

for index in xrange(len(s1)): # Check char distribution

if charDis[s1[index]] != 0: return False

# Try to divide the strings into two part, and may swap parts.

for index in xrange(1, len(s1)):

# Divided, but did not swap the parts

if self.isScramble(s1[:index], s2[:index]) and

self.isScramble(s1[index:], s2[index:]):

return True

# Divided, and swapped the parts

if self.isScramble(s1[:index], s2[-index:]) and

self.isScramble(s1[index:], s2[:len(s2)-index]):

return True

return False

Solution to Maximal Rectangle by LeetCode

24 Jun

Question: https://oj.leetcode.com/problems/maximal-rectangle/ Question Name: Maximal Rectangle

class Solution:

# @param height, a list of integer

# @return an integer

def largestRectangleArea(self, height):

stack = [] # Store the position of bars with non-decreasing height

maxArea = 0

height.append(-1) # Append a pseudo bar at the end so that, after

# the while loop, the one and the only on bar

# left in the stack will definitely be this

# pseudo bar.

index = 0

# In this loop, we are using the stack to find out the largest zone

# for each bar (to say i), in which bar i is the shortest one.

while index < len(height):

if len(stack) == 0:

# This is the first bar. OR all of its previous bars are

# higher than this one.

stack.append(index)

index += 1

elif height[index] >= height[stack[-1]]:

stack.append(index)

index += 1

else:

preBasin = stack.pop()

if len(stack) == 0:

# From beginning to index-1 position, the preBasin has

# the shortest bar.

maxArea = max(maxArea, height[preBasin] * index)

else:

# From stack[-1] position to index-1 position, the

# preBasin has the shortest bar.

maxArea = max(maxArea, height[preBasin] *

(index-stack[-1]-1) )

return maxArea

# @param matrix, a list of lists of 1 length string

# @return an integer

def maximalRectangle(self, matrix):

# Handle the special case that the matrix is empty

if len(matrix) == 0: return 0

# heights[i][j] means on the i(th) row, begin with j(th) position,

# how many consecutive one(s) are there.

heights = [[0] * len(matrix[0]) for _ in xrange(len(matrix))]

for row in xrange(len(matrix)):

# We are going to travel the row from the end to the beginning

if matrix[row][-1] == "1": heights[row][-1] = 1

for col in xrange(len(matrix[0])-2, -1, -1):

if matrix[row][col] == "0":

heights[row][col] = 0

else:

heights[row][col] = heights[row][col+1] + 1

# We transfer the original challenge into an old question: Largest

# Rectangle in Histogram. We compute the largest rectangle on each

# column (towards right). And then choose the maximum among them.

maxArea = 0

for x in xrange(len(matrix[0])):

maxArea = max(maxArea,

self.largestRectangleArea(

[heights[y][x] for y in xrange(len(matrix))]))

return maxArea

Solution to Remove Duplicates from Sorted List II by LeetCode

23 Jun

Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ Question Name: Remove Duplicates from Sorted List II

class Solution:

# @param head, a ListNode

# @return a ListNode

def deleteDuplicates(self, head):

# Handle special case that the list is empty

if head == None: return head

# Add a pseudo head node to make the process uniform

tempHead = ListNode(head.val ^ 0x1)

tempHead.next = head

current = tempHead

while current.next != None:

nextVal = current.next

if nextVal.next != None and nextVal.val == nextVal.next.val:

# This element and its next one are the same.

# They are duplicate. We are going to remove

# all the nodes with this value from the list.

nextVal = nextVal.next

while nextVal.next != None and nextVal.val == nextVal.next.val:

nextVal = nextVal.next

current.next = nextVal.next

else:

current = current.next

# Skip the pseudo head node, and return the real one.

return tempHead.next

Solution to Remove Duplicates from Sorted List by LeetCode

23 Jun

Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/ Question Name: Remove Duplicates from Sorted List

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @return a ListNode

def deleteDuplicates(self, head):

# Handle special case that the list is empty

if head == None: return head

current = head

# Travel the list until the second last node

while current.next != None:

if current.val == current.next.val:

# This element and the next one are the same.

# They are duplicate. We are going to remove

# the next node.

temp = current.next

current.next = current.next.next

del temp

else:

current = current.next

return head

Solution to Largest Rectangle in Histogram by LeetCode

23 Jun

Question: https://oj.leetcode.com/problems/largest-rectangle-in-histogram/ Question name: Largest Rectangle in Histogram

class Solution:

class Status(object):

''' A class to store the intermediate status of the dividing zone.

A name tuple is better if it is allowed.

'''

__slots__ = ["heightIndex", "begin", "end"]

def __init__(self, heightIndex, begin, end):

self.heightIndex = heightIndex

self.begin = begin

self.end = end

return

# @param height, a list of integer

# @return an integer

def largestRectangleArea(self, height):

height = sorted(enumerate(height), key = lambda x: x[1])

# All bars have non-negative height. Area is at least 0.

maxArea = 0

# Initialize the stack. Recursive solution will lead to stack overflow

stack = [self.Status(0, 0, len(height)-1)]

while len(stack) != 0:

subSection = stack.pop()

# Terminate case

if subSection.begin > subSection.end: continue

# Skip the bars if they are not in current zone [begin, end].

while not subSection.begin <= height[subSection.heightIndex][0]

<= subSection.end:

subSection.heightIndex += 1

# Liebig's law of the minimum. The height of the rectangle

# is determined by the lowest bar.

area = (subSection.end - subSection.begin + 1) *

height[subSection.heightIndex][1]

maxArea = max(maxArea, area)

# All the bars in current zone [begin, end] have the same height.

# No lower bar, so no need to divide current zone.

if height[subSection.heightIndex][1] == height[-1][1]: continue

# Divide current zone with the lowest bar. Only after removing

# the lowest bar, the height of new zones could be higher

# (also possibly keep the same).

# Left part of current zone.

stack.append(self.Status(subSection.heightIndex+1,

subSection.begin,

height[subSection.heightIndex][0]-1))

# Right part of current zone.

stack.append(self.Status(subSection.heightIndex+1,

height[subSection.heightIndex][0]+1,

subSection.end))

return maxArea

Update on 2014-06-24: Thanks to optimization, the previous solution passed all the tests. But when I met with the question “Maximal Rectangle”, I realized the previous one is not the designed … Read More »

Solution to Remove Duplicates from Sorted Array II by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ Question Name: Remove Duplicates from Sorted Array II The second previous element might be overwritten in the last round.

class Solution:

# @param A a list of integers

# @return an integer

def removeDuplicates(self, A):

if len(A) < 3: return len(A)

front, back = 2, 2

secondPre = A[front-2]

while front < len(A):

if A[front] == A[front-1] and A[front] == secondPre:

secondPre = A[front-1]

else:

secondPre = A[front-1]

A[back] = A[front]

back += 1

front += 1

return back

Well, inspired by http://www.mitbbs.com/article_t/JobHunting/32770131.html, there is a better and more generic solution as:

class Solution:

# @param A a list of integers

# @param M the times that duplicates are allowed

# @return an integer

def _removeDuplicatesHelper(self, A, M):

''' Remove some duplicate items in A. So that one single item

appears at most M times.

'''

if len(A) < 2: return len(A)

toWrite = 1 # The position for next write. And toWrite - 1

# is th previous appeared item.

count = 1 # The occurrence of previous appeared item.

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

if A[index] == A[toWrite-1]:

# Is a duplicate item, being the same as the previous one.

count += 1

if count <= M:

# It is allowed to appear M times or less.

A[toWrite] = A[index]

toWrite += 1

else:

# Meet with a new item.

A[toWrite] = A[index]

toWrite += 1

count = 1

return toWrite

# @param A a list of integers

# @return an integer

def removeDuplicates(self, A):

return self._removeDuplicatesHelper(A, 2)

With the parameter M … Read More »

Solution to Search in Rotated Sorted Array II by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/ Question Name: Search in Rotated Sorted Array II I did not notice, there is no duplicate in Search in Rotated Sorted Array. SO I’ve done this in that question.

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @return an integer

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

if begin > end: return -1

mid = (begin + end) // 2

if A[begin] < A[end]: rotated = False

else: rotated = True

if A[mid] == target:

return mid

elif A[mid] < target:

if rotated:

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

if temp != -1: return temp

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

else:

if rotated:

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

if temp != -1: return temp

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

# @param A, a list of integers

# @param target, an integer to be searched

# @return a boolean

def search(self, A, target):

if self._searchHelper(A, target, 0, len(A)-1) == -1:

return False

else:

return True

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