L25.【LeetCode笔记】 三步问题的四种解法(含矩阵精彩解法!)
目录
1.题目
2.三种常规解法
方法1:递归做
编辑
方法2:改用循环做
初写的代码
提交结果
分析
修改后的代码
提交结果
for循环的其他写法
提交结果
方法3:循环+数组
提交结果
3.方法4:矩阵
算法
代码实践
1.先计算矩阵n次方
2.后将矩阵n次方嵌入递推式中
提交结果
1.题目
https://leetcode.cn/problems/three-steps-problem-lcci/
三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
示例1:
输入:n = 3 输出:4 说明: 有四种走法示例2:
输入:n = 5 输出:13提示:
- n范围在[1, 1000000]之间
2.三种常规解法
方法1:递归做
和之前青蛙跳台阶的思想一样(参见35.【C语言】详解函数递归文章),先找递推公式,再写递归
int recursion(int n)
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;return (recursion(n-1)+recursion(n-2)+recursion(n-3))%1000000007;
}
int waysToStep(int n)
{return recursion(n);
}
算法上没问题,但是时间复杂度过高,提交后没有通过
方法2:改用循环做
初写的代码
int waysToStep(int n)
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4; int a=1;int b=2;int c=4;int d=0;for (int i=3;i<n;i++){d=a+b+c;a=b;b=c;c=d;}return c%1000000007;
}
提交结果

分析
虽然代码中返回值写成c%1000000007,但是没有完全领会题目的意思,c的值并没有真正改变,可以看看报错的数字:当n==61时,"2082876103 + 1748130326"相加溢出了,可以设想2082876103和1748130326产生的原因,n==某个数溢出了,可以使程序溢出的n的临界值
将代码最后改成return c;测试n的值
多次尝试后



当未模1000000007时,
| n==34 | n==35 | n==34 |
| 615693474 | 1132436852 | 2082876103 |
615693474+1132436852=1748130326(大于1000000007),求出了出错提示上的两个数字
a+b+c可能数值超过int的范围,因此要分两次模1000000007,由于d=a+b+c,则程序的计算顺序为:先算a+b,后算+c,则应该对(a+b)先模1000000007再+c,再对d模一次

修改后的代码
d=(a+b)%1000000007+c;d%=1000000007;a=b;b=c;c=d;
提交结果

for循环的其他写法
for (int i=3;i<n;i++){d=(a+b)%1000000007+c;a=b;b=c;c=d;c%=1000000007;}
提交结果

方法3:循环+数组
int waysToStep(int n)
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;int* arr=(int*)malloc(sizeof(int)*(n+1));arr[1]=1;arr[2]=2;arr[3]=4;for (int i=4;i<=n;i++){arr[i]=(arr[i-3]+arr[i-2])%1000000007+arr[i-1];arr[i]%=1000000007;}return arr[n];}
提交结果

3.方法4:矩阵
算法
改写成矩阵形式
①
②
③
将上方三个式子合三为一
(关键式子)
递推
......
可以一直递推到
**************************************************************************************************************
**************************************************************************************************************
设则最终答案为
代码实践
1.先计算矩阵n次方
//矩阵[1,1,1;1,0,0;0,1,0]的n次方(n为计算次数)
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
int main()
{int arr1[3][3] = { 1,1,1,1,0,0,0,1,0 };int arr2[3][3] = { 0 };int arr3[3][3] = { 1,1,1,1,0,0,0,1,0 };int n;scanf("%d", &n);for (int i = 1; i <= n; i++){if (i % 2)//i为奇数{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr2[i][j] = 0;for (int k = 0; k < 3; k++){arr2[i][j] += arr3[i][k] * arr1[k][j];}}}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr3[i][j] = 0;for (int k = 0; k < 3; k++){arr3[i][j] += arr2[i][k] * arr1[k][j];}}}}}if (n % 2){for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){printf("%d ", arr2[i][j]);}printf("\n");}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){printf("%d ", arr3[i][j]);}printf("\n");}}return 0;
}
2.后将矩阵n次方嵌入递推式中
int waysToStep(int n)
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;long long arr1[3][3] = { 1,1,1,1,0,0,0,1,0 };long long arr2[3][3] = { 0 };long long arr3[3][3] = { 1,1,1,1,0,0,0,1,0 };n-=4;//不是-3,计算的是矩阵n次方的运行次数for (int i = 1; i <= n; i++){if (i % 2)//i为奇数{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr2[i][j] = 0;for (int k = 0; k < 3; k++){arr2[i][j] += (arr3[i][k] * arr1[k][j])%1000000007;}}}}else{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){arr3[i][j] = 0;for (int k = 0; k < 3; k++){arr3[i][j] += (arr2[i][k] * arr1[k][j])%1000000007;}}}}}if (n%2)return (arr2[0][0]*4+arr2[0][1]*2+arr2[0][2])%1000000007;elsereturn (arr3[0][0]*4+arr3[0][1]*2+arr3[0][2])%1000000007;
}
提交结果

封装成函数
其实封装成函数代码看起来更简洁
void calc_matirx_power(long long int (*a)[3] ,long long int (*b)[3] ,long long int (*c)[3] )
{for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){a[i][j] = 0;for (int k = 0; k < 3; k++){a[i][j] += (b[i][k] * c[k][j])%1000000007;}}}
}int waysToStep(int n)
{if (n==1)return 1;if (n==2)return 2;if (n==3)return 4;long long arr1[3][3] = { 1,1,1,1,0,0,0,1,0 };long long arr2[3][3] = { 0 };long long arr3[3][3] = { 1,1,1,1,0,0,0,1,0 };n-=4;//不是-3,计算的是矩阵n次方的运行次数for (int i = 1; i <= n; i++){if (i % 2)//i为奇数{calc_matirx_power(arr2,arr3,arr1);}else{calc_matirx_power(arr3,arr2,arr1);}}if (n%2)return (arr2[0][0]*4+arr2[0][1]*2+arr2[0][2])%1000000007;elsereturn (arr3[0][0]*4+arr3[0][1]*2+arr3[0][2])%1000000007;
}
注意calc_matrix_power参数类型的写法:long long int (*a)[3]
这种写法可以看看这篇文章:★♛★指针(重难点)合集

提交结果
相关文章:
L25.【LeetCode笔记】 三步问题的四种解法(含矩阵精彩解法!)
目录 1.题目 2.三种常规解法 方法1:递归做 编辑 方法2:改用循环做 初写的代码 提交结果 分析 修改后的代码 提交结果 for循环的其他写法 提交结果 方法3:循环数组 提交结果 3.方法4:矩阵 算法 代码实践 1.先计算矩阵n次方 2.后将矩阵n次方嵌入递推式中 提…...
sdut-C语言实验-合数分解
sdut-C语言实验-合数分解 分数 12 全屏浏览 切换布局 作者 马新娟 单位 山东理工大学 合数是指在大于1的整数中,除了1和本身外,还能被其他数整除的数。例如,4、6、8、9、10等都是合数。把一个合数分解成若干个质因数乘积的形式(即求质因…...
深入理解 pytest Fixture 方法及其应用
在 Python 自动化测试领域,pytest 是当之无愧的王者。提到 pytest,不得不说它的一大核心功能——Fixture。Fixture 的强大,让复杂的测试流程变得井井有条,让测试代码更加灵活和可复用。 那么,pytest 的 Fixture 究竟是…...
在Linux上获取MS(如Media Server)中的RTP流并录制为双轨PCM格式的WAV文件
在Linux上获取MS(如Media Server)中的RTP流并录制为双轨PCM格式的WAV文件 一、RTP流与WAV文件格式二、实现步骤三、伪代码示例四、C语言示例代码五、关键点说明六、总结在Linux操作系统上,从媒体服务器(如Media Server,简称MS)获取RTP(Real-time Transport Protocol)流…...
Midjourney技术浅析(八):交互与反馈
Midjourney 的用户交互与反馈通过用户输入(User Input)和用户反馈(User Feedback)机制,不断优化和改进图像生成的质量和用户满意度。 一、用户交互与反馈模块概述 用户交互与反馈模块的主要功能包括: 1.…...
【Spring MVC 核心机制】核心组件和工作流程解析
在 Web 应用开发中,处理用户请求的逻辑常常会涉及到路径匹配、请求分发、视图渲染等多个环节。Spring MVC 作为一款强大的 Web 框架,将这些复杂的操作高度抽象化,通过组件协作简化了开发者的工作。 无论是处理表单请求、生成动态页面&#x…...
回归问题的等量分层
目录 一、说明 二、什么是分层抽样? 三、那么回归又如何呢? 四、回归分层(Stratification on Regression) 一、说明 在同一个数据集中,我们可以看成是一个抽样体。然而,我们如果将这个抽样体分成两份&#…...
Unity-Mirror网络框架-从入门到精通之Basic示例
文章目录 前言Basic示例场景元素预制体元素代码逻辑BasicNetManagerPlayer逻辑SyncVars属性Server逻辑Client逻辑 PlayerUI逻辑 最后 前言 在现代游戏开发中,网络功能日益成为提升游戏体验的关键组成部分。Mirror是一个用于Unity的开源网络框架,专为多人…...
CSS 图片廊:网页设计的艺术与技巧
CSS 图片廊:网页设计的艺术与技巧 引言 在网页设计中,图片廊是一个重要的组成部分,它能够以视觉吸引的方式展示图片集合,增强用户的浏览体验。CSS(层叠样式表)作为网页设计的主要语言之一,提供…...
AI 发展的第一驱动力:人才引领变革
在科技蓬勃发展的当下,AI 成为了时代的焦点,然而其发展并非一帆风顺,究竟什么才是推动 AI 持续前行的关键力量呢? 目录 AI 发展现状剖析 期望与现实的落差 落地困境根源 人才:AI 发展的核心动力编辑 技术突破的…...
[创业之路-229]:《华为闭环战略管理》-5-平衡记分卡与战略地图
目录 一、平衡记分卡 1. 财务角度: 2. 客户角度: 3. 内部运营角度: 4. 学习与成长角度: 二、BSC战略地图 1、核心内容 2、绘制目的 3、绘制方法 4、注意事项 一、平衡记分卡 平衡记分卡(Balanced Scorecard&…...
用uniapp写一个播放视频首页页面代码
效果如下图所示 首页有导航栏,搜索框,和视频列表, 导航栏如下图 搜索框如下图 视频列表如下图 文件目录 视频首页页面代码如下 <template> <view class"video-home"> <!-- 搜索栏 --> <view class…...
【视觉SLAM:八、后端Ⅰ】
视觉SLAM的后端主要解决状态估计问题,它是优化相机轨迹和地图点的过程,从数学上看属于非线性优化问题。后端的目标是结合传感器数据,通过最优估计获取系统的状态(包括相机位姿和场景结构),在状态估计过程中…...
PaddleOCROCR关键信息抽取训练过程
步骤1:python版本3.8.20 步骤2:下载代码,安装依赖 git clone https://gitee.com/PaddlePaddle/PaddleOCR.git pip uninstall opencv-python -y # 安装PaddleOCR的依赖 ! pip install -r requirements.txt # 安装关键信息抽取任务的依赖 !…...
用Python操作字节流中的Excel文档
Python能够轻松地从字节流中加载文件,在不依赖于外部存储的情况下直接对其进行读取、修改等复杂操作,并最终将更改后的文档保存回字节串中。这种能力不仅极大地提高了数据处理的灵活性,还确保了数据的安全性和完整性,尤其是在网络…...
python 桶排序(Bucket Sort)
桶排序(Bucket Sort) 桶排序是一种分布式排序算法,适用于对均匀分布的数据进行排序。它的基本思想是:将数据分到有限数量的桶中,每个桶分别排序,最后将所有桶中的数据合并。 桶排序的步骤: 划…...
Elasticsearch:探索 Elastic 向量数据库的深度应用
Elasticsearch:探索 Elastic 向量数据库的深度应用 一、Elasticsearch 向量数据库简介 1. Elasticsearch 向量数据库的概念 Elasticsearch 本身是一个基于 Lucene 的搜索引擎,提供了全文搜索和分析的功能。随着技术的发展,Elasticsearch 也…...
【每日学点鸿蒙知识】属性变量key、waterflow卡顿问题、包无法上传、Video控件播放视频、Vue类似语法
1、HarmonyOS 属性变量常量是否可以作为object对象的key? a: object new Object() this.a[Constants.TEST_KEY] "456" 可以先定义,再赋值 2、首页点击回到waterflow的首节点,0~index全部节点被重建,导致卡顿 使用s…...
小程序中引入echarts(保姆级教程)
hello hello~ ,这里是 code袁~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 🦁作者简介:一名喜欢分享和记录学习的在校大学生…...
基于 Node.js 的 ORM(对象关系映射)工具——Sequelize介绍与使用,并举案例分析
便捷性介绍 支持多种数据库,包括 PostgreSQL、MySQL、MariaDB、SQLite 和 Microsoft SQL Server。Sequelize 提供了丰富的功能,帮助开发者用 JavaScript(或 TypeScript)代码操作数据库,而无需直接书写 SQL 语句。 Se…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Vue3 PC端 UI组件库我更推荐Naive UI
一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用,前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率,还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库(Naive UI、Element …...
StarRocks 全面向量化执行引擎深度解析
StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计,相比传统行式处理引擎(如MySQL),性能可提升 5-10倍。以下是分层拆解: 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...

