LeetCode – Page 18

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

Solution to 4Sum by LeetCode

8 Apr

Quesion: http://oj.leetcode.com/problems/4sum/ Question Name: 4Sum or 4-sum The key point is to prune when further qualified combination is not possible.

class Solution:

# @return a list of lists of length 4, [[val1,val2,val3,val4]]

def fourSum(self, num, target):

result = []

num.sort()

firstIndex = 0

while firstIndex < len(num)-3:

secondIndex = firstIndex + 1

while secondIndex < len(num)-2:

thirdIndex = secondIndex + 1

fourthIndex = len(num) - 1

while thirdIndex < fourthIndex:

if num[firstIndex] + num[secondIndex] + num[thirdIndex]

+ num[thirdIndex] > target:

# Already too larger, not possible to find any qualified

# list afterwards

break

if num[firstIndex] + num[secondIndex] + num[fourthIndex]

+ num[fourthIndex] < target:

# Already too small, not possible to find any qualified

# list forwards

break

temp = num[firstIndex] + num[secondIndex] + num[thirdIndex]

+ num[fourthIndex]

if temp == target:

result.append([num[firstIndex], num[secondIndex],

num[thirdIndex], num[fourthIndex]])

# Skip the duplicate numbers as num[thirdIndex]

thirdIndex += 1

while thirdIndex < fourthIndex + 1 and

num[thirdIndex] == num[thirdIndex-1]:

thirdIndex += 1

# Skip the duplicate numbers as num[fourthIndex]

fourthIndex -= 1

while fourthIndex > thirdIndex -1 and

num[fourthIndex] == num[fourthIndex+1]:

fourthIndex -= 1

elif temp > target:

# Skip the duplicate numbers as num[fourthIndex]

fourthIndex -= 1

while fourthIndex > thirdIndex -1 and

num[fourthIndex] == num[fourthIndex+1]:

fourthIndex -= 1

else:

# Skip the duplicate numbers as num[thirdIndex]

thirdIndex += 1

while thirdIndex < fourthIndex + 1 and

num[thirdIndex] == num[thirdIndex-1]:

thirdIndex += 1

# Skip the duplicate numbers as num[secondIndex]

secondIndex += 1

while secondIndex < len(num)-1 and

num[secondIndex] == num[secondIndex-1]:

secondIndex += 1

# Skip the duplicate numbers as num[firstIndex]

firstIndex += 1

while firstIndex < len(num) - 2 and

num[firstIndex] == num[firstIndex-1]:

firstIndex += 1

return result

Solution to Letter Combinations of a Phone Number by LeetCode

5 Apr

Question: http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/ Question Name: Letter Combinations of a Phone Number

class Solution:

# @return a list of strings, [s1, s2]

def letterCombinations(self, digits):

# Mapping table for translating number to letters

num2letter = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno",

"7":"pqrs", "8":"tuv", "9":"wxyz"}

# The result for an empty string is an empty string.

if len(digits) == 0: return [""]

# We are only handling numbers from 2 to 9.

if not digits[0] in num2letter: raise LookupError("Unacceptable input.")

# Terminate case for recursion

if len(digits) == 1: return [i for i in num2letter[digits[0]]]

# The strings for the current digit.

temp = [i for i in num2letter[digits[0]]]

result = []

# Recursion case. Append the recursion result to each string for current digit.

for tail in self.letterCombinations(digits[1:]):

result.extend([i+tail for i in temp])

return result

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]

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