杨氏矩阵和杨辉三角


杨氏矩阵

有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。

要求:时间复杂度小于O(N);

分析

若要满足要求时间复杂度小于O(N),就不能每一行一个个找。

根据杨氏矩阵的特点(行递增、列递增),我们可以从矩阵的右上角开始,

就比如我们要找上图中的数字7,

9>7,因为列递增 ,9是该列最小的数字,都大于7,所以第4列的数字都比7大,排除第4列

右上角数字变为了6,6<7,因为递增,6是该行最大的数字,都小于7,所以第1行的数字都比7小,排除第1行

右上角数字变为了7,7=7,找到了

代码实现

//             假设有4列,x行,y列,key是要找的数字
int FindNum(int arr[][4], int x, int y, int key)
{int i = 0;int j = y - 1;//满足此循环,i和j都是合法的while (j >= 0 && i < x){if (arr[i][j] > key){j--;}else if (arr[i][j] < key){i++;}else{return 1;//找到了}}return 0;//没找到
}

杨辉三角

在屏幕上打印杨辉三角

分析

杨辉三角的特点:除了外围的数字为1,其他满足 数字 这列的上一行数字 + 上一行前一列数字

我们定义有i行j列

其中数字是1的下标满足:j==0或i==j

其他数字的下标满足:[i][j] = [i-1][j] + [i-1][j-1]

代码实现

#include<stdio.h>
//在屏幕上打印杨辉三角。
void YanghuiTriangle(int arr[][4], int n)
{for (int i = 0; i < n; i++){for (int j = 0; j <= i; j++){if (j == 0 || i == j){arr[i][j] = 1;}else{arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];}}}//打印for (int i = 0; i < n; i++){for (int j = 0; j <= i; j++){printf("%d ", arr[i][j]);}printf("\n");}
}
int main()
{int arr[4][4] = { 0 };YanghuiTriangle(arr, 4);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/259921.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

树和二叉树的基本知识

一、树的概念及结构 1.树的概念 树是一种 非线性 的数据结构&#xff0c;它是由 n &#xff08; n>0 &#xff09;个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的 。 有一个 特殊…

阿里云服务器“镜像”全方面解析

阿里云服务器镜像怎么选择&#xff1f;云服务器操作系统镜像分为Linux和Windows两大类&#xff0c;Linux可以选择Alibaba Cloud Linux&#xff0c;Windows可以选择Windows Server 2022数据中心版64位中文版&#xff0c;阿里云服务器网aliyunfuwuqi.com来详细说下阿里云服务器操…

软考29-上午题-排序

一、排序的基本概念 1-1、稳定性 稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后&#xff0c;次序不变&#xff0c;则是稳定的。 1-2、归位 每一趟排序能确定一个元素的最终位置。 1-3、内部排序 排序记录全部存放在内存中进行排序的过程。 1-4、外部…

【网络安全 | 网络协议】一文讲清HTTP协议

HTTP概念简述 HTTP&#xff08;Hypertext Transfer Protocol&#xff09;协议&#xff0c;又称超文本传输协议&#xff0c;用于传输文本、图像、音频、视频以及其他多媒体文件。它是Web应用程序通信的基础&#xff0c;通过HTTP协议&#xff0c;Web浏览器可以向Web服务器发起请…

电路设计(20)——数字电子钟的multism仿真

1.设计要求 使用数字芯片&#xff0c;设计一个电子钟&#xff0c;用数码管显示&#xff0c;可以显示星期&#xff0c;时、分、秒&#xff0c;可以有按键校准时间。有整点报警功能。 2.设计电路 设计好的multism电路图如下所示 3.芯片介绍 时基脉冲使用555芯片产生。在仿真里面…

挑战杯 地铁大数据客流分析系统 设计与实现

文章目录 1 前言1.1 实现目的 2 数据集2.2 数据集概况2.3 数据字段 3 实现效果3.1 地铁数据整体概况3.2 平均指标3.3 地铁2018年9月开通运营的线路3.4 客流量相关统计3.4.1 线路客流量排行3.4.2 站点客流量排行3.4.3 入站客流排行3.4.4 整体客流随时间变化趋势3.4.5 不同线路客…

NodeLocal DNS介绍及部署应用

1 NodeLocal DNS是什么&#xff1f; NodeLocal DNSCache 通过在集群节点上运行一个 DaemonSet 来提高 clusterDNS 性能和可靠性。处于 ClusterFirst 的 DNS 模式下的 Pod 可以连接到 kube-dns 的 serviceIP 进行 DNS 查询。通过 kube-proxy 组件添加的 iptables 规则将其转换为…

蓝桥杯DP算法——背包问题(C++)

目录 一、01背包问题 二、完全背包问题 三、多重背包问题 四、多重背包问题&#xff08;优化版&#xff09; 五、分组背包问题 一、01背包问题 01背包问题就是有N件物品&#xff0c;一个空间大小为V的背包&#xff0c;每个物品只能使用一次&#xff0c;使得背包中所装物品…

2019年江苏省职教高考计算机技能考试——一道程序改错题的分析

题目&#xff1a;函数将str字符串中的5个数字字符串转换为整数&#xff0c;并保存在二维数组m的最后一行&#xff0c;各元素为3、-4、16、18、6。并经函数move处理后&#xff0c;运行结果如下&#xff1a; 18 6 3 -4 16 16 18 6 3 -4 -4 16 …

【AIGC】Stable Diffusion之模型微调工具

推荐一款好用的模型微调工具&#xff0c;cybertron furnace 是一个lora训练整合包&#xff0c;提供训练 lora 模型的工具集或环境。集成环境包括必要的依赖项和配置文件、预训练脚本&#xff0c;支持人物、二次元、画风、自定义lora的训练&#xff0c;以简化用户训练 lora 模型…

【Linux】软件包管理器 yum | vim编辑器

前言: 软件包管理器 yum和vim编辑器讲解 文章目录 软件包管理器 yum编辑器-vim四种模式普通模式批量化注释和批量化去注释末行模式临时文件 软件包管理器 yum yum&#xff08;Yellowdog Updater, Modified&#xff09;是一个在基于 RPM&#xff08;管理软件包的格式和工具集合&…

软考学习--计算机组成原理与体系结构

计算机组成原理与体系结构 数据的表示 进制转换 R 进制转换为 10 进制–按权展开法 10进制转换为2进制 原码 反码 补码 移码 原码 &#xff1a;数字的二进制表示反码 &#xff1a; 正数的反码等于原码&#xff0c;负数的反码等于原码取反补码&#xff1a; 正数的补码等…

跟着pink老师前端入门教程-day24

四、移动端WEB开发之响应式布局 1、响应式开发 1.1 响应式开发原理 就是使用媒体查询针对不同宽度的设备进行布局和样式的设置&#xff0c;从而适配不同设备的目的。 1.2 响应式布局容器 响应式需要一个父级做为布局容器&#xff0c;来配合子级元素来实现变化效果。 原理…

世界顶级名校计算机专业,都在用哪些书当教材?(文末送书)

目录 01《深入理解计算机系统》02《算法导论》03《计算机程序的构造和解释》04《数据库系统概念》05《计算机组成与设计&#xff1a;硬件/软件接口》06《离散数学及其应用》07《组合数学》08《斯坦福算法博弈论二十讲》参与规则 清华、北大、MIT、CMU、斯坦福的学霸们在新学期里…

FL Studio 21.2.3.4004 All Plugins Edition Win/Mac音乐软件

FL Studio 21.2.3.4004 All Plugins Edition 是一款功能强大的音乐制作软件&#xff0c;提供了丰富的音频处理工具和插件&#xff0c;适用于专业音乐制作人和爱好者。该软件具有直观的用户界面&#xff0c;支持多轨道录音、混音和编辑&#xff0c;以及各种音频效果和虚拟乐器。…

《统计学简易速速上手小册》第6章:多变量数据分析(2024 最新版)

文章目录 6.1 主成分分析&#xff08;PCA&#xff09;6.1.1 基础知识6.1.2 主要案例&#xff1a;客户细分6.1.3 拓展案例 1&#xff1a;面部识别6.1.4 拓展案例 2&#xff1a;基因数据分析 6.2 聚类分析6.2.1 基础知识6.2.2 主要案例&#xff1a;市场细分6.2.3 拓展案例 1&…

探索设计模式的魅力:迭代器模式让你轻松驾驭复杂数据集合

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;并且坚持默默的做事。 文章目录 一、&#x1f4a1; 引言二、原理与结构 &#x1f4da;&#x1f465; 迭代器模式的关…

【二十八】springboot整合logback实现日志管理

本章节是记录logback在springboot项目中的简单使用&#xff0c;本文将会演示如何通过logback将日志记录到日志文件或输出到控制台等管理操作。将会从以下几个方面进行讲解。最后实现将特定级别的特定日志保存到日志文件。 一、依赖 <dependency><groupId>ch.qos.l…

基于python的遥感影像灰色关联矩阵纹理特征计算

遥感影像纹理特征是描述影像中像素间空间关系的统计特征&#xff0c;常用于地物分类、目标识别和变化检测等遥感应用中。常见的纹理特征计算方式包括灰度共生矩阵&#xff08;GLCM&#xff09;、灰度差异矩阵&#xff08;GLDM&#xff09;、灰度不均匀性矩阵&#xff08;GLRLM&…

51_蓝桥杯_led流水灯

一 原理图分析 二 三八译码器工作原理 三八译码器&#xff1a;3个输入控制8路互斥的低电平有效输出。 C B A 输出 0 0 0 Y0 0 0 1 Y1 0 1 0 Y2 0 1 1 Y3 1 0 0 Y4 1 0 1 Y5 1 1 0 Y6 1 1 1 Y7 三 锁存器工作原理 锁存器&#xff1a;当使…