scxyz的博客

在解决链表的很多问题时，设置快慢指针是一个很好的解决思路。这次问题的是删除链表倒数第 n 个结点。例如， 1 -> 2 -> 3 -> 4 -> 5，删除倒数第2个变成 1 -> 2 -&g

字符串匹配有多种方法，这里先讲最简单的两种算法： BF算法 和 RK算法，复杂度也相对较高。它们均为单模式串匹配的算法，也就是一个串跟一个串进行匹配。BF算法简介Brute Force，暴力匹配算法，也叫朴素匹配算法。比较简单、好懂，但相应的性能也不高。在字符串 A 中查找字符串 B ，那字符串 A 就是主串，字符串 B 就是模式串。主串的长度记作 n ，模式串的长度记作 m ，所以...

深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。作为图的搜索算法，既可用于有向图，也可用于无向图，以下均用无向图讲解。广度优先搜索Breadth-First-Search，BFS。一种“地毯式”层层推进的搜索策略，先查找离起始顶点最近的，然后是次近的，依次往外搜索。s 表示起始顶点，t 表示终止顶点。搜索一条从 s 到 t 的路径。实际上，求得的路径就是从 s 到 t ...

图是一种非线性表数据结构。图中的元素我们就叫作顶点（vertex）。一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫作边（edge）。跟顶点相连接的边的条数，叫作顶点的度（degree）无向图边没有方向的图就叫作“无向图”。有向图边有方向的图叫作“有向图”。有向图中，把度分为入度（In-degree）和出度（Out-degree）。顶点的入度，表示有多少条边指向这个顶...

概念将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是 哈希算法。通过原始数据映射之后得到的二进制值串就是 哈希值。要求从哈希值不能反向推导出原始数据对输入数据非常敏感，一个 Bit 修改得到的哈希值也大不相同散列冲突的概率要很小执行效率高效常见应用安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。后三个应用均与分布式系统有关。下面...

本文根据清华大学邓俊辉老师课程《数据结构》总结，课程地址 。遍历介绍 按照事先约定的某种规则或次序，对节点各访问一次而且仅一次。与向量和列表等线性结构一样，二叉树的这类访问也统称为遍历（traversal）。二叉树本身并不具有天然的全局次序， 故为实现遍历，需通过在各节点与其孩子之间约定某种局部次序， 间接地定义某种全局次序。按惯例左兄弟优先于右兄弟， 若记做节点 V ，...

本文根据清华大学邓俊辉老师课程《数据结构》总结，课程地址 。递归 与 递归方程从递推角度看，为求解数组 A 的求和问题 sum(A,n)，需要 - 递归求解规模为 n-1 的问题 sum(A,n-1) - 再累加上 A[n-1] 递推方程 看其复杂度， (1)T(n)=T(n−1)+O(1)//recurrence(2)T(0)=O(1)//base:su

本文根据清华大学邓俊辉老师课程《数据结构》总结，课程地址 。循环和级数之间的关系，怎样确定其复杂度，有以下几种常见的情况。1for (int i=0; ii++) for (int j=0; jj++) O1Operation(i, j); 外层（i）有 n 层循环，也就是n 项相加。内层（j）每层循环 n 次，也就是每项计算 n 次。加一起复杂度为

本文根据清华大学邓俊辉老师课程《数据结构》总结，课程地址 。RAM 寄存器RAM（Random Access Machine 寄存器），和图灵机（TM）一样，RAM模型也是一半计算工具的简化与抽象。 每一基本操作仅需常数时间：寄存器读写（赋值）、四则运算、比较、goto、call、return。通过RAM使我们可以独立于具体的平台，对算法的效率进行比较与评判。对算法给出客观

【算法与数据结构】链表的介绍与python实现 上篇【算法与数据结构】链表的介绍与python实现 下篇上面简单介绍了链表，这篇用python实现链表的基本一些操作。包括打印链表，插入，删除，查找，翻转。class Node(): def __init__(self, data, next=None): self.data = data self.n...

【算法与数据结构】链表的介绍与python实现 上【算法与数据结构】链表的介绍与python实现 下本文部分文字图片引用了极客时间的《数据结构与算法之美》链表篇 https://time.geekbang.org/column/article/41013讲解的很不错的课程，如果有需要可以去订阅。链表介绍链表通过指针将一组零散的内存块串联在一起。内存块称为链表的“结点”。为了将...

在解决链表的很多问题时，设置快慢指针是一个很好的解决思路。这次解决两个问题：链表中是否有环结构求单链表的中间节点快慢指针的另一个问题 删除链表倒数第n个结点 ，请点击查看。链表中环的检测class Node(): def __init__(self, data, next=None): self.data = data self.next =...

BM算法， Boyer-Moore，非常高效，是KMP算法的3~4倍。高能预警，此算法较难。核心思想匹配过程其实就是模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF和RK算法做法是往后滑动一位，从模式串第一个字符重新匹配。上图中，主串中的 c 其实在模式串中并不存在，所以滑动时只要与 c 有重合，肯定无法匹配。所以可以把模式串多滑动几位，移到c后面再开始匹配。这样效率就提高了...