• Status: 2


    Data structures

    Tree

    def preorder(tree):
        if tree:
            print(tree.getRootVal())
            preorder(tree.getLeftChild())
            preorder(tree.getRightChild())
            
    def postorder(tree):
        if tree != None:
            postorder(tree.getLeftChild())
            postorder(tree.getRightChild())
            print(tree.getRootVal())
            
    def inorder(tree):
      if tree != None:
          inorder(tree.getLeftChild())
          print(tree.getRootVal())
          inorder(tree.getRightChild())
    

    Binary Search Tree (BST)

    https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

    # Python program to demonstrate delete operation
    # in binary search tree
     
    # A Binary Tree Node
    class Node:
     
        # Constructor to create a new node
        def __init__(self, key):
            self.key = key 
            self.left = None
            self.right = None
     
     
    # A utility function to do inorder traversal of BST
    def inorder(root):
        if root is not None:
            inorder(root.left)
            print root.key,
            inorder(root.right)
     
     
    # A utility function to insert a new node with given key in BST
    def insert( node, key):
     
        # If the tree is empty, return a new node
        if node is None:
            return Node(key)
     
        # Otherwise recur down the tree
        if key < node.key:
            node.left = insert(node.left, key)
        else:
            node.right = insert(node.right, key)
     
        # return the (unchanged) node pointer
        return node
     
    # Given a non-empty binary search tree, return the node
    # with minum key value found in that tree. Note that the
    # entire tree does not need to be searched 
    def minValueNode( node):
        current = node
     
        # loop down to find the leftmost leaf
        while(current.left is not None):
            current = current.left 
     
        return current 
     
    # Given a binary search tree and a key, this function
    # delete the key and returns the new root
    def deleteNode(root, key):
     
        # Base Case
        if root is None:
            return root 
     
        # If the key to be deleted is smaller than the root's
        # key then it lies in  left subtree
        if key < root.key:
            root.left = deleteNode(root.left, key)
     
        # If the kye to be delete is greater than the root's key
        # then it lies in right subtree
        elif(key > root.key):
            root.right = deleteNode(root.right, key)
     
        # If key is same as root's key, then this is the node
        # to be deleted
        else:
             
            # Node with only one child or no child
            if root.left is None :
                temp = root.right 
                root = None
                return temp 
                 
            elif root.right is None :
                temp = root.left 
                root = None
                return temp
     
            # Node with two children: Get the inorder successor
            # (smallest in the right subtree)
            temp = minValueNode(root.right)
     
            # Copy the inorder successor's content to this node
            root.key = temp.key
     
            # Delete the inorder successor
            root.right = deleteNode(root.right , temp.key)
        return root 
    

    Graphs

    https://www.python.org/doc/essays/graphs/
    https://www.python-course.eu/graphs_python.php
    https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

    graph = {'A': set(['B', 'C']),
             'B': set(['A', 'D', 'E']),
             'C': set(['A', 'F']),
             'D': set(['B']),
             'E': set(['B', 'F']),
             'F': set(['C', 'E'])}
    

    Depth First Search (DFS)

    def dfs(graph, start):
        visited, stack = set(), [start]
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                stack.extend(graph[vertex] - visited)
        return visited
    
    dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}
    
    def dfs(graph, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        for next in graph[start] - visited:
            dfs(graph, next, visited)
        return visited
    
    dfs(graph, 'C') # {'E', 'D', 'F', 'A', 'C', 'B'}
    
    def dfs_paths(graph, start, goal):
        stack = [(start, [start])]
        while stack:
            (vertex, path) = stack.pop()
            for next in graph[vertex] - set(path):
                if next == goal:
                    yield path + [next]
                else:
                    stack.append((next, path + [next]))
    
    list(dfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
    
    def dfs_paths(graph, start, goal, path=None):
        if path is None:
            path = [start]
        if start == goal:
            yield path
        for next in graph[start] - set(path):
            yield from dfs_paths(graph, next, goal, path + [next])
    
    list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]
    

    Breadth First Search (BFS)

    def bfs(graph, start):
        visited, queue = set(), [start]
        while queue:
            vertex = queue.pop(0)
            if vertex not in visited:
                visited.add(vertex)
                queue.extend(graph[vertex] - visited)
        return visited
    
    bfs(graph, 'A') # {'B', 'C', 'A', 'F', 'D', 'E'}
    
    def bfs_paths(graph, start, goal):
        queue = [(start, [start])]
        while queue:
            (vertex, path) = queue.pop(0)
            for next in graph[vertex] - set(path):
                if next == goal:
                    yield path + [next]
                else:
                    queue.append((next, path + [next]))
    
    list(bfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
    

    Shortest Path

    def shortest_path(graph, start, goal):
        try:
            return next(bfs_paths(graph, start, goal))
        except StopIteration:
            return None
    
    shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
    

    Union Find (Disjoint set)

    https://github.com/imressed/python-disjoint-set/blob/master/disjoint_set.py

    class DisjointSet:
        '''
         Disjoint Set data structure (Union–Find), is a data structure that keeps track of a 
         set of elements partitioned into a number of disjoint (nonoverlapping) subsets.
         
         Methods:
            find: Determine which subset a particular element is in. Takes an element of any
            subset as an argument and returns a subset that contains our element.
            
            union: Join two subsets into a single subset. Takes two elements of any subsets
            from disjoint_set and returns a disjoint_set with merged subsets.
            
            get: returns current disjoint set.
        '''
        _disjoint_set = list()
    
        def __init__(self, init_arr):
            self._disjoint_set = []
            if init_arr:
                for item in list(set(init_arr)):
                    self._disjoint_set.append([item])
    
        def _find_index(self, elem):
            for item in self._disjoint_set:
                if elem in item:
                    return self._disjoint_set.index(item)
            return None
    
        def find(self, elem):
            for item in self._disjoint_set:
                if elem in item:
                    return self._disjoint_set[self._disjoint_set.index(item)]
            return None
        
        def union(self,elem1, elem2):
            index_elem1 = self._find_index(elem1)
            index_elem2 = self._find_index(elem2)
            if index_elem1 != index_elem2 and index_elem1 is not None and index_elem2 is not None:
                self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2]+self._disjoint_set[index_elem1]
                del self._disjoint_set[index_elem1]
            return self._disjoint_set
            
        def get(self):
            return self._disjoint_set
    
    

    Min/Max heap (Priority Queue|Heap Queue)

    http://interactivepython.org/courselib/static/pythonds/Trees/BinaryHeapImplementation.html

    import heapq
    heapq.heappush(h,7)
    heapq.heappop(h) #returns 0
    


    class BinHeap:
        def __init__(self):
            self.heapList = [0]
            self.currentSize = 0
    
    
        def percUp(self,i):
            while i // 2 > 0:
              if self.heapList[i] < self.heapList[i // 2]:
                 tmp = self.heapList[i // 2]
                 self.heapList[i // 2] = self.heapList[i]
                 self.heapList[i] = tmp
              i = i // 2
    
        def insert(self,k):
          self.heapList.append(k)
          self.currentSize = self.currentSize + 1
          self.percUp(self.currentSize)
    
        def percDown(self,i):
          while (i * 2) <= self.currentSize:
              mc = self.minChild(i)
              if self.heapList[i] > self.heapList[mc]:
                  tmp = self.heapList[i]
                  self.heapList[i] = self.heapList[mc]
                  self.heapList[mc] = tmp
              i = mc
    
        def minChild(self,i):
          if i * 2 + 1 > self.currentSize:
              return i * 2
          else:
              if self.heapList[i*2] < self.heapList[i*2+1]:
                  return i * 2
              else:
                  return i * 2 + 1
    
        def delMin(self):
          retval = self.heapList[1]
          self.heapList[1] = self.heapList[self.currentSize]
          self.currentSize = self.currentSize - 1
          self.heapList.pop()
          self.percDown(1)
          return retval
    
        def buildHeap(self,alist):
          i = len(alist) // 2
          self.currentSize = len(alist)
          self.heapList = [0] + alist[:]
          while (i > 0):
              self.percDown(i)
              i = i - 1
    
    bh = BinHeap()
    bh.buildHeap([9,5,6,2,3])
    
    print(bh.delMin())
    print(bh.delMin())
    print(bh.delMin())
    print(bh.delMin())
    print(bh.delMin())
    
    

    Circular Queue

    class CircularQueue:
    
        #Constructor
        def __init__(self):
            self.queue = list()
            self.head = 0
            self.tail = 0
            self.maxSize = 8
    
        #Adding elements to the queue
        def enqueue(self,data):
            if self.size() == self.maxSize-1:
                return ("Queue Full!")
            self.queue.append(data)
            self.tail = (self.tail + 1) % self.maxSize
            return True
    
        #Removing elements from the queue
        def dequeue(self):
            if self.size()==0:
                return ("Queue Empty!") 
            data = self.queue[self.head]
            self.head = (self.head + 1) % self.maxSize
            return data
    
        #Calculating the size of the queue
        def size(self):
            if self.tail>=self.head:
                return (self.tail-self.head)
            return (self.maxSize - (self.head-self.tail))
    

    Dequeue (Double ended queue|Head tail linked list)

    http://interactivepython.org/courselib/static/pythonds/BasicDS/ImplementingaDequeinPython.html

    class Deque:
        def __init__(self):
            self.items = []
    
        def isEmpty(self):
            return self.items == []
    
        def addFront(self, item):
            self.items.append(item)
    
        def addRear(self, item):
            self.items.insert(0,item)
    
        def removeFront(self):
            return self.items.pop()
    
        def removeRear(self):
            return self.items.pop(0)
    
        def size(self):
            return len(self.items)
    

    Queue

    http://interactivepython.org/RkmcZ/courselib/static/pythonds/BasicDS/ImplementingaQueueinPython.html

    class Queue:
        def __init__(self):
            self.items = []
    
        def isEmpty(self):
            return self.items == []
    
        def enqueue(self, item):
            self.items.insert(0,item)
    
        def dequeue(self):
            return self.items.pop()
    
        def size(self):
            return len(self.items)
    

    Stack

    class Stack:
         def __init__(self):
             self.items = []
    
         def isEmpty(self):
             return self.items == []
    
         def push(self, item):
             self.items.append(item)
    
         def pop(self):
             return self.items.pop()
    
         def peek(self):
             return self.items[len(self.items)-1]
    
         def size(self):
             return len(self.items)
    

    Trie

    http://interactivepython.org/runestone/static/pythonds/Trees/SearchTreeImplementation.html
    https://www.geeksforgeeks.org/trie-insert-and-search/

    Quick trie

    https://github.com/kamyu104/LeetCode/blob/master/Python/word-squares.py

    class TrieNode(object):
        def __init__(self):
            self.indices = []
            self.children = [None] * 26
    
        def insert(self, words, i):
            cur = self
            for c in words[i]:
                if not cur.children[ord(c)-ord('a')]:
                    cur.children[ord(c)-ord('a')] = TrieNode()
                cur = cur.children[ord(c)-ord('a')]
                cur.indices.append(i)
    
    Advanced trie
    # Python program for insert and search
    # operation in a Trie
     
    class TrieNode:
         
        # Trie node class
        def __init__(self):
            self.children = [None]*26
     
            # isEndOfWord is True if node represent the end of the word
            self.isEndOfWord = False
     
    class Trie:
         
        # Trie data structure class
        def __init__(self):
            self.root = self.getNode()
     
        def getNode(self):
         
            # Returns new trie node (initialized to NULLs)
            return TrieNode()
     
        def _charToIndex(self,ch):
             
            # private helper function
            # Converts key current character into index
            # use only 'a' through 'z' and lower case
             
            return ord(ch)-ord('a')
     
     
        def insert(self,key):
             
            # If not present, inserts key into trie
            # If the key is prefix of trie node, 
            # just marks leaf node
            pCrawl = self.root
            length = len(key)
            for level in range(length):
                index = self._charToIndex(key[level])
     
                # if current character is not present
                if not pCrawl.children[index]:
                    pCrawl.children[index] = self.getNode()
                pCrawl = pCrawl.children[index]
     
            # mark last node as leaf
            pCrawl.isEndOfWord = True
     
        def search(self, key):
             
            # Search key in the trie
            # Returns true if key presents 
            # in trie, else false
            pCrawl = self.root
            length = len(key)
            for level in range(length):
                index = self._charToIndex(key[level])
                if not pCrawl.children[index]:
                    return False
                pCrawl = pCrawl.children[index]
     
            return pCrawl != None and pCrawl.isEndOfWord
     
    # driver function
    def main():
     
        # Input keys (use only 'a' through 'z' and lower case)
        keys = ["the","a","there","anaswe","any",
                "by","their"]
        output = ["Not present in trie",
                  "Present in tire"]
     
        # Trie object
        t = Trie()
     
        # Construct trie
        for key in keys:
            t.insert(key)
     
        # Search for different keys
        print("{} ---- {}".format("the",output[t.search("the")]))
        print("{} ---- {}".format("these",output[t.search("these")]))
        print("{} ---- {}".format("their",output[t.search("their")]))
        print("{} ---- {}".format("thaw",output[t.search("thaw")]))
     
    if __name__ == '__main__':
        main()
    

    Dynamic Programming (DP)

    Dynamic Programming by Gayle Laakman

    Cheat sheet

    Cheat sheet

    Problems

    Fibonacci

    Leetcode solutions: https://github.com/kamyu104/LeetCode

    def F(n):
        if n == 0: return 0
        elif n == 1: return 1
        else: return F(n-1)+F(n-2)
    

    Skyline Problem

    https://gist.github.com/jbochi/3287392

    buildings = [
        [1, 11, 5],
        [2, 6, 7],
        [3, 13, 9],
        [12, 7, 16],
        [14, 3, 25],
        [19, 18, 22],
        [23, 13, 29],
        [24, 4, 28],
    ]
    
    LEFT = 0
    HEIGHT = 1
    RIGHT = 2
    
    def skyline(buildings):
        left = min(b[LEFT] for b in buildings)
        right = max(b[RIGHT] for b in buildings)
        last_height = None
        output = []
        for i in range(left, right + 1):
            heights = [b[HEIGHT] for b in buildings if b[LEFT] <= i < b[RIGHT]]
            height = max(heights) if heights else 0
            if height != last_height:
                output += [i, height]
                last_height = height
        return output
    
    if __name__ == '__main__':
        assert(skyline(buildings) == [1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0])
    

    Cycle detection in directed graph

    https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

    from collections import defaultdict
     
    class Graph():
        def __init__(self,vertices):
            self.graph = defaultdict(list)
            self.V = vertices
     
        def addEdge(self,u,v):
            self.graph[u].append(v)
     
        def isCyclicUtil(self, v, visited, recStack):
            # Mark current node as visited and 
            # adds to recursion stack
            visited[v] = True
            recStack[v] = True
            # Recur for all neighbours
            # if any neighbour is visited and in 
            # recStack then graph is cyclic
            for neighbour in self.graph[v]:
                if visited[neighbour] == False:
                    if self.isCyclicUtil(neighbour, visited, recStack) == True:
                        return True
                elif recStack[neighbour] == True:
                    return True
            # The node needs to be poped from 
            # recursion stack before function ends
            recStack[v] = False
            return False
     
        # Returns true if graph is cyclic else false
        def isCyclic(self):
            visited = [False] * self.V
            recStack = [False] * self.V
            for node in range(self.V):
                if visited[node] == False:
                    if self.isCyclicUtil(node,visited,recStack) == True:
                        return True
            return False
    

    Cycle detection in undirected graph

    https://www.geeksforgeeks.org/detect-cycle-undirected-graph/

    from collections import defaultdict
      
    #This class represents a undirected graph using adjacency list representation
    class Graph:
        def __init__(self,vertices):
            self.V= vertices #No. of vertices
            self.graph = defaultdict(list) # default dictionary to store graph
        # function to add an edge to graph
        def addEdge(self,v,w):
            self.graph[v].append(w) #Add w to v_s list
            self.graph[w].append(v) #Add v to w_s list
        # A recursive function that uses visited[] and parent to detect
        # cycle in subgraph reachable from vertex v.
        def isCyclicUtil(self,v,visited,parent):
            #Mark the current node as visited 
            visited[v]= True
            #Recur for all the vertices adjacent to this vertex
            for i in self.graph[v]:
                # If the node is not visited then recurse on it
                if  visited[i]==False : 
                    if(self.isCyclicUtil(i,visited,v)):
                        return True
                # If an adjacent vertex is visited and not parent of current vertex,
                # then there is a cycle
                elif  parent!=i:
                    return True
            return False
        #Returns true if the graph contains a cycle, else false.
        def isCyclic(self):
            # Mark all the vertices as not visited
            visited =[False]*(self.V)
            # Call the recursive helper function to detect cycle in different
            #DFS trees
            for i in range(self.V):
                if visited[i] ==False: #Don't recur for u if it is already visited
                    if(self.isCyclicUtil(i,visited,-1))== True:
                        return True
            return False
    

    Devamını oku


    Yorumlar




    Yorum yazabilmek icin en az 5 karmaya ihtiyaciniz var. Paylasim yaparak karmani artirabilirsin.

    Yorumlar