Python – Page 20 – Code Says

Solution to Reverse Nodes in k-Group by LeetCode

24 Apr

Question: http://oj.leetcode.com/problems/reverse-nodes-in-k-group/ Question Name: Reverse Nodes in k-Group

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param pre, a ListNode

# @param current, a ListNode

# @param k, an integer

# @return a ListNode

def _reverseNextK(self, pre, current, k):

# Not enough nodes to reverse

if current == None: return None, None

# Last node to reverse

if k == 1:

nextNode = current.next

current.next = pre

return current, nextNode

# Recursively reverse the remaining nodes

newHead, nextHead = self._reverseNextK(current, current.next, k-1)

if newHead == None:

# Not enough nodes to reverse

return None, None

else:

# Reversing

current.next = pre

return newHead, nextHead

# @param head, a ListNode

# @param k, an integer

# @return a ListNode

def reverseKGroup(self, head, k):

newHead, nextHead = self._reverseNextK(None, head, k)

if newHead == None: return head # Not enough nodes to reverse

else: result = newHead # Record the new head node

preTail = head

# As long as there are enough nodes to reverse, do it.

while nextHead != None:

currentNode = nextHead

# Reverse the nodes inside the next K-group

newHead, nextHead = self._reverseNextK(None, currentNode, k)

if newHead != None: preTail.next = newHead # Reversed

else: preTail.next = currentNode # Not reversed

preTail = currentNode

return result

Solution to Min-Abs-Sum-Of-Two by codility

21 Apr

Question: https://codility.com/demo/take-sample-test/min_abs_sum_of_two Question Name: Min-Abs-Sum-Of-Two or MinAbsSumOfTwo There are two O(nlogn) solutions for this question. Both solutions have the same overall time complexity and space complexity. And both solutions need to sort the array in non-decreasing order first. The first … Read More »

Solution to Count-Distinct-Slices by codility

17 Apr

Question: https://codility.com/demo/take-sample-test/count_distinct_slices Question Name: Count-Distinct-Slices or CountDistinctSlices

def solution(M, A):

accessed = [-1] * (M + 1) # -1: not accessed before

# Non-negative: the previous occurrence position

front, back = 0, 0

result = 0

for front in xrange(len(A)):

if accessed[A[front]] == -1:

# Met with a new unique item

accessed[A[front]] = front

else:

# Met with a duplicate item

# Compute the number of distinct slices between newBack-1 and back

# position.

newBack = accessed[A[front]] + 1

result += (newBack - back) * (front - back + front - newBack + 1) / 2

if result >= 1000000000: return 1000000000

# Restore and set the accessed array

for index in xrange(back, newBack):

accessed[A[index]] = -1

accessed[A[front]] = front

back = newBack

# Process the last slices

result += (front - back + 1) * (front - back + 2) / 2

return min(result, 1000000000)

Solution to Count-Triangles by codility

17 Apr

Question: https://codility.com/demo/take-sample-test/count_triangles Question Name: Count-Triangles or CountTriangles This problem is nearly the same as the exercise in presentation of lesson 13. Update on May 24, 2014: Thanks to @Adam. Fix a bug, which lower the performance.

def solution(A):

n = len(A)

result = 0

A.sort()

for first in xrange(n-2):

third = first + 2

for second in xrange(first+1, n-1):

while third < n and A[first] + A[second] > A[third]:

third += 1

result += third - second - 1

return result

Solution to Count-Div by codility

16 Apr

Question: https://codility.com/demo/take-sample-test/count_div Question Name: Count-Div or CountDiv It is completely a mathematic question. Not qualified for a 2-star problem.

def solution(A, B, K):

if A % K == 0: return (B - A) // K + 1

else: return (B - (A - A % K )) // K

Solution to Swap Nodes in Pairs by LeetCode

11 Apr

Question: http://oj.leetcode.com/problems/swap-nodes-in-pairs/ Question Name: Swap Nodes in Pairs

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param a ListNode

# @return a ListNode

def swapPairs(self, head):

# If it is empty list or one-element list, no need to process

if head == None or head.next == None:

return head

# Record the head node of the new list

newHead = head.next

# We are going to travel the list with two nodes each time.

current = head

previous = None

while current != None and current.next != None:

# If there is, we need to adjust the previous node so

# that it links to the adjusted remaining list in a

# right way.

if previous != None:

previous.next = current.next

previous = current

# Adjust the current two nodes

temp = current.next.next

current.next.next = current

current.next = temp

# Move to the next round

current = current.next

return newHead

Solution to Merge k Sorted Lists by LeetCode

11 Apr

Question: http://oj.leetcode.com/problems/merge-k-sorted-lists/ Question Name: Merge k Sorted Lists

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

# Definition and implement of a min heap

class _Heap:

# Make it 1-based index

heap = [None]

def __init__(self):

return

def size(self):

return len(self.heap) - 1

def _swin(self, K):

while (K > 1 and self.heap[K//2].val > self.heap[K].val):

self.heap[K//2], self.heap[K] = self.heap[K], self.heap[K//2]

K = K//2

return

def _sink(self, K):

N = len(self.heap)

while 2 * K < N:

tempIndex = 2 * K

if tempIndex + 1 < N and self.heap[tempIndex + 1].val < self.heap[tempIndex].val:

tempIndex += 1

if self.heap[K].val <= self.heap[tempIndex].val:

break

self.heap[tempIndex], self.heap[K] = self.heap[K], self.heap[tempIndex]

K = tempIndex

return

def add(self, item):

self.heap.append(item)

self._swin(len(self.heap)-1)

return

def delMin(self):

if len(self.heap) == 2: return self.heap.pop()

self.heap[1], self.heap[-1] = self.heap[-1], self.heap[1]

temp = self.heap.pop()

self._sink(1)

return temp

class Solution:

# @param a list of ListNode

# @return a ListNode

def mergeKLists(self, lists):

# Handle the special case: empty input

if len(lists) == 0: return None

# Initial our heap with the first node in each list

heap = _Heap()

for singleList in lists:

if singleList != None:

heap.add(singleList)

# Actually empty input

if heap.size() == 0: return None

# Build the head of the result list

head = heap.delMin()

if head.next != None: heap.add(head.next)

# Merge the remaining part of all the lists

current = head

while heap.size() != 0:

current.next = heap.delMin()

current = current.next

if current.next != None:

heap.add(current.next)

return head

Solution to Generate Parentheses by LeetCode

11 Apr

Question: http://oj.leetcode.com/problems/generate-parentheses/ Question Name: Generate Parentheses A good question to show the good side of recursion. Memorization could improve the performance.

class Solution:

# @param two integer: the number of remaining "(" and ")"

# @return a list of string

def _generateParenthesis(self, n, m):

if n == 0: return [")"*m]

elif n == m: return ["("+i for i in self._generateParenthesis(n-1, m)]

else: return ["("+i for i in self._generateParenthesis(n-1, m)] +

[")"+i for i in self._generateParenthesis(n, m-1)]

# @param an integer

# @return a list of string

def generateParenthesis(self, n):

return self._generateParenthesis(n, n)

Solution to Valid Parentheses by LeetCode

11 Apr

Question: http://oj.leetcode.com/problems/valid-parentheses/ Question Name: Valid Parentheses

class Solution:

# @return a boolean

def isValid(self, s):

stack = []

matchingTable = {"(":")", "[":"]", "{":"}"}

for letter in s:

if letter == "(" or letter == "[" or letter == "{":

stack.append(letter)

elif letter == ")" or letter == "]" or letter == "}":

if len(stack) == 0 or letter != matchingTable[stack.pop()]:

# Unmatched parentheses found

return False

else:

# Only valid parentheses.

pass

return len(stack) == 0

Solution to Remove Nth Node From End of List by LeetCode

11 Apr

Question: http://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/ Question Name: Remove Nth Node From End of List

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @return a ListNode

def removeNthFromEnd(self, head, n):

former = head

latter = head

# Skip n-1 nodes with latter

for _ in xrange(n-1): latter = latter.next

if latter.next == None:

# There are totally n nodes. And we are

# removing the head node.

head = head.next

else:

# There are more than n nodes.

latter = latter.next # Totally skip n nodes

# Find the previous node to the nth node from end

while latter.next != None:

former = former.next

latter = latter.next

# Remove the nth node from end

former.next = former.next.next

return head

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