数据结构与算法的笔记简单整理（持续更新

开学学习内容

数据结构

  • [快速转置算法][https://blog.csdn.net/qq845579063/article/details/51354847]

  • [KMP算法详解][https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html]

  • BM算法

  • 带头结点的链表（dummyHead？）

  • 双向循环链表

  • 邻接表表示的是出度（从顶点A连接到B和C，因而链表结构为A->B->C；反之，在逆邻接表中为B->A和C->A）

  • 连通图：删去任意一个节点，所有顶点仍然互相连通的图。

    反之，若删去则分为两个图，则称为关节点。

    删去K个节点后无法保证连通图，则称连通图的连通度为K。

    待解决~~

  • 最小生成树

    • kruskal算法（按边加）
    • prim算法（按顶点加）

  • AOE AOV

    其中AOV主要介绍如何通过拓扑排序判断AOV中是否存在有向环。

    AOE主要介绍如何计算最早开始时间和最晚结束时间

  • 最短路径算法：

    • Dijkstra算法

      • 单源最短路径（只能算出一个顶点到其他顶点的最短路径）
      • 不能有负权值，不能有环

    • Floyd算法

      • 没有负权值的顾虑，可计算任意两点之间距离。

      • 本质是动态规划

      • ```
        1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
        2 for each vertex v
        3 dist[v][v] ← 0
        4 for each edge (u,v)
        5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)
        6 for k from 1 to |V|
        7 for i from 1 to |V|
        8 for j from 1 to |V|
        9 if dist[i][j] > dist[i][k] + dist[k][j]
        10 dist[i][j] ← dist[i][k] + dist[k][j]
        11 end if

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21

              

        * 拓扑排序



        ## LeetCode

        - 双指针
        - 链表→递归&迭代
        - dummyHead
        - 循环不变量的确定
        - 不变量（例如区间，在写之前就应当确定是[a,b]或者[a,b)）



        ## 编写中遇到的c++语法问题

        - ```cpp
          template <class Type> // == template <typename Type>

  • 关于<<和>>的运算符重载：

    • 一般的运算符重载可以在类内直接解决

    • 但是这两个运算符 为保证和正常使用cin和cout的习惯 需要将参数列表设为(istream &input,class Classname)（同时返回也要右值引用

    • 但是类内声明时 会默认在参数列表首位加上this指针

    • 因此 这类函数只能在外部声明（假如数据全部可访问） 或者只能在类内作为友元函数来访问 因为友元函数不会加上this指针

    • 较为正确的方法：

      1
      2
      3
      4
      5
      6
      7
      8
      class Candidate:
      {
          private:
          //..
          public:
          //..
          friend ostream& operator<<(ostream& output, const Candidate candidate) // 重载输出函数
      }

  • STL的stack的pop()函数不会返回弹出数据 如需使用请结合pop()

  • c++的文件读入（istream）输出（ostream）一段文字

    最后我先用了cin.get()将输入的文字输出到ostream 然后读取时用getline将istream内数据读取

  • 经过一番探索后我发现
    将带模板的类的声明和定义放在.h和.cpp中 另外加上main.cpp是不对的行为
    因为template function will be compiled only when it is used
    而main中只包含了头文件而不包含.cpp 会导致其”invisible to the implementation”
    所以 要么都写在头文件中 要么就在h末尾加上#include”…cpp”

  • if (a = 1) cout << "..";
// equal to
// 1. a=1;
// if (a) ..
// cause the = operator will return this integer

    1
    2
    3
    4

    - ```cpp
      int a = 3 << 4; // a = 3 * (2 ^ 4) = 48 左移运算符
      int b = 8 >> 1; // b = 8 / (2 ^ 1) = 4  右移运算符

  • vector的几种赋值or拷贝方法：

    1
    2
    3
    4
    5
    6
    7
    8
    vector<int> example={1,2,3,4};
    vector<int> target1(example);
    vector<int> target2(example.begin(),example.begin()+2);
    vector<int> target3;
    target3.assign(2,2);
    target3.assign(example.begin(),example.begin()+2); //[a,b)
    vector<int> target4;
    target4.swap(example);//example={}

  • sizeof(bool)==1 byte

  • c++ closure

    In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions.

  • 自己编写的一个用于获得任意要求的整数值的函数：

    本来想使用template 但是经过研究发现 lambda不能用在template函数中 见如下说明：

    The evaluation of a lambda-expression results in a prvalue temporary (12.2). This temporary is called the closure object. A lambda-expression shall not appear in an unevaluated operand (Clause 5). [ Note: A closure object behaves like a function object (20.8).—end note ] (emphasis mine)

    换言之，lambda是一个闭包，有类型也有状态（state），而template是动态的，未编译的，不可能接受包容state。

    （这个问题貌似在c20里得到了解决）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //用function来闭包处理lambda函数
    int getIntValue(const function<bool(int)>& judgeFunc) {//for freely customizing the int value you want
    	int value;
    	while (true)
    	{
    		cin >> value;
    		if (cin.fail()) {
    			cerr << "input error\n";
    			cin.clear();
    			cin.ignore(1024, '\n');
    		}
    		else if (!judgeFunc(value)) {//对这句进行灵活定制
    			cerr << "dont meet the command\n";
    		}
    		else
    			break;
    	}

    	return value;
    }

other

  • 拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科。 它只考虑物体间的位置关系而不考虑它们的形状和大小。 拓扑英文名是Topology，直译是地志学，最早指研究地形、地貌相类似的有关学科。

  • 蛇形命名法：student_num,sum_score如是。

开学之前

AES算法

  • 对称加密算法（advanced encryption standard）（即可逆）

  • 概念

    • 密钥

      • AES128/192/256

    • 填充

      • 在存在不满的情况下 以一些规则来填充未满部分

    • 模式

      明文加密为密文

  • 加密过程

    • 初始轮

      加轮密钥

    • 普通轮

      字节代替

      行移位

      列混淆

      加轮密钥

    • 最终轮

      字节代替

      行移位

      加轮密钥

快速排序

  • 分治法
  • pivot的选择的几种方式
    • 选第一个
    • 随机数
  • partition的分法
    • 挖坑法
    • 指针交换fa

优先队列

  • 最大优先队列：最大的元素优先出队
  • 最小优先队列：最小的元素优先出队
  • 实现：堆排序

跳跃表

在链表中建立索引 乃至于索引的索引 来加快查找速度

插入：

  • 新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
  • 把索引插入到原链表。O（1）
  • 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
  • 总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）

删除：

  • 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
  • 删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
  • 总体上，跳跃表删除操作的时间复杂度是O（logN）。

HashMap

  • 默认初始长度为16 且每次扩容只能*2

  • 均匀分布：位运算

    index = HashCode（Key） & （Length – 1）

Chrome 脚本安装

  1. 打开chrome扩展程序页 – chrome://extensions
  2. 将刚才的自定义脚本保存为以user.js为后缀的 .js文件，例如test.user.js，拖入扩展程序页。
  3. 重启浏览器。
  4. 进入月饼抢购活动页面。此时脚本已自动执行。

link

空间复杂度

S(n)=O(f(n))

例如 递归的空间复杂度为n

归并排序

分而治之 先分为一个个小块（类似于二叉树一样） 再往上溯源 合并

快速排序

桶排序

伪代码（摘自Wikipedia

1
2
3
4
5
6
7
function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

Floyd 最短路算法

邻接表

数组＋单链表

判断单链表是否存在环

快慢法

一直走法

该图片由Andreas Breitling在Pixabay上发布

技术
#技术
数据结构与算法的笔记简单整理（持续更新
http://baokker.github.io/2021/09/26/数据结构与算法的笔记简单整理/
作者
Baokker
发布于
2021年9月26日
更新于
2022年5月29日
许可协议