Sheng – Page 28 – Code Says

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 »

Solution to helium2013 (Find-Three) by codility

17 Mar

Question: https://codility.com/demo/take-sample-test/find_three Question Name: helium2013 or Find-Three or FindThree For this question, we have two similar but different ways to solve it. The first solution uses the border array algorithm. And the other one is with the Z algorithm for … Read More »

Solution to Fib-Frog by codility

11 Mar

Question: https://codility.com/demo/take-sample-test/fib_frog Question Name: Fib-Frog or FibFrog To solve this question, we are using the Breadth First Search with pruning. For a game with N intermediate nodes, the count of Fibonacci numbers, to say CF, is proportional to log(N) [Wikipedia]. … Read More »

Solution to Ladder by codility

9 Mar

Question: https://codility.com/demo/take-sample-test/ladder Question Name: Ladder To solve this question, there are two key points. Firstly, for a given N rungs, the number of different ways of climbing is the (N+1)th element in the Fibonacci numbers. Naturally, we could get the … 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

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