Tag: Original

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

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

递归

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

动态规划与分治法的思考

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

分治法与回溯法的思考

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

一只青蛙跳出来的分治法、回溯法与动态规划

从2018年7月份开始，基础薄弱的我从0开始刷LeetCode题目。目的性很明确，也很简单——就是为了提高解决问题的思考实践能力，也为了提升自己的核心竞争力。也许，牛人会觉得这并不算什么竞争力。是的，我同意的。但，这是我目前能做的比较基础的事情罢了。迄今（2018年12月28日）为止，已经刷了108道题目。顺序基本上是按照出现的频率（Frequency）来刷的，这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后，有那么一些题目会觉得“似曾相识”了，也会有一种触类旁通的感觉了。所以，我觉得应该适当放慢刷题的速度，同时做做总结了。所以，计划了一项视频解说计划，在YouTubeh和B站都建立了《小旭解说算法之路》的频道，欢迎订阅，多多提建议。那么，进入正题。经过了108道题的历练之后，我来说说对于分治法、回溯法和动态规划的理解。我觉得他们三者是一个相互有交集的概念，并不... Read More

最大流问题之 Ford-Fulkerson 算法

Ford-Fulkerson算法（亦即标号法？）的输入与步骤如下输入给定一个容量为c的图G=(V, E)，源点s与汇点（终点）步骤对图G中每一个边(u, v)的流量f(u, v)进行初始化为查询过程：寻找（DFS、深度优先搜索方式）图G中的一条路径p，其中每一条边(u, v) ∈p，都有fc(u, v) = c(u, v) - f(u, v) > 0（c(u, v) 代表当前边的容量，f(u, v) 代表当前边已有的流量，即c(u, v) - f(u, v)代表当前边可用的最大流量，即剩余流量调整过程：计算当前路径下每条边的最小剩余容量，cf(p) = min{fc(u, v) : (u, v) ∈p}，然后对于每条边进行如下操作f(u, v) = f(u, v) + cf(p) （前向狐f(v, u) = f(v, u) - cf(p) （后向狐往复上述2与3步骤，直至无法找到路径p为止... Read More

滴滴出行业务平台研发岗位内推

有意者欢迎骚扰:huxu@didichuxing.co更新于：2018.05.25 15:5【在线业务研发工程师(PHP/Golang)我们需要一个这要的你有志于参与一场出行行业的变革；对于大流量高并发业务场景的技术挑战心潮澎湃。用你的代码影响成千上万人负责快车、专车、拼车、优步、优享、出租车等核心业务的服务端研发工作；负责接送机、站点拼车、跨城、小巴等垂直出行场景的服务建设和通勤、休娱、商旅等新出行场景孵化。【中台建设&中间件研发工程师/众里寻你千百度每一次将复杂世界变得简单都让你心花怒放；每一次你的系统都能云淡风轻跨越一座座流量洪峰，而你依然心若止水。你来协助我们提升生产力负责打磨现有产品业务流程，深入了解司乘两端业务，对出行场景进行抽象优化；负责出行中台&中间件架构设计和优化工作，提供新业务的快速扩展和接入能力。有意者欢迎骚扰:huxu@didichuxing.co... Read More

[维护中]基于文本图形（ncurses）的文本搜索工具 ncgrep

源码下载http://github.com/ncgrep/ncgre背景作为一个VIM党，日常工作开发中，会经常利用grep进行关键词搜索，以快速定位到文件。如图但是，这一过程会有两个效率问题展示的结果无法进行直接交互，需要手动粘贴文件路径在打开展示的结果没有进行分组，直接将结果罗列出来可想而知，当搜索的内容结果集比较大时，可谓痛苦。那可以用Vim中的Ag插件进行搜索啊？是的，但他只解决了交互的问题。仍然没有解决结果集分组分类的痛点。思路在使用Eclipse等IDE进行文本全局搜索时，在加载效果（懒加载）可视化方面有很大优势。那么，期望基于linux系统，提供一个类似的搜索工具。优点（功能）如下结果集可以直接交互结果集可以进行分组展示结果集通过“懒加载”方式装载基于文本图形界面的类库是什么呢？网上大致了解了下VIM、htop类似的软件，其都是基于一个叫ncurses的类库实现的。项目... Read More

[开发中]基于树莓派的智能家居项目的设想与实现 Hestia

注：本文内容的准确性仅限于笔者写该篇文章时的情况，不保证后续与实际项目代码一致。实时内容还请关注Github项目托管页面：https://github.com/GenialX/hestia-serve树莓派，一个五脏俱全，集几乎所有功能于一身的微型计算器。大约一两月之前，屈屈300百大洋收入囊中。入手之后，出于对自动化的兴趣，慢慢地研究如何实现室内家电的智能自动化控制。在断断续续地，不断地摸索之后，有了若干想实现的点子，迄今为止也有所实践。点子利用红外线传感器智能控制空调、电视等基于红外遥控的家电设备；智能控制家中的灯泡设备（部分基于网络协议）；方案硬件首先，除了树莓派之外，还需要如下硬件移动端设备 Android手机一台（iPhone手机当然也没问题，但是本案例中只基于Android手机做了实现外网可直接访问的服务器一台（本案例使用阿里云服务器基于树莓派（点我购买）的传感器若干基于光敏电阻的光线传感器一个... Read More

利用内网穿透 frp 工具实现外网链接（ssh）内网树莓派设备

内网穿透原理内网穿透（Net穿透）也即端口映射，笔者粗暴理解是一种能够将外网机器与内网机器（外网无法直接访问的设备）建立通信的一种技术解决方案。百度百科尽管有许多穿越NAT的技术，但没有一项是完美的，这是因为NAT的行为是非标准化的。这些技术中的大多数都要求有一个公共服务器，而且这个服务器使用的是一个众所周知的、从全球任何地方都能访问得到的IP地址。一些方法仅在建立连接时需要使用这个服务器，而其它的方法则通过这个服务器中继所有的数据——这就引入了带宽开销的问题。具体原理详见百度百科=>https://baike.baidu.com/item/NAT%E7%A9%BF%E8%B6%8需要资源一台公网服务器（可以通过IP直接访问树莓派（也可以是电脑，以树莓派为例安装本文以frp v 0.13.0为例（具体版本可以自己定，但不保证其他版本能够成功）。笔者在go 1.7.4版本下编译frp ... Read More

ZigZag Conversion(math)

QuestioThe string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibilityP A H A P L S I I Y I And then read line by line:"PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of rowsstring convert(string text, int nRows);convert("PAYPALISH... Read More

PHP Internals Book 中文版 – Zvals – 基础结构

基础结构一个zval（“Zend value”的缩写）代表一个任意类型的PHP变量。所以，它很可能是PHP中最重要的数据结构，同时你将会频繁地使用它。本章节讲述zvals的基础概念及其使用方法。类型和值每一个zval都会存储某个值和其对应的类型。这点非常重要，因为PHP是一门动态类型语言，所以变量的类型只有当运行时才会确定，并不是在编译时就能够确定。此外，zval的类型在其生命周期是可以改变的，所以如果这个zval在最初存储了一个整形，那么在之后的某个时间点他也可能会存储了一个字符串。 类型是存储在一个整形的标签中（一个 unsigned char 类型的变量）。它有8中类型的值，分别对应着PHP中的8中变量类型。这些值可以用诸如IS_TYPE形式的常量来使用。比如：IS_NULL对应null类型，IS_STRING对应字符串类型。真实的值是存储在一个联合体中，如下所示typedef union _zvalue_value ... Read More