LeeCode——回溯法、动态规划、贪心法、分治法(快速说明)

news/2024/12/5 13:01:47/

1、四种方法的对比

算法方法用处优点缺点拓展与改良
回溯法适用于求解组合问题、排列问题、搜索问题等。

1. 可以搜索整个解空间,找到最优解。

2. 不需要预先知道问题的解可能在哪里。

1. 时间复杂度高,因为需要遍历整个解空间。

2. 需要较大的空间存储搜索轨迹。

1. 剪枝优化。

2. 双向搜索。

动态规划适用于求解具有最优子结构的问题。

1. 重复计算较少,效率高。

2. 可以通过将问题划分为多个子问题来简化问题。

1. 需要存储中间结果,占用空间较大。

2. 不能很好地处理某些非最优子结构的问题。

1. 记忆化搜索。

2. 状态压缩。

贪心法适用于求解具有贪心选择性质的问题。

1. 算法简单,易于实现。

2. 通常时间效率较高。

1. 得到的不一定是最优解,很难证明其正确性。

2. 对于某些问题,可能无法使用贪心策略。

1. 局部搜索等启发式方法。

2. 迭代深化策略。

分治法适用于将一个大问题划分为多个相似子问题的情况。

1. 对于一些规模较大的问题,可以减少问题的复杂度。

2. 可以利用并行计算提高效率。

1. 划分子问题需要一定的技巧和经验。

2. 对于一些问题,划分子问题比较困难。

1. 增加唯一性条件来避免重复计算。

2. 引入随机化算法增加多样性。


2、一句话理解四种算法思想(知乎大佬总结的)

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

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

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

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


回溯算法 Backtracking

通常用于求解组合问题、排列问题、搜索问题等,其优点在于可以搜索整个解空间,找到最优解,但缺点则是时间复杂度高,存储搜索轨迹需要较大空间。对回溯法可以通过剪枝优化、双向搜索等方式进行改良。

动态规划 Dynamic Programming

适用于求解具有最优子结构的问题,其优点在于重复计算较少,效率高,可以通过将问题划分为多个子问题来简化问题,但缺点则是需要存储中间结果,占用空间较大,不能很好地处理某些非最优子结构的问题。对动态规划可以通过记忆化搜索、状态压缩等方式进行改良。

贪心算法 Greedy

适用于具有贪心选择性质的问题,其优点在于算法简单易于实现,通常时间效率较高,但其缺点在于得到的不一定是最优解,难以证明其正确性,对于某些问题也无法使用贪心策略。对贪心法可以通过局部搜索等启发式方法、迭代深化策略等方式进行改良。

分治算法 Divide and Conquer

适用于将一个大问题划分为多个相似子问题的情况,其优点包括对于一些规模较大的问题可以减少问题的复杂度,可以利用并行计算提高效率,但其缺点在于划分子问题需要一定的技巧和经验,对于一些问题,划分子问题也比较困难。对分治法可以通过增加唯一性条件来避免重复计算、引入随机化算法等方式进行改良。


分治法应用

在计算机算法中,回溯法是一种常见的算法思想,通常用于解决组合问题、排列问题、搜索问题等。回溯法的基本思路是:从问题的子集或解空间开始,逐渐向下一步扩展,直到找到问题的解,或者无解时回溯到上一步继续搜索。

除了 n 皇后问题外,回溯法还有许多其他应用问题,如:

  1. 组合总和问题:给定一个正整数数组 candidates 和一个正整数 target,找出 candidates 中所有可以使数字和等于 target 的唯一组合。这个问题可以通过回溯法的思想来解决。

  2. 全排列问题:给定一个包含不同整数的数组 nums,返回其所有可能的全排列。这个问题也可以通过回溯法来解决。

  3. 单词搜索问题:给定一个 m × n 的二维字符网格和一个字符串 word,如果 word 存在于网格中,则返回 true;否则,返回 false。单词搜索问题也可以通过回溯法来解决。

  4. 八皇后问题:在 8×8 的国际象棋棋盘中放置 8 个皇后,使它们互相攻击不了。这也是一个著名的回溯法应用问题。

总之,回溯法是一种常见的算法思想,适用于许多组合、排列和搜索问题。在实际应用中,我们可以根据具体问题的特点和要求,选择合适的回溯法算法来解决。


01背包(动态规划)

#include <stdio.h>
#include <math.h>#define N 6  // 背包空间// 物品
#define W 4  // 物品数量
int value[] = {7,3,5,2};   // 价值
int weight[] = {1,2,5,4};    // 重量// 数组记录
int count[W+1][N+1] = {};int main(){int t,f;  // 两个for循环// 数组初始化for(t=0; t<W+1; t++){for(f=0; f<N+1; f++){count[t][f] =0;}}int i,j;  // 两个for循环for(i=1; i<W+1; i++){    // 遍历所有物品int nowWeight = weight[i-1];  // 当前物品的重量int nowValue = value[i-1];   // 当前价值for(j=1; j<N+1; j++){   // 遍历从 1 - 10重量的情况// 如果可以加上当前物品——并且——加上后的价值大于之前记录的价值,则更新——不行则记录之前的!if(nowWeight<=j && nowValue + count[i-1][j-nowWeight] > count[i-1][j]){count[i][j] = nowValue + count[i-1][j-nowWeight];}else{count[i][j] = count[i-1][j];}}}int n,m;  // 两个for循环// 打印结果for(n=0; n<W+1; n++){for(m=0; m<N+1; m++){printf("%d ",count[n][m]);}printf("\n");}return 0;
}

N皇后(回溯法)

递归方法:

#include <stdio.h>
#include <math.h>#define N 4
int q[N+1];     // 数组里面存储的是——皇后所在的列号   [i,j]     j = q[i] j列号   i行号(第i个皇后)
int answer = 0; // 方案数int queenCheck(int j){    // 行号int i = 0;for(i=0;i < j; i++){   // 循环判断 前面的所有皇后if(q[i] == q[j] || abs(j-i) == abs(q[j]-q[i])){  // 是否在同一列 || 是否在同一个斜线上return 0; // 不合法}}return 1; // 合法
}void queenInit(){int i;for(i=0; i<=N; i++){q[i] = 0;}
}void printAnswer(){int i;printf("plan %d:",answer);for(i=0; i<=N; i++){printf("%d ",q[i]);}printf("\n");
}void queenFunc(int j){  // 从第j个皇后开始int i;for(i=1;i<=N;i++){q[j] = i;   // 位置不断往后挪//如果合法if(queenCheck(j)){if(j == N){  // 找到了 N皇后的一组解answer++;printAnswer();  // 打印方案}else{queenFunc(j+1);   // 下一个皇后}}}
}int main(){queenInit(); // 初始化QueenqueenFunc(1); // 执行return 0;
}

迭代方法:

#include <stdio.h>
#include <math.h>#define N 8
int q[N+1];     // 数组里面存储的是——皇后所在的列号   [i,j]     j = q[i] j列号   i行号(第i个皇后)int queenCheck(int j){    // 行号int i = 0;for(i=0;i < j; i++){   // 循环判断 前面的所有皇后if(q[i] == q[j] || abs(j-i) == abs(q[j]-q[i])){  // 是否在同一列 || 是否在同一个斜线上return 0; // 不合法}}return 1; // 合法
}void queenInit(){int i;for(i=0; i<=N; i++){q[i] = 0;}
}
void printAnswer(int answer){int i=0;printf("plan %d:",answer);for(i=0; i<=N; i++){printf("%d ",q[i]);}printf("\n");
}void queenFunc(){int answer = 0; // 方案数int j = 1; // 从第一个皇后开始while (j>=1){q[j] =q[j] + 1;    // 从1开始,方便比较while (!queenCheck(j) && q[j]<=N){  // 不合法 && 位置没有超出q[j] +=1;  // 往后挪}if(q[j]<=N){ // 找到了合法位置if(j == N){  // 找到了 N皇后的一组解answer++;printAnswer(answer);  // 打印方案}else{j++;  // 下一个皇后}}else{    // 溢出了也没有找到——回溯!!q[j] = 0; // 把失败的皇后位置重置j--;   // 回溯  ---如果一直回溯到之前的第一行皇后 ---此时皇后位置也越界了————那么说明——已经把全部的方案都走完了!}}printf("all plans: %d",answer);}int main(){queenInit(); // 初始化QueenqueenFunc(); // 执行return 0;
}


http://www.ppmy.cn/news/107585.html

相关文章

Linux安装Redis数据库,实现远程连接

文章目录 1. Linux(centos8)安装redis数据库2. 配置redis数据库3. 内网穿透3.1 安装cpolar内网穿透3.2 创建隧道映射本地端口 4. 配置固定TCP端口地址4.1 保留一个固定tcp地址4.2 配置固定TCP地址4.3 使用固定的tcp地址连接 转发自cpolar内网穿透的文章&#xff1a;公网远程连接…

AHB-to-APB Bridge——06testbench、env、base_test、scb

框架&#xff1a; testbench&#xff1a; HCLK_PCLK_RATIO&#xff1a;随机定义hclk pclk比率&#xff1b;各个接口clk、rst连接&#xff1b;生成满足相应比率的pclk&#xff1b;与DUT的连接&#xff1b;将vif set到agt中去&#xff1b;agt在set到底层 关于rest_if&#xff…

【满分】【华为OD机试真题2023B卷 JAVAJS】数字游戏

华为OD2023(B卷)机试题库全覆盖,刷题指南点这里 数字游戏 时间限制:1s 空间限制:256MB 限定语言:不限 题目描述: 小明玩一个游戏。系统发1+n张牌,每张牌上有一个整数。第一张给小明,后n张按照发牌顺序排成连续的一行。需要小明判断,后n张牌中,是否存在连续的若干张…

QT的标准对话框使用

QT 中提供的标准对话框&#xff1a; QColorDialog QFileDialog QFontDialog QInputDialog QMessageBox QProgressDialog 1 颜色选择对话框使用: void ShowColorSelectDialog(){QTextStream out(stdout);//颜色对话框:QColor color QColorDialog::getColor(Qt::blue,this,&qu…

生产环境之负载均衡LVS+keepalived方案(2)_LVS介绍

LVS简介 LVS&#xff08;Linux Virtual Server&#xff09;即Linux虚拟服务器&#xff0c;linux内核2.6.X之后的版本默认已集成了LVS模块&#xff08;内核模块名为&#xff1a;ipvs&#xff09;&#xff0c;实现了基于传输层的请求负载均衡调度方案&#xff0c;LVS支持的工作模…

Data Feed数据源

本文档参考backtrader官方文档,是官方文档的完整中文翻译,可作为backtrader中文教程、backtrader中文参考手册、backtrader中文开发手册、backtrader入门资料使用。 Data Feed数据源章节目录 数据源(data feed)数据源概述数据源通用参数CSV数据源通用参数GenericCSVData数据源…

公开报名|CCPTP云渗透测试认证专家第二期培训班,将在云网基础设施安全国家工程研究中心举办

CCPTP云渗透测试认证专家由云安全联盟大中华区发布&#xff0c;是全球首个云渗透测试能力培养课程及人才培养认证&#xff0c;弥补了国内云渗透测试认知的差距和技能型人才培养的空白。4月1日-13日&#xff0c;CCPTP 首期班成功举办&#xff0c;于2023年5月10日部分学员完成考试…

如何Debug调试Android程序

当开发过程中遇到一些奇怪的bug&#xff0c;但又迟迟定位不出来原因是什么的时候&#xff0c;最好的解决办法就是调试了。调试允许我们逐行地执行代码&#xff0c;并可以实时观察内存中的数据&#xff0c;从而能够比较轻易地查出问题的原因。总结一下使用Android Studio来调试A…