背包问题(Knapsack Problem)是指给定一个容量固定为W的背包和一组数量为n的物品,每个物品的重量为wi,价值为vi,要求从物品中选择若干放入背包,使总物品重量不超过背包容量,并且使价值最大。这是动态规划的一类非常典型的问题。
贪心算法简介
贪心算法(Greedy Algorithm),又可称作贪婪算法,简称贪心,它是一指一种决策策略,依据统一的规则,在局部选择最优解,继而成为全局最优解。最经典的问题就是一类最短路径问题,从当前节点选择离它最近的节点,然后继续,到达目标节点后这一路径就是全局最短路径(这是Dijkstra算法);再如可分割的背包问题,物品有不同的重量和价值,但物品可分割,这也是贪心算法的经典应用案例。
树状树组简介
树状数组,即Binary Indexed Tree,简单来理解就是用数组来表示一颗树,它的实际存储结构是数组,但元素之间的逻辑关系是树。通常用于解决区间问题和快速计算前缀和的问题。
Introduction to Trie
回溯算法从入门到精通
回溯(Backtracking)是指在求解的过程中,不断的试探每一步的所有可能的解,如果发现不符合要求,就回退到最初的状态,尝试另外一种可能,直到所有的可能的解都找到。它与DFS的思想是一致的。
BFS and DFS Made Easy
双指针总结
Binary Search Made Easy
二分查找 Binary Search是效率特别高的一种算法,它能将线性复杂度O(n)降低到对数级别O(logn)。但它对输入数据有要求,比如对于数组来说必须是排序的,否则是不能应用二分的。今天就来理解一下二分查找,然后总结常见的题目和注意事项。