95的算法都是基于这6种算法思想

　　写在前面
　　因为本次文章篇幅较长，所以为了便利大家查看今日最新职位信息，所以将内容上移至顶部，忘各位大大海涵
　　职位
　　要求算法交易工程师
　　薪资：20k40k
　　工作位置：上海1。有进行算法开发的经验，有股票，期货等金融行业基本知识，了解经典量化策略加分；
　　2。知名院校本科及以上学历，计算机、物理、数学、统计等相关理工类专业；05年工作经验
　　3。CRustGoPython至少一种语言的多年工作经验；
　　4。团队的技术栈未来会以Rust为主；
　　5。优秀的数据结构和算法基础；6。有高频交易相关工作经验，工程或者策略加分。量化研究员
　　薪资：20k40k
　　工作位置：上海1。硕士及以上学历，03年工作经验，统计、金融工程、数学、物理、计算机等相关专业优先。
　　2。拥有股票多因子、CTA策略研究、机器学习、深度学习项目中的一种或多种经验。
　　3。具备扎实的数理逻辑能力和统计学基础。高中阶段理科竞赛、各类大学生建模竞赛及机器学习竞赛中有获奖经历者优先。
　　4。具备扎实的编程能力，熟练使用python进行数据处理、数据分析和策略开发。熟练掌握CLinuxRust者优先。
　　5。对量化策略研究有浓厚兴趣，热爱探索，注重细节。量化研发工程师
　　薪资：20k40k
　　工作城市：上海1。统招本科或以上学历，具备扎实的编程基础和数据结构算法基础，优秀的编程能力和问题解决能力；
　　2。对经验不设要求，应届生也考虑，具备核心业务系统或负责业务系统架构设计开发经验加分；
　　3。对工程化有较好理解，对网络、自动化测试、安全、性能有较好理解；
　　4。不对目前使用语言过多要求，热爱技术、喜欢钻研技术、持续学习成长；
　　投递方式
　　通过FreemenAPP选择城市并搜索职位名称
　　算法思想是解决问题的核心，万丈高楼起于平地，在算法中也是如此，95的算法都是基于这6种算法思想，结下了介绍一下这6种算法思想，帮助你理解及解决各种算法问题。1递归算法
　　1。1算法策略
　　递归算法是一种直接或者间接调用自身函数或者方法的算法。
　　递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。
　　优缺点：优点：实现简单易上手缺点：递归算法对常用的算法如普通循环等，运行效率较低；并且在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归太深，容易发生栈溢出
　　1。2适用场景
　　递归算法一般用于解决三类问题：数据的定义是按递归定义的。（斐波那契数列）问题解法按递归算法实现。（回溯）数据的结构形式是按递归定义的。（树的遍历，图的搜索）
　　递归的解题策略：第一步：明确你这个函数的输入输出，先不管函数里面的代码什么，而是要先明白，你这个函数的输入是什么，输出为何什么，功能是什么，要完成什么样的一件事。第二步：寻找递归结束条件，我们需要找出什么时候递归结束，之后直接把结果返回第三步：明确递归关系式，怎么通过各种递归调用来组合解决当前问题
　　1。3使用递归算法求解的一些经典问题斐波那契数列汉诺塔问题树的遍历及相关操作
　　DOM树为例
　　下面以以DOM为例，实现一个document。getElementById功能
　　由于DOM是一棵树，而树的定义本身就是用的递归定义，所以用递归的方法处理树，会非常地简单自然。
　　第一步：明确你这个函数的输入输出
　　从DOM根节点一层层往下递归，判断当前节点的id是否是我们要寻找的iddcal
　　输入：DOM根节点document，我们要寻找的iddcal
　　输出：返回满足idsisteran的子结点functiongetElementById（node，id）｛｝
　　第二步：寻找递归结束条件
　　从document开始往下找，对所有子结点递归查找他们的子结点，一层一层地往下查找：如果当前结点的id符合查找条件，则返回当前结点如果已经到了叶子结点了还没有找到，则返回nullfunctiongetElementById（node，id）｛当前结点不存在，已经到了叶子结点了还没有找到，返回nullif（！node）returnnull当前结点的id符合查找条件，返回当前结点if（node。idid）returnnode｝
　　第三步：明确递归关系式
　　当前结点的id不符合查找条件，递归查找它的每一个子结点functiongetElementById（node，id）｛当前结点不存在，已经到了叶子结点了还没有找到，返回nullif（！node）returnnull当前结点的id符合查找条件，返回当前结点if（node。idid）returnnode前结点的id不符合查找条件，继续查找它的每一个子结点for（vari0；inode。childNodes。length；i）｛递归查找它的每一个子结点varfoundgetElementById（node。childNodes〔i〕，id）；if（found）returnfound；｝returnnull；｝
　　就这样，我们的一个document。getElementById功能已经实现了：functiongetElementById（node，id）｛if（！node）returnnull；if（node。idid）returnnode；for（vari0；inode。childNodes。length；i）｛varfoundgetElementById（node。childNodes〔i〕，id）；if（found）returnfound；｝returnnull；｝getElementById（document，dcal）；
　　最后在控制台验证一下，执行结果如下图所示：
　　使用递归的优点是代码简单易懂，缺点是效率比不上非递归的实现。Chrome浏览器的查DOM是使用非递归实现。非递归要怎么实现呢？
　　如下代码：functiongetByElementId（node，id）｛遍历所有的Nodewhile（node）｛if（node。idid）returnnode；nodenextElement（node）；｝returnnull；｝
　　还是依次遍历所有的DOM结点，只是这一次改成一个while循环，函数nextElement负责找到下一个结点。所以关键在于这个nextElement如何实现非递归查找结点功能：深度遍历functionnextElement（node）｛先判断是否有子结点if（node。children。length）｛有则返回第一个子结点returnnode。children〔0〕；｝再判断是否有相邻结点if（node。nextElementSibling）｛有则返回它的下一个相邻结点returnnode。nextElementSibling；｝否则，往上返回它的父结点的下一个相邻元素，相当于上面递归实现里面的for循环的i加1while（node。parentNode）｛if（node。parentNode。nextElementSibling）｛returnnode。parentNode。nextElementSibling；｝nodenode。parentNode；｝returnnull；｝
　　在控制台里面运行这段代码，同样也可以正确地输出结果。不管是非递归还是递归，它们都是深度优先遍历，这个过程如下图所示。
　　实际上getElementById浏览器是用的一个哈希map存储的，根据id直接映射到DOM结点，而getElementsByClassName就是用的这样的非递归查找。
　　参考：我接触过的前端数据结构与算法2分治算法
　　2。1算法策略
　　在计算机科学中，分治算法是一个很重要的算法，快速排序、归并排序等都是基于分治策略进行实现的，所以，建议理解掌握它。
　　分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为阿子问题解的合并。
　　2。2适用场景
　　当出现满足以下条件的问题，可以尝试只用分治策略进行求解：原始问题可以分成多个相似的子问题子问题可以很简单的求解原始问题的解是子问题解的合并各个子问题是相互独立的，不包含相同的子问题
　　分治的解题策略：第一步：分解，将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题第二步：解决，解决各个子问题第三步：合并，将各个子问题的解合并为原问题的解
　　2。3使用分治法求解的一些经典问题二分查找归并排序快速排序汉诺塔问题React时间分片
　　二分查找
　　也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。
　　第一步：分解
　　每次猜拳都把上一次的结果分出大的一组和小的一组，两组相互独立选择数组中的中间数functionbinarySearch（items，item）｛low、mid、high将数组分成两组varlow0，highitems。length1，midMath。floor（（lowhigh）2），elemitems〔mid〕。。。｝
　　第二步：解决子问题
　　查找数与中间数对比比中间数低，则去中间数左边的子数组中寻找；比中间数高，则去中间数右边的子数组中寻找；相等则返回查找成功while（lowhigh）｛if（elemitem）｛比中间数高lowmid1｝elseif（elemitem）｛比中间数低highmid1｝else｛相等returnmid｝｝
　　第三步：合并functionbinarySearch（items，item）｛varlow0，highitems。length1，mid，elemwhile（lowhigh）｛midMath。floor（（lowhigh）2）elemitems〔mid〕if（elemitem）｛lowmid1｝elseif（elemitem）｛highmid1｝else｛returnmid｝｝return1｝
　　最后，二分法只能应用于数组有序的情况，如果数组无序，二分查找就不能起作用了functionbinarySearch（items，item）｛快排quickSort（items）varlow0，highitems。length1，mid，elemwhile（lowhigh）｛midMath。floor（（lowhigh）2）elemitems〔mid〕if（elemitem）｛lowmid1｝elseif（elemitem）｛highmid1｝else｛returnmid｝｝return1｝测试vararr〔2，3，1，4〕binarySearch（arr，3）2binarySearch（arr，5）1
　　测试成功
　　3贪心算法
　　3。1算法策略
　　贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。
　　某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。
　　3。2适用场景
　　在日常生活中，我们使用到贪心算法的时候还是挺多的，例如：
　　从100章面值不等的钞票中，抽出10张，怎样才能获得最多的价值？
　　我们只需要每次都选择剩下的钞票中最大的面值，最后一定拿到的就是最优解，这就是使用的贪心算法，并且最后得到了整体最优解。
　　但是，我们任然需要明确的是，期望通过局部的最优选择获得整体的最优选择，仅仅是期望而已，也可能最终得到的结果并不一定不能是整体最优解。
　　例如：求取A到G最短路径：
　　根据贪心算法总是选择当前最优选择，所以它首先选择的路径是AB，然后BE、EG，所得到的路径总长为15410，然而这并不是最短路径，最短路径为ACG：224，所以说，贪心算法得到得并不一定是最优解。
　　那么一般在什么时候可以尝试选择使用贪心算法喃？
　　当满足一下条件时，可以使用：原问题复杂度过高求全局最优解的数学模型难以建立或计算量过大没有太大必要一定要求出全局最优解，比较优就可以
　　如果使用贪心算法求最优解，可以按照以下步骤求解：首先，我们需要明确什么是最优解（期望）然后，把问题分成多个步骤，每一步都需要满足：
　　可行性：每一步都满足问题的约束
　　局部最优：每一步都做出一个局部最优的选择不可取消：选择一旦做出，在后面遇到任何情况都不可取消最后，叠加所有步骤的最优解，就是全局最优解
　　3。3经典案例：活动选择问题
　　使用贪心算法求解的经典问题有：最小生成树算法单源最短路径的Dijkstra算法Huffman压缩编码背包问题活动选择问题等
　　其中活动选择问题是最简单的，这里详细介绍这个。
　　活动选择问题是《算法导论》上的例子，也是一个非常经典的问题。有n个活动（a1，a2，，an）需要使用同一个资源（例如教室），资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和结束时间fi。一旦被选择后，活动ai就占据半开时间区间〔si，fi）。如果〔si，fi）和〔sj，fj）互不重叠，ai和aj两个活动就可以被安排在这一天。
　　该问题就是要安排这些活动，使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
　　共有7个活动，它们在18个小时内需要占用的时间如上图，如何选择活动，能让这间教室利用率最高喃（能够举行更多的活动）？
　　贪心算法对这种问题的解决很简单的，它开始时刻开始选择，每次选择开始时间与与已选择活动不冲突的，结束时间又比较靠前的活动，这样会让剩下的时间区间更长。
　　首先a1活动的结束时间最早，选择a1活动a1结束后，a2有时间冲突，不可选择，a3、a4都可选择，但a4结束时间最早，选择a4依次选择时间没有冲突的，又结束时间最早的活动
　　最终选择活动为a1，a4，a5，a7。为最优解。
　　4回溯算法
　　4。1算法策略
　　回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。
　　4。2适用场景
　　回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。
　　4。3使用回溯算法的经典案例深度优先搜索01背包问题正则表达式匹配八皇后数独全排列
　　等等，深度优先搜索我们在图那一章已经介绍过，这里以正则表达式匹配为例，介绍一下
　　正则表达式匹配varstringabbc
　　varregexab｛1，3｝c
　　console。log（string。match（regex））
　　〔abbc，index：0，input：abbc，groups：undefined〕
　　它的匹配过程：
　　在第5步匹配失败，此时b｛1，3｝已经匹配到了两个b正在尝试第三个b，结果发现接下来是c。此时就需要回溯到上一步，b｛1，3｝匹配完毕（匹配到了bb），然后再匹配c，匹配到了c匹配结束。
　　5动态规划
　　5。1算法策略
　　动态规划也是将复杂问题分解成小问题求解的策略，与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。
　　所以，动态规划适用于子问题重叠的情况，即不同的子问题具有公共的子子问题，在这种情况下，分治策略会做出很多不必要的工作，它会反复求解那些公共子子问题，而动态规划会对每个子子问题求解一次，然后保存在表格中，如果遇到一致的问题，从表格中获取既可，所以它无需求解每一个子子问题，避免了大量的不必要操作。
　　5。2适用场景
　　动态规划适用于求解最优解问题，比如，从面额不定的100个硬币中任意选取多个凑成10元，求怎样选取硬币才可以使最后选取的硬币数最少又刚好凑够了10元。这就是一个典型的动态规划问题。它可以分成一个个子问题（每次选取硬币），每个子问题又有公共的子子问题（选取硬币），子问题之间相互关联（已选取的硬币总金额不能超过10元），边界条件就是最终选取的硬币总金额为10元。
　　针对上例，也许你也可以说，我们可以使用回溯算法，不断的去试探，但回溯算法是使用与求解广度的解（满足要求的解），如果是用回溯算法，我们需要尝试去找所有满足条件的解，然后找到最优解，时间复杂度为O（2n），这性能是相当差的。大多数适用于动态规划的问题，都可以使用回溯算法，只是使用回溯算法的时间复杂度比较高而已。
　　最后，总结一下，我们使用动态规划求解问题时，需要遵循以下几个重要步骤：定义子问题实现需要反复执行解决的子子问题部分识别并求解出边界条件
　　5。3使用动态规划求解的一些经典问题爬楼梯问题：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？背包问题：给出一些资源（有总量及价值），给一个背包（有总容量），往背包里装资源，目标是在背包不超过总容量的情况下，装入更多的价值硬币找零：给出面额不定的一定数量的零钱，以及需要找零的钱数，找出有多少种找零方案图的全源最短路径：一个图中包含u、v顶点，找出从顶点u到顶点v的最短路径最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变剩下元素的顺序实现）
　　这里以最长公共子序列为例。
　　爬楼梯问题
　　这里以动态规划经典问题爬楼梯问题为例，介绍求解动态规划问题的步骤。
　　第一步：定义子问题
　　如果用dp〔n〕表示第n级台阶的方案数，并且由题目知：最后一步可能迈2个台阶，也可迈1个台阶，即第n级台阶的方案数等于第n1级台阶的方案数加上第n2级台阶的方案数
　　第二步：实现需要反复执行解决的子子问题部分dp〔n〕dp〔n1〕dp〔n2〕
　　第三步：识别并求解出边界条件第0级1种方案dp〔0〕1第1级也是1种方案dp〔1〕1
　　最后一步：把尾码翻译成代码，处理一些边界情况letclimbStairsfunction（n）｛letdp〔1，1〕for（leti2；in；i）｛dp〔i〕dp〔i1〕dp〔i2〕｝returndp〔n〕｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（n）
　　优化空间复杂度：letclimbStairsfunction（n）｛letres1，n11，n21for（leti2；in；i）｛resn1n2n1n2n2res｝returnres｝
　　空间复杂度：O（1）
　　6枚举算法
　　6。1算法策略
　　枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。
　　6。2解题思路确定枚举对象、枚举范围和判定条件。逐一列举可能的解，验证每个解是否是问题的解。
　　7刷题
　　7。1爬楼梯问题
　　假设你正在爬楼梯。需要n阶你才能到达楼顶。
　　每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
　　注意：给定n是一个正整数。
　　示例1：输入：2输出：2解释：有两种方法可以爬到楼顶。1。1阶1阶2。2阶
　　示例2：输入：3输出：3解释：有三种方法可以爬到楼顶。1。1阶1阶1阶2。1阶2阶3。2阶1阶
　　解法：动态规划
　　动态规划（DynamicProgramming，DP）是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。
　　分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。
　　我们使用动态规划求解问题时，需要遵循以下几个重要步骤：定义子问题实现需要反复执行解决的子子问题部分识别并求解出边界条件
　　第一步：定义子问题
　　如果用dp〔n〕表示第n级台阶的方案数，并且由题目知：最后一步可能迈2个台阶，也可迈1个台阶，即第n级台阶的方案数等于第n1级台阶的方案数加上第n2级台阶的方案数
　　第二步：实现需要反复执行解决的子子问题部分dp〔n〕dp〔n1〕dp〔n2〕
　　第三步：识别并求解出边界条件第0级1种方案dp〔0〕1第1级也是1种方案dp〔1〕1
　　最后一步：把尾码翻译成代码，处理一些边界情况letclimbStairsfunction（n）｛letdp〔1，1〕for（leti2；in；i）｛dp〔i〕dp〔i1〕dp〔i2〕｝returndp〔n〕｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（n）
　　优化空间复杂度：letclimbStairsfunction（n）｛letres1，n11，n21for（leti2；in；i）｛resn1n2n1n2n2res｝returnres｝
　　空间复杂度：O（1）
　　7。2使用最小花费爬楼梯
　　数组的每个索引作为一个阶梯，第i个阶梯对应着一个非负数的体力花费值cost〔i〕（索引从0开始）。
　　每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
　　您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为0或1的元素作为初始阶梯。
　　示例1：输入：cost〔10，15，20〕输出：15解释：最低花费是从cost〔1〕开始，然后走两步即可到阶梯顶，一共花费15。
　　示例2：输入：cost〔1，100，1，1，1，100，1，1，100，1〕输出：6解释：最低花费方式是从cost〔0〕开始，逐个经过那些1，跳过cost〔3〕，一共花费6。
　　注意：cost的长度将会在〔2，1000〕。每一个cost〔i〕将会是一个Integer类型，范围为〔0，999〕。
　　解法：动态规划
　　本题注意理解题意：第i级台阶是第i1级台阶的阶梯顶部。踏上第i级台阶花费cost〔i〕，直接迈一大步跨过而不踏上去则不用花费。楼梯顶部在数组之外，如果数组长度为len，那么楼顶就在下标为len
　　第一步：定义子问题
　　踏上第i级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：最后迈1步踏上第i级台阶：dp〔i1〕cost〔i〕最后迈1步踏上第i级台阶：dp〔i2〕cost〔i〕
　　第二步：实现需要反复执行解决的子子问题部分
　　所以踏上第i级台阶的最小花费为：dp〔i〕min（dp〔i2〕，dp〔i1〕）cost〔i〕
　　第三步：识别并求解出边界条件第0级cost〔0〕种方案dp〔0〕cost〔0〕第1级，有两种情况1：分别踏上第0级与第1级台阶，花费cost〔0〕cost〔1〕2：直接从地面开始迈两步直接踏上第1级台阶，花费cost〔1〕dp〔1〕min（cost〔0〕cost〔1〕，cost〔1〕）cost〔1〕
　　最后一步：把尾码翻译成代码，处理一些边界情况letminCostClimbingStairsfunction（cost）｛cost。push（0）letdp〔〕，ncost。lengthdp〔0〕cost〔0〕dp〔1〕cost〔1〕for（leti2；in；i）｛dp〔i〕Math。min（dp〔i2〕，dp〔i1〕）cost〔i〕｝returndp〔n1〕｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（n）
　　优化：letminCostClimbingStairsfunction（cost）｛letncost。length，n1cost〔0〕，n2cost〔1〕for（leti2；in；i）｛lettmpn2n2Math。min（n1，n2）cost〔i〕n1tmp｝returnMath。min（n1，n2）｝；时间复杂度：O（n）空间复杂度：O（1）
　　更多解答
　　7。3最大子序和
　　给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
　　示例：输入：〔2，1，3，4，1，2，1，5，4〕输出：6解释：连续子数组〔4，1，2，1〕的和最大，为6。
　　进阶：
　　如果你已经实现复杂度为O（n）的解法，尝试使用更为精妙的分治法求解。
　　第一步：定义子问题
　　动态规划是将整个数组归纳考虑，假设我们已经知道了以第i1个数结尾的连续子数组的最大和dp〔i1〕，显然以第i个数结尾的连续子数组的最大和的可能取值要么为dp〔i1〕nums〔i〕，要么就是nums〔i〕单独成一组，也就是nums〔i〕，在这两个数中我们取最大值
　　第二步：实现需要反复执行解决的子子问题部分dp〔n〕Math。max（dp〔n1〕nums〔n〕，nums〔n〕）
　　第三步：识别并求解出边界条件dp〔0〕nums〔0〕
　　最后一步：把尾码翻译成代码，处理一些边界情况
　　因为我们在计算dp〔i〕的时候，只关心dp〔i1〕与nums〔i〕，因此不用把整个dp数组保存下来，只需设置一个pre保存dp〔i1〕就好了。
　　代码实现（优化）：letmaxSubArrayfunction（nums）｛letmaxnums〔0〕，pre0for（constnumofnums）｛if（pre0）｛prenum｝else｛prenum｝maxMath。max（max，pre）｝returnmax｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（1）
　　7。4买卖股票的最佳时机
　　给定一个数组，它的第i个元素是一支给定股票第i天的价格。
　　如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
　　注意：你不能在买入股票前卖出股票。
　　示例1：输入：〔7，1，5，3，6，4〕输出：5解释：在第2天（股票价格1）的时候买入，在第5天（股票价格6）的时候卖出，最大利润615。注意利润不能是716，因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
　　示例2：输入：〔7，6，4，3，1〕输出：0解释：在这种情况下，没有交易完成，所以最大利润为0。
　　解法：动态规划
　　第一步：定义子问题
　　动态规划是将整个数组归纳考虑，假设我们已经知道了i1个股票的最大利润为dp〔i1〕，显然i个连续股票的最大利润为dp〔i1〕，要么就是就是prices〔i〕minprice（minprice为前i1支股票的最小值），在这两个数中我们取最大值
　　第二步：实现需要反复执行解决的子子问题部分dp〔i〕Math。max（dp〔i1〕，prices〔i〕minprice）
　　第三步：识别并求解出边界条件dp〔0〕0
　　最后一步：把尾码翻译成代码，处理一些边界情况
　　因为我们在计算dp〔i〕的时候，只关心dp〔i1〕与prices〔i〕，因此不用把整个dp数组保存下来，只需设置一个max保存dp〔i1〕就好了。
　　代码实现（优化）：letmaxProfitfunction（prices）｛letmax0，minpriceprices〔0〕for（leti1；iprices。length；i）｛minpriceMath。min（prices〔i〕，minprice）maxMath。max（max，prices〔i〕minprice）｝returnmax｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（1）
　　7。5回文子串
　　给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
　　具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
　　示例1：输入：abc输出：3解释：三个回文子串：a，b，c
　　示例2：输入：aaa输出：6解释：6个回文子串：a，a，a，aa，aa，aaa
　　提示：输入的字符串长度不会超过1000。
　　解法一：暴力法letcountSubstringsfunction（s）｛letcount0for（leti0；is。length；i）｛for（letji；js。length；j）｛if（isPalindrome（s。substring（i，j1）））｛count｝｝｝returncount｝letisPalindromefunction（s）｛leti0，js。length1while（ij）｛if（s〔i〕！s〔j〕）returnfalseij｝returntrue｝
　　复杂度分析：时间复杂度：O（n3）空间复杂度：O（1）
　　解法二：动态规划
　　一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。其中，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。
　　我们怎么去描述子问题呢？
　　显然，一个子串由两端的i、j指针确定，就是描述子问题的变量，子串s〔i。。。j〕（dp〔i〕〔j〕）是否是回文串，就是子问题。
　　我们用二维数组记录计算过的子问题的结果，从basecase出发，像填表一样递推出每个子问题的解。jaabaiaaba
　　注意：ij，只需用半张表，竖向扫描
　　所以：ij：dp〔i〕〔j〕trueji1s〔i〕s〔j〕：dp〔i〕〔j〕trueji1s〔i〕s〔j〕dp〔i1〕〔j1〕：dp〔i〕〔j〕true
　　即：s〔i〕s〔j〕（ji1dp〔i1〕〔j1〕）：dp〔i〕〔j〕true
　　否则为false
　　代码实现：letcountSubstringsfunction（s）｛constlens。lengthletcount0constdpnewArray（len）for（leti0；ilen；i）｛dp〔i〕newArray（len）。fill（false）｝for（letj0；jlen；j）｛for（leti0；ij；i）｛if（s〔i〕s〔j〕（ji1dp〔i1〕〔j1〕））｛dp〔i〕〔j〕truecount｝else｛dp〔i〕〔j〕false｝｝｝returncount｝
　　代码实现（优化）：
　　把上图的表格竖向一列看作一维数组，还是竖向扫描，此时仅仅需要将dp定义为一维数组即可letcountSubstringsfunction（s）｛constlens。lengthletcount0constdpnewArray（len）for（letj0；jlen；j）｛for（leti0；ij；i）｛if（s〔i〕s〔j〕（ji1dp〔i1〕））｛dp〔i〕truecount｝else｛dp〔i〕false｝｝｝returncount；｝
　　复杂度分析：时间复杂度：O（n2）空间复杂度：O（n）
　　更多解答
　　7。6最长回文子串
　　给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。
　　示例1：输入：babad输出：bab注意：aba也是一个有效答案。
　　示例2：输入：cbbd输出：bb
　　解法：动态规划
　　第1步：定义状态
　　dp〔i〕〔j〕表示子串s〔i。。j〕是否为回文子串，这里子串s〔i。。j〕定义为左闭右闭区间，可以取到s〔i〕和s〔j〕。
　　第2步：思考状态转移方程
　　对于一个子串而言，如果它是回文串，那么在它的首尾增加一个相同字符，它仍然是个回文串dp〔i〕〔j〕（s〔i〕s〔j〕）dp〔i1〕〔j1〕
　　第3步：初始状态：dp〔i〕〔i〕true单个字符是回文串if（s〔i〕s〔i1〕）dp〔i〕〔i1〕true连续两个相同字符是回文串
　　代码实现：constlongestPalindrome（s）｛if（s。length2）returnsres：最长回文子串letress〔0〕，dp〔〕for（leti0；is。length；i）｛dp〔i〕〔i〕true｝for（letj1；js。length；j）｛for（leti0；ij；i）｛if（ji1s〔i〕s〔j〕）｛dp〔i〕〔j〕true｝elseif（s〔i〕s〔j〕dp〔i1〕〔j1〕）｛dp〔i〕〔j〕true｝获取当前最长回文子串if（dp〔i〕〔j〕ji1res。length）｛ress。substring（i，j1）｝｝｝returnres｝
　　复杂度分析：时间复杂度：O（n2）空间复杂度：O（n2）
　　7。7最小路径和
　　给定一个包含非负整数的mxn网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
　　说明：每次只能向下或者向右移动一步。
　　示例1：输入：grid〔〔1，3，1〕，〔1，5，1〕，〔4，2，1〕〕输出：7解释：因为路径13111的总和最小。
　　示例2：输入：grid〔〔1，2，3〕，〔4，5，6〕〕输出：12
　　提示：mgrid。lengthngrid〔i〕。length1m，n2000grid〔i〕〔j〕100
　　1、DP方程当前项最小路径和当前项值上项或左项中的最小值grid〔i〕〔j〕Math。min（grid〔i1〕〔j〕，grid〔i〕〔j1〕）
　　2、边界处理grid的第一行与第一列分别没有上项与左项故单独处理计算起项最小路径和计算第一行：for（letj1；jcol；j）grid〔0〕〔j〕grid〔0〕〔j1〕
　　计算第一列：for（leti1；irow；i）grid〔i〕〔0〕grid〔i1〕〔0〕
　　3、代码实现varminPathSumfunction（grid）｛letrowgrid。length，colgrid〔0〕。lengthcalcboundaryfor（leti1；irow；i）calcfirstcolgrid〔i〕〔0〕grid〔i1〕〔0〕for（letj1；jcol；j）calcfirstrowgrid〔0〕〔j〕grid〔0〕〔j1〕for（leti1；irow；i）for（letj1；jcol；j）grid〔i〕〔j〕Math。min（grid〔i1〕〔j〕，grid〔i〕〔j1〕）returngrid〔row1〕〔col1〕｝；
　　7。8买卖股票的最佳时机II
　　给定一个数组，它的第i个元素是一支给定股票第i天的价格。
　　设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
　　注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
　　示例1：输入：〔7，1，5，3，6，4〕输出：7解释：在第2天（股票价格1）的时候买入，在第3天（股票价格5）的时候卖出，这笔交易所能获得利润514。随后，在第4天（股票价格3）的时候买入，在第5天（股票价格6）的时候卖出，这笔交易所能获得利润633。
　　示例2：输入：〔1，2，3，4，5〕输出：4解释：在第1天（股票价格1）的时候买入，在第5天（股票价格5）的时候卖出，这笔交易所能获得利润514。注意你不能在第1天和第2天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
　　示例3：输入：〔7，6，4，3，1〕输出：0解释：在这种情况下，没有交易完成，所以最大利润为0。
　　提示：1prices。length31040prices〔i〕104
　　解法一：峰底买入，峰顶卖出
　　如图，在第二天买入，第三天卖出，第四天买入，第五天卖出获利最高，此处代码不再赘述，可以自己尝试写一下
　　解法二：贪心算法
　　贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。
　　某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。
　　对应于该题，第一天买入，第二天卖出，，第i天买入，第i1天卖出，如果i天买入第i1天卖出有利润则买入，否则不买
　　第i1天买入第i天卖出获利prices〔i1〕prices〔i〕，我们仅仅需要将prices〔i1〕prices〔i〕的所有正值加起来就是可获取的最大利益
　　代码实现：letmaxProfitfunction（prices）｛letprofit0for（leti0；iprices。length1；i）｛if（prices〔i1〕prices〔i〕）｛profitprices〔i1〕prices〔i〕｝｝returnprofit｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（1）
　　7。9分发饼干
　　假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子i，都有一个胃口值gi，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸sj。如果sjgi，我们可以将这个饼干j分配给孩子i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
　　注意：
　　你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。
　　示例1：输入：〔1，2，3〕，〔1，1〕输出：1解释：你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1，2，3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。
　　示例2：输入：〔1，2〕，〔1，2，3〕输出：2解释：你有两个孩子和三块小饼干，2个孩子的胃口值分别是1，2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2。解法：贪心算法constfindContentChildren（g，s）｛if（！g。length！s。length）return0g。sort（（a，b）ab）s。sort（（a，b）ab）letgi0，si0while（gig。lengthsis。length）｛if（g〔gi〕s〔si〕）gi｝returngi｝
　　7。10分割数组为连续子序列
　　给你一个按升序排序的整数数组num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为3。
　　如果可以完成上述分割，则返回true；否则，返回false。
　　示例1：输入：〔1，2，3，3，4，5〕输出：True解释：你可以分割出这样两个连续子序列：1，2，33，4，5
　　示例2：输入：〔1，2，3，3，4，4，5，5〕输出：True解释：你可以分割出这样两个连续子序列：1，2，3，4，53，4，5
　　示例3：输入：〔1，2，3，4，4，5〕输出：False
　　提示：输入的数组长度范围为〔1，10000〕
　　解法：贪心算法
　　从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为3），剔除之后，依次往后遍历：判断当前元素是否能够拼接到前一个满足条件的连续子序列上，可以的话，则拼接如果不可以，则判断以当前元素开始能否构成连续子序列（长度为3），可以的话，则剔除连续子序列否则，返回falseconstisPossiblefunction（nums）｛letmaxnums〔nums。length1〕arr：存储原数组中数字每个数字出现的次数tail：存储以数字num结尾的且符合题意的连续子序列个数letarrnewArray（max2）。fill（0），tailnewArray（max2）。fill（0）for（letnumofnums）｛arr〔num〕｝for（letnumofnums）｛if（arr〔num〕0）continueelseif（tail〔num1〕0）｛tail〔num1〕tail〔num〕｝elseif（arr〔num1〕0arr〔num2〕0）｛arr〔num1〕arr〔num2〕tail〔num2〕｝else｛returnfalse｝arr〔num〕｝returntrue｝
　　复杂度分析：时间复杂度：O（n）空间复杂度：O（n）
　　7。11全排列问题
　　给定一个没有重复数字的序列，返回其所有可能的全排列。
　　示例：输入：〔1，2，3〕输出：〔〔1，2，3〕，〔1，3，2〕，〔2，1，3〕，〔2，3，1〕，〔3，1，2〕，〔3，2，1〕〕
　　解法：回溯算法
　　本题是回溯算法的经典应用场景
　　1。算法策略
　　回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。
　　2。适用场景
　　回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。
　　3。代码实现
　　我们可以写一下，数组〔1，2，3〕的全排列有：先写以1开头的全排列，它们是：〔1，2，3〕，〔1，3，2〕，即1〔2，3〕的全排列；再写以2开头的全排列，它们是：〔2，1，3〕，〔2，3，1〕，即2〔1，3〕的全排列；最后写以3开头的全排列，它们是：〔3，1，2〕，〔3，2，1〕，即3〔1，2〕的全排列。
　　即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
　　这显然是一个递归结构；递归的终止条件是：一个排列中的数字已经选够了，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做depth，或者命名为index，表示当前要确定的是某个全排列中下标为index的那个数是多少；used（object）：用于把表示一个数是否被选中，如果这个数字（num）被选择这设置为used〔num〕true，这样在考虑下一个位置的时候，就能够以O（1）的时间复杂度判断这个数是否被选择过，这是一种以空间换时间的思想。letpermutefunction（nums）｛使用一个数组保存所有可能的全排列letres〔〕if（nums。length0）｛returnres｝letused｛｝，path〔〕dfs（nums，nums。length，0，path，used，res）returnres｝letdfsfunction（nums，len，depth，path，used，res）｛所有数都填完了if（depthlen）｛res。push（〔。。。path〕）return｝for（leti0；ilen；i）｛if（！used〔i〕）｛动态维护数组path。push（nums〔i〕）used〔i〕true继续递归填下一个数dfs（nums，len，depth1，path，used，res）撤销操作used〔i〕falsepath。pop（）｝｝｝
　　4。复杂度分析时间复杂度：O（nn！），其中n为序列的长度这是一个排列组合，每层的排列组合数为：Amnn！（nm）！，故而所有的排列有：A1nA2nAn1nn！（n1）！n！（n2）！n！n！（1（n1）！1（n2）！1）n！（1121412n1）2n！并且每个内部结点循环n次，故非叶子结点的时间复杂度为O（nn！）空间复杂度：O（n）
　　7。12括号生成
　　数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
　　示例：输入：n3输出：〔（（（））），（（）（）），（（））（），（）（（）），（）（）（）〕
　　解答：回溯算法（深度优先遍历）
　　算法策略：回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。
　　对应于本题，我们可以每次试探增加（或），注意：加入（的条件是，当前是否还有（可以选择加入）的时候，受到（的限制，如果已选择的结果里的（小于等于已选择里的）时，此时是不能选择）的，例如如果当前是（），继续选择）就是（）），是不合法的
　　代码实现：constgenerateParenthesis（n）｛constres〔〕constdfs（path，left，right）｛肯定不合法，提前结束if（leftnleftright）return到达结束条件if（leftright2n）｛res。push（path）return｝选择dfs（path（，left1，right）dfs（path），left，right1）｝dfs（，0，0）returnres｝
　　复杂度分析（来源leetcode官方题解）：
　　本文转载自三分钟学前端