60分钟搞定Tarjan算法求解无向图的割点与桥

本人在学习 Tarjan 算法求解无向图的割点与桥的问题时,很快发现了一篇简洁易懂的文章。很顺利地了解算法的思路,并写出了“高效”的代码,此时内心飘过 —— So Easy。然而,当我翻开《算法竞赛进阶指南》这本书的有关篇章时,我发现其中经过精简优化的代码有几条语句让我不得其所。以至于,花了较多心思和时间来思考🤔这段真正高效的 Tarjan 算法的工作原理以及代码的编写。关于 Tarjan 算法,我将会写若干篇系列文章,来完整系统地介绍 Tarjan 算法的原理以及其主要解决的问题。而在本章我主要讲一个问题 —— 如何使用 Tarjan 算法求解无向图的割点与桥。在讲述问题之前,我们先来简单地了解下什么是 Tarjan 算法?Tarjan 算法Tarjan 算法是基于深度优先搜索的算法,用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥,进一步地可以求解无向图的... Read More

递归

递归递归是什么?递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法 。维基百科简单说,就是自身调用自身。为什么使用递归?往往面对一类问题时,如果它的规模足够小或者说达到既定的边界条件时,我们可以直接获取答案。但是,当这类问题的规模比较大时,却往往无法直接获取答案。那么,这个时候就可以通过“自身调用自身”的方式,来不断地减小问题的规模,直到问题的规模被缩减到足够小时,直接将答案返回上层的调用者,最终获取到原问题的解。如果将求解的过程逆过来,那么就是所谓的递推。通过这种方式,我们可以写出“优雅”的代码去解决规模比较大的问题。进而,避免了通过递推的方式,在每一次递推时产生的复杂的条件判断的问题。上文中提到经过递归调用,会不断地减小问题的规模,有些作者认为这是一种减治法。递归的特性自身调用自身在上文中,已经提到了这个特性,而且也非常好理解,不再赘述。... Read More

到底该如何刷LeetCode?

引言本人非计算机专业出身,本科期间一直觉得数据结构与算法是一项非常基础也重要的知识,但是由于自己可有可无的欲望和糟糕的自律能力,并没有深入地学习这项知识技能。但是,随着时间的流逝,无论在工作中、网络中还是朋友圈中,发现数据结构与算法是无比的重要,以至于任何一位牛人都无不逆天地掌握这项最基本的本领。所以,在2018年8月份,我下定决心通过刷LeetCode来锻炼这一本领——数据结构与算法。从那时起,几乎是从0起步,很多知识都不了解,基本上每刷几道题都会卡到一个完全没有遇到过的知识点,尽管到现在也会时不时地发生。但是,我一直都在坚持,并且从未放弃,累计现在已经刷了421道题目(其实不止)。你也许会问这是为什么,当然,我会在文中的后面讲到。不过,在此之前,我不得不提我是怎么计划并走过这次还未完成的刷题之旅的——到底该如何刷LeetCode?步骤频率优先 —— 因人而异的刷题顺序最开始的前两个月,... Read More

我与我的职业梦想 – 如何成为一名优秀的软件工程师

如果方便,建议边听《只要为你活一天——刘家昌》边阅读无知少年对于计算机的热爱,甚至可以追溯到初中时为了弄明白步步高9188英语词典学习机中的RPG游戏,懵懵懂懂地看着VB的语法书;高中时,在全部人都沉浸在游戏的网吧中,看着是似懂不懂的C语言程序设计教学视频;高考报自愿时,在百度中输入“计算机专业怎么样?”后一脸憧憬的神情。最后,总于“成功”地依从父母的安排学习了自动化专业。甚至在大一十一假期回来后,亲友问道自动化是干什么时,我都无法准确的解释。我想我就是这样,从小没有目标,没有梦想的那种小朋友,以至于混到了大学,自己的专业都是被人规划好的,却毫无感觉。大学期间,由于一部室友推荐的讲述Facebook创业史的电影——《社交网络》让我迷上了互联网技术。从大一下学期开始自学Web技术,大二上学期注册了属于自己的域名并建立了博客。就在这样的环境中,磕磕绊绊地学着计算机相关的杂七杂八的知识。在一个... Read More

后缀数组(Suffix Array)

本文介绍后缀数组的定义与构建的过程。首先,文章介绍什么是后缀数组,随后讲解了最自然的朴素算法。为了引出更高效的算法,文章提及了倍增思想与基数排序的背景基础知识。接着,通过模拟演练的方式一步一步地演示如何创建后缀数组。将构建的抽象过程形象地展示出来,使读者更易理解。定义给定字符串,其所有后缀有。(6为字符串的长度)。如下所示S = "banana"s1 = "banana"s2 = "anana"s3 = "nana"s4 = "ana"s5 = "na"s6 = "a"后缀数组即为由构成的有序的(字典序升序排列的)字符串数组。vector<string> sa{"a", "ana", "anana", "banana", "na", "nana"};构建后缀数组的动态过程演示动画: https://visualgo.net/zh/suffixarra思路如何构建后缀数组?若字符串的长... Read More

树状数组(Binary Indexed Tree)

树状数组或二叉索引树(英语:Binary Indexed Tree),又以其发明者命名为Fenwick树。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和, 区间和。它可以以的时间得到任意前缀和,并同时支持在时间内支持动态单点值的修改。空间复杂度。摘自维基百科文章先介绍低位运算(lowbit)的基本知识,再提及如何将一个整数划分为个区间的运算过程,进而延展到如何将线性序列以树行结构进行存取,接着介绍了高级数据结构——树状数组的两个基本操作——查询前缀和与单点增加,最后介绍了树状数组的一个应用——求解逆序对数。lowbit(低位)运算定义为非负整数在二进制表示下“最低位的1及其后边所有的0”构成的数值。比如:,其二进制表示为 ,则其低位。公式如何计算一个整数中二进制表示下所有位是1的数值?比如,则其二进制表示下所有位是1的数值有:,。... Read More

2018年度回忆与总结 – 算法

工作特价车这个项目周期持续半年之多,应该算是成长最多的一个项目了。在产品侧,能够深入到用户的角度与产品沟通产品形态,但尚浅。在技术侧,由于前期的积累与沉淀,能够快速的判断技术方案,给出技术排期,快速迭代。在运营侧,参与每周的运营周会,学习产品效果的评估分析、问题分析与解决的过程,但尚浅。整个项目,对于沟通能力、产品分析能力、业务技术熟悉程度与产品运营的过程有了一定的增长与认识。提升了相当的软实力。服务化改造针对现有的业务系统进行代码与架构级别的改造,这里我参与了一次代码级别的改造(未上线)。整体思路是围绕DDD(Domain-Driven Design)思想进行系统分层,按业务概念收敛模块,按产品形态收敛系统组件。在这个过程中,对于系统的建模能力,业务的抽象分析能力有了一定的提升。计算机算法主要关注点在LeetCode上,从2018年9月份开始,累计刷题189道。在基础算法与数据结构方面,... Read More

动态规划与分治法的思考

如果一个问题具有最优子结构的性质,此外子问题具有重叠性质,那么可以采用自底向上的动态规划的思路进行求解。同时,往往可以用递归的方式自顶向地进行求解,即分治法。如果用分治法去求解这个问题时,能够利用备忘录法进行避免对于子问题的重复计算,那么其计算的效率可以和动态规划的计算效率相比。文章来源:胡小旭 =>动态规划与分治法的思考 Read More

分治法与回溯法的思考

共同的递归性质在广义上来说,所有递归的算法都属于分治法。无非是将问题分解成一个规模更小的问题,还是将问题分解成若干个,甚至和输入规模多项式级别的子问题。那么对于前者,有些作者称作是减治法,后者称作分治法。那么对于回溯法(以深度优先搜搜方式进行)来说,目前为止我见过的都是通过递归的形式来实现的,那么从这个意义上来讲,回溯算法就是分治法的一种。回溯状态的有无再说,之所以称作是回溯法,是因为在搜索的过程中需要回溯到问题的某个状态,所以这往往需要保存回溯时的一些状态属性。然而,分治法通常并不需要考虑回溯状态的保存。分解问题的规模分治法往往是将问题分解成若干个子问题的形式,然而回溯法往往是将问题分解成规模更小的一个子问题。由于分治法将问题分解成若干个子问题,故当前问题的解需要依赖于若干个子问题,也就是若干个搜索路径的解,所以重点在于如何合并子问题的解;而然回溯法问题规模就为1个,当前的搜索路径的问题... Read More