杨氏矩阵和杨辉三角的空间复杂度较小的解题思路
文章目录
- 题目1 杨氏矩阵
- 题目2 杨辉三角
题目1 杨氏矩阵
有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。
要求:时间复杂度小于O(N);
思路:
我们可以通过题目要求分析得到:矩阵最右上角的数是一行中最大的数,是一列中最小的数
我们可以将这个数和需要查找的数进行比较:
如果这个数比查找的数大,说明查找的数肯定不在这一列,往左查找。
如果这个数比查找的数小,说明该行肯定没有这个数,往下查找。
举例分析:
矩阵
1 2 3
4 5 6
7 8 9
如果我们要查找5
(1)先和最右上角的3进行对比,5比3大,3又是第0行最大的数,所以该行肯定没有5,往下查找。
查找的范围为:
4 5 6
7 8 9
(2)此时最右上角的数为6,6比5大,6这一列的数肯定都比6大,所以这一列肯定没有5,往左查找。
查找的范围为:
4 5
7 8
(3)此时最右上角的数为5,成功找到该数并打印出所在矩阵的位置。
其他情况依次类推。
代码如下:
#include <stdio.h>
#define N 3
int main()
{int arr[N][N] = { {1,2,3},{4,5,6},{7,8,9} };int num;int flag;while (scanf("%d", &num) != EOF){int i = 0;int j = N - 1; //开始的i和j定位到矩阵最右上角的数flag = 0; //假设最开始找不到该数while(i < N && j >= 0){if (arr[i][j] > num)//如果最右上脚的数比查找的数大,则可以不用再查找这一列{j--;}else if (arr[i][j] < num){i++;}else{flag = 1;break;}}if (flag == 1){printf("成功查找到该数,该数处于第 %d 行,第 %d 列\n", i + 1, j + 1);}else{printf("该矩阵中找不到该数\n");}}return 0;
}
结果如图:
题目2 杨辉三角
在屏幕上打印杨辉三角:
1
1 1
1 2 1
1 3 3 1
……
思路:
首先我们观察杨辉三角的例子,可以找到规律:假设这是一个正方形,空白的地方对应的数是0,除去第一列的数都是1,每一行后面的每个数都是由上面一行该位置的数加上其前面的一个数之和。
我们可以发现,从第二行开始,每一行只和上面一行有联系,所以我们可以填一行的数组就打印一行,不用二维数组来解决,降低空间复杂度。
我们可以用一维数组的方式来实现,除去第一列,每一行后面的数的值等于当前位置的数加上前面一个位置的数之和。
因为我们每次将两个数相加时,要保证这两个数的值都没有被修改过
如果我们从左往右赋值,后面的数在进行相加的时候前面的数已经被修改了,会导致后面的数都是一样的,所以,我们需要从右往左依次计算结果。
举例分析:
假如我们想要输出杨辉三角前三行。
我们可以把杨辉三角看成
1 0 0
1 1 0
1 2 1
(0只是方便我们思考与计算,最终不用打印出来)
(1)首先每一列第一个数都是1,第一行直接打印1就行。
(2)此时数组的值分别为1 0 0,开始打印第二行,把第一行的数转换成第二行的数,可以发现第二行跟第一行的区别就是第二行第二个数是1,在第一行的基础上,我们可以将第二个数0和前面的1相加(标重的字体),将结果得到的1替换掉当前位置的0,然后直接输出,继续下一行的打印。
(3)此时数组的值分别为1 1 0,第三行后面两个数都和第二行不同,如果用刚才的思路,从左往右计算,那么,第三个数的计算就会变成0+2替换掉0,数组为1 2 2,显然不满足题目要求,第二个数先被修改了导致第三个数错误,所以,为了满足前面的数不被修改,我们需要从右往左计算。
(4)数组为1 1 0,首先计算第三个数,0+1=1,替换掉0,得到数组1 1 1,然后计算第二个数,1+1=2,替换掉当前位置的1,得到数组1 2 1,将第二行转换成第三行,之后输出结果。
代码如下:
#include <stdio.h>
#define N 10
int main()
{int arr[N] = { 1 };printf("1\n"); //第一行只有一个1,直接打印int i = 0;for (i = 1; i < N; i++) //从第二行开始赋值{int j = 0;for (j = i; j > 0; j--){arr[j] += arr[j - 1]; //从右往左依次计算}for (j = 0; j <= i; j++){printf("%d ", arr[j]);}printf("\n");}return 0;
}
相关文章:

杨氏矩阵和杨辉三角的空间复杂度较小的解题思路
文章目录 题目1 杨氏矩阵题目2 杨辉三角 题目1 杨氏矩阵 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。 要求:时间复杂度小于O(N); 思路: 我们可以通过题目…...

【第六篇】SpringSecurity的权限管理
一、权限管理的实现 服务端的各种资源要被SpringSecurity的权限管理控制可以通过注解和标签两种方式来处理。 放开了相关的注解后在Controller中就可以使用相关的注解来控制了 JSR250注解 /*** JSR250*/ @Controller @RequestMapping("/user") public class UserC…...
未来工作场所:数字化转型的无限可能
探索技术如何重塑我们的工作环境与协作方式 引言 在21世纪的第三个十年,数字化转型已不再仅仅是科技公司的专利,它如同一股不可阻挡的潮流,深刻地渗透到了每一个行业的血脉之中。从灵活的远程办公模式到工作流程的智能化重构,技术…...

Landsat8的质量评估波段的一个应用
Landsat8一直是遥感界的热门话题。这不仅延续了自1972年以来NASA连续对地观测,而且这颗卫星为科学界带来了一些新的东西——质量评估波段(the Quality Assessment (QA) Band)。根据USGS Landsat Missions webpage,“QA通过标示哪个…...
OpenZeppelin Ownable合约 怎么使用
文章目录 智能合约的访问控制Ownable合约使用方法 智能合约的访问控制 熟悉OpenZeppelin的智能合约库的开发者都知道这个库已经提供了根据访问等级进行访问限制的选项,其中最常见的就是Ownable合约管理的onlyOwner模式,另一个是OpenZeppelin的Roles库&a…...
vue3框架基本使用(基础指令)
一、响应式数据 1.ref ref可以定义 基本类型的响应式数据, 也可以定义对象类型响应式数据 <template><h1>{{ name }}</h1><button click"test">修改姓名</button> </template><script setup lang"ts"…...

ubuntu20.04设置共享文件夹
ubuntu20.04设置共享文件夹 一,简介二,操作步骤1,设置Windows下的共享目录2,挂载共享文件夹3,测试是否挂载成功 一,简介 在公司电脑上,使用samba设置共享文件夹,IT安全部门权限不通…...
三十五、 欧盟是如何对法律政策环境进行评估的?
我国对于如何评估数据接收方所在法律政策环境尚无明确详细的指引,故在实践中,为了进一步提升合规水平,企业也可同步参考在数据隐私保护法治方面领先的欧盟标准。 在欧盟法院于 2020 年 7 月作出 Schrems II案件的判决后,为保证境外…...

项目实战--文档搜索引擎
在我们的学习过程中,会阅读很多的文档,例如jdk的API文档,但是在这样的大型文档中,如果没有搜索功能,我们是很难找到我们想查阅的内容的,于是我们可以实现一个搜索引擎来帮助我们阅读文档。 1. 实现思路 1…...

计算机视觉基础课程知识点总结
图像滤波 相关: 核与图像同向应用,不翻转。 卷积: 核在应用前翻转,广泛用于信号处理和深度学习(现在常说的二维卷积就是相关)。 内积: 向量化的点积操作,是相关和卷积的一部分。 模板匹配:通过在图像中…...

编译原理:语法分析
目录 引言上下文无关文法 CFG: Context-Free Grammar定义推导方法最左推导和最右推导 分析树分析树->抽象语法树常见的上下文无关文法文法设计二义性文法扩展巴科斯范式:EBNF extended Backus Normal Form 文法和语言分类相关术语直接推导推导*推导句型、句子、语…...

React 中的 Lanes
React 中有一个 Lane 的概念,Lane 就像高速路上的不同车道,具有不同优先级,在 React Lane 通过一个 32 位的二进制数来表示。越小优先级别越高,SyncLane 级别最高。用二进制存储的方式,可以通过逻辑操作快速判断 Lane …...

【复旦邱锡鹏教授《神经网络与深度学习公开课》笔记】线性分类模型损失函数对比
本节均以二分类问题为例进行展开,统一定义类别标签 y ∈ { 1 , − 1 } y\in\{1,-1\} y∈{1,−1},则分类正确时 y f ( x ; w ) > 0 yf(x;w)>0 yf(x;w)>0,且值越大越正确;错误时 y f ( x ; w ) < 0 yf(x;w)<0 yf(x;…...

数组(C语言)(详细过程!!!)
目录 数组的概念 一维数组 sizeof计算数组元素个数 二维数组 C99中的变⻓数组 数组的概念 数组是⼀组相同类型元素的集合。 数组分为⼀维数组和多维数组,多维数组⼀般比较多见的是二维数组。 从这个概念中我们就可以发现2个有价值的信息:(1)数…...

视频生成模型 Dream Machine 开放试用;微软将停止 Copilot GPTs丨 RTE 开发者日报 Vol.224
开发者朋友们大家好: 这里是 「RTE 开发者日报」 ,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE(Real-Time Engagement) 领域内「有话题的 新闻 」、「有态度的 观点 」、「有意思的 数据 」、「有思考的 文…...

Vue30-自定义指令:对象式
一、需求:创建fbind指定 要用js代码实现自动获取焦点的功能! 二、实现 2-1、步骤一:绑定元素 2-2、步骤二:input元素获取焦点 此时,页面初始化的时候,input元素并没有获取焦点,点击按钮&…...

2024/06/13--代码随想录算法(贪心)3/6|134.加油站、135.分发糖果、860.柠檬水找零、406.根据身高重建队列
134.加油站 力扣链接 class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:curSum 0 # 当前累计的剩余油量totalSum 0 # 总剩余油量start 0 # 起始位置for i in range(len(gas)):curSum gas[i] - cost[i]totalSum gas[i] - co…...
机器学习的分类
机器学习分类 机器学习是人工智能的一个分支,它使计算机系统能够从数据中学习并做出决策或预测。机器学习(Machine Learning)是一种基于数据驱动的方法,旨在通过自动化的统计模型和算法从数据中学习和提取模式,以进…...

【Linux】进程控制3——进程程序替换
一,前言 创建子进程的目的之一就是为了代劳父进程执行父进程的部分代码,也就是说本质上来说父子进程都是执行的同一个代码段的数据,在子进程修改数据的时候进行写时拷贝修改数据段的部分数据。 但是还有一个目的——将子进程在运行时指向一个…...

PFC旁路二极管、继电器驱动电路以及PFC主功率
R001和R002以及R003三个电阻作用是限放X电容上的电 整流桥串联两个BJ1和BJ2 电容C3:给整流桥储能,给后续llc供电 PFC工作是正弦波上叠加高频电流 PFC功率部分 2个PFC电感(选择两个磁芯骨架小,有利于散热)、2个续流二极管&…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...