Python – Page 21 – Code Says

Solution to 4Sum by LeetCode

8 Apr

Quesion: http://oj.leetcode.com/problems/4sum/ Question Name: 4Sum or 4-sum The key point is to prune when further qualified combination is not possible.

class Solution:

# @return a list of lists of length 4, [[val1,val2,val3,val4]]

def fourSum(self, num, target):

result = []

num.sort()

firstIndex = 0

while firstIndex < len(num)-3:

secondIndex = firstIndex + 1

while secondIndex < len(num)-2:

thirdIndex = secondIndex + 1

fourthIndex = len(num) - 1

while thirdIndex < fourthIndex:

if num[firstIndex] + num[secondIndex] + num[thirdIndex]

+ num[thirdIndex] > target:

# Already too larger, not possible to find any qualified

# list afterwards

break

if num[firstIndex] + num[secondIndex] + num[fourthIndex]

+ num[fourthIndex] < target:

# Already too small, not possible to find any qualified

# list forwards

break

temp = num[firstIndex] + num[secondIndex] + num[thirdIndex]

+ num[fourthIndex]

if temp == target:

result.append([num[firstIndex], num[secondIndex],

num[thirdIndex], num[fourthIndex]])

# Skip the duplicate numbers as num[thirdIndex]

thirdIndex += 1

while thirdIndex < fourthIndex + 1 and

num[thirdIndex] == num[thirdIndex-1]:

thirdIndex += 1

# Skip the duplicate numbers as num[fourthIndex]

fourthIndex -= 1

while fourthIndex > thirdIndex -1 and

num[fourthIndex] == num[fourthIndex+1]:

fourthIndex -= 1

elif temp > target:

# Skip the duplicate numbers as num[fourthIndex]

fourthIndex -= 1

while fourthIndex > thirdIndex -1 and

num[fourthIndex] == num[fourthIndex+1]:

fourthIndex -= 1

else:

# Skip the duplicate numbers as num[thirdIndex]

thirdIndex += 1

while thirdIndex < fourthIndex + 1 and

num[thirdIndex] == num[thirdIndex-1]:

thirdIndex += 1

# Skip the duplicate numbers as num[secondIndex]

secondIndex += 1

while secondIndex < len(num)-1 and

num[secondIndex] == num[secondIndex-1]:

secondIndex += 1

# Skip the duplicate numbers as num[firstIndex]

firstIndex += 1

while firstIndex < len(num) - 2 and

num[firstIndex] == num[firstIndex-1]:

firstIndex += 1

return result

Solution to Nailing-Planks by codility

8 Apr

Question: https://codility.com/demo/take-sample-test/nailing_planks Question Name: Nailing Planks or NailingPlanks This question is designed to be solved with binary search method (BUT there is a better solution! It is updated at the end of this post.). And the binary solution is as … Read More »

Solution to Min-Max-Division by codility

6 Apr

Question: https://codility.com/demo/take-sample-test/min_max_division Question Name: Min-Max-Division or MinMaxDivision Logically, it seems to be similar with the boron2013 (Flags) challenge by Codility. And the following is my Python solution. UPDATE – 2014/09/19: thanks to Martin Kysel. The function signature is changed to: … Read More »

Solution to Letter Combinations of a Phone Number by LeetCode

5 Apr

Question: http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/ Question Name: Letter Combinations of a Phone Number

class Solution:

# @return a list of strings, [s1, s2]

def letterCombinations(self, digits):

# Mapping table for translating number to letters

num2letter = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno",

"7":"pqrs", "8":"tuv", "9":"wxyz"}

# The result for an empty string is an empty string.

if len(digits) == 0: return [""]

# We are only handling numbers from 2 to 9.

if not digits[0] in num2letter: raise LookupError("Unacceptable input.")

# Terminate case for recursion

if len(digits) == 1: return [i for i in num2letter[digits[0]]]

# The strings for the current digit.

temp = [i for i in num2letter[digits[0]]]

result = []

# Recursion case. Append the recursion result to each string for current digit.

for tail in self.letterCombinations(digits[1:]):

result.extend([i+tail for i in temp])

return result

Solution to 3Sum Closest by LeetCode

5 Apr

Question: http://oj.leetcode.com/problems/3sum-closest/ Question Name: 3Sum Closest

class Solution:

# @return an integer

def threeSumClosest(self, num, target):

result = 0xFFFFFFFF # Initially set a impossible large number

resultDif = 0xFFFFFFFF # Initially set a impossible large number

num.sort()

i = 0 # For the first item

while i < len(num) - 2:

j = i + 1 # For the middle item

k = len(num) - 1 # For the last item

while j < k:

temp = num[i]+ num[j]+num[k]

if temp == target:

# Not possible to be closer

return temp

elif temp< target:

if target - temp < resultDif:

# Find a closer combination

resultDif = target -temp

result = temp

# Skip duplicate num[j-1]

j += 1

while j < k+1 and num[j] == num[j-1]: j += 1

else:

if temp - target < resultDif:

# Find a closer combination

resultDif = temp - target

result = temp

# Skip duplicate num[k+1]

k -= 1

while k > j-1 and num[k] == num[k+1]: k -= 1

# Skip duplicate num[i-1]

i += 1

while i < len(num)-1 and num[i] == num[i-1]: i += 1

return result

Solution to Longest Common Prefix by LeetCode

5 Apr

Question: http://oj.leetcode.com/problems/longest-common-prefix/ Question Name: Longest Common Prefix

class Solution:

# @return a string

def longestCommonPrefix(self, strs):

if len(strs) == 0: return ""

longest = len(strs[0]) # use the first string as the base

for string in strs[1:]:

# Compute the new longest common prefix of current string

# and longest common prefix so far from previous rounds

index = 0

while index < len(string) and index < longest and

strs[0][index] == string[index]:

index += 1

longest = min(index, longest)

return strs[0][:longest]

Solution to Integer to Roman by LeetCode

31 Mar

Question: http://oj.leetcode.com/problems/integer-to-roman/ Question Name: Integer to Roman

class Solution:

# @return a string

def intToRoman(self, num):

result = ""

# In the first round, we will generate the Romen numbers without

# considering the issue about four repeating characters.

transTable = {1:"I", 5:"V", 10:"X", 50:"L", 100:"C", 500:"D", 1000:"M"}

for trans in sorted(transTable.keys())[::-1]:

while num != 0 and num >= trans:

num -= trans

result += transTable[trans]

if num == 0: break

# In the second round, we will replace the quanlified four-repeating-

# character with the subtractive notation

simplifyTable = {"DCCCC":"CM", "CCCC":"CD", "LXXXX":"XC", "XXXX":"XL",

"VIIII":"IX", "IIII":"IV"}

# Consider the largest four repeating characters first.

simplifyContent = ["DCCCC", "CCCC", "LXXXX", "XXXX", "VIIII", "IIII"]

for item in simplifyContent:

if item in result: result = result.replace(item, simplifyTable[item])

return result

Solution to Roman to Integer by LeetCode

31 Mar

Question: http://oj.leetcode.com/problems/roman-to-integer/ Question Name: Roman to Integer

class Solution:

# @return an integer

def romanToInt(self, s):

transSingleTable = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}

transDoubleTable = {"IV":4, "IX":9, "XL":40, "XC":90, "CD":400, "CM":900 }

result = 0

index = 0

roman = s.upper()

while index < len(s):

if index < len(s)-1 and roman[index:index+2] in transDoubleTable:

# Two-letter numeral

result += transDoubleTable[roman[index:index+2]]

index += 2

elif roman[index] in transSingleTable:

# One-letter numeral

result += transSingleTable[roman[index]]

index += 1

else:

# Unexpected input

raise LookupError("Invalid Roman numeral!")

return result

Solution to Regular Expression Matching by LeetCode

30 Mar

Question: http://oj.leetcode.com/problems/regular-expression-matching/ Question Name: Regular Expression Matching Year ago, at the first time I read the book “Beautiful Code”, I was completely shocked by the amazingly beautiful regular expression matcher. It is elegant, simple, and really beautiful. As that book … Read More »

Solution to Container With Most Water by LeetCode

28 Mar

Question: http://oj.leetcode.com/problems/container-with-most-water/ Question Name: Container With Most Water

class Solution:

# @return an integer

def maxArea(self, height):

area = 0

left, right = 0, len(height)-1

# Without loss of generality, we consider the left is lower than right.

# Our goal is to find out the container with most water. Equally, we

# are finding out the slice, whose borders form a container with most

# water. So a brute force method is: examine all the slices between

# current left and current right.

# And all the slices between left and right = ( all the slices

# between left+1 and right) + (all the slices beginning with left).

# Among all the slices beginning with left, the current [left, right] has

# the maximum water: height_of_left * (right - left). For any other slice,

# begin with left, the width (right - left) would be less. And the height

# would be equal or less.

# As a result, for all the slices beginning with left, we just need to

# consider the current one [left, right].

while left < right:

area = max(area, (right-left)*min(height[left], height[right]))

if height[left] < height[right]:

left += 1

else:

right -= 1

return area

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