当前位置: 首页 > news >正文

食材网站模板微信推广的好处

食材网站模板,微信推广的好处,做营销型网站公司,哪些网做网站比较好前言 最近被我大哥安利了一道算法题, 这道题说难, 还不至于我做不出来, 说简单吧, 我还想不到最优解, 等把最优解告诉我之后, 我还正好能理解. 我甚至曾经怯怯的认为, 这题就是我哥专门给我找的, 嘿嘿, 心中说不出的小欢喜. 题来了, 此题出自力扣, 原题链接: https://leetco…前言 最近被我大哥安利了一道算法题, 这道题说难, 还不至于我做不出来, 说简单吧, 我还想不到最优解, 等把最优解告诉我之后, 我还正好能理解. 我甚至曾经怯怯的认为, 这题就是我哥专门给我找的, 嘿嘿, 心中说不出的小欢喜. 题来了, 此题出自力扣, 原题链接: https://leetcode-cn.com/problems/count-submatrices-with-all-ones/ 描述: 给你一个只包含 0 和 1 的 rows * columns 矩阵 mat 请你返回有多少个 子矩形 的元素全部都是 1 。 例子: 输入mat [[1,0,1],[1,1,0],[1,1,0]] 输出13 解释 有 6 个 1x1 的矩形。 有 2 个 1x2 的矩形。 有 3 个 2x1 的矩形。 有 1 个 2x2 的矩形。 有 1 个 3x1 的矩形。 矩形数目总共 6 2 3 1 1 13 。题意清晰明了, 开始尝试解题(使用 C 来进行解题). 方案一 首先直观上最先想到的, 就是穷举了. 一力破十会. 将所有出现的情况遍历一遍, 然后就能得出总数了. 思路如下: 利用i, j 将二维数组的所有节点遍历一遍利用m, n将以[i][j]为左上顶点的子矩阵遍历一遍判断i, j, m, n四个变量确定的矩阵是否为全1矩阵 代码实现: int numSubmat(int** mat, int matSize, int* matColSize){int result 0;// 遍历所有节点for (int i 0; i matSize; i) {for (int j 0; j *matColSize; j) {// 遍历当前节点为左上顶点的所有子矩阵for (int m i; m matSize; m) {for (int n j; n *matColSize; n) {// 判断当前子矩阵是否为全1矩阵int isOk 1;for (int p i; p m; p) {for (int q j; q n; q) {if(mat[p][q] ! 1){isOk 0;break;}}if(!isOk) break;}// 计算总数if(isOk) result;}}}}return result; }随手写个测试用: #include stdio.h #include stdlib.hint numSubmat(int** mat, int matSize, int* matColSize);int main() {// 定义数组长度int matSize 3, matColSize 3;// 分配数组空间int **mat (int **)malloc(matSize*sizeof(int*));// 动态分配内容for (int i 0; i matSize; i) {mat[i] (int *)malloc(matColSize*sizeof(int));}// 给数组填内容, 这里可以接收键盘数组mat[0][0] 1;mat[0][1] 0;mat[0][2] 1;mat[1][0] 1;mat[1][1] 1;mat[1][2] 0;mat[2][0] 1;mat[2][1] 1;mat[2][2] 0;int result numSubmat(mat, matSize, matColSize);printf(%d, result);return 0; }执行过后, OK, 么的问题. 看一下时间复杂度呢? 一眼就看到了函数里的六层循环, 么的说, O(n^6). 这时, 我大哥说他的时间复杂度是 O(n^3). 那我这小心情, 必须整出来, 再想. 方案二 上面的六层循环中, 能不能想办法去掉一层呢? 有. 在最后判断是否全1的循环中, 如果左上的数字是0, 那必然没有全1子矩阵了 再如果向下找的时候, 碰到0, 那下一列的时候也没必要超过这里了, 因为子矩阵至少有一个0了, 如下图: 在向右遍历的时候同理, 这样, 我们就可以确定, 所有遍历到的值都是1, 可以将判断全1的两层循环去掉. nice. 修改代码如下: int numSubmat(int** mat, int matSize, int* matColSize){int result 0;// 遍历所有节点for (int i 0; i matSize; i) {for (int j 0; j *matColSize; j) {if(mat[i][j] 0) continue;int thisMaxColSize *matColSize; // 当前向右最大值// 遍历当前节点为左上顶点的所有子矩阵for (int m i; m matSize; m) {for (int n j; n thisMaxColSize; n) {if(mat[m][n] 1) result;// 记录向右的最大值else thisMaxColSize n;}}}}return result; }OK, 经过测试完全么的问题. 再看看现在的时间复杂度. O(n^4); 比刚才的六次方, 直接降了两个数量级. 但是比我大哥还差点意思哈. 方案三 打扰了, 没有想到O(n^3)的解法. 经过我哥的一番指点, 可以说是豁然开朗. 思路不变. 上面的四层循环, 有没有什么办法能再减少一层呢? 想一下, 我们在第四层循环中, 向右遍历, 找的是什么? 是连续1的个数, 如果我们不用向右遍历, 直接就知道了这个连续1的个数, 那是不是就可以把这一层也省了呢? 那么问题来了, 如何不遍历就知道呢? 预处理. 在所有的遍历之前, 先进行一次遍历, 把每个节点向右的连续1个数计算好. 这个思路有点妙啊. 废话不多说, 再来: int min(int a, int b){return a b ? b : a; }int numSubmat(int** mat, int matSize, int* matColSize){// 进行预处理, 将每个节点向右的连续1个数算好(从右下向左上处理)for (int i matSize - 1; i 0; i--) {for (int j *matColSize - 1; j 0 ; j--) {if(mat[i][j] 0) continue;// 最右侧不处理if(j *matColSize-1) continue;// 每个节点的数字等于右边的加1mat[i][j] mat[i][j1] 1;}}int result 0;// 遍历所有节点for (int i 0; i matSize; i) {for (int j 0; j *matColSize; j) {if(mat[i][j] 0) continue;int thisMaxColSize *matColSize; // 当前向右最大值// 遍历当前节点为左上顶点的所有子矩阵for (int m i; m matSize; m) {// 记录向右的最大值thisMaxColSize min(thisMaxColSize, mat[m][j]);result thisMaxColSize;}}}return result; }再看时间复杂度, 终于, O(n^3). 还有没有比三次方更快的解法呢? 可能..大概..或许有吧. 但是我想了好久也没有想到. 以上, 其实到第二个方案我都想到了, 但是最后一步怎么都没迈出去, 原因归结为做的少, 遇到的少. 算法题偶尔做做还挺好的, 也不需要很高深的数学知识, 还可以锻炼思维, 蛮有趣的, 之后可以抽时间来看看, 嘿嘿.
http://www.huolong8.cn/news/143457/

相关文章:

  • c 可以做网站花都网络推广seo公司
  • 海南公司网站建设网页制作培训费用多少
  • 购物网站服务器硬件配置学生个人网页设计作品代码
  • 建设部网站怎么查询企业业绩wpf做的网站
  • 网站开发网站开发设计风信子 网站建设
  • 网站百度分享怎么做上海微信网站制作哪家专业
  • 装修公司做宣传在哪个网站wordpress安装创建数据库文件目录
  • 网站右下角广告代码python采集更新wordpress
  • 网站制作的大公司手机网站开发+手机模拟器
  • 如何找到网站是谁做的做甜点的网站
  • 德州市建设局质监站网站wordpress鼠标特效主题
  • 河北省建设局网站首页漯河市万金镇网站建设
  • 网站加关键词代码wordpress 百度搜索
  • 制作网站的视频教程企业官网型网站建设
  • host绑定网站wordpress4.7 自豪
  • 沈阳做网站公司百姓网
  • 网站建设大作业有代码做房产网站长
  • 石家庄便宜做网站做电销有什么资料网站
  • 北京网站开发需要多少钱自建电商网站销售商品
  • 小型网站项目策划书广告设计专业英语
  • 手机网站被拦截怎么解除安国网站建设
  • 网站建设跟推广评价指标有什么关系wordpress的主题安装在什么目录
  • 南昌网站建设报价单品牌公司设计
  • 图书馆建设网站打不开wordpress数据库thinkphp
  • wxparse wordpress做十来个网站优化
  • 台式机做网站服务器网站内容建设的布局和结构
  • 学校网站建设招标公告建筑网招工网
  • 北京专业企业营销网站建设免费注册邮箱帐号
  • 网站服务器类型四川大学官方网站规划建设处
  • 域名网站账号seo网站建设视频教程