Please enable JavaScript.

Coggle requires JavaScript to display documents.

数据结构+算法框架, 算法 (图形算法, 图形遍历, 排序算法, 拓扑搜索算法, 搜索算法, 最小spanning tress, 贪婪算法,…

- - - - built-in: integer; float; short; double;
    - - user-defined: derived from primitive ds by combining 2+ DS
        
        liniear
        
        data arragned in memory in a linear sequential manner
        
        static
        
        structure-associtated memory locs are fixed at compile time
        
        array
        
        dynamic
        
        struc-associated mem locs change
        
        linked list; stack; queue
        
        non-linear
        
        data are connected to several other items not organized sequentiallly
        
        tree
        
        graph
- - - - dp: memoization
      - brutal force
      - divide and conquer: >=2 recursive calls
        
        quicksort
        
        merge sort
      - randomized
        
        quick sort
      - simple recursion
- - - - time efficiency 不同
      - space efficiency不同
- - - - comma is must, even there is only 1 element
    - - tuple(<string>)
    - - tuple(<list>)
- - - - 更新某个、某些元素
      - 获取(打印)
    - - O(N)
  - - - O(1)
  - - - built-in list ds
        
        插入end
        
        <mylist>.append(<value>)
        
        O(1)
        
        <mylist>.extend(<mylist2>)
        
        O(N)
        
        插入位置beginning
        
        插入位置middle
        
        <mylist>.insert(<index>, <values>)
        
        O(N)
      - array module
        
        <myarray>.append(value); <myarray>.insert(<index>, <value>);<myarray>.extend(<myarray2>); <myarray>+<myarray2>
        
        can have full error
        
        ????
        
        similar to list
        
        can have type error
      - numpy module
        
        import numpy
        
        numpy.array(<myarray>); numpy.insert(<myarray>, <idx>, <val>);numpy.append(<myarray>, <myarray2>);
  - - - binary search（ordered array）
        
        O(log(N))
      - looking thru every elment
        
        O(N)
      - 根据已知的idx读取然后判断
        
        O(1)
  - - - list
        
        <mylist>.remove(<value>)
        
        in-place removal
        
        or throws ValueError
        
        O(N)
        
        return None
        
        removes 1st if more than 2 found
        
        <mylist>.pop(<idx>)
        
        <idx> optional, by default -1
        
        idx our of range
        
        throws IndexError
        
        return popped item value
        
        del <mylist>[idx or idx range]
- - - - list comprehension: [x for x in iterable]
      - type constructor:list(iterable)
        
        是一般函数
      - brackets: [1], [1,2,3]
      - built-in functions that return a list, such as sorted(iterable)
      - string methods
        
        <mystring>.split(sep=' ')
    - - brackets: []
      - type constructor:list()
  - - - O(1), O(N)
    - - O(N)
  - - - O(N)
    - - O(N)
- - - - numpy ndarray基于此。
- - - - 全为T-->T; empty->T;其他->F
  - - - 全T->T; 仅有一个T->T；empty->F;全F->F
  - - - key in dic
        
        O(1)
      - value in dict.values()
    - - O(N)
  - - - ** implies that an argument is a dictionary
        
        Using ** [double star] is a shortcut that allows you to pass multiple arguments to a function directly using a dictionary.
- - - - O(1)
        
        space armortized O(1)
        
        平摊分析在计算机科学中，是用于算法分析中的方法，平摊分析常用于分析数据结构，在使用平摊分析前须知道数据结构各种操作所可能发生的时间，并计算出最坏情况下的操作情况并加以平均，得到操作的平均耗费时间。平摊分析只能确保最坏情况性能的每次操作耗费的平均时间，并不能确认平均情况性能。
    - - if exist, return that value
  - - - O(1)
  - - - exception:KeyError
        
        O(1)
  - - - for k in <dict>
        
        O(N)
  - - - type constructor
        
        dict(key = value, key2 = val2...)
      - notation
        
        {ky1: val1, ky2:val2......}
      - <dict>.copy(): shallow
      - {}.fromkeys(<list>, value=None)
        
        create a same value dict
    - - notation
        
        {}curly brackets
      - type constructor dict()
  - - - return poped value
      - 删除key-value pair
        
        O(1)
      - if key not exists, return value
    - - 删除key-val pair
- - - - diff keys, same hash values, same locs of the array of dict values
    - - linked list 存储“同一位置”dict values
- - - - good hash fun性质
        
        distributes hash values uniformly across hash tables
        
        min collisions
        
        leverage all Input data
        
        min colliisons
      - collision restolution technique
        
        direct chaining
        
        LL
        
        never gets full, each buket grows forever
        
        如果常使用deletion，比较适合
        
        performace leaks(O(1)->O(N))
        
        open addressing
        
        probing 探测（list？）
        
        easy implementation though more computaitons
        
        适合已知input size的场景
        
        when ht gets full, new ht affects performance
        
        类型
        
        quadratic probing
        
        double hashing
        
        linear probing
      - 类型
        
        mod ASCII function: for string input
        
        mod functi: for numeric input
- - - - stack
      - queue
- - - - 打印机打印队列
      - 电话中心来电系统
- - - - out of place bubble
        
        O(N2) + O(1)
        
        space？
  - - - out of place插入
        
        O(N2) + O(1)
        
        space？
  - - - O(N2)+O(N)
        
        space？???
        
        如果data在range比如0-1间均匀分布
  - - - 非线性排序。。。
        
        O(NlogN)+O(N)
        
        stable
        
        space is concern
  - - - unstable
      - space？？
  - - - 增加新位置，释放旧位置，空间复杂度O(1)????
- - - - <sep>.join(iterable)
- - - - 直觉中的copy就是deep copy
      - 全盘复制原始对象
      - 更新copy元素不会影响原始对象
    - - 创建一个指针，指向原始对象
- - - - stack = []
    - - The biggest issue is that it can run into speed issues as it grows. The items in the list are stored next to each other in memory, if the stack grows bigger than the block of memory that currently holds it, then Python needs to do some memory allocations. This can lead to some append() calls taking much longer than other ones.
        
        O(n)
  - - - class Node:
        class Stack:
        
        The linked list has two methods addHead(item) and removeHead() that run in constant time. These two methods are suitable to implement a stack.
  - - - The same methods on deque as seen in the list are used, append() and pop().
        
        Deque is preferred over the list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.
  - - - Data is inserted into Queue using the put() function and get() takes data out from the Queue.
- - - - 网页的back功能
- - - - create
        
        linked list
        
        each node has 3 components
        
        left pointer
        
        data
        
        right pointer
        
        list
        
        parent [x]
        
        x 最小为1（root index）
        
        right child [2x+1][
        
        left child [2x]
      - methods of BT on LL
        
        search
        
        level-order traversal
        
        ???
        
        insert
        
        no root
        
        tree exists
        
        where to insert that node?
        
        a first vacant place(parent w/o a child)
        
        delete a node
        
        使用deepest node进行替代
        
        traverse
        
        DFS: depth first search
        
        inorder traverse
        
        left subtree-root-right subtree
        
        Time O(N); Space O(N)
        
        1 more item...
        
        postorder traverse
        
        left subtree-right subtree-root
        
        preorder traverse
        
        root-left subtree-right subtree
        
        BFS: breadth first research
        
        level 1 - level 2(left - right)-...last level(left - right)
        
        space O(1)
        
        iteartion
      - methods of BT on list
        
        insert
        
        delete
        
        使用deepest node 代替，再删除deepest node（last index）
        
        traverse
        
        BFS
        
        DFS
        
        inorder
        
        postorder
        
        preorder
    - - 类型
        
        full bt
        
        each partent has 2 children
        
        perfect bt
        
        full bt + leaf nodes at the same level(same depth)
        
        cpmplete
        
        full bt + only last level is not full, leafs are as left as possbile
        
        balanced
        
        leaf nodes at the same level, some levels are not full
    - - BST(二叉查找树）
        
        AVL/自平衡二叉查找数
        
        定义：BST+self-balancing(all nodes)
        
        balancing: difference between height of left subtree and right subtree <=1
        
        VS BST: much faster in searching
        
        implementations
        
        search for a node
        
        traversal
        
        create
        
        insert a node
        
        case 2. rotation required
        
        right-right condition: left rotation (starting from grandpartent)
        
        right-left condition
        
        1 more item...
        
        left-left condition: right rotaiton (starting from grandpartent)
        
        1 more item...
        
        left-right condition
        
        1 more item...
        
        case 1. rotation not requrired
        
        delete a node
        
        tree empty
        
        yes
        
        1 more item...
        
        no
        
        1 more item...
        
        delte entire tree
        
        left, root, right = none
        
        定义： BT + left child value <=partent value+ right child value > parent value
        
        versus BT: much faster in inseration, deletion
        
        排序的时间不算进来吗？？
        
        implementations on LL
        
        insert
        
        recursion, base case root.data = None
        
        create
        
        traverse
        
        similar to BT
        
        search
        
        recursion, base case root.data = value
        
        delate a node
        
        case 1 a leaf
        
        case 2 a node w/ a child
        
        reassign parent
        
        case 3 a node w/ 2 children
        
        用right sub上最小node做为 successor, 替换node，删除successor，reassign parent
        
        ？？？
        
        delete entire tree
        
        root, left, right = none
      - binary heap(二叉堆、完全二叉数或近似完全二叉树）
        
        定义： BT + min heap + complete tree
        
        root value<= child value
        
        定义： BT + max heap + complete tree
        
        root value >= child value
        
        就像堆场（越来越重或者越来越轻，从上往下）
        
        用途
        
        在O(logN)时间内找最小或最大node
        
        ??
        
        在O(logNode) 时间内内插入node
        
        其他数据结构表现
        
        算法举例
        
        prim's alg
        
        ??
        
        heap sort
        
        ???
        
        priority queue
        
        ???
        
        implemantations
        
        insert
        
        有vacant location
        
        NO
        
        array of fixed size
        
        1 more item...
        
        YES
        
        查到last index后面
        
        1 more item...
        
        traverse
        
        DFS;BFS
        
        create
        
        left child [2x]
        
        parent [x]
        
        index从1开始
        
        right child [2x+1]
        
        extract a node
        
        only allow extract root
        
        用last index node代替，last index node = none
        
        proper BH?
        
        2 more items...
        
        peek, size,extact max/min
        
        delete entire BH
        
        list is none
        
        basic structures
        
        array/list
        
        better: easy to implement; space efficiency
        
        ????
        
        reference
    - - 帮助理解advanced tree structure
      - 是许多问题的解法
        
        heap proving
        
        ???
        
        exposion parsion
        
        ???
        
        haffinan coding
        
        ??
  - - - each node contains non-repeated chars
      - each node stores link(s) to the next node
      - store or search strings in a time and space effiently way
        
        ?????跟谁比
      - each node keeps track of "end of string".
    - - auto completion
      - spelling checker
    - - search for a string
        
        case 2. The string exists
        
        case 3. The string is a prefix of another string, bud does not exist in a trie
        
        case 1:the string doesn't exit
      - creation
        
        case 2: not empty and new string's prefix is comon to another strings prefix
        
        new string prefix is already present as complet string
        
        case 1: trie is empty
        
        case 4 string to be inserted is already presented in Trie
      - delete a string
        
        string is prefix of another string:set endofstring = false
        
        other string is a prefix of this string: delete extra chars?
        
        none node depends on this string: delete?
        
        string share prefix with other string: delte extra chars?
- - - - 每个node（树杈的端点）有两个成分
        
        数据
        
        链接（子node）
      - root node and under it sub nodes
      - 等级状的数据
        
        下层是上层的细分
    - - 比线性的数据结构，更快访问数据
      - 对于等级状的数据，比如说，文件架构，组织架构，以tree结构存储是自然的
      - tree有不同的类型，对应不同应用场景
    - - edge
      - leaf
        
        no children
      - root
        
        no partent
      - sibling
        
        same parent
      - ancestor
      - depth of a node
        
        to the root
      - height of a node
        
        no. of edges to the deepest node
      - depth of a tree
        
        0
      - height of a tree
        
        no. of edges to the farthest leaf
- - - - Once a bounded length deque is full, when new items are added, a corresponding number of items are discarded from the opposite end.
        
        Bounded length deques provide functionality similar to the tail filter in Unix.
        
        They are also useful for tracking transactions and other pools of data where only the most recent activity is of interest.
    - - append(x)
        Add x to the right side of the deque.
        
        appendleft(x)
        Add x to the left side of the deque.
      - clear()
        Remove all elements from the deque leaving it with length 0.
      - copy()
        Create a shallow copy of the deque.
      - count(x)
        Count the number of deque elements equal to x.
      - extend(iterable)
        Extend the right side of the deque by appending elements from the iterable argument.
        
        extendleft(iterable)
        Extend the left side of the deque by appending elements from iterable. Note, the series of left appends results in reversing the order of elements in the iterable argument.
      - index(x[, start[, stop]])
        Return the position of x in the deque (at or after index start and before index stop). Returns the first match or raises ValueError if not found.
      - insert(i, x)
        Insert x into the deque at position i. If the insertion would cause a bounded deque to grow beyond maxlen, an IndexError is raised.
      - pop()
        Remove and return an element from the right side of the deque. If no elements are present, raises an IndexError.
        
        popleft()
        Remove and return an element from the left side of the deque. If no elements are present, raises an IndexError.
      - remove(value)
        Remove the first occurrence of value. If not found, raises a ValueError.
      - reverse()
        Reverse the elements of the deque in-place and then return None.
      - rotate(n=1)
        Rotate the deque n steps to the right. If n is negative, rotate to the left.When the deque is not empty, rotating one step to the right is equivalent to d.appendleft(d.pop()), and rotating one step to the left is equivalent to d.append(d.popleft()).
    - - source
- - - - 计算
        
        drop constant
        
        渐进分析中，忽略常数，可以去除算法效率中的硬件噪声，trivial 算法差异噪声，让算法比较更直接
        
        drop non-dominant terms
        
        渐进分析中，dominant项目可以充分比较算法效率
        
        运算
        
        加法
        
        “do this, if it is done, do that”
        
        乘法
        
        "do this each time you do that"
        
        递归
      - 类型
- - - - recursion：f(x) = max(x, f(x-1))
      - iteration: max, curr(2 pointers)