枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这里他们就是判断类问题我们就可以使用枚举。

​ 但是注意这里我们需要考虑的就是枚举的方式,也就是枚举的角度。这里有一个小的例子就是最长回文子串的问题。

​ 首先我们就是用一个最简单的方式就是枚举出所有的字串,然后在这些字串里面找回文串。这样我们首先需要进行枚举就需要 n 平方的复杂度,然后我们还需要 n 的时间去判断这个串是不是回文,那么也就是说我们需要 n 三次方的时间复杂度。

​ 然后上面的方式枚举的对象就是所有的字串,但是我们仔细就会发现重点在于回文子串的中心,如果我们枚举的是回文子串的中心以及回文的长度,我们就更简单的找到最长回文子串。中心不仅仅就是每一个字符还包括他们之间的缝隙,这样我们就有了 2n + 1 个中心,然后在对他们进行回文判断,最后的时间复杂度也就是 n 平方。

​ 这里是从 n 三次方降到了 n 平方的复杂度,这样的原因在于我们去掉了很多的无用的字串,第一个枚举的方法就是枚举所有的字串,然后第二个就是仅仅找出那些具有回文形式的字串,这样就少了一个 n 。经常这样思考会慢慢锻炼我们优化时间复杂度的能力。

​ 并且这里看着是 n 平方其实他根本没有那么多的复杂度,因为每一个中心能找到的会问其实并不多除非我们给的一个串是一个完全相同的字符,这也就是第二种算法的最坏情况。

​ 其实在枚举的过程中有的枚举并没有必要,因为这些就是用来占用了时间复杂度但是没有给程序带来多大的帮助。然后我们在计算的时候有时候题目给的条件很少,这时候我们就需要使用枚举来增加我们已知的条件。

​ 再看一个例子就是在一个矩阵中填满数,然后这些数有正有负我们需要获取一个和的最大矩阵。这里我们先不考虑 DP 而是使用枚举的方式来解这道题。因为这道题的内容是静态的,也就是矩阵是不变化的,我们可以使用计算存储,然后再使用排容原理解题。首先我们考虑一维的情况,我们可以新开一个矩阵,这个矩阵的目的就在于把原来的矩阵的到当前位置的和记录下来。这样我们仅仅需要一次的扫描就能获取从 0 到当前位置的和,然后我们可以计算出任何两个点的之间的和,使用排容原理,就是后面的下标的和减去前面的下标的和即可。这样一个最大的和我们就可以使用 n 的复杂度完成。

​ 然后我们扩展到二维的情况,就是新开一个矩阵,然后每一个位置记录 ( 0 , 0 ) 位置到当前位置的和。至于这个和怎么算还需要一个过程,中间我们还需要构造一个矩阵,这个矩阵就是先计算出每一行的和,也就是我们上面所说的一维的情况,然后再过渡到二维的辅助阵列。

​ 那么这个算法的复杂度就是一开始我们需要算出这个辅助矩阵的和需要 n 平方的时间,然后需要进行排容原理,也就是我们要枚举左上角和右下角的位置这里就需要 n 的四次方的时间。

​ 但是这样做还是不够好,也就是我们枚举了每一个矩形,我们只是优化了 计算矩形的和。但是我们可以使用另外一种思路就是枚举左右边界,然后我们计算出上下界,这样的话这里的时间复杂度就是 n 平方乘以我们算出上下界的时间。而我们算上下界的时候因为我们已经指定了宽度所以说这个宽度之间的东西我们可以把它影射成一维的解决即可。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】问题1075: 台球碰撞(此次问题较难)

题目描述 在平面直角坐标系下,台球桌是一个左下角在(0,0),右上角在(L,W)的矩形。有一个球心在(x,y),半径为R的圆形母球放在台球桌上(整个球都在台球...

28150
来自专栏Python小屋

最快的组合数算法之Python实现

原理:以Cni(8,3)为例,按定义式将其展开为(8*7*6*5*4*3*2*1)/(3*2*1)/(5*4*3*2*1),对于8到6之间的数,分子上出现一次而...

37670
来自专栏爱撒谎的男孩

回溯算法

28430
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

39380
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

36240
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

34540
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

34860
来自专栏ACM算法日常

海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

11220
来自专栏Small Code

【Python】统计字符串中英文、空格、数字、标点个数

题外话:今天打酱油的做了**数据挖掘工程师的在线笔试题,被打击了。 本文代码可在 这里 下载。 问题 在网上无意间看到这么一个题目:统计一个字符串中的中英文、空...

69650
来自专栏数据小魔方

求和函数系列——sum函数家族

今天要跟大家分享的是一组求和函数系列——sum函数家族! excel中最长用到的求和函数就是sum函数系列了,sum函数系列一共有三组函数: sum sumif...

29240

扫码关注云+社区

领取腾讯云代金券