LeetCode – Page 6

Solution to Binary Tree Preorder Traversal by LeetCode

23 Jul

Question: https://oj.leetcode.com/problems/binary-tree-preorder-traversal/ Question Name: Binary Tree Preorder Traversal

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return a list of integers

def preorderTraversal(self, root):

# Empty tree

if root == None: return []

result = []

stack = [root]

while len(stack) != 0:

# Access the root firstly

current = stack.pop()

result.append(current.val)

# Then we are going to access its left son and right son.

if current.right != None: stack.append(current.right)

if current.left != None: stack.append(current.left)

return result

Solution to Reorder List by LeetCode

22 Jul

Question: https://oj.leetcode.com/problems/reorder-list/ Question Name: Reorder List

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @return nothing

def reorderList(self, head):

listInArray = []

# Store all the nodes in the list into an array.

current = head

while current != None:

listInArray.append(current)

current = current.next

# Check whether it's an empty list.

listLen = len(listInArray)

if listLen == 0: return

# Reorder the List as required

for index in xrange(listLen // 2):

listInArray[index].next = listInArray[listLen-1-index]

listInArray[listLen-1-index].next = listInArray[index+1]

# End the list

listInArray[listLen // 2].next = None

return

Solution to Linked List Cycle II by LeetCode

22 Jul

Question: https://oj.leetcode.com/problems/linked-list-cycle-ii/ Question Name: Linked List Cycle II Same as the problem in Cracking the Coding Interview.

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @return a boolean

def detectCycle(self, head):

if head == None: return None

slower = head # Move one step each time

quicker = head # Move two steps each time

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

slower = slower.next

quicker = quicker.next.next

# The slower and quicker meet with each other. There is a cycle.

if slower == quicker: break

else:

# quicker reach the end. Limited list never have cycle.

return None

# Both latter and former move one step in each round, until they meet.

# The meeting place is the entry point of cycle.

latter, former = head, quicker

while latter != former:

latter = latter.next

former = former.next

return former

Solution to Linked List Cycle by LeetCode

22 Jul

Question: https://oj.leetcode.com/problems/linked-list-cycle/ Question Name: Linked List Cycle Same as the problem in Cracking the Coding Interview.

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @return a boolean

def hasCycle(self, head):

if head == None: return False

slower = head # Move one step each time

quicker = head # Move two steps each time

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

slower = slower.next

quicker = quicker.next.next

if slower == quicker: return True

# quicker reach the end. Limited list never have cycle.

return False

Solution to Word Break II by LeetCode

22 Jul

Question: https://oj.leetcode.com/problems/word-break-ii/ Question Name: Word Break II

class Solution:

# @param s, a string

# @param dict, a set of string

# @return a boolean

def _isBreakable(self, s, dict):

''' Solve it with dynamic programming.

'''

couldBreak = [False] * len(s)

for breakAfterCurrent in xrange(len(s)):

if s[: breakAfterCurrent+1] in dict:

# The substring from beginning to here is in the dict.

# We can make a break between this position and its

# next position.

couldBreak[breakAfterCurrent] = True

continue

# Otherwise, we will try to check, whether this substring

# s[:breakAfterCurrent+1] could be composed by breakable

# head and a tail, which is in the dict.

for preBreak in xrange(breakAfterCurrent):

if couldBreak[preBreak] == False:

# The head is not breakable

continue

elif s[preBreak+1: breakAfterCurrent+1] not in dict:

# The tail is not in the dict.

continue

else:

# As long as we know it's breakable, no need to

# continue the search for current position.

couldBreak[breakAfterCurrent] = True

break

return couldBreak[-1]

# @param s, a string

# @param dict, a set of string

# @return a list of strings

def wordBreak(self, s, dict):

''' Solve it with dynamic programming.

'''

# First of all, use a much-less-time-consuming method to check

# whether the answer is an empty list.

# It is important to pass some unbreakable tests.

if not self._isBreakable(s, dict): return []

sLen = len(s)

couldBreak = [[] for _ in xrange(sLen)]

# There may be multiple candidates in dict, having the same length.

# So we are using set to find out the unique ones.

# This is an optimization. Without this, we can still pass all

# the tests by trying all lengths.

candidateLen = set([len(item) for item in dict])

for breakAfterCurrent in xrange(sLen):

if s[: breakAfterCurrent+1] in dict:

# The substring from beginning to here is in the dict.

# We can make a break between this position and its

# next position.

couldBreak[breakAfterCurrent].append([s[: breakAfterCurrent+1]])

# Otherwise, we will try to check, whether this substring

# s[:breakAfterCurrent+1] could be composed by breakable

# head and a tail, which is in the dict.

for preBreak in candidateLen:

preBreak = breakAfterCurrent - preBreak

if preBreak < 0:

# Not enough characters.

continue

elif couldBreak[preBreak] == []:

# The head is not breakable

continue

elif s[preBreak+1: breakAfterCurrent+1] not in dict:

# The tail is not in the dict.

continue

else:

combinations = [item +[s[preBreak+1: breakAfterCurrent+1]]

for item in couldBreak[preBreak]]

couldBreak[breakAfterCurrent].extend(combinations)

return [" ".join(combination) for combination in couldBreak[-1]]

Solution to Word Break by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/word-break/ Question Name: Word Break Similar with Palindrome Partitioning II by LeetCode. Dynamic programming is suitable here.

class Solution:

# @param s, a string

# @param dict, a set of string

# @return a boolean

def wordBreak(self, s, dict):

''' Solve it with dynamic programming.

'''

couldBreak = [False] * len(s)

for breakAfterCurrent in xrange(len(s)):

if s[: breakAfterCurrent+1] in dict:

# The substring from beginning to here is in the dict.

# We can make the substring with zero break.

couldBreak[breakAfterCurrent] = True

continue

# Otherwise, we will try to check, whether this substring

# s[:breakAfterCurrent+1] could be composed by a breakable

# head and a tail, which is in the dict.

for preBreak in xrange(breakAfterCurrent):

if couldBreak[preBreak] == False:

# The head is not breakable

continue

elif s[preBreak+1: breakAfterCurrent+1] not in dict:

# The tail is not in the dict.

continue

else:

# As long as we know it's breakable, no need to

# continue the search for current position.

couldBreak[breakAfterCurrent] = True

break

return couldBreak[-1]

Solution to Copy List with Random Pointer by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/copy-list-with-random-pointer/ Question Name: Copy List with Random Pointer Quite similar with the Clone Graph by LeetCode.

# Definition for singly-linked list with a random pointer.

# class RandomListNode:

# def __init__(self, x):

# self.label = x

# self.next = None

# self.random = None

class Solution:

# @param head, a RandomListNode

# @return a RandomListNode

def copyRandomList(self, head):

# Store the mapping between old nodes and new nodes

mapOldToNew ={None:None}

# Clone all the old nodes with only labels.

current = head

while current != None:

mapOldToNew[current] = RandomListNode(current.label)

current = current.next

# Assign the next and random of new cloned nodes.

current = head

while current != None:

mapOldToNew[current].next = mapOldToNew[current.next]

mapOldToNew[current].random = mapOldToNew[current.random]

current = current.next

# Return the cloned head

return mapOldToNew[head]

Solution to Single Number II by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/single-number-ii/ Question Name: Single Number II Follow Up: Every element appears N times except one for M time (N != M): If N > M: If N % M == 0: use dictionary to count the appearance; If N … Read More »

Solution to Single Number by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/single-number/ Question Name: Single Number

class Solution:

# @param A, a list of integer

# @return an integer

def singleNumber(self, A):

''' Basic knowledge for cryptography: XOR operation

'''

result = 0

for item in A: result ^= item

return result

Solution to Candy by LeetCode

18 Jul

Question: https://oj.leetcode.com/problems/candy/ Question Name: Candy

class Solution:

# @param ratings, a list of integer

# @return an integer

def candy(self, ratings):

sortedRatings = enumerate(ratings)

sortedRatings = sorted(sortedRatings, key = lambda x: x[1])

candyCount = [-1] * len(ratings)

# Lowest rating, First service.

for child in sortedRatings:

position = child[0]

# Each child must have at least one candy.

candyForThisChild = 1

# Children with a higher rating get more candies than their

# neighbors.

# Check its left neighbor, if exists.

if position != 0 and ratings[position-1] < ratings[position]:

candyForThisChild = max(candyForThisChild,

candyCount[position-1] + 1)

# Check its right neighbor, if exists.

if position != len(ratings)-1 and

ratings[position+1] < ratings[position]:

candyForThisChild = max(candyForThisChild,

candyCount[position+1] + 1)

candyCount[position] = candyForThisChild

return sum(candyCount)

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