【算法刷题】Day17

文章目录

  • 1. 不同路径 II
    • 题干:
    • 算法原理:
    • 代码:
  • 2. 在排序数组中查找元素的第一个和最后一个位置
    • 题干:
    • 算法原理:
      • 解法一:暴力解法 O(n)
      • 解法二:朴素二分
      • 解法三:查找区间左右端点
    • 代码:
    • 二分模版:
      • 查找左区间模版:
      • 查找右区间模版:

1. 不同路径 II

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
原题链接


题干:

这道题和 第16天 的题非常相似
只是在机器人走的路径上加了一个障碍物
障碍物为 1 ,没有障碍物为 0
所以这里我们要看给的二维数组的映射关系


算法原理:

  1. 状态表示
    经验 + 题目要求
    以[ i,j ] 为结尾时…
    dp[i][j] 表示:走到 [i, j] 位置处,⼀共有多少种方式
  2. 状态转移方程
    在这里插入图片描述
    从 [i, j] 位置的上方( [i - 1, j] 的位置)向下走一步,转移到 [i, j] 位置
    从 [i, j] 位置的左方( [i, j - 1] 的位置)向右走⼀步,转移到 [i, j] 位置
    但是如果有障碍物,那么就为 0
  3. 初始化
    这里我们依然要使用虚拟节点来写
    不过,这里我们要做到以下两点:
    (1)虚拟节点里面的值,要保证后面填表的结果正确
    (2)下标的映射
    这里最重要的就是第二点
    要注意给的二维数组和现在和映射
    在这里插入图片描述
  4. 填表顺序
    从上往下填写每一行
    每一行从左往右填写
  5. 返回值
    dp[m][n]

代码:

class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
        int m = ob.length;
        int n = ob[0].length;

        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(ob[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i -1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

在这里插入图片描述

2. 在排序数组中查找元素的第一个和最后一个位置

在这里插入图片描述

原题链接


题干:

一个非递减顺序的数组
找目标值的 开始 和 结束位置
返回下标

算法原理:

解法一:暴力解法 O(n)

从前往后进行查找
遇到第一个目标值记录,遇到最后一个目标值记录

很简单,但是时间复杂度会比较高

解法二:朴素二分

这个是不可取
因为朴素二分只能找到中间值是否是目标值
并不能确定范围

解法三:查找区间左右端点

根据数组的“二段性”
我们可以找到目标值的左端点和右端点


查找区间左端点
在这里插入图片描述

我们可以看到,如果找左端点
我们可以根据左端点划分为两个区间,小于目标值,大于等于目标值
在这里插入图片描述

这个时候

  1. x < t 的时候 left = mid + 1
  2. x >= t 的时候 right = mid

接下来在继续进行查找
为什么在第二步 要求 right = mid 呢?
因为这个时候的 mid 很有可能就是左端点

细节处理:

  1. 循环条件(left < right)
    (1)left < right 的时候,就是最终结果,无需判断
    (2)如果判断,就会导致死循环
  2. 求中点的方法
    我们知道有两种求中点的方法,主要是因为如果长度是偶数
    我们可以定位到中间靠左,或者中间靠右
    (1)left + (right - left) / 2 左端点
    (2)left + (right - left + 1) / 2 右端点 (,会死循环)
    定位右端点会导致死循环
    在这里插入图片描述

查找区间右端点
这个跟查找左端点非常类似
在这里插入图片描述
如果找右端点
我们可以根据有端点划分为两个区间,小于等于目标值,大于目标值
在这里插入图片描述
这个时候

  1. x <= t 的时候 left = mid
  2. x > t 的时候 right = mid - 1

细节处理:

  1. 循环条件(left < right)
    (1)left < right 的时候,就是最终结果,无需判断
    (2)如果判断,就会导致死循环
  2. 求中点的方法
    (1)left + (right - left) / 2 左端点 (,会死循环)
    (2)left + (right - left + 1) / 2 右端点

代码:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        //处理边界情况
        if(nums.length == 0) {
            return ret;
        }

        //1.二分左端点
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        //判断是否有结果
        if(nums[left] != target) {
            return ret;
        }else {
            ret[0] = right;
        }

        //2.二分右端点
        left = 0;
        right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        ret[1] = left;
        return ret;
    }
}

在这里插入图片描述


二分模版:

查找左区间模版:

	while(left < right) {
		int mid = left + (right - left) / 2;
        if(......) {
            left = mid + 1;
        }else {
            right = mid;
        }
    }

查找右区间模版:

	while(left < right) {
		int mid = left + (right - left + 1) / 2;
        if(......) {
            left = mid;
        }else {
            right = mid - 1;
        }
    }

下面出现 - 1,上面就 + 1

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

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

相关文章

redis未授权漏洞复现

什么是redis redis就是个数据库&#xff0c;跟mysql不同的地方在于redis主要将数据存在内存中&#xff0c;读写速度非常快 redis未授权 其原因很简单&#xff0c;就是redis服务器在默认安装好不配置的情况下可以直接免密码登录&#xff0c;登录后在web目录写入一句话木马&am…

为什么选择国产WordPress:HelpLook的优势解析

如今网站建设可以说已经是企业必备。而在众多的网站建设工具中&#xff0c;WordPress无疑是其中的佼佼者。作为一款开源的CMS&#xff08;内容管理系统&#xff09;&#xff0c;WordPress拥有丰富的插件和主题&#xff0c;以及强大的功能&#xff0c;使得用户可以轻松地构建出符…

web前端之若依二次开发经验、使用IDEA启动若依项目、sysConfigController报错提示的解决办法、环境搭建

MENU 前言前端创建路由的细节 后端启动后端项目细节 前言 1、官网地址 2、在线文档 3、演示地址 4、代码下载 5、野生版的若依开发文档 此文章包括前端和后端&#xff0c;记录开发中遇到的一些问题。 前端 创建路由的细节 1、从系统管理进入菜单管理页面创建菜单&#xff0c;菜…

最强Pose模型RTMO开源 | 基于YOLO架构再设计,9MB+9ms性能完爆YOLO-Pose

实时多人在图像中的姿态估计面临着在速度和精度之间实现平衡的重大挑战。尽管两阶段的上下文方法在图像中人数增加时会减慢速度&#xff0c;但现有的单阶段方法往往无法同时实现高精度和实时性能。 本文介绍了RTMO&#xff0c;这是一个单阶段姿态估计框架&#xff0c;通过在YOL…

03进程基础-学习笔记

Process 进程 进程为操作系统的基本调度单位&#xff0c;占用系统资源(cpu,内存)完成特定任务&#xff0c;所有说进程是操作系统的标准执行单元 进程与程序的差别 程序是静态资源&#xff0c;存储与电脑磁盘中(disk磁盘资源)程序执行后会创建进程&#xff0c;负责完成功能&a…

第十五章总结

一.输入/输出流 1.输入流 InputStrema类是字节输入流的抽象类&#xff0c;它是所有字节输入流的父类。 该类中所有方法遇到错误都会引发IOException异常。 read()方法&#xff1a;从输入流中读取数据的下一个字节。返回0~255的int字节值。如果因为已经到达流末尾而没有可用的…

完美解决labelimg xml转可视化中文乱码问题,不用matplotlib

背景简述 我们有一批标注项目要转可视化&#xff0c;因为之前没有做过&#xff0c;然后网上随意找了一段代码测试完美&#xff08;并没有&#xff09;搞定&#xff0c;开始疯狂标注&#xff0c;当真正要转的时候傻眼了&#xff0c;因为测试的时候用的是英文标签&#xff0c;实…

重生奇迹mu再生原石介绍

再生原石的作用&#xff1a; 可以通过坎特鲁提炼之塔的NPC艾尔菲丝提炼成功就可以可获得再生宝石。 再生原石的用法&#xff1a; 1、打怪获得再生原石去提炼之塔&#xff08;进入坎特鲁遗址的141188位置的传送台&#xff09;。 2、找到&#xff08;艾儿菲丝&#xff09;把原…

【程序】STM32 读取光栅_编码器_光栅传感器_7针OLED

文章目录 源代码工程编码器基础程序参考资料 源代码工程 源代码工程打开获取&#xff1a; http://dt2.8tupian.net/2/28880a55b6666.pg3这里做了四倍细分&#xff0c;在屏幕上显示 速度、路程、方向。 接线方法&#xff1a; 单片机--------------串口模块 单片机的5V-------…

【JAVA基础(对象和封装以及构造方法)】----第四天

对象和封装以及构造方法 面向对象和面向过程面向过程面向对象 类与对象及其使用定义类创建一个对象&#xff0c;操作类补充&#xff08;成员变量和局部变量&#xff09; private 修饰类 封装练习编写类编写测试输出结果 面向对象和面向过程 面向过程 在了解面向对象之前先来了…

C语言刷题每日一题——求1到100中包含数字9的整数的个数

思路分析 创建一个变量count记录个数使用一个for循环完成从1到100的循环每次循环判断该数字是否包含数字9——第一种情况 &#xff1a;个位包含9&#xff0c;即求模10的结果为9 &#xff1b;第二种情况&#xff1a;十位包含9&#xff0c;即除以10的结果为9&#xff08;两种情况…

【Vulnhub 靶场】【VulnCMS: 1】【简单】【20210613】

1、环境介绍 靶场介绍&#xff1a;https://www.vulnhub.com/entry/vulncms-1,710/ 靶场下载&#xff1a;https://download.vulnhub.com/vulncms/VulnCMS.ova 靶场难度&#xff1a;简单 发布日期&#xff1a;2021年06月13日 文件大小&#xff1a;1.4 GB 靶场作者&#xff1a;to…

Stable Diffusion - High-Resolution Image Synthesis with Latent Diffusion Models

Paper name High-Resolution Image Synthesis with Latent Diffusion Models Paper Reading Note Paper URL: https://arxiv.org/abs/2112.10752 Code URL: https://github.com/CompVis/latent-diffusion TL;DR 2021 年 runway 和慕尼黑路德维希马克西米利安大学出品的文…

服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌X系列服务器&#xff0c;4块SAS硬盘组建了一组RAID5阵列&#xff0c;还有1块磁盘作为热备盘使用。服务器上层安装的linux操作系统&#xff0c;操作系统上部署了一个基于oracle数据库的OA&#xff08;oracle已经不再为该OA系统提供后续服务…

vue3+echarts 立体柱状效果

vue3echarts 立体柱状效果 废话不多说&#xff0c;直接上代码 就两步&#xff0c;直接复制粘贴一手 <div id"main" class"chart" ref"chartDom"></div>import * as echarts from echarts; type EChartsOption echarts.EChartsOpti…

前端实现一个时间区间内,再次单选功能,使用Antd组件库内日历组件Calendar

需求&#xff1a;需要先让用户选择一个时间区间&#xff0c;然后再这个时间区间中&#xff0c;让用户再次去单选其种特殊日期。 思路&#xff1a; 1.先用Antd组件库中日期选择DatePicker.RangePicker实现让用户选择时间区间 2.在选择完时间区间后&#xff0c;用这个时间区间…

蓝桥杯专题-真题版含答案-【扑克牌排列】【放麦子】【纵横放火柴游戏】【顺时针螺旋填入】

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…

低代码发展现状调研和思考

低代码开发是近年来迅速崛起的软件开发方法&#xff0c;让编写应用程序变得更快、更简单。有人说它是美味的膳食&#xff0c;让开发过程高效而满足&#xff0c;但也有人质疑它是垃圾食品&#xff0c;缺乏定制性与深度。你认为低代码到底是美味的膳食还是垃圾食品呢&#xff0c;…

linux系统启动时运行web程序

1.修改rc.local文件 执行命令如果找不到会报错command not found &#xff0c;使用全路径即可 找不到的话 可以使用which 命令 找到路径 后台查看执行日志 2.修改rc.local文件的权限 chmod x rc.local 然后reboot 可以查到进程和启动日志

CAD 审图意见的导出

看图的时候喜欢在图上直接标注意见&#xff0c;但是如果还要再把意见一行一行的导出到word里面就很麻烦&#xff0c;在网上看了一个审图软件&#xff0c;报价要980&#xff0c;而且那个审图意见做的太复杂了。 我的需求就是把图上标的单行文字和多行文字直接导出来就行&#x…