Wang Yiran

介绍 动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20 世纪 50 年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。(来自百度百科) 简单来说，就是把问题分成多个阶段，每个阶段都符合一个式子（状态转移），后面阶段的状态（结果）一般可以由前面阶段的状态（结果）转移而来。 找出状态转移方程，动态规划已经成功了 90%。使用动态规划求解时，最关键的是找出状态转移方程，而想要找出状态转移方程，首先要对问题状态有清晰的定义。一般来说，动态规划求解主要包括以下步骤： 划分阶段：把问题划分成子问题，类似于分治法，每个阶段一般是有序的。 定义状态：每个阶段，都有属于自己的最优状态，每一个阶段的最优状态，可以从前面阶段的最优状态中转化获得。 状态转化：不同阶段之间的转化关系， ...

介绍贪心算法，总是在对问题求解的时候作出局部当前最优的选择，须注意的是，当前的状态不会受到以后的状态/阶段选择的影响，只和当前的状态有关。求解贪心算法的基本思路如下： 建立数学模型来描述问题。 将求解的问题分解成为若干个小问题。 每次对小问题求解，总是得到子问题的局部最优解。 将每一次局部最优解合并，就是整体最优解。 但是贪心算法也有自己的缺陷： 不能保证最后求得的是最佳解法。 不能用来求解最大值或者最小值。 柠檬水找零问题描述在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。 求解思路主要的思路是不断地将金额和纸币面额按照从大到小对比，如果金额大于纸币面额，那么就计算该面额纸币的张数。然后剩下的用更小的面额对比即可。 /** * @param {number[]} bills * @return { ...

原理简介回溯法，又名试探法，是一种优选搜索算法，可以理解为试探性搜索算法。在搜索到某一步的时候，如果发现不能满足条件，那么就退回到上一步，在上一步重新选择。 回溯法是以深度优先方式来搜索问题的解，也就是里面的每一步可以理解为一个结点，这些步骤串起来就是一棵树，也就是解空间树。比如第一步只有 1 种做法，第二步有 4 种做法，那么第二步选择一种尝试之后，如果匹配，会假设当前步骤没有问题，继续往第 3 步深入探索，而不是先尝试第二步的其他选择。 当搜索解空间树中的任何一个结点的时候，判断该结点是不是包含问题的解。 如果不包含，那么就把当前的结点以及剩下的节点步骤全部抛弃（也称为剪枝），然后往上一层的结点回溯，也就是退回上一步重新选择（之前的选择走不通）。 如果包含，说明当前结点是可能获取到解的，继续进入下一层子树进行深度优先搜索。 8皇后问题问题描述八皇后问题，是一个著名的学习回溯法的案例，时间退回到 1848 年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题：在 8 × 8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有 ...

二分查找问题描述有一长数组，其中的数字都有序，现在给一个数字，要你从该数组中找出该数的索引值，如果数字不存在，则返回 -1。 求解思路先初始化边界，low 为左边界，high 为右边界，datas 为数组，target 为要查找的目标值，执行下面循环： 如果 low <= high，取出中间值 mid= low + (high-low)/2，然后用 datas[mid] 和 target 比较： datas[mid]== target：直接返回 mid。 datas[mid]> target：说明 target 可能存在左边区间，high = mid-1，继续循环。 datas[mid]< target：说明 target 可能存在右边区间，low = mid+1，继续循环。 代码实现/** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) ...

介绍树是由 n（n >= 0）个结点组成的有限集合，也可以理解为：树是由根结点和若干子树构成。 有且只有一个特定的结点，称为根结点。 每一个元素称为结点。 除根结点外，其余结点被分成 m（m >= 0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）。 每一个结点，可以拥有多个子树。 平时我们说的最多的是二叉树，也就是每一个结点，最多有两个子结点，也就是左右子结点，并且左右两个子结点是有顺序要求的，不可以随意颠倒。 下面为大家介绍几种二叉树： 满二叉树：每一层的结点，都完全覆盖（全部有值），也就是每一个非叶子结点，都有两个子结点。 完全二叉树：除了最后一层以外，每一层的结点数都达到最大个数，最后一层的结点，都连续并且靠左。（满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树）。 二叉查找树：任意非空结点的左子树如果不为空，则左子树的值小于根结点的值，任意非空结点的右子树如果不为空，则右子树的值大于根结点的值，任意结点的左右子树都是二叉查找树，并且结点的数值互不相等。 树的遍历树的顺序遍历方式，一般有前序，中序，后序遍历： 前序遍历：对于每一个结点， ...

介绍我们此处说的栈，是数据结构中的栈，而不是指系统层面的，系统层面说的栈区（ stack ），是指由编译器自动分配释放，存放函数的参数值，局部变量的值等区域。数据结构里面的栈是限定仅在表尾进行插入或者删除的线性表，所谓的表尾，其实就是我们所称的栈顶，相应的，我们可以称表头为栈底。栈的最重要的特性，是后进先出（Last in first out），也称为 LIFO 结构。 使用两个栈实现队列解题思路栈结构的特性是先进后出，而队列的特性是先进先出，也就是先进来的数据先出去，就像是水管一样，前面的水先流出来。 但是假如我们不想直接使用队列，想用栈实现队列，至少需求多少个栈可以实现一个队列呢？答案是两个，为什么呢？ 因为栈本身是先进后出的，假设我们需要先进先出，那么势必需要另外一个堆栈保存数据。数据进入一个堆栈，出来时是逆序的，但是数据依次进入两个堆栈，出来是正序的。 有两个栈 stack1 和 stack2，如果有新的数据进入，那么我们可以直接 push 到 stack1 中。 如果需要取出数据，那么我们优先取出 stack2 的数据，如果 stack2 里面的数据是空的，那么我们需要把 s ...

翻转句子里的单词问题描述现在有一个小任务，假设有一个字符串 “I love coding”，要求将里面单词的顺序翻转，但是单词内部的字母顺序不变，也就是翻转之后结果为 “coding love I“。 求解思路 将字符串分割成若干个子串。 利用中心对称，将字符串转换成为倒序的。 遍历子串，去掉多余的空格，每个有效的子串后面增加一个空格。 去掉结果最后多余的空格。 代码实现const reverseWords = s => { const arr = s.split(' '); const res = []; for (let i = arr.length - 1; i >= 0; i--) { arr[i] && res.push(arr[i]); } return res.join(' ');}; 寻找最长回文子串问题描述“上海自来水来自海上”，这句话不管是顺着读还是逆着读，都是一样的，这就是回文串。给出一个字符串 s，找 ...

数组在计算机中是以连续空间的形态存在，而链表则是不要求空间连续，每一个元素都保存着下一个元素的地址，使其更加灵活。 约瑟夫环问题问题描述著名的约瑟夫问题：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3… 这样依次报数），数到 m 的 士兵会被淘汰出列，之后的士兵再从 1 开始报数。直到最后剩下一个士兵，求这个士兵的编号。 求解思路假设我们现在需要使用数组解决该问题，用一个数组存在 1，2，3，4，5 … 编号，要求返回最后一个士兵的编号。思路如下 初始化剩下的士兵人数 retainNum 为 n，循环下面的操作，直到全部士兵出圈。 初始化 k = 0，从第一个士兵开始计数，每次遍历到数值不为 -1 的元素，则 k+1，如果 k = M，则说明该士兵需要被淘汰出局，则元素的值置为 -1，淘汰的数量 num + 1，且 k 重新赋值为 0。 遍历数组元素，找到数值不为 -1 的元素，就是最后剩下的士兵。 假设 5 个士兵，数到 3 就淘汰，具体的执行过程如下： 代码实现如下：/** * @param {number ...

R-CNN（Rich feature hierarchies for accurate object detection and semantic segmentation）是最早将深度学习应用于目标检测领域的方法之一，其使用基于候选区域的方法替代滑动窗口来寻找图像中可能存在目标的区域，使用卷积神经网络替代人工设计的特征用于目标特征的提取，然后使用支持向量机（SVM）判断目标类别并使用边框回归（Bounding-Box Regression）修正候选框（Bounding Box）的位置。相较于传统的方法，R-CNN 提高了检测的准确率和面对复杂环境的鲁棒性。 如下图，R-CNN 可以分为以下四个步骤。 使用候选区域方法找出图片中可能存在目标的区域。 将这些区域缩放成相同尺寸输入卷积神经网络，通过网络提取每个区域的特征。 将提取到的特征输入分类器并判别每个特征所属类别。 使用边框回归修正候选框的位置。

介绍在之前的文章中，我们了解到神经网络的输入层中的每个节点都与下一层的每个节点相连接，我们称这种连接方式为全连接（Fully-connected），但是这种全连接方式存在一些明显的缺陷。首先如果使用全连接网络处理图片的话，需要将图像矩阵转换为一列向量，这样就破坏了图像的空间信息。其次假设我们将一张尺寸为 $240\times240\times3$ 的三通道图片作为全连接网络的输入，则在输入层总共需要 172800个权重，如此多的参数需要很大的计算量和时间处理，并且大量的参数还会导致过拟合（模型在训练集上表现好，在测试集上表现差，泛化能力差）。在计算机视觉中广泛应用的卷积神经网络可以用来克服上述问题，在卷积神经网络中我们采取局部连接节点的方式代替全连接的方式，通常一个卷积神经网络由输入层、卷积层，激活层、池化层和全连接层构成。 卷积和卷积核在开始学习卷积神经网络前，我们需要了解卷积和卷积核（Kernel）的相关内容。通常情况下，深度学习中所谓的卷积实际上是互相关操作（在后面的内容中我将用卷积来称呼互相关操作），如下图，两个矩阵的卷积即是将两个矩阵中对应位置的元素相乘再求和，则这两个矩阵的 ...