当前位置:首页 » 操作系统 » 算法模板题

算法模板题

发布时间: 2024-09-05 22:19:28

Ⅰ 回溯算法与贪心算法

回溯是递归的副产品,只要有递归就会有回溯 ,所以回溯法也经常和二叉树遍历,深度优先搜索混在一起,因为这两种方式都是用了递归。

回溯法就是暴力搜索,并不是什么高效的算法,最多再剪枝一下。

回溯算法能解决如下问题:

组合问题:N个数里面按一定规则找出k个数的集合

排列问题:N个数按一定规则全排列,有几种排列方式

切割问题:一个字符串按一定规则有几种切割方式

子集问题:一个N个数的集合里有多少符合条件的子集

棋盘问题:N皇后,解数独等等

回溯算法的本质是纵向遍历

回溯算法模板为

贪心的本质是选择每一阶段的局部最优,从而达到全局最优

贪心算法一般分为如下四步:

将问题分解为若干个子问题

找出适合的贪心策略

求解每一个子问题的最优解

将局部最优解堆叠成全局最优解

eg:摆动序列

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]

输出: 7

解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。

热点内容
饥荒联机版服务器搭建程序 发布:2025-03-16 02:55:18 浏览:684
win7如何访问共享 发布:2025-03-16 02:55:14 浏览:37
centosphp升级 发布:2025-03-16 02:42:04 浏览:52
绝地求生体验服为什么服务器已满了 发布:2025-03-16 02:42:03 浏览:706
服务器电脑机房是干嘛的 发布:2025-03-16 02:30:47 浏览:489
龙贝格算法c语言 发布:2025-03-16 02:26:28 浏览:102
c语言字符串读入 发布:2025-03-16 02:21:23 浏览:478
python爬虫开发环境 发布:2025-03-16 02:19:55 浏览:627
androidondestory 发布:2025-03-16 02:12:49 浏览:863
软件源码侵权 发布:2025-03-16 02:06:54 浏览:288