LeetCode – Page 19

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 »

Solution to ZigZag Conversion by LeetCode

27 Mar

Question: http://oj.leetcode.com/problems/zigzag-conversion/ Question Name: ZigZag Conversion

class Solution:

# @return a string

def convert(self, s, nRows):

assert nRows > 0 # Must be a non-negative number

# Handle a specific case, nRows be 1.

# In such case, the input and output should be the same.

if nRows == 1: return s

# cache[i] stores the characters in the (i+1)th row,

# in their original order.

cache = [[] for _ in xrange(nRows)]

position = 0 # The index of current row in cache.

direction = +1 # The direction to find the next row.

for element in s:

cache[position].append(element)

# If we are in the first row, we should find the next

# row in an increasing order

if position == 0: direction = +1

# If we are in the last row, we should find the next

# row in a decreasing order

elif position == nRows - 1: direction = -1

position += direction

return "".join(["".join(row) for row in cache])

Solution to Longest Palindromic Substring by LeetCode

27 Mar

Question: http://oj.leetcode.com/problems/longest-palindromic-substring/ Question Name: Longest Palindromic Substring Completely the same basis as this problem by Codility.

class Solution:

# @return a string

def longestPalindrome(self, s):

center, right = 0,1

newS = "#"+"#".join(s)+"#"

palHalfLenCenteringHere = [1] * len(newS)

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

assert index <= right

if index < right and index + palHalfLenCenteringHere[2*center-index] < right:

# No way to extend the right. Thus the center is not changed.

palHalfLenCenteringHere[index] = palHalfLenCenteringHere[2*center-index]

else:

# We MIGHT extend the right. And we DO change the center here.

# IF we did NOT extend the right, the new center and old one have completely

# the SAME effect on the next steps/rounds.

center = index

if index < right:

# Use some pre-computed information

palHalfLenCenteringHere[index] = right - center

else:

# Actually scanning from scratch

palHalfLenCenteringHere[index] = 1

right += 1

# Try to extend the right

while right < len(newS) and 2*center-right >= 0 and

newS[right] == newS[2*center-right]:

right += 1

palHalfLenCenteringHere[index] += 1

# Find the longest palindromic substring

center, halfLen = max(enumerate(palHalfLenCenteringHere), key=lambda x: x[1])

result = newS[center - halfLen + 1: center + halfLen]

return result.replace("#", "")

Solution to Add Two Numbers by LeetCode

26 Mar

Question: http://oj.leetcode.com/problems/add-two-numbers/ Question Name: Add Two Numbers

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @return a ListNode

def addTwoNumbers(self, l1, l2):

return self._addTwoSingleNumbers(l1, l2, 0)

def _addTwoSingleNumbers(self, l1, l2, carry):

value = carry

# Make sure, either both l1 and l2 are None,

# or l2 is not None.

# To simplify the if-elif block

if l2 == None: l1, l2 = l2, l1

if l1 == None and l2 == None:

if value == 0: return None # No need to create a new node

else: return ListNode(value) # Create the last node

elif l1 == None:

# l2 is not None

value += l2.val

tempNode = ListNode(value % 10)

tempNode.next = self._addTwoSingleNumbers(None, l2.next, value/10)

return tempNode

else:

# Both are not None

value += l1.val + l2.val

tempNode = ListNode(value % 10)

tempNode.next = self._addTwoSingleNumbers(l1.next, l2.next, value/10)

return tempNode

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