Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  算法分类

STL中的二分查找

二分查找的原理非常简单,但写出的代码中很容易含有很多Bug,二分查找一文中讲解过如何实现不同类型的二分查找,但是否一定要自己去实现二分查找呢?答案显然是否定的,本文将讲解STL中与二分查找有关函数的具体使用方法及其实现原理。

继续阅读»

STL中链表的排序

STL中的链表使用起来非常方便,但其不能使用标准的排序函数sort,那么怎么对其进行排序呢?其实list自带有sort成员函数,使用的是非递归的归并排序,本文将讲解其排序的基本思想及具体代码实现。

继续阅读»

取石子游戏

取石子是一种很有意思的游戏,一般给你若干堆石子,两个人根据指定规则轮流从中取若干石子,规定最后取光石子玩家获胜,假定双方玩家都采取最优策略,问先手是否有什么必胜策略。这个游戏看似简单,实则蕴含深刻的数学原理,本文将分析几种常见的取石子游戏的玩法。

继续阅读»

最远点对问题

二维平面上有n个点,怎么寻找距离最远的两个?
前面讨论过最近点对的问题,这里研究其相对的问题,虽然题目类似,但思想方法截然不同,本文将使用graham凸包扫描法和旋转卡壳算法进行求解。

继续阅读»

最近点对问题

二维平面上有n个点,怎么寻找距离最近的两个?
本文将实现一种O(nlogn)时间复杂度的分治算法,具体的思想方法参考了编程之美中寻找最近点对一章。

继续阅读»

外部排序

外部排序是指大量数据的排序,通常待排序的数据保存在外存储器上(比如硬盘),待排序的文件无法一次装入内存,需要在内存和硬盘之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,本文将通过具体的代码讲解一个简单的外部排序算法实现。

继续阅读»

短链接算法实现

短链接由于微博的流行变得应用非常广泛,短连接简单来说就是把一个很长的URL地址转化为相对简短的地址而且仍然可以正常使用,如把地址http://noalgo.info/转化为http://t.cn/R74gDvp,当然我这里本来就比较短,不过对于再长的地址也是转化成为相同长度的短链接。
本文将介绍短链接的简介及生成的算法原理,最后提供一个C++版本的短链接生成代码。

继续阅读»

MD5算法原理及实现

MD5(Message Digest Algorithm 5,消息摘要算法第五版)是计算机安全领域广泛使用的一种散列函数,经MD2、MD3和MD4发展而来,可以用于保护信息传输的完整一致性。本文将介绍MD5算法的原理及C++实现,并简单介绍其应用场景。
注意,虽然MD5算法是不可逆的,但是目前其已经被破解了,不再是认为安全的,因为通过多次尝试并进行对比,可能可以得到一个MD5刚好是给定MD5值的串,通过特殊的方法可以加速这种尝试,从而在较快的时间内对其进行破解。

继续阅读»

KM算法

KM算法是求一个二分图在完备匹配下的最大权匹配的算法,该算法是通过给每一个顶点标号将求最大匹配问题转化为求完备匹配的问题。
KM算法是在匈牙利算法基础上实现的,如果还未了解匈牙利算法及二分图相关概念,请先看匈牙利算法这篇文章。
继续阅读»

匈牙利算法

匈牙利算法是解决二分图最大匹配的经典算法,由匈牙利数学家Edmonds提出,核心是通过寻找增广路径以求得最大匹配。
本文将介绍匈牙利算法的思想及原理解释,最后提供一个C++代码实现。

继续阅读»

STL操作总结

  • STL(Standard Template Library,标准模板库)是C++标准不可缺少的一部分,也是我们平时写程序非常实用的工具。
    本文简单总结了若干STL中常用数据结构的用法,包括向量(vector)、栈(stack)、队列(queue)、优先队列(priority queue)、映射(map)、集合(set)等,供使用时快速参考。详细的内容参考STL手册。

    继续阅读»

  • 我的博客

    NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

    站内搜索

    最新评论