Sheng – Page 20 – Code Says

Solution to Combinations by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/combinations/ Question Name: Combinations

class Solution:

# @return a list of lists of integers

def combine(self, n, k):

pool = range(1, n+1) # The candidates to choose

limit = 1 << len(pool)

current = 0 # In current, bit[i] == 1 means S[i] is chosen.

result = []

while current < limit:

# Construct the list for "current"

temp = []

for index in xrange(len(pool)):

if (1 << index) & current != 0:

temp.append(pool[index])

if len(temp) > k: # List is too long

break

else:

if len(temp) == k: # List is qualified for result

result.append(temp)

# Else, it is too short

current += 1

return result

Solution to Subsets by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/subsets/ Question Name: Subsets

class Solution:

# @param S, a list of integer

# @return a list of lists of integer

def subsets(self, S):

''' A problem to test the bit operation.

'''

S.sort() # Make sure the result is non-descending order.

limit = 1 << len(S)

current = 0 # In current, bit[i] == 1 means S[i] is chosen.

result = []

while current < limit:

# Construct the list for "current"

temp = []

for index in xrange(len(S)):

if (1 << index) & current != 0:

temp.append(S[index])

result.append(temp)

current += 1

return result

Solution to Word Search by LeetCode

19 Jun

Question: https://oj.leetcode.com/problems/word-search/ Question Name: Word Search The description and comments are misleading. Comments says “@param board, a list of lists of 1 length string”. And in the example, the input board is [[“ABCE”], [“SFCS”], [“ADEE”]]. But actually, in the tests, … Read More »

Solution to Minimum Window Substring by LeetCode

19 Jun

Question: https://oj.leetcode.com/problems/minimum-window-substring/ Question Name: Minimum Window Substring

class Solution:

# @return a string

def minWindow(self, S, T):

minWindow = [-1,-1]

# The begin and end position (both inclusive) of current window

begin, end = -1, 0

# The number of each char in current window

totalCount = {i:0 for i in T}

# Compute the char distribution in T

need = {}

for item in T: need[item] = need.get(item, 0) + 1

# Find the first window, containing all the characters in T

needCount = len(T)

while end < len(S):

if S[end] in need:

if begin == -1: begin = end

totalCount[S[end]] += 1

if totalCount[S[end]] <= need[S[end]]:

# Find one more char for a qualified window

needCount -= 1

# Enough chars to form a window

if needCount == 0: break

end += 1

else:

# Did not find a window

return ""

# Try to minimize the window length by removing the leftmost items

while True:

if S[begin] in need:

if totalCount[S[begin]] > need[S[begin]]:

totalCount[S[begin]] -= 1

begin += 1

else:

# Already be minimum

break

else:

begin += 1

minWindow = [begin, end]

# Try next window, ending with S[begin]

while True:

# Find the next window, ending with current S[begin]

end += 1

while end < len(S):

if S[end] == S[begin]: break

if S[end] in totalCount: totalCount[S[end]] += 1

end += 1

else:

# No windows left.

break

# Minimize current window, by removing the leftmost items

begin += 1

while begin <= end:

if S[begin] in need:

if totalCount[S[begin]] > need[S[begin]]:

totalCount[S[begin]] -= 1

begin += 1

else:

# Minimized

break

else:

begin += 1

if end - begin < minWindow[1] - minWindow[0]:

# Find a shorter window

minWindow[0], minWindow[1] = begin, end

return S[minWindow[0]: minWindow[1]+1]

Solution to Sort Colors by LeetCode

17 Jun

Question: https://oj.leetcode.com/problems/sort-colors/ Question Name: Sort Colors

class Solution:

# @param A a list of integers

# @return nothing, sort in place

def sortColors(self, A):

''' The one-pass solution is similar with the 3-way

quick sort algorithm.

'''

nextZero = 0 # The position to store the next 0

nextTwo = len(A) - 1 # The position to store the next 2

index = 0

while index <= nextTwo: # !!! BEWARE OF THE RANGE !!!

if A[index] == 0: # May need to be moved to the head.

if index == nextZero:

# Already in the head part. No need to move.

index += 1

nextZero += 1

else:

# Move the the head part.

A[index], A[nextZero] = A[nextZero], A[index]

nextZero += 1

elif A[index] == 2: # Need to be moved to the tail.

A[index], A[nextTwo] = A[nextTwo], A[index]

nextTwo -= 1

else: # Keep in the middle range.

index += 1

return

Solution to Search a 2D Matrix by LeetCode

17 Jun

Question: https://oj.leetcode.com/problems/search-a-2d-matrix/ Question Name: Search a 2D Matrix

class Solution:

# @param matrix, a list of lists of integers

# @param target, an integer

# @return a boolean

def searchMatrix(self, matrix, target):

''' Flatten the matrix into 1-dimension list. Then this

question turns to be binary search question.

'''

rowLen = len(matrix)

colLen = len(matrix[0])

begin, end = 0, rowLen * colLen - 1

while begin <= end:

mid = (begin + end) // 2

# Convert to 1D binary search question

midCell = matrix[mid//colLen][mid%colLen]

if midCell > target: end = mid - 1

elif midCell < target: begin = mid + 1

else: return True

return False

Solution to Set Matrix Zeroes by LeetCode

17 Jun

Question: https://oj.leetcode.com/problems/set-matrix-zeroes/ Question Name: Set Matrix Zeroes

class Solution:

# @param matrix, a list of lists of integers

# RETURN NOTHING, MODIFY matrix IN PLACE.

def setZeroes(self, matrix):

# Empty matrix

if len(matrix) == 0 or len(matrix[0]) == 0: return

row = [False] * len(matrix)

column = [False] * len(matrix[0])

# Record the rows and columns with element(s) being zero.

for rowIndex in xrange(len(matrix)):

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

if matrix[rowIndex][colIndex] == 0:

row[rowIndex] = True

column[colIndex] = True

# Set the qualified entire row(s) and column(s) to zero.

for rowIndex in xrange(len(matrix)):

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

if row[rowIndex] == True or column[colIndex] == True:

matrix[rowIndex][colIndex] = 0

return

Solution to Edit Distance by LeetCode

16 Jun

Question: https://oj.leetcode.com/problems/edit-distance/ Question Name: Edit Distance

class Solution:

# @return an integer

def minDistance(self, word1, word2):

''' Implement the minimum edit distance according to

the description of WikiPedia:

http://en.wikipedia.org/wiki/Edit_distance

Some other implements are available here:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

'''

delCost = insCost = subCost = 1 # The cost for each operation

steps = range(len(word1)+1)

for word2Index in xrange(len(word2)):

diag = steps[0] # d(i-1, j-1)

steps[0] += 1

for word1Index in xrange(len(word1)):

temp = steps[word1Index+1]

if word1[word1Index] == word2[word2Index]:

steps[word1Index+1] = diag

else:

steps[word1Index+1] = min(steps[word1Index+1] + insCost,

steps[word1Index] + delCost,

diag + subCost)

diag = temp # Store d(i-1, j-1) for next cell

return steps[-1]

Solution to Text Justification by LeetCode

15 Jun

Question: https://oj.leetcode.com/problems/text-justification/ Question Name: Text Justification

class Solution:

# @param words, a list of strings

# @param L, an integer

# @return a list of strings

def fullJustify(self, words, L):

begin, end = 0, 0 # The index of begin word (inclusive) and end

# word (exclusive) in one line

result =[]

while True:

wordsLen = 0 # The total length of all words to be used

# in this line.

# Determine how many following words are used for this line.

while end < len(words):

if wordsLen + len(words[end]) + (end - begin) <= L:

wordsLen += len(words[end])

end += 1

else:

break

else:

# This is the last line.

temp = " ".join(words[begin:end])

temp += " " * (L - len(temp))

result.append(temp)

break

# Construct the line after text justification.

temp = ""

if end == begin + 1:

# This line only contains one word.

temp = words[begin] + " " * (L - len(words[begin]))

else:

# This line contains multiple words.

spaceCount = (L - wordsLen) // (end - begin -1)

oneMoreSpace = (L- wordsLen) % (end- begin - 1)

for index in xrange(begin, end-1):

if index - begin < oneMoreSpace:

temp += words[index] + " " * (spaceCount + 1)

else:

temp += words[index] + " " * spaceCount

temp += words[end-1]

result.append(temp)

begin = end

return result

Solution to Sqrt(x) by LeetCode

15 Jun

Question: https://oj.leetcode.com/problems/sqrtx/ Question Name: Sqrt(x)

class Solution:

# @param x, an integer

# @return an integer

def sqrt(self, x):

begin, end = 0, x

# Use binary search to find the largest

# integer i such that, i * i <= x

while begin <= end:

mid = (begin + end) // 2

temp = mid * mid

if temp == x: return mid

elif temp < x: begin = mid + 1

else: end = mid - 1

return end

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