LeetCode 35, 242, 994
目录
- 35. 搜索插入位置
- 题目链接
- 标签
- 思路
- 代码
- 242. 有效的字母异位词
- 题目链接
- 标签
- 思路
- 代码
- 994. 腐烂的橘子
- 题目链接
- 标签
- 思路
- 代码
35. 搜索插入位置
题目链接
35. 搜索插入位置
标签
数组 二分查找
思路
本题与 704. 二分查找 十分相似,只不过本题在找不到 target
时不返回 -1
,而是返回 target
应该插入的位置。
可以思考一下当找不到值时,左、右指针 left, right
指向哪里。结论是 左指针left
指向第一个大于target
的元素,右指针right
指向最后一个小于target
的元素。
例如对于nums = [1, 2, 3, 4, 5, 7, 8], target = 6
:
开始
left = 0, right = 6, mid = 3
,发现此时target > nums[mid]
,将左指针left
移动到mid + 1
的位置;
此时left = 4, right = 6, mid = 5
,发现此时target < nums[mid]
,将右指针right
移动到mid - 1
的位置;
此时left = 4, right = 4, mid = 4
,发现此时target > nums[mid]
,将左指针left
移动到mid + 1
的位置;
此时left = 5, right = 4
,有left > right
,退出循环。
发现left = 5
是nums
中第一个大于target
的元素,而right = 4
是nums
中最后一个小于target
的元素,而left = 5
恰好是这个元素应该插入的位置,所以 在找不到值时,返回left
作为待插入索引。
代码
class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left >> 1);if (target < nums[mid]) {right = mid - 1; // 在左子区间查询} else if (target > nums[mid]) {left = mid + 1; // 在右子区间查询} else {return mid;}}return left; // 在找不到值时,返回 left 作为待插入索引}
}
242. 有效的字母异位词
题目链接
242. 有效的字母异位词
标签
哈希表 字符串 排序
思路
若 s
和 t
中每个字符出现的次数都相同,则称 s
和 t
互为字母异位词。理解了这句话就会做本题了,这句话意味着对于 s
和 t
,不需要关心它们的字符顺序,只需要关心它们每个字符出现的次数,所以可以通过 先统计两个字符串中每个字符出现的次数,然后比较统计的结果是否完全一致 的方法来解决本题。
统计字符出现的次数有两种方法,一种是使用Map
,键为字符,值为字符出现的次数;另一种是使用int[]
,索引为字符(字符最多也就128个,并且 字符的底层就是数字),索引指向的元素为字符出现的次数。使用int[]
比Map
要快很多,所以本题解使用int[]
。
一般来说,使用int[]
时得自己构建 字符与索引之间的映射。例如:
- 如果统计的是全部的大写字符,则对于大写字符
ch
,它在统计数组中的索引为ch - 'A'
,这个统计数组的长度为26; - 如果统计的是全部的小写字符,则对于小写字符
ch
,它在统计数组中的索引为ch - 'a'
,这个统计数组的长度为26; - 如果统计的是全部字符,则对于字符
ch
,它在统计数组中的索引为ch - '\0'
(由于'\0' == 0
,所以这里的索引可以简写为ch
),这个统计数组的长度为128。
代码
class Solution {public boolean isAnagram(String s, String t) {int[] sCnt = count(s); // 统计s中的字符出现次数int[] tCnt = count(t); // 统计t中的字符出现次数for (int i = 0; i < sCnt.length; i++) {if (sCnt[i] != tCnt[i]) { // 如果有一个字符的出现次数不一样return false; // 则不是字母异位词,返回 false}}return true; // 每个字符的出现情况都一样,返回 true}// 统计字符串str中的字符出现次数private int[] count(String str) {int[] cnt = new int[26]; // s 和 t 仅包含小写字母,共26个for (char ch : str.toCharArray()) {cnt[ch - 'a']++;}return cnt;}
}
994. 腐烂的橘子
题目链接
994. 腐烂的橘子
标签
广度优先搜索 数组 矩阵
思路
本题是一道 模拟题,可以采用 模拟橘子腐烂过程 的方法来计算感染的时间:感染之前先记录新鲜橘子的数量,只有在新鲜橘子数量大于0的情况下才进行感染,每轮感染对腐烂橘子上下左右的新鲜橘子进行感染,然后统计本轮感染的橘子的数量,如果本轮感染没有感染任何橘子,则说明新鲜橘子不可能被感染完,返回 -1
;否则就将本轮感染的橘子从新鲜橘子中移除,并让时间加1分钟。当新鲜橘子数量为0时,返回时间即可。
模拟有一个难点:如何统计每轮感染的橘子数?可以在感染时将橘子的状态设置为0, 1, 2
除外的任意一种状态,然后在统计时遍历整个网格,对于状态为自定义状态的橘子,将其状态改为2
,并让统计结果加一。
代码
class Solution {public int orangesRotting(int[][] grid) {int time = 0; // 记录感染的时间int rest = countFresh(grid); // 剩余新鲜橘子的数量while (rest > 0) {// 对腐烂橘子上下左右的新鲜橘子进行感染for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {if (grid[i][j] == 2) {infect(grid, i, j);}}}int infected = countInfect(grid); // 统计本轮感染的橘子数量if (infected == 0) { // 如果本轮感染的橘子数量为0,则说明不可能感染完所有橘子return -1;}rest -= infected; // 将 本轮感染的橘子 从 剩余新鲜的橘子中 移除time++; // 时间过了1分钟}return time;}// 感染上下左右的橘子,将感染的橘子状态设置为-2private void infect(int[][] grid, int i, int j) {int m = grid.length, n = grid[0].length;for (int k = 0; k < 4; k++) {int ki = i + dir[k][0], kj = j + dir[k][1];if (ki >= 0 && ki < m && kj >= 0 && kj < n // 如果这个橘子在矩阵中&& grid[ki][kj] == 1) { // 并且是新鲜橘子grid[ki][kj] = -2; // 则将其感染}}}// 统计本轮感染的橘子数量,统计完毕后将感染橘子的状态置为2private int countInfect(int[][] grid) {int cnt = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {if (grid[i][j] == -2) {cnt++;grid[i][j] = 2;}}}return cnt;}// 统计初始的新鲜橘子数量private int countFresh(int[][] grid) {int cnt = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {if (grid[i][j] == 1) {cnt++;}}}return cnt;}private int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组,分别为 向右、向下、向左、向上
}
相关文章:
LeetCode 35, 242, 994
目录 35. 搜索插入位置题目链接标签思路代码 242. 有效的字母异位词题目链接标签思路代码 994. 腐烂的橘子题目链接标签思路代码 35. 搜索插入位置 题目链接 35. 搜索插入位置 标签 数组 二分查找 思路 本题与 704. 二分查找 十分相似,只不过本题在找不到 tar…...

ctfshow-web入门-文件包含(web87)巧用 php://filter 流绕过死亡函数的三种方法
目录 方法1:php://filter 流的 base64-decode 方法 方法2:通过 rot13 编码实现绕过 方法3:通过 strip_tags 函数去除 XML 标签 除了替换,新增 file_put_contents 函数,将会往 $file 里写入 <?php die(大佬别秀了…...
adb shell ps -T打印出来参数的含义,以及D,T,Z代表的状态含义是什么?
在Android系统中,使用adb shell ps命令可以查看当前系统中运行的进程信息。当你添加-T选项时(注意,标准的ps命令在Android的adb shell中可能不直接支持-T选项,这通常与Linux中的ps命令略有不同),你可能是想…...
leetcode77组合——经典回溯算法
本文主要讲解组合的要点与细节,以及回溯算法的解题步骤,按照步骤思考更方便理解 c和java代码如下,末尾 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 具体要点: …...

springcloud-alibba之FeignClient
代码地址:springcloud系列: springcloud 组件分析拆解 1.FeignClient的集成 springboot版本:3.1.5 springcloud组件版本:2022.0.4 nacos客户端的版本:2.3.2 1.引pom 这里引入了nacos和feginclient的版本 <dependency>…...

三、docker配置阿里云镜像仓库并配置docker代理
一、配置阿里云镜像仓库 1. 登录阿里云官网,并登录 https://www.aliyun.com/ 2. 点击产品 - 容器 - 容器与镜像服务ACR - 管理控制台 - 镜像工具 - 镜像加速器 二、配置docker代理 #1. 创建docker相关的systemd文件 mkdir -p /etc/systemd/system/docker.servic…...

【面向就业的Linux基础】从入门到熟练,探索Linux的秘密(十一)-git(3)
Git是目前最流行的版本控制系统之一,在现代软件开发中扮演着重要的角色。它能够有效地跟踪文件变化、协作开发,并存储项目的历史记录。本文的目的是向读者介绍Git的基本概念和工作原理,帮助初学者快速上手使用Git,并帮助有经验的开…...

全面解析 TypeScript 泛型的二三事
2024年了相信大家都已经在日常开发的过程中使用上了 TypeScript 了。TypeScript 增强了代码可靠性和可维护性,确保减少运行时错误并提高开发人员的工作效率。 TypeScript 通过类型声明 使得 javascript 拥有了强类型校验。而泛型的是类型声明中最重要的一环&#x…...

单/多线程--协程--异步爬虫
免责声明:本文仅做技术交流与学习... 目录 了解进程和线程 单个线程(主线程)在执行 多线程 线程池 协程(爬虫多用) 假异步:(同步) 真异步: 爬虫代码模版 异步-爬虫 同步效果--19秒 异步效果--7秒 了解进程和线程 # --------------------> # ------> # …...
android pdf框架-11,查看图片
前10篇文章,9章关于pdf的,pdf解析后,里面也是有各种图片,于是利用pdf的view来展示图片,似乎也是个不错的想法. android手机中的图片查看功能,有的可以展示,有的不能.比如华为,荣耀对大体积的png是可以显示的,小米是不显示,只有缩略图. 一张png50m大,比如清明上河图,原图是tif…...
【CSS】深入浅出弹性布局
CSS的弹性布局(Flexbox)是一种用于在容器中沿着一维方向(水平或垂直)来布局、对齐和分配容器内项目空间的有效方式。它旨在提供一个更加有效的方式来布局、对齐和分配容器中项目的空间,即使它们的大小未知或是动态变化…...

医院挂号系统小程序的设计
管理员账户功能包括:系统首页,个人中心,患者管理,医生管理,专家信息管理,科室管理,预约信息管理,系统管理 微信端账号功能包括:系统首页,专家信息࿰…...

广州外贸建站模板
Yamal外贸独立站wordpress主题 绿色的亚马尔Yamal外贸独立站wordpress模板,适用于外贸公司建独立站的wordpress主题。 https://www.jianzhanpress.com/?p7066 赛斯科Sesko-W外贸建站WP主题 适合机械设备生产厂家出海做外贸官网的wordpress主题,红橙色…...

KDP数据分析实战:从0到1完成数据实时采集处理到可视化
智领云自主研发的开源轻量级Kubernetes数据平台,即Kubernetes Data Platform (简称KDP),能够为用户提供在Kubernetes上的一站式云原生数据集成与开发平台。在最新的v1.1.0版本中,用户可借助 KDP 平台上开箱即用的 Airflow、AirByte、Flink、K…...

【人工智能】-- 智能机器人
个人主页:欢迎来到 Papicatch的博客 课设专栏 :学生成绩管理系统 专业知识专栏: 专业知识 文章目录 🍉引言 🍉机器人介绍 🍈机器人硬件 🍍机械结构 🍍传感器 🍍控…...

Android广播机制
简介 某个网络的IP范围是192.168.0.XXX,子网 掩码是255.255.255.0,那么这个网络的广播地址就是192.168.0.255。广播数据包会被发送到同一 网络上的所有端口,这样在该网络中的每台主机都将会收到这条广播。为了便于进行系统级别的消息通知&…...
SQL FOREIGN KEY
SQL FOREIGN KEY 简介 SQL(Structured Query Language)是用于管理关系数据库管理系统(RDBMS)的标准编程语言。在SQL中,FOREIGN KEY是一个重要的概念,用于建立和维护数据库中不同表之间的关系。本文将详细介绍SQL FOREIGN KEY的概念、用途、以及如何在SQL中实现和使用FO…...

绘唐3最新版本哪里下载
绘唐3最新版本哪里下载 绘唐最新版本下载地址 推文视频创作设计是一种通过视频和文字的形式来进行推广的方式,可以通过一些专业的工具来进行制作。 以下是一些常用的小说推文视频创作设计工具: 视频剪辑软件:如Adobe Premiere Pro、Fina…...
[ES6] 箭头函数
JavaScript 是一种广泛使用的编程语言,随着其发展和演变,引入了很多新的特性来提高代码的可读性和开发效率。其中一个重要的特性就是 ES6(ECMAScript 2015)中引入的箭头函数(Arrow Function)。箭头函数不仅…...
BiLSTM模型实现
# 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 # 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 import torch import torch.nn as nn# 本函数实现将中文文本映射为…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...