Python – Page 22 – Code Says

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

Solution to Longest Substring Without Repeating Characters by LeetCode

26 Mar

Question: http://oj.leetcode.com/problems/longest-substring-without-repeating-characters/ Question Name: Longest Substring Without Repeating Characters This is a typical dynamic programming problem.

class Solution:

# @return an integer

def lengthOfLongestSubstring(self, s):

# Handle the special case: empty string

if len(s) == 0: return 0

lastAppPos = {s[0]:0} # Last appear position of alphabet

longestEndingHere = [1] * len(s) # Longest substring ending here

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

lastPos = lastAppPos.get(s[index], -1)

if lastPos < index - longestEndingHere[index-1]:

# The substring, ending in the previous position, could be

# extended WITHOUT chop.

longestEndingHere[index] = longestEndingHere[index-1] + 1

else:

# The substring, ending in the previous position, have to

# be chopped and THEN extended.

longestEndingHere[index] = index - lastPos

lastAppPos[s[index]] = index # Update the last appear position

return max(longestEndingHere)

Solution to Median of Two Sorted Arrays by LeetCode

25 Mar

Question: http://oj.leetcode.com/problems/median-of-two-sorted-arrays/ Question Name: Median of Two Sorted Arrays This question is quite similar with the nu2011 (DoubleMedian) by Codility. Both of them are the variants of the question: find the kth smallest element in two sorted array. BTW: LeetCode’ … Read More »

Solution to Two-Sum by LeetCode

24 Mar

Question: http://oj.leetcode.com/problems/two-sum/ Question Name: Two Sum Futher reading: http://stackoverflow.com/questions/8334981/find-pair-of-numbers-in-array-that-add-to-given-sum

class Solution:

# @return a tuple, (index1, index2)

def twoSum(self, num, target):

index1, index2, total = 0, len(num)-1, 0

sortedNum = sorted(enumerate(num), key=lambda x:x[1])

while index1 != index2:

total = sortedNum[index1][1] + sortedNum[index2][1]

if total == target:

if sortedNum[index1][0] > sortedNum[index2][0] :

return (sortedNum[index2][0]+1, sortedNum[index1][0]+1)

else:

return (sortedNum[index1][0]+1, sortedNum[index2][0]+1)

elif total > target:

index2 -= 1

else:

index1 += 1

return (-1, -1)

Solution to Distinct by codility

18 Mar

Question: https://codility.com/demo/take-sample-test/distinct Question Name: Distinct In this question, the expected worst-case time complexity is O(N*log(N)). Thus the designed, or says official, solution would be sort the input and travel them. This solution is practically good. And it is shown as … 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...