JavaScript数据结构与算法基础

• 定义子问题&＃xff1a;F(n) &＃61; F(n - 1) &＃43; F(n - 2)
• 反复执行&＃xff1a;从2循环到n,执行上述公式。

2. 爬楼梯问题

题目链接&＃xff1a;70. 爬楼梯 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

思路&＃xff1a;

• 爬到第n阶可以在第n-1阶爬1个台阶&＃xff0c;或者在第n-2阶爬2个台阶。
• F(n) &＃61; F(n-1) &＃43; F(n-2)
• 使用动态规划。

解题步骤&＃xff1a;70. 爬楼梯 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

• 定义子问题&＃xff1a;F(n) &＃61; F(n-1) &＃43; F(n-2)
• 反复执行&＃xff1a;从2循环到n&＃xff0c;执行上述公式。

var climbStairs &＃61; function(n) {if(n <2) return 1;const dp &＃61; [1,1];for(let i &＃61; 2;i <&＃61; n;i&＃43;&＃43;){dp[i] &＃61; dp[i - 1] &＃43; dp[i - 2]}return dp[n]
};
// 时间复杂度O(n) 临时变量数组空间复杂度O(n)//空数组改为两个变量,将空间复杂度下降至O(1)
var climbStairs &＃61; function(n) {if(n <2) return 1;let dp0 &＃61; 1;let dp1 &＃61; 1;for(let i &＃61; 2;i <&＃61; n;i&＃43;&＃43;){const temp &＃61; dp0;dp0 &＃61; dp1;dp1 &＃61; dp0 &＃43; temp;}return dp1
};


3. 打家劫舍

题目链接:198. 打家劫舍 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

思路:

• f(k) &＃61; 从前K个房屋中能窃取的最大数额。

• Ak &＃61; 第k个房屋的钱数。

• f(k) &＃61; max(f(k-2)&＃43;Ak,f(k-1))。

• 考虑动态规划

解题步骤&＃xff1a;

• 定义子问题&＃xff1a;f(k) &＃61; max(f(k-2)&＃43;Ak,f(k-1))。
• 反复执行&＃xff1a;从2循环到n&＃xff0c;执行上述公式。

var rob &＃61; function(nums) {if(nums.length &＃61;&＃61;&＃61; 0) return 0const dp &＃61; [0,nums[0]];for(let i &＃61;2;i<&＃61;nums.length;i&＃43;&＃43;){dp[i] &＃61; Math.max(dp[i-2] &＃43; nums[i - 1],dp[i - 1])}return dp[dp.length - 1]
};


- 贪心算法

1. 贪心算法是什么&＃xff1f;

• 贪心算法是算法设计中的一种方法。
• 期盼通过每个阶段的局部最优选择&＃xff0c;从而达到全局的最优。
• 结果并不一定是最优。

2. 零钱兑换

题目链接&＃xff1a;455. 分发饼干 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

思路&＃xff1a;

• 局部最优&＃xff1a;既能满足孩子&＃xff0c;还消耗最小。
• 先将“较小的饼干”分给“胃口最小”的孩子。

解题步骤&＃xff1a;

• 对饼干数组和胃口数组升序排序。
• 遍历饼干数组&＃xff0c;找到能满足第一个孩子的饼干
• 然后继续遍历饼干&＃xff0c;找到满足第二、三、.....、n个孩子的饼干。

var findContentChildren &＃61; function(g, s) {const sortFunc &＃61; function(a,b) {return a -b}g.sort(sortFunc);s.sort(sortFunc);let i &＃61; 0;s.forEach(n &＃61;> {if(n >&＃61; g[i]){i&＃43;&＃43;}})return i;
};


3. 买股票问题

题目链接&＃xff1a;122. 买卖股票的最佳时机 II - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

思路&＃xff1a;

• 前提&＃xff1a;上帝视角&＃xff0c;知道未来的价格。
• 局部最优&＃xff1a;见好就收&＃xff0c;见差不动&＃xff0c;不做任何长远打算

解题步骤&＃xff1a;

• 新建一个变量&＃xff0c;用来统计总利润。
• 遍历价格数组&＃xff0c;如果当前价格

var maxProfit &＃61; function(prices) {let profit &＃61; 0;for(let i &＃61;1;i prices[i - 1]){profit &＃43;&＃61; prices[i] - prices[i - 1];}}return profit
};


- 回溯算法

1. 回溯算法是什么

• 回溯算法是算法设计的一种方法。
• 回溯算法是一种渐进式寻找构建问题解决的策略。
• 回溯算法会先从一个可能的动作开始解问题&＃xff0c;如果不行&＃xff0c;就回溯并选择另一个动作&＃xff0c;直到问题解决。

2. 什么问题适合回溯算法解决&＃xff1f;

• 有很多路。
• 这些路里&＃xff0c;有死路,也有出路。
• 通常需要递归模拟所有的路。

3. 全排列

• 用递归模拟出所有的情况。
• 遇到包含重复元素的情况&＃xff0c;就回溯
• 收集所有到达递归终点的情况&＃xff0c;就返回

题目链接&＃xff1a;46. 全排列 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

思路&＃xff1a;

• 要求&＃xff1a;1、所有排列情况 2、没有重复元素
• 有出路、有死路
• 考虑回溯算法

解题步骤&＃xff1a;

• 有递归模拟所有的情况。
• 遇到包含重复元素的情况&＃xff0c;就回溯。
• 收集所有到达递归的情况&＃xff0c;并返回

var permute &＃61; function(nums) {const res &＃61; [];const backtrack &＃61; (path) &＃61;>{ //返回函数if(path.length &＃61;&＃61;&＃61; nums.length){ // 长度相等就返回res.push(path);return;}nums.forEach(n &＃61;> {if(path.includes(n)){ // 不能包含一模一样的数字return;}backtrack(path.concat(n));})}backtrack([])return res;
};
// 时间复杂度O(n!) 空间复杂度O(n)


4. 子集问题

题目链接&＃xff1a;78. 子集 - 力扣&＃xff08;LeetCode&＃xff09; (leetcode-cn.com)

思路:

• 要求&＃xff1a;1、所有子集&＃xff1b;2、没有重复元素
• 有出路、有死路。
• 考虑使用回溯算法。

解题步骤&＃xff1a;

• 用递归模拟出所有情况
• 保证接的数字都是后面的数字。
• 收集所有到达递归终点的情况&＃xff0c;并返回。

var subsets &＃61; function(nums) {const res &＃61;[]const backtrack &＃61; (path,l,start) &＃61;>{if(path.length &＃61;&＃61;&＃61; l){res.push(path)return;} for(let i &＃61; start;i};


- 完结

- 知识体系结构

• 数据结构&＃xff1a;栈、队列、链表、集合、字典、树、图、堆。
• 算法&＃xff1a;链表/树/图的遍历、数组的排序和搜索
• 算法设计思想&＃xff1a;分而治之、动态规划、贪心、回溯。

- 重点难点

• 数据结构&＃xff1a;所有数据结构都很重要&＃xff0c;跟前端最相关的是链表和树。
• 算法&＃xff1a;链表/树/图的遍历、数组的排序和搜索.....
• 设计思想&＃xff1a;分而治之、动态规划常考&＃xff0c;贪心、回溯次之。

- 经验心得

• 搞清楚数据结构与算法的特点和应用场景。
• 用JS实现一遍&＃xff0c;最好能用第二第三语言再实现一遍。
• 学会分析时间/空间复杂度。
• 提炼前端和算法结合点&＃xff0c;用于工作实战。

- 拓展建议

• 多刷题&＃xff0c;最好能保证300道以上。
• 多总结各种套路、模板。
• 多遇到源码&＃xff0c;比如React、Lodash、V8......
• 多实战&＃xff0c;将数据结构与算法用于工作。