2018年度回忆与总结 – 算法

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

动态规划与分治法的思考

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

分治法与回溯法的思考

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

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

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

[LeetCode]743. Network Delay Time

原题There areNnetwork nodes, labelled1toN.Giventimes, a list of travel times asdirectededgestimes[i] = (u, v, w), whereuis the source node,vis the target node, andwis the time it takes for a signal to travel from source to target.Now, we send a signal from a certain nodeK. How long will it take for all nodes to receive the signal? If it is impossible, return-1.NoteNwill be in the range[1, 100].Kwil... 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

[LeetCode]Sum of Subarray Minimums

原题Given an array of integersA, find the sum ofmin(B), whereBranges overevery (contiguous) subarray ofA.Since the answer may be large,return the answer modulo10^9 + 7.Example 1Input: [3,1,2,4Output: 1Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.Note1 <= A.length <= 300001 <= A[i] <题解首先明确题... Read More

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

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

2017年度回忆与总结 – 心态

写在前面在写之前,我注意到标题中的词语,描写的到底是2017年还是2018年?想想,应该是总结2017的过往之后,对2018年的期望。一年一次的总结是否应该详细些呢?不!因为我觉得,大篇幅的总结并没有太大的价值。首先,并没有谁会在乎我在2017年里的细节。其次,有价值的总结并非在于字数之多。在这里也明确下本篇及以后“年度总结”内容范围,仅包含个人在工作、专业能力、职业及其相关方面的内容。工作2017年2月14号入职滴滴,这一年在工作上做得最多的就是努力地熟悉业务。的确,滴滴的业务发展快速,产品不断地迭代与重构。通过逐渐地参与产品的研发、维护工作,意思到要了解和学习的东西还有很多。也正是因为这一过程,熟知了滴滴相关的业务,培养了研发与维护的能力,提升了自信心。考研在2016年的总结中,并没有列出这一计划。但却是,我觉得比较重要的一件事情。目前为止,能否考入仍未有结果。所以,单就此过程来谈谈感... 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

从小白到机器学习算法工程师,我做了哪些准备?

一、方向选择都说选择比努力重要,这个鸡汤我觉得可以干了。起初接触人工智能领域是在硕士选择导师的时候,当时民叔推荐来到人工智能与机器人研究所,跟随现在的硕导做图像处理方面的研究,用到一些机器学习的算法做分类工作。在学校学习平台比较重要,它决定了你会见识什么人、什么样的黑科技、什么样的应用等,没有这些东西勾起你的好奇心,也就没有对未来的规划或者说期待。硕士期间,养成了看论文的习惯,专注领域顶级期刊论文,当然了首先是先把自己研究的课题相关知识看的透彻,这个在第二小节中会介绍:为什么硕士课题很重要。一些我认识是牛人的人说,看论文是在跟领域大牛在交流,这个确实刚开始体会不到,起初很排斥看论文,更加上我的英语那是一个...后来看多了,发现知识之间都是相通的,可能解决一个问题用的是同一个方法,这样看一篇论文的时间会大大缩短,有效率了,心里便更愿意去看论文。康奈尔大学图书馆网站每天更新世界上各个大牛写的论... 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