相关文章推荐
淡定的槟榔  ·  HTTP error 403.7 when ...·  9 月前    · 
爱看球的人字拖  ·  js中下拉框如何删除一个选项 - ...·  1 年前    · 
完美的抽屉  ·  oracle中多列转行_ITPUB博客·  1 年前    · 
彷徨的充电器  ·  2023年5月了,最近在探索跨平台方案,Qt ...·  1 年前    · 
果断的乌冬面  ·  UNI-APP本地图片转Base64_梦想追 ...·  1 年前    · 
Code  ›  【算法】分治思想、动态规划、回溯、贪心算法开发者社区
分治算法 const 贪心算法 动态规划
https://cloud.tencent.com/developer/article/2096922
道上混的豌豆
1 年前
作者头像
叫我詹躲躲
0 篇文章

【算法】分治思想、动态规划、回溯、贪心算法

前往专栏
腾讯云
开发者社区
文档 意见反馈 控制台
首页
学习
活动
专区
工具
TVP
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP
返回腾讯云官网
社区首页 > 专栏 > 前端进阶-詹躲躲 > 【算法】分治思想、动态规划、回溯、贪心算法

【算法】分治思想、动态规划、回溯、贪心算法

作者头像
叫我詹躲躲
发布 于 2022-09-06 20:50:17
392 0
发布 于 2022-09-06 20:50:17
举报

四种算法思想

❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️❤️

分治 :分而治之,先解决子问题,再将子问题的解合并求出原问题。

贪心 :一条路走到黑,选择当下局部最优的路线,没有后悔药。

回溯 :一条路走到黑,手握后悔药,可以无数次重来。(英雄联盟艾克大招无冷却)。

动态规划 :上帝视角,手握无数平行宇宙的历史存档,同时发展出无数个未来。

分治算法 Divide and Conquer

分治算法思想很大程度上是基于递归的,也比较适合用递归来实现。顾名思义,分而治之。一般分为以下三个过程:

分解:将原问题分解成一系列子问题。
解决:递归求解各个子问题,若子问题足够小,则直接求解。
合并:将子问题的结果合并成原问题。

比较经典的应用就是归并排序 (Merge Sort) 以及快速排序 (Quick Sort) 等。我们来从归并排序理解分治思想,归并排序就是将待排序数组不断二分为规模更小的子问题处理,再将处理好的子问题合并起来。

上代码。

const mergeSort = function(arr) {
    const len = arr.length;
    if (len > 1) {
        // 对半分解
        const middle = Math.floor(len / 2);
        const left = arr.slice(0, middle);
        const right = arr.slice(middle, len);
        let i = 0; 
        let j = 0;
        let k = 0;
        // 分别对左右进行排序
        mergeSort(left);
        mergeSort(right);
        while(i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k] = left[i];
            } else {
                arr[k] = right[j];
        // 检查余项
        while(i < left.length) {
            arr[k] = left[i];
        while(j < right.length) {
            arr[k] = right[j];
    return arr;

复杂度分析

时间复杂度:O(nlogn)
空间复杂度:O(n)

动态规划 Dynamic Programming

LeetCode真题

  1. 爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/

虽然动态规划的最终版本 (降维再去维) 大都不是递归,但解题的过程还是离开不递归的。新手可能会觉得动态规划思想接受起来比较难,确实,动态规划求解问题的过程不太符合人类常规的思维方式,我们需要切换成机器思维。

使用动态规划思想解题,首先要明确动态规划的三要素。动态规划三要素

重叠子问题
最优子结构
状态转移方程

重叠子问题

切换机器思维,自底向上思考。

爬第 n 阶楼梯的方法数量,等于两部分之和:

爬上 n-1 阶楼梯的方法数量
爬上 n-2 阶楼梯的方法数量

最优子结构

子问题的最优解能够推出原问题的优解。状态转移方程

dp[n] = dp[n-1] + dp[n-2]

具备三要素,确认边界条件,初始化状态,开始切菜:

    dp[0] = 1
    dp[1] = 1
const climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];

复杂度分析

时间复杂度:O(n)
空间复杂度:O(n)

优化

在此基础上,我们还可以通过压缩空间来对算法进行优化。因为 dp[i]只与 dp[i-1] 和 dp[i-2] 有关,没有必要存储所有出现过的 dp 项,只用两个临时变量去存储这两个状态即可。

const climbStairs = function(n) {
    let a1 = 1;
    let a2 = 1;
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2];
    return a2;

复杂度分析

时间复杂度:O(n)
空间复杂度:O(1)

贪心算法 Greedy

最近某音很火的贪心土味情话
喂,不是吧。今天喝了脉动啊,吃了果冻啊,但是,还是忍不住对你心动啊。

回到算法中,贪心算法是动态规划算法的一个子集,可以更高效解决一部分更特殊的问题。实际上,用贪心算法解决问题的思路,并不总能给出最优解。因为它在每一步的决策中,选择目前最优策略,不考虑全局是不是最优。LeetCode真题

LeetCode 455. 分发饼干

https://leetcode-cn.com/problems/assign-cookies/description/ 思路

贪心算法+双指针求解。

给一个孩子的饼干应当尽量小并且能满足孩子,大的留来满足胃口大的孩子
因为胃口小的孩子最容易得到满足,所以优先满足胃口小的孩子需求
按照从小到大的顺序使用饼干尝试是否可满足某个孩子
当饼干 j >= 胃口 i 时,饼干满足胃口,更新满足的孩子数并移动指针  i++ j++ res++
当饼干 j < 胃口 i 时,饼干不能满足胃口,需要换大的 j++

关键点

将需求因子 g 和 s 分别从小到大进行排序,使用贪心思想配合双指针,每个饼干只尝试一次,成功则换下一个孩子来尝试。复杂度分析

时间复杂度:O(nlogn)
空间复杂度:O(1)
const findContentChildren = function (g, s) {
    g = g.sort((a, b) => a - b);
    s = s.sort((a, b) => a - b);
    let gi = 0; // 胃口值
    let sj = 0; // 饼干尺寸
    let res = 0;
    while (gi < g.length && sj < s.length) {
        if (s[sj] >= g[gi]) {
            gi++;
            sj++;
            res++;
        } else {
            sj++;
    return res;

回溯算法 Backtracking

回溯算法本质上就是枚举,使用摸着石头过河的查找策略,还可以通过剪枝少走冤枉路。LeetCode真题

LeetCode 17.电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/ 思路

使用回溯法进行求解,回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解,回溯算法会舍弃它,并在前面的一些步骤做出一些修改,并重新尝试找到可行解。究其本质,其实就是枚举。

如果没有更多的数字需要被输入,说明当前的组合已经产生。

如果还有数字需要被输入:

遍历下一个数字所对应的所有映射的字母
将当前的字母添加到组合最后,也就是 str + tmp[r]

关键点

在for循环中调用递归。复杂度分析

N+M 是输入数字的总数

时间复杂度:O(3^N * 4^M)
空间复杂度:O(3^N * 4^M)
const letterCombinations = function (digits) {
    if (!digits) {
        return [];
    const len = digits.length;
    const map = new Map();
    map.set('2', 'abc');
    map.set('3', 'def');
    map.set('4', 'ghi');
    map.set('5', 'jkl');
    map.set('6', 'mno');
    map.set('7', 'pqrs');
    map.set('8', 'tuv');
    map.set('9', 'wxyz');
    const result = [];
    function generate(i, str) {
        if (i == len) {
            result.push(str);
            return;
        const tmp = map.get(digits[i]);
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r]);
 
推荐文章
淡定的槟榔  ·  HTTP error 403.7 when you run applications - Internet Information Services | Microsoft Learn
9 月前
爱看球的人字拖  ·  js中下拉框如何删除一个选项 - OSCHINA - 中文开源技术交流社区
1 年前
完美的抽屉  ·  oracle中多列转行_ITPUB博客
1 年前
彷徨的充电器  ·  2023年5月了,最近在探索跨平台方案,Qt 和 C# 该怎么选? - 知乎
1 年前
果断的乌冬面  ·  UNI-APP本地图片转Base64_梦想追逐太阳的少年的博客-CSDN博客
1 年前
今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
删除内容请联系邮箱 2879853325@qq.com
Code - 代码工具平台
© 2024 ~ 沪ICP备11025650号