【左神算法刷题班】第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:在有序二维数组中查找目标值 给定一个每一行有序、每一列也有序,整体可能无序的二维数组 再给定一个数num, 返回二维数组中有没有num这个数 例子 数组如下,找 6 是否存在。 1 3 5 7 2 4 6 13 3 9 14 …...
【Terraform学习】本地变量(Terraform配置语言学习)
背景: 关于如何在机器上拉terraform代码,初始化就不重复了,需要的可以查看前面的文章: 【Terraform学习】Terraform-AWS部署快速入门(快速入门)_向往风的男子的博客-CSDN博客 使用本地变量命名资源 将每…...

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

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

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

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

Android Studio实现图形验证码
源代码 源代码MainActivity 效果图32行需要修改,不修改会报错:需要常量表达式,我的代码已修改 点击后 MainActivity import static com.example.graphicverificationcode.RxCaptcha.TYPE.NUMBER;import android.annotation.SuppressLint; …...
JAVA面试数据库篇
目录 一.优化 1.MYSQL中,如何定位慢查询? 2.SQL语句执行慢,如何分析呢? 3.索引 了解过索引吗?(什么是索引) 索引的底层数据结构了解过吗? B树和B树的区别是什么呢? 什么是聚…...

Android高手进阶教程(三)之----Android 中自定义View的应用.
大家好我们今天的教程是在Android 教程中自定义View 的学习,对于初学着来说,他们习惯了Android 传统的页面布局方式,如下代码: <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"htt…...
第一百一十三回 dart中的getter/setter方法
文章目录 概念介绍使用方法示例代码使用扩展 我们在上一章回中介绍了 flutter_screenutil包相关的内容,本章回中将介绍 dart中的setter/getter方法.闲话休提,让我们一起Talk Flutter吧。 概念介绍 我们在这里介绍的setter/getter方法属于编程语言中的…...

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

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

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

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

探讨uniapp的网络通信问题
uni-app 中有很多原生的 API,其中我们经常会用到的肯定有:uni.request(OBJECT) method 有效值 注意:method有效值必须大写,每个平台支持的method有效值不同,详细见下表。 success 返回参数说明 data 数据说明 最终…...

【左神算法刷题班】第18节:汉诺塔问题、岛屿问题、最大路径和问题
第18节 题目1:汉诺塔问题(变体) 体系学习班18节有讲暴力递归的汉诺塔原题。 给定一个数组arr,长度为N,arr中的值只有1,2,3三种 arr[i] 1,代表汉诺塔问题中,从上往下第…...

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

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

41、可靠传输——停等ARQ
前面两节内容我们学习了传输层的基本概况的一些知识,包括传输层在TCP/IP协议栈中负责的任务、传输层的两大协议,以及端口号、套接字等一些基本的概念。从这一节开始,我们将开启两大协议中TCP协议的学习。 但是,经过之前的学习&am…...
RK3568 cmake编译
一.简介 CMake是开源、跨平台的构建工具,可以让我们通过编写简单的配置文件去生成本地的Makefile,这个配置文件是独立于运行平台和编译器的,这样就不用亲自去编写Makefile了,而且配置文件可以直接拿到其它平台上使用,…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

回溯算法学习
一、电话号码的字母组合 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"…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...