LeetCode – Page 2

Solution to Implement Trie (Prefix Tree) by LeetCode

1 Jan

Question: https://leetcode.com/problems/implement-trie-prefix-tree/ Question Name: Implement Trie (Prefix Tree) Not a full implementation. The delete function is not required.

class TrieNode(object):

def __init__(self):

"""

Initialize your data structure here.

"""

self.isWord = False

self.sons = {}

class Trie(object):

def __init__(self):

self.root = TrieNode()

def insert(self, word):

"""

Inserts a word into the trie.

:type word: str

:rtype: void

"""

current = self.root

for letter in word:

if letter not in current.sons:

current.sons[letter] = TrieNode()

current = current.sons[letter]

current.isWord = True

def search(self, word):

"""

Returns if the word is in the trie.

:type word: str

:rtype: bool

"""

current = self.root

for letter in word:

if letter not in current.sons:

return False

else:

current = current.sons[letter]

return current.isWord

def startsWith(self, prefix):

"""

Returns if there is any word in the trie

that starts with the given prefix.

:type prefix: str

:rtype: bool

"""

current = self.root

for letter in prefix:

if letter not in current.sons:

return False

else:

current = current.sons[letter]

return True

# Your Trie object will be instantiated and called as such:

# trie = Trie()

# trie.insert("somestring")

# trie.search("key")

Solution to Course Schedule by LeetCode

22 Dec

Question: https://leetcode.com/problems/course-schedule/ Question Name: Course Schedule

class Solution(object):

def _hasLoop(self, courseID, adjacencySet, reachableNodes, currentPath):

"""

:type numCourses: int

:type adjacencySet: List[set(int)]

:type: reachableNodes: mutable, set(int)

:type: current_path: mutalbe, set(int)

:rtype: bool

"""

if courseID in currentPath:

return True

currentPath.add(courseID)

reachableNodes.add(courseID)

for prerequisite in adjacencySet[courseID]:

if self._hasLoop(prerequisite, adjacencySet, reachableNodes, currentPath):

return True

currentPath.remove(courseID)

return False

def _buildAdjacencySet(self, numCourses, prerequisites):

"""

:type numCourses: int

:type prerequisites: List[List[int]]

:rtype: List[set(int)]

"""

adj_set = [set() for _ in xrange(numCourses)]

for prerequisite in prerequisites:

adj_set[prerequisite[0]].add(prerequisite[1])

return adj_set

def canFinish(self, numCourses, prerequisites):

"""

:type numCourses: int

:type prerequisites: List[List[int]]

:rtype: bool

"""

# Find out the courses, which are not prerequisite of others.

is_prerequisite = [False for _ in xrange(numCourses)]

for prerequisite in prerequisites:

is_prerequisite[prerequisite[1]] = True

adjacency_set = self._buildAdjacencySet(numCourses, prerequisites)

is_doable = [False for _ in xrange(numCourses)]

for courseID in xrange(numCourses):

if is_prerequisite[courseID]:

continue

# Check whether it is possible to finish this course.

# If it is, all its direct/indirect prerequisites are also doable.

reachable_nodes = set()

current_path = set()

if self._hasLoop(courseID, adjacency_set, reachable_nodes, current_path):

return False

for courseID in reachable_nodes:

is_doable[courseID] = True

return all(is_doable)

Solution to Reverse Linked List by LeetCode

3 Sep

Question: https://leetcode.com/problems/reverse-linked-list/ Question Name: Reverse Linked List

# Definition for singly-linked list.

# class ListNode(object):

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution(object):

def reverseList(self, head):

"""

:type head: ListNode

:rtype: ListNode

"""

if head == None:

return None

# Store the nodes from head to end.

stack = []

while head != None:

stack.append(head)

head = head.next

# Rebuild the list from end to head.

for index in xrange(len(stack)-1, 0, -1):

stack[index].next = stack[index-1]

stack[0].next = None

return stack[-1]

Solution to Isomorphic Strings by LeetCode

1 Sep

Question: https://leetcode.com/problems/isomorphic-strings/ Question Name: Isomorphic Strings The key point is to avoid 2+ characters map to the same character.

class Solution(object):

def isIsomorphic(self, s, t):

"""

:type s: str

:type t: str

:rtype: bool

"""

mapping = {}

for index in xrange(len(s)):

if not s[index] in mapping:

# New mapping is found.

mapping[s[index]] = t[index]

elif mapping[s[index]] != t[index]:

# No 2+ characters may map to the same character.

return False

# Make sure that no 2+ characters may map to the same character.

if len(set(mapping.keys())) != len(set(mapping.values())):

return False

return True

Solution to Count Primes by LeetCode

29 Aug

Question: https://leetcode.com/problems/count-primes/ Question Name: Count Primes

class Solution(object):

def countPrimes(self, n):

"""

:type n: int

:rtype: int

"""

# The first and second elements are never used. Otherwise,

# primesRecord[i] is for interger i.

primesRecord = [False] * n

primesCount = 0

for number in xrange(2, n):

if primesRecord[number] == False:

# Cannot be divided by any smaller integer. This is

# a prime nubmer.

primesCount += 1

current = number

while current < n:

# This is a composite number.

primesRecord[current] = True

current += number

return primesCount

Solution to Remove Linked List Elements by LeetCode

29 Aug

Question: https://leetcode.com/problems/remove-linked-list-elements/ Question Name: Remove Linked List Elements

# Definition for singly-linked list.

# class ListNode(object):

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution(object):

def removeElements(self, head, val):

"""

:type head: ListNode

:type val: int

:rtype: ListNode

"""

# Find the first non-val node as the new head node.

newHead = head

while newHead != None and newHead.val == val:

newHead = newHead.next

if newHead == None: return None

previous = newHead

current = previous.next

while current != None:

if current.val == val:

# Skip this node.

previous.next = current.next

current = current.next

else:

# Move to the next node.

previous = current

current = current.next

return newHead

Solution to Happy Number by LeetCode

29 Aug

Question: https://leetcode.com/problems/happy-number/ Question Name: Happy Number

class Solution(object):

def _nextNumber(self, n):

"""

:type n: int

:rtype: bool

"""

result = 0

while n != 0:

result += (n % 10) **2

n /= 10

return result

def isHappy(self, n):

"""

:type n: int

:rtype: bool

"""

met = set()

while not n in met:

if n == 1: return True

met.add(n)

n = self._nextNumber(n)

return False

Solution to Bitwise AND of Numbers Range by LeetCode

23 Aug

Question: https://leetcode.com/problems/bitwise-and-of-numbers-range/ Question Name: Bitwise AND of Numbers Range A variant of number of 1 bits in an interger. For any non-zero interger 0b?????????1000 (? could be 1 or 0, and there are zero or one or more 0s after … Read More »

Solution to Number of Islands by LeetCode

31 Jul

Question: https://leetcode.com/problems/number-of-islands/ Question Name: Number of Islands A variant of weighted quick union.

class Islands:

''' This class is a variant of weighted quick union.

'''

# Reference: http://algs4.cs.princeton.edu/15uf/

# http://algs4.cs.princeton.edu/15uf/QuickUnionUF.java.html

parent_ = None

size_ = None

components_ = 0

def __init__(self, nodes_count):

# parent_[i] is the index of i(th) node's parent.

# If parent_[i] is -1, the i(th) node is

# either water

# or root of some tree.

self.parent_ = [-1] * nodes_count

# size_[i] is the size of the (sub)tree, whose root is the i(th) node.

# If size_[i] is 0, the i(th) node is not land.

self.size_ = [1] * nodes_count

# The number of islands.

self.components_ = 0

def _root(self, node):

''' Find the root node of the tree, which contains the given node.

'''

root = node

while self.parent_[root] != -1:

root = self.parent_[root]

return root

def count(self):

''' Return the number of trees in this forest, that is, the number

of islands.

'''

return self.components_

def union(self, node1, node2):

''' Connect the island with node1 and island with node2 into one

island.

'''

# Did not check whether the nodes are water or land. Caller should make

# sure the they are land.

root1 = self._root(node1)

root2 = self._root(node2)

# The nodes are in one tree.

if root1 == root2: return

size1 = self.size_[root1]

size2 = self.size_[root2]

if size1 <= size2:

# Attach the tree with ndoe1 to the tree with node2

self.parent_[root1] = root2

self.size_[root2] += self.size_[root1]

else:

# Attach the tree with ndoe2 to the tree with node1

self.parent_[root2] = root1

self.size_[root1] += self.size_[root2]

self.components_ -= 1

return

def add_land(self, node):

''' Convert this cell from water to land.

'''

self.parent_[node] = -1

self.size_[node] = 1

self.components_ += 1

class Solution:

# @param {character[][]} grid

# @return {integer}

def numIslands(self, grid):

if len(grid) == 0 or len(grid[0]) == 0: return 0

geo = Islands(len(grid) * len(grid[0]))

# These two for loops could be combined to one for loop. However, we

# keep them separated for better understanding.

# Initialize each land cell.

for row in xrange(len(grid)):

for column in xrange(len(grid[0])):

if grid[row][column] == "1":

node_id = row * len(grid[0]) + column

geo.add_land(node_id)

# Combine all adjacent lands into an island.

for row in xrange(len(grid)):

for column in xrange(len(grid[0])):

if grid[row][column] == "0":

# This is a water cell.

continue

else:

# This is a land cell.

node1_id = row * len(grid[0]) + column

if row != len(grid) - 1 and grid[row + 1][column] == "1":

node2_id = (row + 1) * len(grid[0]) + column

geo.union(node1_id, node2_id)

if column != len(grid[0]) - 1 and grid[row][column + 1] == "1":

node2_id = row * len(grid[0]) + (column + 1)

geo.union(node1_id, node2_id)

return geo.count()

Solution to Binary Tree Right Side View by LeetCode

18 Jun

Question: https://leetcode.com/problems/binary-tree-right-side-view/ Question Name: Binary Tree Right Side View A variant of level order tree 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 {TreeNode} root

# @return {integer[]}

def rightSideView(self, root):

current_layer = [root] if root != None else []

result = []

while len(current_layer) != 0:

result.append(current_layer[-1].val)

next_layer = []

for node in current_layer:

if node.left != None: next_layer.append(node.left)

if node.right != None: next_layer.append(node.right)

current_layer = next_layer

return result

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