Python – Page 19 – Code Says

Solution to Search in Rotated Sorted Array by LeetCode

11 May

Question: http://oj.leetcode.com/problems/search-in-rotated-sorted-array/ Question Name: Search in Rotated Sorted Array

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @param begin, an integer to indicate the begin pos to search

# @param end, an integer to indicate the end pos to search

# @return an integer

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

''' Use a modified binary search algorithm to find the target

in a may-be-rotated array A from position begin to end.

'''

# Did not find the target

if begin > end: return -1

mid = (begin + end) // 2

if A[begin] < A[end]: rotated = False # Sorted and not rotated

else: rotated = True # Sorted and then rotated

if A[mid] == target:

# Target found

return mid

elif A[mid] < target:

# If array is not rotated, no need to search in the left part

if rotated:

# Target might be in the left part

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

if temp != -1: return temp

# Search in the right part

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

else:

# If array is not rotated, no need to search in the right part

if rotated:

# Target might be in the right part

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

if temp != -1: return temp

# Search in the left part

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

# @param A, a list of integers

# @param target, an integer to be searched

# @return an integer

def search(self, A, target):

return self._searchHelper(A, target, 0, len(A)-1)

Solution to Search for a Range by LeetCode

11 May

Question: http://oj.leetcode.com/problems/search-for-a-range/ Question Name: Search for a Range

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @return a list of length 2, [index1, index2]

def searchRange(self, A, target):

''' Use binary search to find the occurrence range

of target in array A.

'''

begin = -1

end = -1

# Find the first occurrence of target in A

front = len(A) - 1

back = 0

while back <= front:

mid = (front + back) // 2

if A[mid] > target:

front = mid - 1

elif A[mid] < target:

back = mid + 1

else:

front = mid - 1

begin = mid

# Target is not found in the array A

if begin == -1: return [-1, -1]

# Find the last occurrence of target in A

front = len(A) - 1

back = 0

while back <= front:

mid = (front + back) // 2

if A[mid] > target:

front = mid - 1

elif A[mid] < target:

back = mid + 1

else:

back = mid + 1

end = mid

return [begin, end]

Solution to Longest Valid Parentheses by LeetCode

1 May

Question: http://oj.leetcode.com/problems/longest-valid-parentheses/ Question Name: Longest Valid Parentheses

class Solution:

# @param s, a string

# @return an integer

def longestValidParentheses(self, s):

stack = []

# The leftmost ")"s are useless to form a valid parentheses

for item in s.lstrip(")"):

if item == "(":

stack.append(item)

else:

if stack[-1] == "(":

# A valid parentheses is found

stack.pop()

stack.append(2)

elif len(stack) > 1 and stack[-2] == "(":

# A valid parentheses is found

# stack[-1] != "(", otherwise the previous if block

# will be executed.

# stack[-1] != ")", otherwise, in the previous round,

# a valid parentheses is found, and ")" should not

# be in the stack

# So stack[-1] must be a number.

temp =stack.pop()

stack.pop()

stack.append(temp + 2)

else:

# We should start a new search for the remaining part.

# And any content in the remaining part can NOT form

# a valid parentheses with previous content.

stack.append(")")

continue

# Compress the previous valid parentheses

# For example, with "()()",after dealing with the last ")"

# the stack would be [2,2], we try to compress into one unit

# as [4].

# After compression, we could guarantee, if current procession

# letter is ")", and there is a previous matching "(", there

# will be only one or zero integer between them in the stack.

while len(stack) > 1 and isinstance(stack[-2], int):

temp = stack.pop()

temp += stack.pop()

stack.append(temp)

# Remove the non-number elements

stack = [item for item in stack if isinstance(item,int)]

if len(stack) == 0: return 0

else: return max(stack)

Solution to psi2012 (Wire-Burnouts) by codility

28 Apr

Question: https://codility.com/demo/take-sample-test/wire_burnouts Question Name: psi2012 or Wire-Burnouts or WireBurnouts A good application of weighted quick union algorithm.

class WeightedQuickUnion(object):

''' A class for weighted quick union data structure

Details: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

'''

ID = None # ID[i] = component identifier of i

weight = None # weight[i] = number of nodes in the subtree(component)

# with i being the root

def __init__(self, size):

assert size > 0

# Each individual cell is a component

self.ID = [i for i in xrange(size)]

# Each component has only one item initially

self.weight = [1 for i in xrange(size)]

return

def findRoot(self, cell):

''' Return the root of tree, to which cell belongs.

That is, the component identifier of cell.

'''

assert 0 <= cell < len(self.ID)

while cell != self.ID[cell]: cell = self.ID[cell]

return cell

def isConnected(self, p, q):

''' Check whether p and q belong to same component/tree.

'''

assert 0 <= p < len(self.ID) and 0 <= q < len(self.ID)

return self.findRoot(p) == self.findRoot(q)

def union(self, p, q):

''' Merge the components (trees), to which p and q belong

'''

assert 0 <= p < len(self.ID) and 0 <= q < len(self.ID)

rootP = self.findRoot(p)

rootQ = self.findRoot(q)

# Already the same component

if rootP == rootQ: return

if self.weight[rootP] >= self.weight[rootQ]:

self.ID[rootQ] = rootP

self.weight[rootP] += self.weight[rootQ]

else:

self.ID[rootP] = rootQ

self.weight[rootQ] += self.weight[rootP]

return

class Grid(object):

''' A wrapper class of WeightedQuickUnion for the current grid

'''

grid = None

size = -1

def __init__(self, size):

self.grid = WeightedQuickUnion(size*size)

# This is a size * size grid

self.size = size

return

def isConnected(self, x1, y1, x2, y2):

''' Check whether the nodes (x1, y1) and (x2, y2) in the grid

is connected or not.

'''

p = x1 * self.size + y1

q = x2 * self.size + y2

return self.grid.isConnected(p, q)

def union(self, x1, y1, x2, y2):

''' Connect two nodes (x1, y1) and (x2, y2) in the grid

'''

p = x1 * self.size + y1

q = x2 * self.size + y2

self.grid.union(p, q)

return

def solution(N, A, B, C):

# Not enough burn out wires to stop the current from flowing

if len(A) < N + N - 2: return -1

grid = Grid(N)

# Get all the wires, which will burn out.

removed = {}

for index in xrange(len(A)):

if C[index] == 0: removed[(A[index], B[index], A[index], B[index]+1)] = True

else: removed[(A[index], B[index], A[index]+1, B[index])] = True

# Add all the never-burn wires to the grid

for x in xrange(N):

for y in xrange(N):

if y + 1 < N and not (x, y, x, y+1) in removed:

grid.union(x, y, x, y+1)

if x + 1 < N and not (x, y, x+1, y) in removed:

grid.union(x, y, x+1, y)

# Even if all the wires in A, B, and C burn out, the current is still flowing

if grid.isConnected(0, 0, N-1, N-1): return -1

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

# Recovery one burn-out wire

if C[index] == 0:

grid.union(A[index], B[index], A[index], B[index]+1)

else:

grid.union(A[index], B[index], A[index]+1, B[index])

# After recovery, the current could flow.

if grid.isConnected(0, 0, N-1, N-1): return index + 1

# Would never be here.

return -1

Solution to Next Permutation by LeetCode

28 Apr

Question: http://oj.leetcode.com/problems/next-permutation/ Question Name: Next Permutation This problem seems like a mathematic question, rather than a programming challenge.

class Solution:

# @param num, a list of integer

# @return a list of integer

def nextPermutation(self, num):

# In the greatest permutation of numbers, any number is larger

# than or equal to the right remaining numbers.

# If the num is not the greatest permutation, there must be

# one or more pairs being rule breakers. That is, in these pairs,

# the left hand number is smaller than the right hand one.

# Search from rightmost to leftmost to find out the least

# significant rule breaker.

back = len(num) - 2

while back >= 0:

front = len(num) - 1

while front > back :

if num[back] < num[front]:

# Rule breaker found.

num[back], num[front] = num[front], num[back]

num[back+1:] = sorted(num[back+1:])

return num

else:

front -= 1

back -= 1

# No rule breaker in this array. Return the lowest possible order.

num.sort()

return num

Solution to Substring with Concatenation of All Words by LeetCode

26 Apr

Question: http://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/ Question Name: Substring with Concatenation of All Words The brute force method works here. Assume the hash function is O(n). Let the length of S be M, the length of L be N, and the length of each … Read More »

Solution to Implement strStr() by LeetCode

25 Apr

Question: http://oj.leetcode.com/problems/implement-strstr/ Question Name: Implement strStr() The KMP is a much better solution. But as long as brute force passed all tests, let’s use brute force.

class Solution:

# @param haystack, a string

# @param needle, a string

# @return a string or None

def strStr(self, haystack, needle):

# Hanlde two special cases.

if needle == "": return haystack

if haystack == "": return None

lenHaystack = len(haystack)

lenNeedle = len(needle)

begin = 0

# Compare each substring as long as their length

# is >= the length of needle

while lenHaystack - begin >= lenNeedle:

for index in xrange(lenNeedle):

if haystack[begin+index] != needle[index]:

# Find a different char

break

else:

# Completely the same

return haystack[begin:]

begin += 1

return None

Solution to Divide Two Integers by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/divide-two-integers/ Question Name: Divide Two Integers

class Solution:

# @return an integer

def divide(self, dividend, divisor):

# Handle the special case that, dividend is zero

if dividend == 0: return 0

# Handle the special case that, divisor is zero

if divisor == 0: raise ZeroDivisionError()

result = 0 # Final result

# Determine the sign of final result, and convert

# dividend or/and divisor into positive integer.

positive = True

if dividend < 0:

dividend = -dividend

positive = (not positive)

if divisor < 0:

divisor = -divisor

positive = (not positive)

# Enlarge the divisor as long as it is <= dividend

step = divisor

stepRes = 1

while (step << 1) <= dividend:

step = step << 1

stepRes = stepRes << 1

while step >= divisor:

while dividend >= step:

dividend -= step

result += stepRes

# If current step is too large, try a smaller

# step (divisor).

step = step >> 1

stepRes = stepRes >> 1

if positive: return result

else: return -result

Solution to Remove Duplicates from Sorted Array by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/ Question Name: Remove Duplicates from Sorted Array

class Solution:

# @param a list of integers

# @return an integer

def removeDuplicates(self, A):

# Handle the special case that, A is empty

if len(A) == 0: return 0

front, back = 1, 1

while front < len(A):

if A[front] != A[front-1]:

# Not a duplicate item

A[back] = A[front]

back += 1

front += 1

return back

Solution to Remove Element by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/remove-element/ Question Name: Remove Element

class Solution:

# @param A a list of integers

# @param elem an integer, value need to be removed

# @return an integer

def removeElement(self, A, elem):

front, back = 0, 0

while front < len(A):

if A[front] != elem:

# Not to be removed

A[back] = A[front]

back += 1

front += 1

return back

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