10 极客大学-算法训练营-覃超-第十课.pdf

贪心 VS 回溯 VS 动态规划

贪心：当下做局部最优的选择， 不能够回退

贪心算法 在每一步总是做出在当前看来最好的选择 ==> 着眼于当下

回溯：能够回退
动态规划：最优判断 + 回退

参考链接

  • coin change 题目

  • 动态规划定义

    课后作业

  • [x] 柠檬水找零（亚马逊在半年内面试中考过）

    1. var lemonadeChange = function (bills) {
    2. /**
    3.  * 如果遍历10， 则数组中减少一个5
    4.  * 如果遍历到20， 则数组中减少 10，5 或者 3个5
    5.  */
    7. let five = 0,
    8.   ten = 0,
    9.   twenty = 0;
    10. for (let index = 0; index < bills.length; index++) {
    11.   const element = bills[index];
    12.   if (element === 5) {
    13.     five++;
    14.   }
    15.   if (element === 10) {
    16.     if (five >= 1) {
    17.       five--;
    18.       ten++;
    19.     } else {
    20.       return false;
    21.     }
    22.   }
    23.   if (element === 20) {
    24.     if (five >= 1 && ten >= 1) {
    25.       five--;
    26.       ten--;
    27.     } else if (five >= 3) {
    28.       five -= 3;
    29.       twenty++;
    30.     } else {
    31.       return false;
    32.     }
    33.   }
    34. }
    35. return true;
    36. };

  • [x] 买卖股票的最佳时机 II （亚马逊、字节跳动、微软在半年内面试中考过）

    1. /**
    2. * 贪心：只关心当前局部最优解
    3. * 1、遍历 prices， 如果 prices[i+1] > prices[i] 卖出股票
    4. * 2、累加差值
    5. */
    6. var maxProfit = function(prices) {
    7. let res = 0;
    8. for(let i=0; i<prices.length; i++){
    9.    if( prices[i+1] > prices[i]){
    10.        let diff = prices[i+1] - prices[i]
    11.        res+=diff;
    12.    }
    13. }
    14. return res;
    15. };

  • [x] 分发饼干（亚马逊在半年内面试中考过）

    1. /**
    2. * 1、将饼干s 和小孩g 按照从小到大的顺序排列
    3. * 2、反向遍历小孩，如果 s[i] >= g[i] res +=1, sIndex--
    4. * 3、注意点：只需要O(n)的时间复杂度，只需要遍历小孩数组即可
    5. */
    6. var findContentChildren = function (g, s) {
    7. g.sort((a, b) => {
    8.   return a - b;
    9. });
    10. s.sort((a, b) => {
    11.   return a - b;
    12. });
    13. let res = 0;
    14. let sIndex = s.length - 1; // 维护一个饼干的序列，避免嵌套循环降低复杂度
    15. for (let i = s.length - 1; i >= 0; i--) {
    16.   if (s[sIndex] >= 0 && s[sIndex] >= g[i]) {
    17.     res += 1;
    18.     sIndex--;
    19.   }
    20. }
    21. return res;
    22. };

  • [ ] 模拟行走机器人

  • 跳跃游戏 （亚马逊、华为、Facebook 在半年内面试中考过）
  • 跳跃游戏 II （亚马逊、华为、字节跳动在半年内面试中考过）