Sheng – Page 27 – Code Says

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 3Sum by LeetCode

4 Apr

Question: http://oj.leetcode.com/problems/3sum/ Question Name: 3Sum Classic question. For more information, you could read the Wikipedia.

class Solution:

# @return num[i]list of lists of length 3, [[val1,val2,val3]]

def threeSum(self, num):

num.sort()

result = []

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:

if num[i]+ num[j] + num[j] > 0 or num[i]+ num[k]+ num[k]< 0:

# num[k] >= any num[j], num[j] <= any num[k]

# Impossible to find a answer in the future

break

if num[i]+ num[j]+num[k]== 0:

# Because the num is sorted, so the num[i] <= num[j] <= num[k]

# And in every round, i or j/k is different from the previous

# round. Therefore, the answer [num[i], num[j], num[k]] is new

# and unique for the result set.

result.append([num[i], num[j], num[k]])

# Skip duplicate num[j-1] and num[k+1]

j += 1

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

k -= 1

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

elif num[i] + num[j]+ num[k]< 0:

# Skip duplicate num[j-1]

j += 1

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

else:

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

Solution to Palindrome Number by LeetCode

27 Mar

Question: http://oj.leetcode.com/problems/palindrome-number/ Question Name: Palindrome Number

class Solution:

# @return a boolean

def _getDigits(self,x):

# Get the number of digits in a non-negative number

result = 1

while x / 10 != 0:

result += 1

x /= 10

return result

def _isPalindromeHelper(self, x, high, low):

if high <= low:

return True

elif (x % 10**high) / 10**(high-1) == (x % 10**low) / 10**(low-1):

return self._isPalindromeHelper(x, high-1, low+1)

else:

# The digits in high position and low position are different

return False

def isPalindrome(self, x):

if x < 0: return False # All negative numbers are not palindrome

else: return self._isPalindromeHelper(x, self._getDigits(x), 1)

Solution to String to Integer (atoi) by LeetCode

27 Mar

Question: http://oj.leetcode.com/problems/string-to-integer-atoi/ Question Name: String to Integer (atoi)

class Solution:

# @return an integer

def atoi(self, str):

INT_MAX, INT_MIN = 2147483647, -2147483648

index = 0

result = 0

sign = 1 # Default we are processing a non-negative number

if len(str) == 0: return 0 # The result for empty string is 0.

while str[index].isspace(): index += 1 # Discard whitespace

if str[index] == "-": sign = -1

if str[index] in "-+": index += 1 # Discard sign char

while index < len(str) and str[index].isdigit():

result = result * 10 + (ord(str[index]) - ord("0")) * sign

index += 1

# Handle overflow. Because Python could handle the large

# integer, this code works well. If with C/C++, we should use

# another method. For example, with non-negative number, the

# test condition for overflow would be:

# if( INT_MAX / 10 < result || INT_MAX - result * 10 <

# (ord(str[index]) - ord("0")) )

if sign == 1 and result >= INT_MAX: return INT_MAX

elif sign == -1 and result <= INT_MIN: return INT_MIN

return result

Solution to Reverse Integer by LeetCode

27 Mar

Question: http://oj.leetcode.com/problems/reverse-integer/ Question Name: Reverse Integer Python is an overwhelmingly excellent choice to solve this question, right? Firstly, this is a non-recursive solution:

class Solution:

# @return an integer

def reverse(self, x):

if x < 0: return int(str(x)[1:][::-1])*-1

else: return int(str(x)[::-1])

We also provide a recursive solution as following:

class Solution:

# @return an integer

def _reverse_helper(self, x):

if -10 < x < 10:

return x, 1

else:

rest, digits = self._reverse_helper(x / 10)

return x % 10 * (10 ** digits) + rest, digits + 1

def reverse(self, x):

if x < 0: return self._reverse_helper(-x)[0] * -1

else: return self._reverse_helper(x)[0]

UPDATE: challenge updated to test the overflow … Read More »

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