算法导论笔记0x16 —— 子串搜索

KMP

m is the length of text
n is the length of pattern

  • [Prefix Array Logic]
  • 初始j指向0索引,i指向1索引
  • 数组0索引初始化为0
  • 检查匹配
    • 不匹配时,跳到j索引的前一个数组值所对应的索引位置继续检查匹配
      • 不匹配时,j=Array[j-1]
      • 若j是0,数组值为0,Array[i]=0
    • 匹配时,数组中的值为j的值加1,i和j同时加1继续检查匹配
      • Array[i]=j+1, i++, j++

Continue reading “算法导论笔记0x16 —— 子串搜索”

算法设计与分析笔记0x0E —— Part 3 NP完全

Partitioning Problems

3-Dimensional Matching

3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T X × Y × Z of triples, does there exist a set of n triples in T such that each element of X Y Z is in exactly one of these triples?

Continue reading “算法设计与分析笔记0x0E —— Part 3 NP完全”

Python 数据分析与展示笔记目录

python数据分析与展示 – 第三周/单元八/Pandas数据特征分析

和单元七一样,直接从课件中整理笔记。

数据排序

  • .sort_index()方法在指定轴上根据索引进行排序,默认升序
    • .sort_index(axis=0, ascending=True)
    • For DataFrame, first argument is some index or columns by which data is sorted.
    • NaN统一放在排序末尾

Continue reading “python数据分析与展示 – 第三周/单元八/Pandas数据特征分析”