【左神算法刷题班】第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/

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[C++]笔记-函数的栈空间(避免栈空间溢出)

错误1 当数组的内存占用较大时,会引发异常 #include <iostream> using namespace std; int main() {char buff[2000000];cout << (int)buff[sizeof(buff) - 1] << endl; 错误 2 当调用次数较小的时候,栈内存还没有满,可以输出,该地址相减除以1024等于100,就…

CANoe自动化工程的搭建

基于XMLCAPL建立自动化工程 1、导入ini文件2、新建 Test Environment3、报告类型4、代码编写 1、导入ini文件 工程的配置的文件&#xff0c;配置DUT相关信息&#xff0c;具体视工程而编写内容。 2、新建 Test Environment 1、新建XML测试用例环境 2、导入XML测试用例文件 …

奥威BI财务数据分析方案:借BI之利,成就智能财务分析

随着智能技术的发展&#xff0c;各行各业都走上借助智能技术高效运作道路&#xff0c;财务数据分析也不例外。借助BI商业智能技术能够让财务数据分析更高效、便捷、直观立体&#xff0c;也更有助于发挥财务数据分析作为企业经营管理健康晴雨表的作用。随着BI财务数据分析经验的…

一元三次方程求解

一元三次方程求解 题目描述提示输入输出格式输入格式输出格式 输入输出样例输入样例输出样例 算法分析A C 代码 题目描述 有形如&#xff1a; a x 3 b x 2 c x d 0 ax^3bx^2c^xd0 ax3bx2cxd0一元三次方程。给出该方程中各项的系数 ( a a a&#xff0c; b b b&#xff0c;…

解密 AI 客服;在不同硬件设备上运行大型语言模型的可能性

&#x1f989; AI新闻 &#x1f680; 微软必应首席执行官称必应聊天优于OpenAI的GPT-4&#xff0c;但成本更高 摘要&#xff1a;微软必应的首席执行官米哈伊尔・帕拉欣表示&#xff0c;必应聊天表现优于OpenAI的GPT-4&#xff0c;但使用了更高成本的检索增强推理技术。必应聊…

k8s的pv和pvc创建

//NFS使用PV和PVC 1、配置nfs存储 2、定义PV 实现 下图的pv和pvc测试 pv的定义 这里定义5个PV&#xff0c;并且定义挂载的路径以及访问模式&#xff0c;还有PV划分的大小 vim /pv.yamlapiVersion: v1 kind: PersistentVolume metadata:name: pv001 spec:capacity:storage: …

Mac OS minicom 无法设置921600问题

MacOS minicom 无法设置921600问题 介绍过程解决方案参考资料 介绍 minicom是Mac上一款非常好用的串口工具。本文假设你已经安装minicom&#xff0c;并且知道minicom的一般配置和使用方法。这是“MacOS minicom 无法设置921600”的解决问题记录。它在以下环境中设置成功&#…

【三维重建】【深度学习】【数据集】基于COLMAP制作自己的NeuS(DTU格式)数据集

【三维重建】【深度学习】【数据集】基于COLMAP制作自己的NeuS(DTU格式)数据集 提示:最近开始在【三维重建】方面进行研究,记录相关知识点,分享学习中遇到的问题已经解决的方法。 文章目录 【三维重建】【深度学习】【数据集】基于COLMAP制作自己的NeuS(DTU格式)数据集前言下载…

BDA初级分析——用SQL筛选数据

一、用SQL对数据分组 GROUP BY Group by&#xff0c;按...分组 作用:根据给定字段进行字段的分组&#xff0c;通常和聚合函数配合使用&#xff0c;实现分组的分析 写法:select ...from ...group by 字段名 (也可以是多个字段) GROUP BY的逻辑 SELECT gender,COUNT(user_id) …

数据分析 | 调用Optuna库实现基于TPE的贝叶斯优化 | 以随机森林回归为例

1. Optuna库的优势 对比bayes_opt和hyperoptOptuna不仅可以衔接到PyTorch等深度学习框架上&#xff0c;还可以与sklearn-optimize结合使用&#xff0c;这也是我最喜欢的地方&#xff0c;Optuna因此特性可以被使用于各种各样的优化场景。 2. 导入必要的库及加载数据 用的是sklea…

恒运资本:布林线什么意思?

布林线是一种经过股票价格的标准差核算出涨跌起伏的技能剖析方法。这种剖析方法由约翰布林在1980年左右开发而来&#xff0c;是一种常用的股市剖析东西。本文将从前史、原理、应用等多个视点叙述布林线的含义&#xff0c;以及它对出资者所带来的意义。 一、前史 布林线在1983年…

Kafka 入门到起飞 - 什么是 HW 和 LEO?何时更新HW和LEO呢?

上文我们已经学到&#xff0c; 一个Topic&#xff08;主题&#xff09;会有多个Partition&#xff08;分区&#xff09;为了保证高可用&#xff0c;每个分区有多个Replication&#xff08;副本&#xff09;副本分为Leader 和 Follower 两个角色&#xff0c;Follower 从Leader同…

安防监控视频云存储平台EasyCVRH.265转码功能更新:新增分辨率配置

安防视频集中存储EasyCVR视频监控综合管理平台可以根据不同的场景需求&#xff0c;让平台在内网、专网、VPN、广域网、互联网等各种环境下进行音视频的采集、接入与多端分发。在视频能力上&#xff0c;视频云存储平台EasyCVR可实现视频实时直播、云端录像、视频云存储、视频存储…

系统架构设计师-信息安全技术(1)

目录 一、信息安全基础 1、信息安全五要素 2、网络安全漏洞 3、网络安全威胁 4、安全措施的目标 二、信息加解密技术 1、对称加密 2、非对称加密 3、加密算法对比 三、密钥管理技术 1、数字证书 2、PKI公钥体系 四、访问控制技术 1、访问控制基本模型 2、访问控制的实现技术…

【ES6】—使用 const 声明

一、不属于顶层对象window 使用const关键字 声明的变量&#xff0c;不会挂载到window属性上 const a 5 console.log(a) console.log(window.a) // 5 // undefined二、不允许重复声明 使用const关键字不允许重复声明相同的变量 cosnt a 5 cosnt a 6 // Uncaught SyntaxEr…

Java基础知识实际应用(学生信息管理系统、猜拳小游戏、打印日历)

一、Java学生信息管理系统 这个系统包含了添加、修改、删除、查询和显示所有学生信息等功能。您可以在此基础上进行修改和完善&#xff0c;以适应您的需求。 import java.util.Scanner;public class StudentManagementSystem {private static Scanner scanner new Scanner(S…

电视机看板大屏适配问题——js基础积累

直接上效果图&#xff1a; 下面直接写代码&#xff1a; 1.html部分的代码 <body><div class"container"><!-- 数据展示区域 --><div class"box"><div class"top">top</div><div class"bottom&…

云原生 envoy xDS 动态配置 java控制平面开发 支持restful grpc

envoy xDS 动态配置 java控制平面开发 支持restful grpc 大纲 基础概念Envoy 动态配置API配置方式动静结合的配置方式纯动态配置方式实战 基础概念 Envoy 的强大功能之一是支持动态配置&#xff0c;当使用动态配置时&#xff0c;我们不需要重新启动 Envoy 进程就可以生效。…

深入理解 Flutter 图片加载原理

作者&#xff1a;京东零售 徐宏伟 来源&#xff1a;京东云开发者社区 前言 随着Flutter稳定版本逐步迭代更新&#xff0c;京东APP内部的Flutter业务也日益增多&#xff0c;Flutter开发为我们提供了高效的开发环境、优秀的跨平台适配、丰富的功能组件及动画、接近原生的交互体验…

【Java基础】Java对象的生命周期

【Java基础】Java对象的生命周期 一、概述 一个类通过编译器将一个Java文件编译为Class字节码文件&#xff0c;然后通过JVM中的解释器编译成不同操作系统的机器码。虽然操作系统不同&#xff0c;但是基于解释器的虚拟机是相同的。java类的生命周期就是指一个class文件加载到类…