C code. C code run. Run code run… please!
Question: https://codility.com/programmers/task/odd_occurrences_in_array Question Name: Odd-Occurrences-In-Array or OddOccurrencesInArray This question is completely the same as the Perm-Missing-Elem by codility. The comment from Kim is very helpful.
1 2 3 4 5 | def solution(A): result = 0 for number in A: result ^= number return result |
Question: https://codility.com/demo/take-sample-test/number_solitaire/ Question Name: Number-Solitaire or NumberSolitaire The key point is: to achieve the position i, we can only come from the positions i-6, i-5, i-4, i-3, i-2, and i-1.
1 2 3 4 5 6 7 8 9 10 11 | def solution(A): # The first six items are used for padding only, so that we can have # a unified for loop, no matter how many squares are there in input. # The first item is never accessed. max_so_far = [A[0]] * (len(A) + 6) for index in xrange(1, len(A)): # Because we have a fixed length of window as 6, the time # complexity of max(max_so_far[index : index + 6]) is O(1). max_so_far[index + 6] = max(max_so_far[index : index + 6]) + A[index] return max_so_far[-1] |
Question: https://codility.com/demo/take-sample-test/max_nonoverlapping_segments/ Question Name: Max-Nonoverlapping-Segments or MaxNonoverlappingSegments It is an easy solution, but a bit hard to prove it. Let’s scan from left to right, according to the end points. Since the input has already been sorted with the end … Read More »
Question: https://leetcode.com/problems/reverse-linked-list/ Question Name: Reverse Linked List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # 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] |
Question: https://leetcode.com/problems/isomorphic-strings/ Question Name: Isomorphic Strings The key point is to avoid 2+ characters map to the same character.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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 |
Question: https://leetcode.com/problems/count-primes/ Question Name: Count Primes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 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 |
Question: https://leetcode.com/problems/remove-linked-list-elements/ Question Name: Remove Linked List Elements
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | # 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 |
Question: https://leetcode.com/problems/happy-number/ Question Name: Happy Number
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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 |
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 »
Question: https://leetcode.com/problems/number-of-islands/ Question Name: Number of Islands A variant of weighted quick union.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | 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() |