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

【左神算法刷题班】第17节:在有序二维数组中查找目标值、等于目标字符串的子序列个数

第17节

题目1:在有序二维数组中查找目标值

给定一个每一行有序、每一列也有序,整体可能无序的二维数组

再给定一个数num,

返回二维数组中有没有num这个数

例子

数组如下,找 6 是否存在。

1  3  5  7
2  4  6  13
3  9  14 14
思路

力扣上做过原题。

从左下角开始,向右上角走。如果当前小于 target,则向右走。如果当前大于 target,则向上走。

题目2:

给定一个每一行有序、每一列也有序,整体可能无序的二维数组

在给定一个正数k,

返回二维数组中,整体第 k 小的数

Leetcode原题:

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

思路
1  3  5  7
2  4  6  13
3  9  14 14

假设我先任意选一个数字10,想要求出所有小于10的数有多少个。从右上角向左下角走,如果当前数小于10,就往下走(此时当前位置左方全是小于10的数),如果大于10,就往左走。沿途通过下标计算,累加所有小于10的数,假设有m个。

根据上述方式,我可以知道小于某个数字的数有多少个。

而整体来看,我知道整个数组最小值是左上角的 min,最大值是右下角的 max,这样我就可以通过二分查找的方式,让 mid=min+(max-min)/2,求出比 mid 小的数有 m 个,如果 m < k,就让 max = mid 继续二分;否则如果 m>k,让 min = mid 继续二分。

如果最后得到答案是 res,而整个数组中没有 res 这个数字,你需要找到距离 res 最近,并且比 res 小的数。

题目3

Leetcode原题:

https://leetcode.com/problems/palindrome-pairs/

在这里插入图片描述

题目4:等于目标字符串的子序列个数(DP)

给定两个字符串S和T

返回S的所有子序列中

有多少个子序列的字面值等于T

思路

样本对应模型,可能性根据结尾字符来划分。

假设S的长度为i,T的长度为j,则 dp[i][j] 表示:从 S 序列 [0…i] 范围上随便选,有多少个子序列的字面值等于 T[0…j] 这个前缀字符串。

dp 表的右下角,就表示了 S 整体字符串有多少个子序列的字面值等于 T 字符串。

状态怎么转移?当我来到 dp[i][j] 的时候,

  • 可能性1:不使用 i 位置的字符,则 dp[i][j] = dp[i-1][j]
  • 可能性2:只有在 S[i] == T[j] 的情况下才可以,使用 S 字符串 i 位置的字符来匹配 T 字符串 j 位置的字符,则 dp[i][j] = dp[i-1][j-1]

考虑上述两种可能性,相加,得到 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

public static int dp(String S, String T) {char[] s = S.toCharArray();char[] t = T.toCharArray();int N = s.length;int M = t.length;int[][] dp = new int[N][M];// s[0..0] T[0..0] dp[0][0]dp[0][0] = s[0] == t[0] ? 1 : 0;for (int i = 1; i < N; i++) {dp[i][0] = s[i] == t[0] ? (dp[i - 1][0] + 1) : dp[i - 1][0];}for (int i = 1; i < N; i++) {for (int j = 1; j <= Math.min(i, M - 1); j++) {dp[i][j] = dp[i - 1][j];if (s[i] == t[j]) {dp[i][j] += dp[i - 1][j - 1];}}}return dp[N - 1][M - 1];
}

题目5

给定一个字符串Str

返回Str的所有子序列中有多少不同的字面值

Leetcode原题:

https://leetcode.com/problems/distinct-subsequences-ii/

思路

主要是观察规律。

在这里插入图片描述

题目6

给定一个数组arr,长度为N,arr中的值只有1,2,3三种
arr[i] == 1,代表汉诺塔问题中,从上往下第i个圆盘目前在左
arr[i] == 2,代表汉诺塔问题中,从上往下第i个圆盘目前在中
arr[i] == 3,代表汉诺塔问题中,从上往下第i个圆盘目前在右
那么arr整体就代表汉诺塔游戏过程中的一个状况
如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1
如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况

题目7

Leetcode 原题:

https://leetcode.com/problems/shortest-bridge/

相关文章:

【左神算法刷题班】第17节:在有序二维数组中查找目标值、等于目标字符串的子序列个数

第17节 题目1&#xff1a;在有序二维数组中查找目标值 给定一个每一行有序、每一列也有序&#xff0c;整体可能无序的二维数组 再给定一个数num&#xff0c; 返回二维数组中有没有num这个数 例子 数组如下&#xff0c;找 6 是否存在。 1 3 5 7 2 4 6 13 3 9 14 …...

【Terraform学习】本地变量(Terraform配置语言学习)

背景&#xff1a; 关于如何在机器上拉terraform代码&#xff0c;初始化就不重复了&#xff0c;需要的可以查看前面的文章&#xff1a; 【Terraform学习】Terraform-AWS部署快速入门&#xff08;快速入门&#xff09;_向往风的男子的博客-CSDN博客 使用本地变量命名资源 将每…...

zabbix自动注册服务器以及部署代理服务器

文章目录 Zabbix自动注册服务器及部署代理服务器一.zabbix自动注册1.什么是自动注册2.环境准备3.zabbix客户端配置4.在 Web 页面配置自动注册5.验证自动注册 二.部署 zabbix 代理服务器1.分布式监控的作用&#xff1a;2.环境部署3.代理服务器配置4.客户端配置5.web页面配置5.1 …...

掌握Python的X篇_32_使用python编辑pdf文件_pdfrw

本篇介绍利用python操作pdf文件&#xff0c;我们平时也会有合并和拆分pdf的需求&#xff0c;此时我们就可以使用本节内容。 文章目录 1. pdfrw的安装2. 切分pdf文件3. pdfrw官网及实现一版四面的实例 1. pdfrw的安装 pip install pdfrw官网地址&#xff1a;https://github.co…...

【软件工程】软件测试

软件测试的对象 软件程序文档 测试对象&#xff1a;各个阶段产生的源程序和文档。 软件测试的目的 基于不同的立场&#xff0c;对软件测试的目的存在着两种完全对立的观点。 &#xff08;1&#xff09;一种观点是通过测试暴露出软件中所包含的故障和缺陷(从用户的角度)&#xf…...

Android性能优化——内存优化

一、内存问题 内存抖动&#xff0c;锯齿状&#xff0c;GC导致卡顿内存泄漏&#xff0c;可用内存减少&#xff0c;频繁GC 内存溢出&#xff0c;OOM&#xff0c;程序异常 二、内存分析工具 Memory ProfilerMemory Analyzer LeakCanary Memory Profiler 实时图表展示应用内存使…...

Android Studio实现图形验证码

源代码 源代码MainActivity 效果图32行需要修改&#xff0c;不修改会报错&#xff1a;需要常量表达式&#xff0c;我的代码已修改 点击后 MainActivity import static com.example.graphicverificationcode.RxCaptcha.TYPE.NUMBER;import android.annotation.SuppressLint; …...

JAVA面试数据库篇

目录 一.优化 1.MYSQL中&#xff0c;如何定位慢查询&#xff1f; 2.SQL语句执行慢&#xff0c;如何分析呢&#xff1f; 3.索引 了解过索引吗&#xff1f;&#xff08;什么是索引&#xff09; 索引的底层数据结构了解过吗&#xff1f; B树和B树的区别是什么呢? 什么是聚…...

Android高手进阶教程(三)之----Android 中自定义View的应用.

大家好我们今天的教程是在Android 教程中自定义View 的学习&#xff0c;对于初学着来说&#xff0c;他们习惯了Android 传统的页面布局方式&#xff0c;如下代码: <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"htt…...

第一百一十三回 dart中的getter/setter方法

文章目录 概念介绍使用方法示例代码使用扩展 我们在上一章回中介绍了 flutter_screenutil包相关的内容&#xff0c;本章回中将介绍 dart中的setter/getter方法.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在这里介绍的setter/getter方法属于编程语言中的…...

搭建Docker环境

目录 一、docker环境搭建 1、卸载旧版本docker 2、安装依赖和设置仓库 3、安装docker 4、启动并加入开机启动 5、验证是否安装成功 二、利用docker搭建nginx 1、拉取镜像 2、启动容器&#xff0c;部署nginx 一、docker环境搭建 1、卸载旧版本docker yum remove docke…...

微服务08-多级缓存

1.什么是多级缓存 传统的缓存策略一般是请求到达Tomcat后,先查询Redis,如果未命中则查询数据库,如图: 存在下面的问题: •请求要经过Tomcat处理,Tomcat的性能成为整个系统的瓶颈 •Redis缓存失效时,会对数据库产生冲击 多级缓存就是充分利用请求处理的每个环节,分…...

Intel汇编和ATT汇编的区别?

一、前缀不同 在 Intel 语法中&#xff0c;没有寄存器前缀或立即前缀。 然而&#xff0c;在 AT&T 中&#xff0c;寄存器的前缀是“%”&#xff0c;而 immed 的前缀是“$”。 Intel 语法十六进制或二进制即时数据分别带有“h”和“b”后缀。 此外&#xff0c;如果第一个十六…...

MongoDB 备份与恢复

1.1 MongoDB的常用命令 mongoexport / mongoimport mongodump / mongorestore 有以上两组命令在备份与恢复中进行使用。 1.1.1 导出工具mongoexport Mongodb中的mongoexport工具可以把一个collection导出成JSON格式或CSV格式的文件。可以通过参数指定导出的数据项&#xff0c…...

探讨uniapp的网络通信问题

uni-app 中有很多原生的 API&#xff0c;其中我们经常会用到的肯定有&#xff1a;uni.request(OBJECT) method 有效值 注意&#xff1a;method有效值必须大写&#xff0c;每个平台支持的method有效值不同&#xff0c;详细见下表。 success 返回参数说明 data 数据说明 最终…...

【左神算法刷题班】第18节:汉诺塔问题、岛屿问题、最大路径和问题

第18节 题目1&#xff1a;汉诺塔问题&#xff08;变体&#xff09; 体系学习班18节有讲暴力递归的汉诺塔原题。 给定一个数组arr&#xff0c;长度为N&#xff0c;arr中的值只有1&#xff0c;2&#xff0c;3三种 arr[i] 1&#xff0c;代表汉诺塔问题中&#xff0c;从上往下第…...

网络安全体系架构介绍

网络安全体系是一项复杂的系统工程&#xff0c;需要把安全组织体系、安全技术体系和安全管理体系等手段进行有机融合&#xff0c;构建一体化的整体安全屏障。针对网络安全防护&#xff0c;美国曾提出多个网络安全体系模型和架构&#xff0c;其中比较经典的包括PDRR模型、P2DR模…...

JSP实训项目设计报告—MVC简易购物商城

JSP实训项目设计报告—MVC简易购物商城 文章目录 JSP实训项目设计报告—MVC简易购物商城设计目的设计要求设计思路系统要求单点登录模块商品展示模块购物车展示模块 概要设计Model层View层Controller层 详细设计Model层View层登录界面系统主界面 Controller层 系统运行效果项目…...

41、可靠传输——停等ARQ

前面两节内容我们学习了传输层的基本概况的一些知识&#xff0c;包括传输层在TCP/IP协议栈中负责的任务、传输层的两大协议&#xff0c;以及端口号、套接字等一些基本的概念。从这一节开始&#xff0c;我们将开启两大协议中TCP协议的学习。 但是&#xff0c;经过之前的学习&am…...

RK3568 cmake编译

一.简介 CMake是开源、跨平台的构建工具&#xff0c;可以让我们通过编写简单的配置文件去生成本地的Makefile&#xff0c;这个配置文件是独立于运行平台和编译器的&#xff0c;这样就不用亲自去编写Makefile了&#xff0c;而且配置文件可以直接拿到其它平台上使用&#xff0c;…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...