Liano-Blog

算法解释动态规划（Dynamic Programming, DP）在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间 通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。同时，我们也可以对动态规划进行空间压缩，起到节省空间消耗的效果。这一技巧笔者将在之后的题目中介绍。 在一些情况下，动态规划可以看成是带有状态记录（memoization）的优先搜索。状态记录的意思为，如果一个子问题在优先搜索时已经计算过一次，我们可以把它的结果储存下来，之后遍历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的，即先解决子问题，再解决父问题；而用带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索到同一个 ...

算法解释搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。 在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。 深度优先搜索深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。 考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，那么按照优先向着“深”的方向前进的策略，假如我们使用递归实现，我们的遍历过程为 1（起始节点）->2（遍历更深一层的左子节点）->4（遍历更深一层的左子节点）->2（无子节点，返回父结点）->1（子节点均已完成遍历，返回父结点）->3（遍历更深一层的右子节点）->1（无子节点，返回父结点）->结束程序（子节点均已完成遍历）。如果我们使用栈实现， ...

常用排序算法以下是一些最基本的排序算法。虽然在 C++ 里可以通过 std::sort() 快速排序，而且刷题时很少需要自己手写排序算法，但是熟习各种排序算法可以加深自己对算法的基本理解，以及解出由这些排序算法引申出来的题目。 快速排序采用左闭右开的二分写法，代码模板如下： 123456789101112131415161718192021void quick_sort(vector<int> &nums, int l, int r) { //特殊情况，没有数或只有一个数，无需排序，直接返回 if (l + 1 >= r) return; //取区间左端点值为排序对象，目标是比它大的都在右边，比它小的都在左边 int first = l, last = r - 1, key = nums[first]; while (first < last) { //寻找比key小的，往前调 while(first < last && nums[last] ...

算法解释二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复杂度为 O(log n)。二分查找适用对象必须是排好序的数组。 具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍，第一是尝试熟练使用一种写法，比如左闭右开（满足 C++、Python 等语言的习惯）或左闭右闭（便于处理边界条件），尽量只保持这一种写法；第二是在做题时思考如果最后区间只剩下一个数或者两个数，自己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。 二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题，指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。 求开方x 的平方根题面题解给你一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。 注意：不允许使用任何内置指数函数和算符，例如 pow ...

算法解释双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。 若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索。 若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。 对于 C++ 语言，指针还可以玩出很多新的花样。一些常见的关于指针的操作如下： 指针与常量 int x;int *p1 = &x; // 指针可以被修改，值也可以被修改const int *p2 = &x; // 指针可以被修改，值不可以被修改（const int）int *const p3 = &x; // 指针不可以被修改（*const），值可以被修改const int *const p4 = &x; // 指针不可以被修改，值也不可以被修改 指针函数与函数指针 // addition是指针函数，一个返回类型是指针的函数int* addition(int a, int b) { int *sum = new int(a + b); return sum ...

分配问题分发饼干题面题解假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 示例 1: 输入: g = [1,2,3], s = [1,1]输出: 1 示例 2: 输入: g = [1,2], s = [1,2,3]输出: 2 两种角度，一，从小孩角度，先满足胃口小的，把大于且最接近的饼干分配给他；二，从饼干角度，先分配分量大的饼干给胃口小于且最接近的孩子。将两数组分别排序，遍历比较即可实现。 思考：为什么小孩要先满足胃口小的，饼干要先分配大的？试一试。 代码 角度一：1234567891011int findContentChildren(vector<int>& children ...

vector介绍特性动态数组，可随时添加或删除元素，头文件 #include<vector> 初始化12345678910111213141516171819// 一维初始化vector<int> a;vector<node> c; // node为结构体类型// 定长初始化，可以作为普通数组使用vector<int> a(n);vector<int> b(n, 1); // n为长度，1为初值// 枚举初始化vector<int> a{1, 2, 3};// 拷贝初始化vector<int> a(n, 1);vector<int> b(a); // b = a// 二维初始化vector<int> v[5]; // 固定第一维vector<vector<int>> v;vector<vector<int>> a(n, vector<int>(m, 0)); // m 行 n 列 函数 代码 功 ...

STL 函数accumulate accumulate(begin, end, init) 复杂度：O(N) 对序列元素求和，begin 和 end 是始末位置的迭代器（左闭右开），init 是加上的初始值。返回求和结果，数据类型与 init 相同。 基础累加求和 12345int a[]={1,3,5,9,10};//对[0,2]区间求和，初始值为0，结果为0+1+3+5=9int res1 = accumulate(a, a + 3, 0);//对[0,3]区间求和，初始值为5，结果为5+1+3+5+9=23int res2 = accumulate(a, a + 4, 5); 自定义二元对象求和 使用 lamda表达式 1234567891011typedef long long ll;struct node { ll num;} st[10];for(int i = 1; i <= n; i++) st[i].num = i + 10000000000;//返回值类型与init一致，同时注意参数类型（a）也要一样/ ...