搞定大厂算法面试之leetcode精讲4.贪婪
视频教程（高效学习）:点击学习
目录：
1.开篇介绍
2.工夫空间复杂度
3.动静布局
4.贪婪
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.枯燥栈
14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其余类型题
什么是贪婪算法
贪婪法，又称贪婪算法，贪心算法，在对问题求解时，总是做出在以后看来最好的抉择，冀望通过每个阶段的部分最优抉择达到全局最优，但后果不肯定最优
实用场景：简略的说，问题可能分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪婪算法的到最初的最优解，这种子问题最优解称为最优子结构
贪婪算法与动静布局的不同点在于它对每个子问题的解决方案都做出以后的最优抉择，不能回退，而动静布局会保留之前的运算后果，并依据之前的后果进行抉择，有回退的性能，贪婪是动静布局的理想化的状况。
122. 交易股票的最佳时机 II（medium）
办法1.动静布局
思路：依据题意只能持有一只股票，不限度交易次数，咱们能够用动静布局来做，首先定义状态，题中有两个状态，一个是天数，一个是是否持有股票，所以咱们定义
dp[i][0]示意第 i天交易完后手里没有股票的最大利润，dp[i][1]示意第 i天交易完后手里持有一支股票的最大利润，接下来就是定义状态转移方程：如果以后的状态是
dp[i][0]，示意手中没股票，则可由前一天的两种状况转移过去，第一种是dp[i-1][0]，示意前一天手里没股票，而且明天没做任何操作。第二种是dp[i-1][1]，示意前一天持有股票，然而明天卖了，所以收益是dp[i-1][1]+prices[i]，咱们需要求出这两种状况下的最大值就是最大利润，状态转移方程就是：dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);如果以后的状态是
dp[i][1]，示意手中有股票，则可由前一天的两种状况转移过去，第一种是dp[i−1][1]，示意前一天手中有股票，即是明天没做任何操作。第二种是dp[i−1][0]，示意前一天没有股票，然而明天买进了，所以收益是dp[i-1][1]-prices[i]，咱们需要求出这两种状况下的最大值就是最大利润，状态转移方程就是：dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
由下面的状态转移方程咱们晓得，以后天的最大收益，只与前一天的状态相干，所以咱们能够不必定义二维数组来寄存状态，只须要将
dp[i - 1][0]，dp[i - 1][1]寄存在变量中。- 复杂度剖析：工夫复杂度：
O(n)，n是数组长度，每天有持有股票或者没持有两种状态，一共2n的状态转移次数，工夫复杂度就是O(2n)，工夫复杂度和常系数无关，所以工夫复杂度就是O(n)。空间复杂度O(n)，因为要开拓n的空间寄存状态，尽管是二维数组，然而第二维是常数。如果进行了状态压缩，空间复杂度能够优化到O(1)
js:
var maxProfit = function (prices) { const n = prices.length; const dp = new Array(n).fill(0).map((v) => new Array(2).fill(0)); //初始化状态数组 (dp[0][0] = 0), (dp[0][1] = -prices[0]); //3.定义初始值 for (let i = 1; i < n; ++i) { //1.确定状态 //2.推导状态转移方程 //以后没持有股票，可由前一天的两种状态转移过了， //1是前一天没持有，明天不动，2是前一天持有，明天卖掉，求这两种状况的较大值 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); //以后持有股票，可由前一天的两种状态转移过了， //1是前一天持有，明天不动，2是前一天没持有，明天买入，求这两种状况的较大值 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } //4.确定输入值 return dp[n - 1][0]; //返回第n-1天的最大值};//空间压缩var maxProfit = function (prices) { const n = prices.length; let dp0 = 0, dp1 = -prices[0]; for (let i = 1; i < n; ++i) { let newDp0 = Math.max(dp0, dp1 + prices[i]); let newDp1 = Math.max(dp1, dp0 - prices[i]); dp0 = newDp0; dp1 = newDp1; } return dp0;};Java:
class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; ++i) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; }}//空间压缩class Solution { public int maxProfit(int[] prices) { int n = prices.length; int dp0 = 0, dp1 = -prices[0]; for (int i = 1; i < n; ++i) { int newDp0 = Math.max(dp0, dp1 + prices[i]); int newDp1 = Math.max(dp1, dp0 - prices[i]); dp0 = newDp0; dp1 = newDp1; } return dp0; }}办法2.贪婪
- 思路：因为不限度交易次数，只有明天价格比昨天高，就交易，利润为正累加，最初的和就是最大的利润，留神第一天是没有利润的，这道题之所以能够用贪婪是因为部分最优：收集每天的正利润，能够推导出，全局最优：求得最大利润。
- 复杂度剖析：工夫复杂度
O(n)，n是数组的长度。空间复杂度是O(1)
js:
var maxProfit = function (prices) { let ans = 0; let n = prices.length; for (let i = 1; i < n; ++i) { //明天价格和昨天的差值是否为正，如果为正累加进去，为负则加0 ans += Math.max(0, prices[i] - prices[i - 1]); } return ans;};Java:
class Solution { public int maxProfit(int[] prices) { int ans = 0; int n = prices.length; for (int i = 1; i < n; ++i) { ans += Math.max(0, prices[i] - prices[i - 1]); } return ans; }}455. 散发饼干 (easy)
- 思路：大尺寸的饼干既能够满足胃口大的孩子也能够满足胃口小的孩子，那么就应该优先满足胃口大的。排序两个数组，从右到左遍历，用大饼干首先满足胃口大的小孩
- 复杂度：工夫复杂度
O(mlogm + nlogn)。空间复杂度O(logm + logn)
js：
var findContentChildren = function (g, s) { g = g.sort((a, b) => a - b); s = s.sort((a, b) => a - b); //排序数组 let result = 0; let index = s.length - 1; for (let i = g.length - 1; i >= 0; i--) { //从胃口大的小孩开始满足 if (index >= 0 && s[index] >= g[i]) { result++; //后果加1 index--; } } return result;};java：
class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int index = 0; int result = 0; for (int i = 0; i < s.length && index < g.length; i++) { if (s[i] >= g[index]) { index++; result++; } } return result; }}435. 无重叠区间 (medium)
办法1.动静布局
- 思路：
dp[i]示意前i个区间中最大不重合区间的个数，首先将区间数组按左边界排序，找出intervals中最多有多少个不反复的区间，动静布局方程dp[i] = Math.max(dp[i], dp[j] + 1)。intervals的长度减去最多的不反复的区间 就是起码删除区间的个数 - 复杂度：工夫复杂度
O(n^2)，两层嵌套循环leetcode执行超时 简单度过高。空间复杂度O(n)，dp数组的空间
js：
//leetcode执行超时 简单度过高var eraseOverlapIntervals = function (intervals) { if (!intervals.length) { return 0; } intervals.sort((a, b) => a[0] - b[0]); //按左边界排序 const n = intervals.length; const dp = new Array(n).fill(1); //初始化dp数组 for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { //循环i,j找出intervals中最多有多少个不反复的区间 //j的右边界小于i的左边界 相当于多出了一个不重合区间 if (intervals[j][1] <= intervals[i][0]) { dp[i] = Math.max(dp[i], dp[j] + 1); //更新dp[i] } } } return n - Math.max(...dp); //n减去最多的不反复的区间 就是起码删除区间的个数};java：
class Solution { public int eraseOverlapIntervals(int[][] intervals) { if (intervals.length == 0) { return 0; } Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] interval1, int[] interval2) { return interval1[0] - interval2[0]; } }); int n = intervals.length; int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (intervals[j][1] <= intervals[i][0]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } return n - Arrays.stream(dp).max().getAsInt(); }}办法2.贪婪
- 思路：intervals按右边界排序，而后从左往右遍历，右边界完结的越早，留给前面的区间的空间就越大，不重合的区间个数就越多，intervals的长度减去最多的不反复的区间 就是起码删除区间的个数
- 复杂度：工夫复杂度
O(nlogn)，数组排序O(nlogn)，循环一次数组O(n)。空间复杂度O(logn)，排序须要的栈空间
js：
var eraseOverlapIntervals = function (intervals) { if (!intervals.length) { return 0; } //按右边界排序，而后从左往右遍历，右边界完结的越早，留给前面的区间的空间就越大，不重合的区间个数就越多 intervals.sort((a, b) => a[1] - b[1]); const n = intervals.length; let right = intervals[0][1]; //right初始化为第一个区间的右边界 let ans = 1; //最多的不重合区间的个数 for (let i = 1; i < n; ++i) { //循环区间数组 if (intervals[i][0] >= right) { //当区间的左边界大于上一个区间的右边界的时候 阐明是一对不重合区间 ++ans; //ans加1 right = intervals[i][1]; //更新right } } return n - ans; //intervals的长度减去最多的不反复的区间 就是起码删除区间的个数};java：
class Solution { public int eraseOverlapIntervals(int[][] intervals) { if (intervals.length == 0) { return 0; } Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] interval1, int[] interval2) { return interval1[1] - interval2[1]; } }); int n = intervals.length; int right = intervals[0][1]; int ans = 1; for (int i = 1; i < n; ++i) { if (intervals[i][0] >= right) { ++ans; right = intervals[i][1]; } } return n - ans; }}能不能用贪婪算法须要满足贪婪选择性，贪婪算法正确的的证实能够用反证法
以这一题为例：
- 咱们的思路是保留最多的不重合的区间，所以依照区间结尾排序，区间结尾完结的越早且和前一个区间不重叠的，就退出最多不反复的区间中，咱们称为算法a，如果算法a中的某一个步骤是抉择区间
[a, b]，咱们称为区间A。 - 假如这个抉择不正确，也就是说算法a失去的不是最优解。
- 咱们假如存在另一个算法c能失去最优解，算法c中的一个步骤是抉择区间
[c, d]，咱们称为区间C，使得它是最优解中的一个区间，其中d>b,因为算法a抉择的是结尾最先完结且不重合的区间，如果算法a不正确，又因为区间数组中的区间是固定的，则其余算法c必定存在d>b的状况。 - 咱们用区间A替换区间C齐全不影响算法c的后果，因为
b<d,所以不影响区间C前面区间的后果。所以咱们抉择了区间A也形成了一个最优解。而咱们假如的是抉择区间A不是最优解，所以和之前的假如矛盾，所以算法a是正确的贪婪算法
55. 跳跃游戏 （medium）
办法1.动静布局
- 思路：
dp[i]示意是否达到地位i，对每个地位i判断是否通过后面的地位跳跃过去，以后地位j能达到，并且以后地位j加上能达到的地位如果超过了i，那dp[i]更新为ture，便是i地位也能够达到。 - 复杂度：工夫复杂度
O(n^2)，空间复杂度O(n)
js:
function canJump(nums) { let dp = new Array(nums.length).fill(false); //初始化dp dp[0] = true; //第一项能达到 for (let i = 1; i < nums.length; i++) { for (let j = 0; j < i; j++) { //以后地位j能达到，并且以后地位j加上能达到的地位如果超过了i，那dp[i]更新为ture，便是i地位也能够达到 if (dp[j] && nums[j] + j >= i) { dp[i] = true; break; } } } return dp[nums.length - 1];}java：
class Solution { public boolean canJump(int[] nums) { boolean[] dp = new boolean[nums.length]; dp[0] = true; for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (dp[j] && nums[j] + j >= i) { dp[i] = true; break; } } } return dp[nums.length - 1]; }}办法2.贪婪
- 思路：不必思考每一步跳跃到那个地位，而是尽可能的跳跃到最远的地位，看最多能笼罩的地位，不断更新能笼罩的间隔。
- 复杂度：工夫复杂度
O(n)，遍历一边。空间复杂度O(1)
js：
var canJump = function (nums) { if (nums.length === 1) return true; //长度为1 间接就是起点 let cover = nums[0]; //能笼罩的最远距离 for (let i = 0; i <= cover; i++) { cover = Math.max(cover, i + nums[i]); //以后笼罩间隔cover和以后地位加能跳跃的间隔中取一个较大者 if (cover >= nums.length - 1) { //笼罩间隔超过或等于nums.length - 1 阐明能达到起点 return true; } } return false; //循环实现之后 还没返回true 就是不能达到起点};java：
class Solution { public boolean canJump(int[] nums) { if (nums.length == 1) { return true; } int cover = nums[0]; for (int i = 0; i <= cover; i++) { cover = Math.max(cover, i + nums[i]); if (cover >= nums.length - 1) { return true; } } return false; }}881. 救生艇 （medium）
- 思路：题意是一条船只能坐2人，要求尽可能的用少的船装下这些人。所以能够用贪婪策略。让更多的人组成2人组，而且这些2人组的两人分量加起来不超过船的载重。所以能够先排序people，用双指针从两边向两头遍历，让重的人和轻的人组成2人组，如果以后最重的人和最轻的人的分量和超过了载重，那只能让重的人先乘一条船。
- 复杂度：工夫复杂度
O(nlogn)，排序的复杂度。空间复杂度O(logn)，排序的栈空间
js：
var numRescueBoats = function (people, limit) { people.sort((a, b) => (a - b)); let ans = 0, left = 0,//左指针初始化在0的地位 right = people.length - 1 //右指针初始化在people.length - 1的地位 while (left <= right) {//两指针向两头聚拢 遍历 //当people[left] + people[right--]) <= limit 示意左右两边的人能够一起坐船 而后让left++ right-- //如果两人坐不下，那只能让重的人先坐一条船 也就是让right-- if ((people[left] + people[right--]) <= limit) { left++ } ans++ } return ans};java：
class Solution { public int numRescueBoats(int[] people, int limit) { Arrays.sort(people); int ans = 0, left = 0, right = people.length - 1; while (left <= right) { if ((people[left] + people[right--]) <= limit) { left++; } ans++; } return ans; }}452. 用起码数量的箭引爆气球 (medium)
- 思路：区间依照结尾从小到大排序，循环数组，如果前面一个区间的开始大于前一个区间的结尾 就须要新增一支箭。
- 复杂度：工夫复杂度
O(nlogn)，排序的复杂度O(nlogn)，循环数组的复杂度O(n)。空间复杂度O(logn)，排序栈空间
js：
var findMinArrowShots = function (points) { if (!points.length) { return 0; } points.sort((a, b) => a[1] - b[1]); //依照区间结尾排序 let pos = points[0][1]; let ans = 1; for (let balloon of points) { if (balloon[0] > pos) { //如果前面一个区间的开始大于前一个区间的结尾 就须要新增一支箭 pos = balloon[1]; //更新pos为新的区间的结尾 ans++; } } return ans;};java：
class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } Arrays.sort(points, new Comparator<int[]>() { public int compare(int[] point1, int[] point2) { if (point1[1] > point2[1]) { return 1; } else if (point1[1] < point2[1]) { return -1; } else { return 0; } } }); int pos = points[0][1]; int ans = 1; for (int[] balloon: points) { if (balloon[0] > pos) { pos = balloon[1]; ++ans; } } return ans; }}134. 加油站(medium)
- 思路：首先判断总油量是否小于总油耗，如果是则必定不能走一圈。如果否，那必定能跑一圈。接下来就是循环数组，从第一个站开始，计算每一站残余的油量，如果油量为负了，就以这个站为终点从新计算。如果到达某一个点为负，阐明终点到这个点两头的所有站点都不能到达该点。
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
var canCompleteCircuit = function (gas, cost) { let totalGas = 0; let totalCost = 0; for (let i = 0; i < gas.length; i++) { totalGas += gas[i]; totalCost += cost[i]; } if (totalGas < totalCost) {//总油量小于总油耗 必定不能走一圈 return -1; } let currentGas = 0; let start = 0; for (let i = 0; i < gas.length; i++) { currentGas = currentGas - cost[i] + gas[i]; if (currentGas < 0) {//如果达到下一站的时候油量为正数 就以这个站为终点 从新计算 currentGas = 0; start = i + 1; } } return start;};java：
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int sum = 0; for(int i = 0;i < n;i++){ sum += gas[i] - cost[i]; } if(sum < 0){ return -1; } int currentGas = 0; int start = 0; for(int i = 0;i < n;i++){ currentGas += gas[i] - cost[i]; if(currentGas < 0){ currentGas = 0; start = i + 1; } } return start; }}621. 任务调度器 (medium)
- 思路：先排个数最多的工作A，在A的冷却工夫内插入其余工作，先计算前n-1行n的距离的工夫大小，再计算和最大次数雷同的字母个数，而后累加进ret。最初在tasks的长度和ret中取较大的一个
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
function leastInterval(tasks, n) { let arr = Array(26).fill(0); for (let c of tasks) { //统计各个字母呈现的次数 arr[c.charCodeAt() - "A".charCodeAt()]++; } let max = 0; for (let i = 0; i < 26; i++) { //找到最大次数 max = Math.max(max, arr[i]); } let ret = (max - 1) * (n + 1); //计算前n-1行n的距离的工夫大小 for (let i = 0; i < 26; i++) { //计算和最大次数雷同的字母个数，而后累加进ret if (arr[i] == max) { ret++; } } return Math.max(ret, tasks.length); //在tasks的长度和ret中取较大的一个}java：
class Solution { public int leastInterval(char[] tasks, int n) { int[] arr = new int[26]; for (char c : tasks) { arr[c - 'A']++; } int max = 0; for (int i = 0; i < 26; i++) { max = Math.max(max, arr[i]); } int ret = (max - 1) * (n + 1); for (int i = 0; i < 26; i++) { if (arr[i] == max) { ret++; } } return Math.max(ret, tasks.length); }}860. 柠檬水找零 (easy)
- 思路：优先找面额大的
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js:
var lemonadeChange = function (bills) { let five = 0, ten = 0; for (const bill of bills) { if (bill === 5) {//面值为5 间接能够兑换柠檬水 five += 1; } else if (bill === 10) {//面值为10 兑换柠檬水 还须要找5元 if (five === 0) { return false; } five -= 1; ten += 1; } else {//面值为20 兑换柠檬水 须要找3个5元或一个10元一个5元 if (five > 0 && ten > 0) { five -= 1; ten -= 1; } else if (five >= 3) { five -= 3; } else { return false; } } } return true;};java：
class Solution { public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; for (int bill : bills) { if (bill == 5) { five++; } else if (bill == 10) { if (five == 0) { return false; } five--; ten++; } else { if (five > 0 && ten > 0) { five--; ten--; } else if (five >= 3) { five -= 3; } else { return false; } } } return true; }}