首页 > 专题系列 > 经典问题 > 数据结构和算法[精选]
2015
10-13

数据结构和算法[精选]

数据结构

线性表链表反转跳跃表(Skip List)-实现(Java)链表排序链表中倒数第k个结点, 调整数组顺序使奇数位于偶数前面

二叉树:二分查找树转化为排序的循环双链表寻找二叉树两个节点的最低公共祖先不使用递归和栈中序遍历二叉树有序链表转化为平衡的二分查找树找出二叉树中某个节点的所有祖先节点,  不使用递归和栈中序遍历二叉树,   二叉树非递归中序遍历, 二叉树非递归先序遍历, 二叉查找树的后序遍历结果

栈:包含min函数的栈直方图最大面积中缀表达式转为后缀表达式寻找下一个较大元素, 用栈来实现表达式求值

算法

排序和查找:无处不在的二分查找 ,基数排序(Radix Sorting)计数排序-Counting Sort归并排序堆排序归并排序对链表进行排序快速排序的随机化和非递归实现 ,快速排序算法及分析0-n^2内的数排序对接近有序的数组排序 求第二小元素

贪心算法:任务选择问题Kruskal最小生成树霍夫曼编码最小生成树Prim算法 , Dijkstra最短路径算法 Dijkstra算法-邻接表-最小堆实现

动态规划:重叠子问题的性质最优子结构的性质最长递增子序列最长公共子序列最小编辑距离(Edit Distance)最小花费路径硬币找零矩阵连乘二项式系数01背包问题扔鸡蛋问题(Egg Dropping Puzzle) ,划分问题最长回文子序列数字转字母的编码方式的个数,  最长公共子串,   Bellman-Ford最短路径算法

数学相关:扩展欧几里得算法整数集合中找出3的最大倍数 , 阶乘末尾0的个数幸运数字卡特兰(Catalan)数巴比伦算法求平方根整数集合中找出3的最大倍数质因数分解及算法实现康托展开式, 约瑟夫环的数学优化方法, 整数中1出现的次数

位运算:能被3整除的数Single Number ISingle Number II判断两个数是否符号相反位运算做除法寻找缺失的数字不用加减乘除做加法

图论:BFS和DFS ,最大流问题-Ford-Fulkerson算法判断强连通图求强连通分量-Kosaraju算法, 二分图判断有向无环图的最短路径,  拓扑排序 Graham’s Scan法求解凸包问题

回溯和剪枝骑士旅游问题分支限界法(1)分支限界法(2)分支限界法(3) ,n皇后问题N皇后问题2(优化) , 哈密顿回路-回溯法

分治:最接近点对问题两个有序数组的中位数棋盘覆盖问题

模式匹配BF算法到KMP算法KMP算法(1)KMP匹配算法(2)优化有限自动机

高级数据结构

字典树(Trie树)并查集并查集优化后缀树简介, 后缀数组及应用 区间树 , 区间最值查询-线段树B树(一)概述和C++实现  B树(二)插入操作的实现,  线段树入门-求给定区间的和 ,

高级算法

遗传算法-入门旅行商(TSP)问题-遗传算法, 模拟退火算法-TSP问题概率算法求解π 

算法分析

渐进分析循环的时间复杂度递归的时间复杂度, 快速排序算法及分析 , NP完全性理论与近似算法


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?