【Leecode】Leecode刷题之路第62天之不同路径

题目出处

62-不同路径-题目出处

题目描述

在这里插入图片描述
在这里插入图片描述

个人解法

思路:

todo

代码示例:(Java)

todo

复杂度分析

todo

官方解法

62-不同路径-官方解法

方法1:动态规划

思路:

在这里插入图片描述

代码示例:(Java)

public class Solution1 {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }


}

此外,由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关,因此我们可以使用滚动数组代替代码中的二维数组,使空间复杂度降低为 O(n)。

public class Solution2 {
    public int uniquePaths(int m, int n) {
        int[] f = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[j] += f[j - 1];
            }
        }
        return f[n - 1];
    }


}

复杂度分析

在这里插入图片描述

方法2:组合数学

思路:

在这里插入图片描述

代码示例:(Java)

public class Solution3 {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }


}

复杂度分析

在这里插入图片描述

考察知识点

收获

Gitee源码位置

62-不同路径-源码

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows修复SSL/TLS协议信息泄露漏洞(CVE-2016-2183) --亲测

漏洞说明&#xff1a; 打开链接&#xff1a;https://docs.microsoft.com/zh-cn/troubleshoot/windows-server/windows-security/restrict-cryptographic-algorithms-protocols-schannel 可以看到&#xff1a; 找到&#xff1a;应通过配置密码套件顺序来控制 TLS/SSL 密码 我们…

第六届国际科技创新(IAECST 2024)暨第四届物流系统与交通运输(LSTT 2024)

重要信息 会议官网&#xff1a;www.lstt.org 大会时间&#xff1a;2024年12月6-8日 大会地点&#xff1a;中国-广州 简介 第六届国际科技创新暨第四届物流系统与交通运输国际&#xff08;LSTT 2024&#xff09;将于2024年12月6-8日在广州举办&#xff0c;这是一个集中探讨…

ArcGIS 软件中路网数据的制作

内容导读 路网数据是进行网络分析的基础&#xff0c;它是建立网络数据集的数据来源。 本文我们以OSM路网数据为例&#xff0c;详细介绍OSM路网数据从下载&#xff0c;到数据处理&#xff0c;添加属性&#xff0c;完成符合网络分析的网络数据集的全部过程。 01 数据获取 比较…

【0346】Postgres内核 Startup Process 通过 signal 与 postmaster 交互实现 (5)

1. Startup Process 进程 postmaster 初始化过程中, 在进入 ServerLoop() 函数之前,会先通过调用 StartChildProcess() 函数来开启辅助进程,这些进程的目的主要用来完成数据库的 XLOG 相关处理。 如: 核实 pg_wal 和 pg_wal/archive_status 文件是否存在Postgres先前是否发…

PYNQ 框架 - OV5640驱动 + Linux 驱动分析

目录 1. 简介 1.1 博文要点 1.2 V4L2 2. 极简 Char 驱动 2.1 源码 2.2 Makefile 2.3 加载驱动 2.4 设备文件 2.5 测试驱动程序 2.6 卸载驱动程序 2.7 自动创建设备文件 2.8 日志等级 3. 极简 V4L2 驱动 3.1 源码 3.2 Makefile 3.3 设备节点类型 3.4 测试 V4L2…

RNN详解及其实现

目录 概述为什么需要 RNN&#xff1f;RNN 理解及其简单实现RNN 完成文本分类任务RNN 存在的问题 概述 提及 RNN&#xff0c;绝大部分人都知道他是一个用于序列任务的神经网络&#xff0c;会提及他保存了时序信息&#xff0c;但是&#xff0c;为什么需要考虑时序的信息&#xf…

Redis开发03:常见的Redis命令

1.输入以下命令&#xff0c;启动redis。 sudo service redis-server start 如果你是直接安装在WSL的&#xff0c;搜索栏搜索Ubuntu或者点击左下角Windows图表找到U那一栏&#xff0c;直接打开Ubentu&#xff0c;输入账密后&#xff0c;输入“sudo service redis-server start”…

【webrtc】 mediasoup中m77的IntervalBudget及其在AlrDetector的应用

IntervalBudget 用于带宽控制和流量整形 mediasoup中m77 代码的IntervalBudget ,版本比较老IntervalBudget 在特定时间间隔内的比特预算管理,从而实现带宽控制和流量整形。 一。 pacedsender 执行周期: 下一次执行的时间的动态可变的 int64_t PacedSender::TimeUntilNextPr…

Docker for Everyone Plus——No Enough Privilege

直接告诉我们flag在/flag中&#xff0c;访问第一小题&#xff1a; sudo -l查看允许提权执行的命令&#xff1a; 发现有image load命令 题目指明了有rz命令&#xff0c;可以用ZMODEM接收文件&#xff0c;看到一些write up说可以用XShell、MobaXterm、Tabby Terminal等软件连接上…

SpringMVC工作原理【流程图+文字详解SpringMVC工作原理】

SpringMVC工作原理 前端控制器&#xff1a;DispactherServlet处理器映射器&#xff1a;HandlerMapping处理器适配器&#xff1a;HandlerAdapter处理器&#xff1a;Handler&#xff0c;视图解析器&#xff1a;ViewResolver视图&#xff1a;View 首先用户通过浏览器发起HTTP请求…

网络安全 社会工程学 敏感信息搜集 密码心理学攻击 密码字典生成

网络安全 社会工程学 敏感信息搜集 密码心理学攻击 理解社会工程学的概念掌握获取敏感信息的方法提高自我信息保护的意识和方法理解密码心理学的概念理解密码特征分析掌握黑客猜解密码的切入方法掌握如何提高密码强壮性 敏感信息搜集 「注」由于对实验环境的限制&#xff0c;…

【机器学习】机器学习的基本分类-监督学习-逻辑回归-对数似然损失函数(Log-Likelihood Loss Function)

对数似然损失函数&#xff08;Log-Likelihood Loss Function&#xff09; 对数似然损失函数是机器学习和统计学中广泛使用的一种损失函数&#xff0c;特别是在分类问题&#xff08;例如逻辑回归、神经网络&#xff09;中应用最为广泛。它基于最大似然估计原理&#xff0c;通过…

SQL基础入门 —— SQL概述

目录 1. 什么是SQL及其应用场景 SQL的应用场景 2. SQL数据库与NoSQL数据库的区别 2.1 数据模型 2.2 查询语言 2.3 扩展性 2.4 一致性与事务 2.5 使用场景 2.6 性能与扩展性 总结 3. 常见的SQL数据库管理系统&#xff08;MySQL, PostgreSQL, SQLite等&#xff09; 3.…

力扣--LCR 149.彩灯装饰记录I

题目 代码 /** Definition for a binary tree node. public class TreeNode { int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right ri…

Admin.NET框架使用宝塔面板部署步骤

文章目录 Admin.NET框架使用宝塔面板部署步骤&#x1f381;框架介绍部署步骤1.Centos7 部署宝塔面板2.部署Admin.NET后端3.部署前端Web4.访问前端页面 Admin.NET框架使用宝塔面板部署步骤 &#x1f381;框架介绍 Admin.NET 是基于 .NET6 (Furion/SqlSugar) 实现的通用权限开发…

软通动力携子公司鸿湖万联、软通教育助阵首届鸿蒙生态大会成功举办

11月23日中国深圳&#xff0c;首届鸿蒙生态大会上&#xff0c;软通动力及软通动力子公司鸿湖万联作为全球智慧物联网联盟&#xff08;GIIC&#xff09;理事单位、鸿蒙生态服务&#xff08;深圳&#xff09;有限公司战略合作伙伴&#xff0c;联合软通教育深度参与了大会多项重磅…

利用若依代码生成器实现课程管理模块开发

目录 前言1. 环境准备1.1 数据库表设计与导入 2. 使用若依代码生成器生成模块代码2.1 导入数据库表2.2 配置生成规则2.2.1 基本信息配置2.2.2 字段信息配置2.2.3 生成信息配置 3. 下载与集成生成代码3.1 解压与集成3.2 启动项目并验证 4. 优化与扩展4.1 前端优化4.2 后端扩展 结…

MySQL Linux 离线安装

下载 进入官网&#xff0c;下载对应的需要MySQL版本&#xff0c;这里是历史版本。 官网 选择第一个MySQL Community Sever社区版&#xff0c;因为这个是免费的。 选择需要的对应版本&#xff1a; 安装 1.将下载好的安装包上传到服务器端 使用FinalShell 客户端连接服务器 …

Milvus 2.5:全文检索上线,标量过滤提速,易用性再突破!

01. 概览 我们很高兴为大家带来 Milvus 2.5 最新版本的介绍。 在 Milvus 2.5 里&#xff0c;最重要的一个更新是我们带来了“全新”的全文检索能力&#xff0c;之所以说“全新”主要是基于以下两点&#xff1a; 第一&#xff0c;对于全文检索基于的 BM25 算法&#xff0c;我们采…

think php处理 异步 url 请求 记录

1、需求 某网站 需要 AI生成音乐&#xff0c;生成mp3文件的时候需要等待&#xff0c;需要程序中实时监听mp3文件是否生成 2、用的开发框架 为php 3、文件结构 配置路由设置 Route::group(/music, function () {Route::post(/musicLyrics, AiMusic/musicLyrics);//Ai生成歌词流式…