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

杨氏矩阵和杨辉三角的空间复杂度较小的解题思路


文章目录

  • 题目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 杨氏矩阵 有一个数字矩阵&#xff0c;矩阵的每行从左到右是递增的&#xff0c;矩阵从上到下是递增的&#xff0c;请编写程序在这样的矩阵中查找某个数字是否存在。 要求&#xff1a;时间复杂度小于O(N); 思路: 我们可以通过题目…...

【第六篇】SpringSecurity的权限管理

一、权限管理的实现 服务端的各种资源要被SpringSecurity的权限管理控制可以通过注解和标签两种方式来处理。 放开了相关的注解后在Controller中就可以使用相关的注解来控制了 JSR250注解 /*** JSR250*/ @Controller @RequestMapping("/user") public class UserC…...

未来工作场所:数字化转型的无限可能

探索技术如何重塑我们的工作环境与协作方式 引言 在21世纪的第三个十年&#xff0c;数字化转型已不再仅仅是科技公司的专利&#xff0c;它如同一股不可阻挡的潮流&#xff0c;深刻地渗透到了每一个行业的血脉之中。从灵活的远程办公模式到工作流程的智能化重构&#xff0c;技术…...

Landsat8的质量评估波段的一个应用

Landsat8一直是遥感界的热门话题。这不仅延续了自1972年以来NASA连续对地观测&#xff0c;而且这颗卫星为科学界带来了一些新的东西——质量评估波段&#xff08;the Quality Assessment (QA) Band&#xff09;。根据USGS Landsat Missions webpage&#xff0c;“QA通过标示哪个…...

OpenZeppelin Ownable合约 怎么使用

文章目录 智能合约的访问控制Ownable合约使用方法 智能合约的访问控制 熟悉OpenZeppelin的智能合约库的开发者都知道这个库已经提供了根据访问等级进行访问限制的选项&#xff0c;其中最常见的就是Ownable合约管理的onlyOwner模式&#xff0c;另一个是OpenZeppelin的Roles库&a…...

vue3框架基本使用(基础指令)

一、响应式数据 1.ref ref可以定义 基本类型的响应式数据&#xff0c; 也可以定义对象类型响应式数据 <template><h1>{{ name }}</h1><button click"test">修改姓名</button> </template><script setup lang"ts"…...

ubuntu20.04设置共享文件夹

ubuntu20.04设置共享文件夹 一&#xff0c;简介二&#xff0c;操作步骤1&#xff0c;设置Windows下的共享目录2&#xff0c;挂载共享文件夹3&#xff0c;测试是否挂载成功 一&#xff0c;简介 在公司电脑上&#xff0c;使用samba设置共享文件夹&#xff0c;IT安全部门权限不通…...

三十五、 欧盟是如何对法律政策环境进行评估的?

我国对于如何评估数据接收方所在法律政策环境尚无明确详细的指引&#xff0c;故在实践中&#xff0c;为了进一步提升合规水平&#xff0c;企业也可同步参考在数据隐私保护法治方面领先的欧盟标准。 在欧盟法院于 2020 年 7 月作出 Schrems II案件的判决后&#xff0c;为保证境外…...

项目实战--文档搜索引擎

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

计算机视觉基础课程知识点总结

图像滤波 相关: 核与图像同向应用&#xff0c;不翻转。 卷积: 核在应用前翻转&#xff0c;广泛用于信号处理和深度学习&#xff08;现在常说的二维卷积就是相关&#xff09;。 内积: 向量化的点积操作&#xff0c;是相关和卷积的一部分。 模板匹配&#xff1a;通过在图像中…...

编译原理:语法分析

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

React 中的 Lanes

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

【复旦邱锡鹏教授《神经网络与深度学习公开课》笔记】线性分类模型损失函数对比

本节均以二分类问题为例进行展开&#xff0c;统一定义类别标签 y ∈ { 1 , − 1 } y\in\{1,-1\} y∈{1,−1}&#xff0c;则分类正确时 y f ( x ; w ) > 0 yf(x;w)>0 yf(x;w)>0&#xff0c;且值越大越正确&#xff1b;错误时 y f ( x ; w ) < 0 yf(x;w)<0 yf(x;…...

数组(C语言)(详细过程!!!)

目录 数组的概念 一维数组 sizeof计算数组元素个数 二维数组 C99中的变⻓数组 数组的概念 数组是⼀组相同类型元素的集合。 数组分为⼀维数组和多维数组&#xff0c;多维数组⼀般比较多见的是二维数组。 从这个概念中我们就可以发现2个有价值的信息&#xff1a;(1)数…...

视频生成模型 Dream Machine 开放试用;微软将停止 Copilot GPTs丨 RTE 开发者日报 Vol.224

开发者朋友们大家好&#xff1a; 这里是 「RTE 开发者日报」 &#xff0c;每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE&#xff08;Real-Time Engagement&#xff09; 领域内「有话题的 新闻 」、「有态度的 观点 」、「有意思的 数据 」、「有思考的 文…...

Vue30-自定义指令:对象式

一、需求&#xff1a;创建fbind指定 要用js代码实现自动获取焦点的功能&#xff01; 二、实现 2-1、步骤一&#xff1a;绑定元素 2-2、步骤二&#xff1a;input元素获取焦点 此时&#xff0c;页面初始化的时候&#xff0c;input元素并没有获取焦点&#xff0c;点击按钮&…...

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…...

机器学习的分类

机器学习分类 ​ 机器学习是人工智能的一个分支&#xff0c;它使计算机系统能够从数据中学习并做出决策或预测。机器学习&#xff08;Machine Learning&#xff09;是一种基于数据驱动的方法&#xff0c;旨在通过自动化的统计模型和算法从数据中学习和提取模式&#xff0c;以进…...

【Linux】进程控制3——进程程序替换

一&#xff0c;前言 创建子进程的目的之一就是为了代劳父进程执行父进程的部分代码&#xff0c;也就是说本质上来说父子进程都是执行的同一个代码段的数据&#xff0c;在子进程修改数据的时候进行写时拷贝修改数据段的部分数据。 但是还有一个目的——将子进程在运行时指向一个…...

PFC旁路二极管、继电器驱动电路以及PFC主功率

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

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...