算法总结

  • 快速union要画分支图合并

  • 快速find要列表找到代替的点

  • 希尔排序knuth序列是 13-4-1,sedewick序列是(1,5,19,41),横向长度=h(13-->4->1),然后纵向对于每一列插入排序。

  • 计数排序的计数数组中的每一个数都是加上之前的数就是位置数组

  • merge-sort就是分裂成每个元素再按照大小合并

  • 快速排序找到一个pivot然后从左右找依次比pivot小的数和大的数排序,递归这个步骤

  • 复杂度展开要展开递归方程找规律

  • huffman代码是贪心算法,每次都找最小的合并,画出二叉树,左0右1,每一个子叶是字母

  • pre-order是先根再左右子树,

  • in-order是先遍历先左子树再根再右子树

  • post-order是先左右子树最后根

  • 最少需要preorder和inorder才能找到原BST,最后用post-order验证

  • BST从叶插入左小右大,删除节点要找到前序或者后继

  • BST从根部插入要旋转,插入的反方向旋转,向R/L旋转就把子树的R/L换成父树的L/R

  • interval-BSt从叶插入左小右大,标明子树的最大值

  • interval-bst寻找,哪边的max大于[a,b]中的a就向哪边递归

  • 一次hash如果collision就+1

           ***平方hash***
           第几次collision就(j+i^2)mod k,j是第一次collision的值
           ***二次hash ***
          h1=k mod 19
          h2=1+k mod 97 
           h(k)=((k mod 19)+(1+k mod 97))mod 19 注意这里没有乘以collision的次数
               比如(45%19+1+45%97)%19=  15
                   collision!
                   (15%19+1+45%97)%19=4 ok
    
  • heapsort每次都要保证最大堆,按顺序插入,先左后右
    priority queen删除最大的节点要先把最大的节点和最小的额节点交换后删除,然后再进行最大堆整理

  • DFS按照字母表顺序深入搜索,递归时返回的每一步都检查是否有新的路线
    被指向的和指出的(A,B)比:

    / |A | B
    ----|----|----
    T | > | < |
    B | < | >|
    F | > | > |
    C | < | < |

图算法:

  • acyslic无环意思就是DFS没有B标记

最短路径算法

  • Dijkstra是每次都找权重最小的边松弛,直到所有定点都被松弛
  • bellman是对每条边松弛知道不再变化

最小生成树算法

  • prim算法是划线每次都找最短的
  • kruskal是找出所有最短的边,直到再找一个就会连成环

  • Kosaraju强连通分量,画一个反向图进行DFS得出(discover,endprocessing),在原图根据endpro递减顺序来进行DFS,每一块DFS开始都是一个SCC

对于DAG的拓扑排序

  1. 从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。

重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348

推荐阅读更多精彩内容

  • 1. 链表 链表是最基本的数据结构,面试官也常常用链表来考察面试者的基本能力,而且链表相关的操作相对而言比较简单,...
    Mr希灵阅读 1,434评论 0 20
  • 一、概述 排序算法概念 在计算机科学与数学中,一个排序算法是将一组杂乱无章的数据按一定的规律顺次排列起来的算法。排...
    简书冷雨阅读 1,027评论 0 0
  • 算法总结 排序算法说明 (1)排序的定义:对一序列对象根据某个关键字进行排序; 输入:n个数:a1,a2,a3,....
    AKyS佐毅阅读 632评论 0 5
  • 作者:大海里的太阳原文地址:http://www.cnblogs.com/wxisme/ 前言 查找和排序算法是算...
    IT程序狮阅读 2,492评论 0 63
  • 第二节 身世磨砺童年苦 苦瓜藤上结苦瓜,麻子年幼多劫难。 麻子的父母是乡下的普通农民,老实巴交,从不招惹是非。守着...
    天河奔骁阅读 356评论 0 5