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

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 = 5nums中第一个大于target的元素,而right = 4nums中最后一个小于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. 有效的字母异位词

标签

哈希表 字符串 排序

思路

st 中每个字符出现的次数都相同,则称 st 互为字母异位词。理解了这句话就会做本题了,这句话意味着对于 st,不需要关心它们的字符顺序,只需要关心它们每个字符出现的次数,所以可以通过 先统计两个字符串中每个字符出现的次数,然后比较统计的结果是否完全一致 的方法来解决本题。

统计字符出现的次数有两种方法,一种是使用Map,键为字符,值为字符出现的次数;另一种是使用int[],索引为字符(字符最多也就128个,并且 字符的底层就是数字),索引指向的元素为字符出现的次数。使用int[]Map要快很多,所以本题解使用int[]

一般来说,使用int[]时得自己构建 字符与索引之间的映射。例如:

  1. 如果统计的是全部的大写字符,则对于大写字符ch,它在统计数组中的索引为ch - 'A',这个统计数组的长度为26;
  2. 如果统计的是全部的小写字符,则对于小写字符ch,它在统计数组中的索引为ch - 'a',这个统计数组的长度为26;
  3. 如果统计的是全部字符,则对于字符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. 二分查找 十分相似&#xff0c;只不过本题在找不到 tar…...

ctfshow-web入门-文件包含(web87)巧用 php://filter 流绕过死亡函数的三种方法

目录 方法1&#xff1a;php://filter 流的 base64-decode 方法 方法2&#xff1a;通过 rot13 编码实现绕过 方法3&#xff1a;通过 strip_tags 函数去除 XML 标签 除了替换&#xff0c;新增 file_put_contents 函数&#xff0c;将会往 $file 里写入 <?php die(大佬别秀了…...

adb shell ps -T打印出来参数的含义,以及D,T,Z代表的状态含义是什么?

在Android系统中&#xff0c;使用adb shell ps命令可以查看当前系统中运行的进程信息。当你添加-T选项时&#xff08;注意&#xff0c;标准的ps命令在Android的adb shell中可能不直接支持-T选项&#xff0c;这通常与Linux中的ps命令略有不同&#xff09;&#xff0c;你可能是想…...

leetcode77组合——经典回溯算法

本文主要讲解组合的要点与细节&#xff0c;以及回溯算法的解题步骤&#xff0c;按照步骤思考更方便理解 c和java代码如下&#xff0c;末尾 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 具体要点&#xff1a; …...

springcloud-alibba之FeignClient

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

三、docker配置阿里云镜像仓库并配置docker代理

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

【面向就业的Linux基础】从入门到熟练,探索Linux的秘密(十一)-git(3)

Git是目前最流行的版本控制系统之一&#xff0c;在现代软件开发中扮演着重要的角色。它能够有效地跟踪文件变化、协作开发&#xff0c;并存储项目的历史记录。本文的目的是向读者介绍Git的基本概念和工作原理&#xff0c;帮助初学者快速上手使用Git&#xff0c;并帮助有经验的开…...

全面解析 TypeScript 泛型的二三事

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

单/多线程--协程--异步爬虫

免责声明:本文仅做技术交流与学习... 目录 了解进程和线程 单个线程(主线程)在执行 多线程 线程池 协程(爬虫多用) 假异步:(同步) 真异步: 爬虫代码模版 异步-爬虫 同步效果--19秒 异步效果--7秒 了解进程和线程 ​ # --------------------> # ------> # …...

android pdf框架-11,查看图片

前10篇文章,9章关于pdf的,pdf解析后,里面也是有各种图片,于是利用pdf的view来展示图片,似乎也是个不错的想法. android手机中的图片查看功能,有的可以展示,有的不能.比如华为,荣耀对大体积的png是可以显示的,小米是不显示,只有缩略图. 一张png50m大,比如清明上河图,原图是tif…...

【CSS】深入浅出弹性布局

CSS的弹性布局&#xff08;Flexbox&#xff09;是一种用于在容器中沿着一维方向&#xff08;水平或垂直&#xff09;来布局、对齐和分配容器内项目空间的有效方式。它旨在提供一个更加有效的方式来布局、对齐和分配容器中项目的空间&#xff0c;即使它们的大小未知或是动态变化…...

医院挂号系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;患者管理&#xff0c;医生管理&#xff0c;专家信息管理&#xff0c;科室管理&#xff0c;预约信息管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;专家信息&#xff0…...

广州外贸建站模板

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

KDP数据分析实战:从0到1完成数据实时采集处理到可视化

智领云自主研发的开源轻量级Kubernetes数据平台&#xff0c;即Kubernetes Data Platform (简称KDP)&#xff0c;能够为用户提供在Kubernetes上的一站式云原生数据集成与开发平台。在最新的v1.1.0版本中&#xff0c;用户可借助 KDP 平台上开箱即用的 Airflow、AirByte、Flink、K…...

【人工智能】-- 智能机器人

个人主页&#xff1a;欢迎来到 Papicatch的博客 课设专栏 &#xff1a;学生成绩管理系统 专业知识专栏&#xff1a; 专业知识 文章目录 &#x1f349;引言 &#x1f349;机器人介绍 &#x1f348;机器人硬件 &#x1f34d;机械结构 &#x1f34d;传感器 &#x1f34d;控…...

Android广播机制

简介 某个网络的IP范围是192.168.0.XXX&#xff0c;子网 掩码是255.255.255.0&#xff0c;那么这个网络的广播地址就是192.168.0.255。广播数据包会被发送到同一 网络上的所有端口&#xff0c;这样在该网络中的每台主机都将会收到这条广播。为了便于进行系统级别的消息通知&…...

SQL FOREIGN KEY

SQL FOREIGN KEY 简介 SQL(Structured Query Language)是用于管理关系数据库管理系统(RDBMS)的标准编程语言。在SQL中,FOREIGN KEY是一个重要的概念,用于建立和维护数据库中不同表之间的关系。本文将详细介绍SQL FOREIGN KEY的概念、用途、以及如何在SQL中实现和使用FO…...

绘唐3最新版本哪里下载

绘唐3最新版本哪里下载 绘唐最新版本下载地址 推文视频创作设计是一种通过视频和文字的形式来进行推广的方式&#xff0c;可以通过一些专业的工具来进行制作。 以下是一些常用的小说推文视频创作设计工具&#xff1a; 视频剪辑软件&#xff1a;如Adobe Premiere Pro、Fina…...

[ES6] 箭头函数

JavaScript 是一种广泛使用的编程语言&#xff0c;随着其发展和演变&#xff0c;引入了很多新的特性来提高代码的可读性和开发效率。其中一个重要的特性就是 ES6&#xff08;ECMAScript 2015&#xff09;中引入的箭头函数&#xff08;Arrow Function&#xff09;。箭头函数不仅…...

BiLSTM模型实现

# 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 # 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 import torch import torch.nn as nn# 本函数实现将中文文本映射为…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

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

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

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

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

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

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

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思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...