算法

标签: 算法总结

算法

图的遍历

广度优先遍历

广度优先遍历实际上是借助于队列结构的先进先出的特点完成遍历任务的。目标呢是从起点出发,一层一层的向外不断扩散遍历所有节点,也有来寻找某两个节点之间的最短距离。

具体思路: 先把读到当前节点入队,然后出队,将相邻节点一次入段,与此同时不断将队头的节点出队,直到队内不再有节点时结束,实现广度优先遍历。

例子:从上往下打印出二叉树的每个节点,同层节点从左至右打印。
这个问题的本质就是一个广度优先遍历

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;
        if(root == NULL)
            return res;
        //用于实现广度优先遍历的队列
        queue<TreeNode*> queueTmp;
        //先将起点入队
        queueTmp.push(root);
        //一直遍历直到队列为空为止
        while(!queueTmp.empty()){
            //取出队头元素
            TreeNode* tmp = queueTmp.front();
            queueTmp.pop();
            res.push_back(tmp->val);
            //放入与其相邻的所有节点
            if(tmp->left)
                queueTmp.push(tmp->left);
            if(tmp->right)
                queueTmp.push(tmp->right);
        }
        return res;
    }
};

深度优先遍历

深度优先遍历是一旦找到一条可行的路径,则一直往下遍历,直到无法继续时,回退寻找其他可行的路径继续遍历,其基本的思想是回溯法。

所以在这里直接记录一下回溯法的思路,回溯法实际上是递归,只不过为了保证能够在恰当的时候回退,需要在递归函数里面加入一个记录已经走过的路径,用于在无法往下寻找的时候弹出一个节点,接着往下寻找

例子:给你两个整数 n和k,从1-n中选择k个数字的组合。比如n=4,那么从1,2,3,4中选取两个数字的组合,包括图上所述的四种

                [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

这个问题可以抽象成深度优先遍历或者说是回溯法,找到一个起点,不断往里放入元素,一旦不行或者满足停止继续搜索的条件,弹出当前,重新往下搜索

class Solution {
public:
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    vector<vector<int>> combine(int n, int k) {
        // write your code here
        vector<vector<int>> res;
        vector<int> sol;
        combineIter(res,sol,1,n,k);
        return res;
    }
    //注意由于解集是要不断往里加的所以一定要传引用
    void combineIter(vector<vector<int>>& res, vector<int>& sol,int start,int n,int k){
        //找到解,放入解集中
        if(k==0){
            res.push_back(sol);
            return;
        }
        for(int i=start;i<n+1;++i){
            //放入临时解
            sol.push_back(i);
            //改变目标为k-1,继续往下搜索,
            combineIter(res,sol,i+1,n,k-1);
            //一旦无法往下走,弹出当前节点,重新寻找路径遍历
            sol.pop_back();
        }
    }
};

排序

排序问题在大体上呢分成选择排序,插入排序和交换排序三种
image

选择排序

简单的选择排序的思路是每次在未排序序列中选出最大的,和未排序序列的最后一位交换

堆排序见数据结构 – 最大堆部分

简单选择排序:

void InsertSort(vector<int> &a)
{
    int n = a.size();
    for(int i=0;i<n;i++){
        int minIndex = i;
        //此处的for循环找出第i小的元素
        for(int j=i+1;j<n;j++){
            if(a[j]<a[minIndex])
                minIndex = j;
        }
        然后将第小的元素与第i位的元素交换
        if(minIndex!=i)
            swap(a[i],a[minIndex]);
    }
}

插入排序

插入排序的思路是将未排序的元素插入到已排序的序列当中,类似于插入扑克牌

void SelectSort(vector<int> &a)
{
    int n = a.size();
    for(int i=1;i<n;i++){
        for(int j=i-1;j>=0;j--){
            if(a[i]<a[j])
                a[j+1]=a[j];
            else
                a[j]=a[i];
                break;
        }
    }
}

交换排序

交换排序的思路是通过不断地交换来确定排序的位置

冒泡排序就是通过不断交换,把未排序序列最大的元素交换到最后一位

void BubbleSort(vector<int> & a)
{
    int n = a.size();
    //对i每个的每个循环找到最后第i大的数,放在n-i的位置上
    for(int i=0;i<n;i++){
        //两两交换
        for(int j=0;j<n-i-1;j++)
            if(a[j+1]<a[j])
                swap(a[j],a[j+1])
    }
}

快速排序则是通过一个pivot,不断地将序列分成大于pivot和小于pivot的两部分,所以快拍的重要部分在于partition

void QuickSort(vector<int> &a, int low, int high)
{
    if(low<high){
        int q = partition(a,low,high);
        QuickSort(a,low,q-1);
        QuickSort(a,q+1,high);
    }
}

int partition(vector<int>& a, int low, int high)
{
    //选择最右边的元素作为哨兵,pivot
    int pivot = a[high];
    //i用来记录最后一个小于pivot的元素的下标,初始化为low-1
    int i = low-1;
    //
    for(int j=low;j<high;++j){
        //一旦发现比pivot小的元素,记录比pivot小的最后一维的下标的i向右移动一步
        //并且将下标i上原有的元素和找到的比pivot小的元素交换
        if(a[j]<pivot){
            i++;
            swap(a[i],a[j]);
        }
    }
    //最后将pivot放到i+1的位置上
    a[high] = a[i+1];
    a[i+1] = pivot;
    //返回i+1,即pivot位置
    return i+1;
}

具体一个partition的循环如下图所示
image

归并排序

归并排序的思路是divide & conquer, 递归地把序列不断拆分,拆分的话直接对半分就行,然后再组合起来,所以关键在于如何merge。

void MergeSort(vector<int> a, int start, int end){
    if(end>start){
        int mid = (start + end) >> 1;
        MergeSort(a,start,mid);
        MergeSort(a,mid+1,end);
        Merge(a,start,mid,mid+1,end);
    }
}

void Merge(vector<int> &a,int low1, int high1, int low2, int high2){
    int i = low1; int j = low2; int n = high1-low1+high2-low2+2;
    vector<int> tmp(n);
    int k= 0;
    while(i<high1 && j<high2){
        if(a[i]<a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    //处理左右两边可能还剩余的元素
    whiel(i<=high1)
        tmp[k++] = a[i++];
    while(j<=high2)
        tmp[k++] = a[j++];
    //复制到原数组当中
    for(int i =0;i<n;i++)
        a[low+i] = tmp[i];
}

字符串相关

字符串查找

暴力

暴力检索法是最好想到的算法,也最好实现,在情况简单的情况下可以直接使用:
这里写图片描述
image
首先将原字符串和子串左端对齐,逐一比较;如果第一个字符不能匹配,则子串向后移动一位继续比较;如果第一个字符匹配,则继续比较后续字符,直至全部匹配。

时间复杂度:O(MN)

哈希检索

RK算法是对BF算法的一个改进:在BF算法中,每一个字符都需要进行比较,并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中,就尝试只进行一次比较来判定两者是否相等。

RK算法也可以进行多模式匹配,在论文查重等实际应用中一般都是使用此算法。
image

首先计算子串的HASH值,之后分别取原字符串中子串长度的字符串计算HASH值,比较两者是否相等:如果HASH值不同,则两者必定不匹配,如果相同,由于哈希冲突存在,也需要按照BF算法再次判定。

按照此例子,首先计算子串“DEF”HASH值为Hd,之后从原字符串中依次取长度为3的字符串“ABC”、“BCD”、“CDE”、“DEF”计算HASH值,分别为Ha、Hb、Hc、Hd,当Hd相等时,仍然要比较一次子串“DEF”和原字符串“DEF”是否一致。

时间复杂度:O(MN)(实际应用中往往较快,期望时间为O(M+N))

前缀树

前缀树也叫作Trie树,用来表示多个或者大量字符串,常用来查找,删除和插入字符串,效率与hash查找各有优劣

举个例子: 假设有几个字符串

image

前缀树的表示形式为:

image

使用前缀树表示多个字符串,由于拥有相同前缀的字符串公用一个父节点,其查找效率仅为O(logL),L为单词的长度

前缀树的基本操作: 查找,插入,删除

  • 查找

    前缀树有一个问题,那上图举例子,假设上图多一个abd的单词,其前缀树表示仍然相同,那如何区分去abd的存在呢,最简单的思路就是给每个节点增加一个引用计数即可,比如有1000个a开头的字母,那么a的应用计数就是1000,ab开头的有999个,那么b的引用计数就是999。

    可见b的引用计数小于a,所以存在单词a,那么得出结论:

    某个字符串在前缀树中的结尾字母的引用计数如果大于末节点的下一个节点的引用计数(大1),说明存在此单词。

  • 插入

    依次比较经过的每一个字母,如果字母存在,则给字母的引用计数加1,如果该字母不存在,直接从该字母开始到此字符串的末尾的每一个字母连接到这棵前缀树上。

  • 删除

    依次比较经过的每一个字母,给所经过的每个字母的引用计数值减1,如果该引用计数值为0的话,则删除此节点,此节点往后的节点也删除,因为必定都属于这个单词。

前缀树的应用

  • 字符串的快速检索加动态查找

    1. 前面也说了字典树的查询时间复杂度是O(logL),L是字符串的长度。所以效率还是比较高的。
    2. hash表,通过hash函数把所有的单词分别hash成key值,查询的时候直接通过hash函数即可,都知道hash表的效率是非常高的为O(1)
    3. hash表不支持动态查询,什么叫动态查询,当我们要查询单词apple时,hash表必须等待用户把单词apple输入完毕才能hash查询。
  • 字符串排序

    上图(2)我们很容易看出单词是排序的,先遍历字母序在前面的比如abdh,然后abdi。

  • 最长公共前缀

    abdh和abdi的最长公共前缀是abd,遍历字典树到字母d时,此时这些单词的公共前缀是abd。

  • 自动匹配前缀显示后缀

    我们使用辞典或者是搜索引擎的时候,输入appl,后面会自动显示一堆前缀是appl的东东吧。

后缀树

后缀树用来表示单个字符串,表示出所有有可能的后缀
例如对于单词banana:

image

其对应的后缀树表示为:

image

后缀树的应用

  • 查找某个字符串s1是否在另外一个字符串s2

    如果s1在字符串s2中,那么s1必定是s2中某个后缀串的前缀。

    理解以下后缀串的前缀这个词,其实每个后缀串也就是起始地点不同而已,前缀也就是从开头开始结尾不定。

    后缀串的前缀就可以组合成该原先字符串的任意子串了。
    比如banana,anan是anana这个后缀串的前缀。

  • 指定字符串s1在字符串s2中重复的次数

    每出现一次s2,必定对应着一个不同的后缀,而这所有的后缀又都有着共同的前缀s2。因此这些后缀在S的后缀树中必定属于某一棵子树。这棵子树的叶子数便等于s2在s1中出现的次数。

  • 两个字符串S1,S2的最长公共部分(广义后缀树)

    建立一棵广义后缀树,如下图:

image

$和#是为了区分字符串的。

我们为每个后缀串末尾单独添加一个空间存储区分字符串的符号。

那么怎么找s1和s2串最长的公共部分?

遍历每个后缀串,如果其引用计数为1则直接跳过,因为不可能有两个子串存放在这里,当引用计数>1时,往下遍历,直到分叉分别记录子串的符号,

如果不同,说明他们是不同字符串的,记录已经匹配的值即可,若相同继续下一次遍历。

上图的ana部分,到ana时,子串$结束,然后继续向下,子串anab以#结束,那么匹配了ana。
  • 最长回文串(广义后缀树)

    把要求的最长回文串的字符串s1和它的反向(逆)字符串s2建立一棵广义后缀树。

    image

    回文串有一个定义就是正反相同,也就是正着和反着可以重和在一起,那么我们直接看这棵广义后缀树的共同前缀即可,每个banana的子串和ananab的子串重合的部分

    都是回文串,我们只需要找到最长的即可。比如上面的anana,从后面不同的标记可以看出两个字符串的某个后缀都有这个前缀,能完美重合到一起。即它是回文串。

    记录Max,每次找到一个回文串比较即可。

Huffman Tree

定义哈夫曼树之前先说明几个与哈夫曼树有关的概念:

路径: 树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

路径长度:路径上的分枝数目称作路径长度。

树的路径长度:从树根到每一个结点的路径长度之和。

结点的带权路径长度:在一棵树中,如果其结点上附带有一个权值,通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度(weighted path length)

image

简单来说就是权值越大的节点深度越浅

image

  • Huffman树的构造

根据哈弗曼树的定义,一棵二叉树要使其WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点
越远离根结点。

哈弗曼依据这一特点提出了一种构造最优二叉树的方法,其基本思想如下:

image
image

版权声明:本文为fsd0722原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/fsd0722/article/details/80056439

智能推荐

ActiveMQ学习4-ActiveMQ的安全机制和集群模式

ActiveMQ的安全机制和集群模式 20 ActiveMQ安全机制 20.1 Web 控制台安全 20.2 消息服务器Broker安全 21 ActiveMQ主从集群 21.1 使用集群的重要性 20.2 主从集群的方式 20.2.1 shared filesystem Master-Slave方式主从集群 20.2.2 shared database Master-Slave方式主从集群 20...

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

猜你喜欢

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...