稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

彻底搞懂背包问题

背包问题Knapsack Problem)是指给定一个容量固定为W的背包和一组数量为n的物品,每个物品的重量为wi,价值为vi,要求从物品中选择若干放入背包,使总物品重量不超过背包容量,并且使价值最大。这是动态规划的一类非常典型的问题。

贪心算法简介

贪心算法(Greedy Algorithm),又可称作贪婪算法,简称贪心,它是一指一种决策策略,依据统一的规则,在局部选择最优解,继而成为全局最优解。最经典的问题就是一类最短路径问题,从当前节点选择离它最近的节点,然后继续,到达目标节点后这一路径就是全局最短路径(这是Dijkstra算法);再如可分割的背包问题,物品有不同的重量和价值,但物品可分割,这也是贪心算法的经典应用案例。

Introduction to Trie

字典树Trie(发音与try一样),也叫前缀树,是在一个树状数据结构中存储一个字典中的所有单词,以快速的实现前缀搜索和单词搜索的数据结构。前缀树是一个多叉树,每个节点会有多个子节点,具体子节点 数量取决于字符集的大小,除了根节点以外,每个节点代表字典中的一个字符,从根节点开始的路径代表着一个前缀或者一个单词。

回溯算法从入门到精通

回溯(Backtracking)是指在求解的过程中,不断的试探每一步的所有可能的解,如果发现不符合要求,就回退到最初的状态,尝试另外一种可能,直到所有的可能的解都找到。它与DFS的思想是一致的。

BFS and DFS Made Easy

广度优先搜索和深度优先搜索在二维数据结构中(树,图和矩阵)有着非常重要和广泛的应用,今天就来好好的学习,理解和总结一下这两种遍历方法。

双指针总结

双指针是指用两个引用或者索引,或者某种键为主的操作手段,在很多场景有重要的应用,比如链表。有些时候还能成为比较巧妙的解题手段。今天就来总结一下双指针的使用。

Binary Search Made Easy

二分查找 Binary Search是效率特别高的一种算法,它能将线性复杂度O(n)降低到对数级别O(logn)。但它对输入数据有要求,比如对于数组来说必须是排序的,否则是不能应用二分的。今天就来理解一下二分查找,然后总结常见的题目和注意事项。

线段树让你不再惧怕区间问题

线段树是用于求解序列区间问题的高效的数组结构,它是以完全二叉树形式来把序列划分为不同的区间,进而把O(n)复杂度提升到O(logn)。

线段树与树状数组有些类似,都可以用于解决区间问题,但线段树更具体普适性,树状数组能解决的问题线段树都可以解决,但反之不然。树状数组的学习可以参考另外一篇文章

编码常见技巧总结

在日常编码中有一些非常常用,但却很细节的小技巧,虽然有朴素的实现的方式,但如果能掌握一些高级技巧不但性能会更好,并且因为技巧比较流行,也不会影响可读性。最简单的例子就是除2和乘2,当然可以直接用乘法和除法,但如果用移位效果更好,也并不影响可读性,因为这是比较流行的做法。

这里就将总结一些常用的小技巧,以供日后查阅。