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

LeetCode 热题100 刷题笔记

一:哈希表

一般哈希表都是用来快速判断一个元素是否出现集合里。

直白来讲其实数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。

1.两数之和

题目链接:. - 力扣(LeetCode)

// 哈希表
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {std::unordered_map <int, int> map;for(int i = 0; i < nums.size(); i++){auto iter = map.find(target - nums[i]);if(iter != map.end()){return {iter->second, i};}else{map.insert(pair<int, int>(nums[i], i));}}return {};}
};

本题其实有四个重点:

  • 为什么会想到用哈希表

本题呢,我就需要一个集合来存放我们遍历过的元素,然后在遍历数组的时候去询问这个集合,某元素是否遍历过,也就是 是否出现在这个集合。那么我们就应该想到使用哈希法了。

  • 哈希表为什么用map

这道题目中并不需要key有序,选择std::unordered_map 效率更高!

  • 本题map是用来存什么的

map目的用来存放我们访问过的元素,因为遍历数组的时候,需要记录我们之前遍历过哪些元素和对应的下标,这样才能找到与当前元素相匹配的(也就是相加等于target)

  • map中的key和value用来存什么的

这道题 我们需要 给出一个元素,判断这个元素是否出现过,如果出现过,返回这个元素的下标。

那么判断元素是否出现,这个元素就要作为key,所以数组中的元素作为key,有key对应的就是value,value用来存下标。

所以 map中的存储结构为 {key:数据元素,value:数组元素对应的下标}。

 2. 字母异位词分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {map<string, int> myhash;vector<vector<string>> myAns;int cint =0;for(int i = 0; i<strs.size(); i++){string temString = strs[i];sort(temString.begin(), temString.end());auto iter = myhash.find(temString);if(iter == myhash.end()){myAns.push_back(vector<string>());myAns.back().push_back(strs[i]);myhash[temString]=cint;cint ++;}else{int index = myhash[temString];myAns[index].push_back(strs[i]);}}return myAns;}
};

 3.最长连续序列

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> myset;for(const int& num : nums){myset.insert(num);}int longestStreak = 0;for(const int& num : myset){if(myset.count(num-1) == 0){int currentNum = num;int currentStreak = 1;while(myset.count(currentNum +1)){currentNum = currentNum + 1;currentStreak = currentStreak + 1; }longestStreak = max(longestStreak, currentStreak);}}return longestStreak;}
};

 二:双指针

1.移动零

// 使用双指针,左指针指向当前已经处理好的序列的尾部,右指针指向待处理序列的头部。
// 右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移
class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size(), left = 0, right = 0;while (right < n) {if (nums[right]) {swap(nums[left], nums[right]);left++;}right++;}}
};

思路:通过右指针来遍历数组,左指针始终指向处理好的序列的尾部。

 2.盛最多水的容器

/* 算法流程:
1.初始化: 双指针 i , j 分列水槽左右两端;
2.循环收窄: 直至双指针相遇时跳出;a.更新面积最大值 res;b.选定两板高度中的短板,向中间收窄一格;
3.返回值: 返回面积最大值 res 即可; */class Solution {
public:int maxArea(vector<int>& height) {int i = 0, j = height.size() - 1, res = 0;while(i < j) {res = height[i] < height[j] ? max(res, (j - i) * height[i++]): max(res, (j - i) * height[j--]); }return res;}
};

3.三数之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[left], c = nums[right]for (int i = 0; i < nums.size(); i++) {// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if (nums[i] > 0) {return result;}// 错误去重a方法,将会漏掉-1,-1,2 这种情况/*if (nums[i] == nums[i + 1]) {continue;}*/// 正确去重a方法if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.size() - 1;while (right > left) {// 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组/*while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;*/if (nums[i] + nums[left] + nums[right] > 0) right--;else if (nums[i] + nums[left] + nums[right] < 0) left++;else {result.push_back(vector<int>{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;// 找到答案时,双指针同时收缩right--;left++;}}}return result;}
};

 思路:

首先将数组排序,然后有一层for循环,i从下标0的地方开始,同时定一个下标left 定义在i+1的位置上,定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0,我们这里相当于 a = nums[i],b = nums[left],c = nums[right]。

接下来如何移动left 和right呢, 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。

相关文章:

LeetCode 热题100 刷题笔记

一&#xff1a;哈希表 一般哈希表都是用来快速判断一个元素是否出现集合里。 直白来讲其实数组就是一张哈希表&#xff0c;哈希表中关键码就是数组的索引下标&#xff0c;然后通过下标直接访问数组中的元素。 1.两数之和 题目链接&#xff1a;. - 力扣&#xff08;LeetCode…...

veridata安装

GoldenGate Veridata是GoldenGate中用于比较数据库间数据同步效果的一个对比软件。Veridata基于Web&#xff0c;支持大据量的数据对比&#xff0c;能够在不停止数据同步的情况下就可以比较数据。 1、安装veridata前我们都会先安装 middleware infrastructure 这时我们会添加几个…...

面试笔记系列三之spring基础知识点整理及常见面试题

目录 如何实现一个IOC容器? 说说你对Spring 的理解&#xff1f; 你觉得Spring的核心是什么&#xff1f; 说一下使用spring的优势&#xff1f; Spring是如何简化开发的&#xff1f; IOC 运行时序 prepareRefresh() 初始化上下文环境 obtainFreshBeanFactory() 创建并…...

面试笔记系列四之SpringBoot+SpringCloud+计算机网络基础知识点整理及常见面试题

目录 Spring Boot 什么是 Spring Boot&#xff1f; Spring Boot 有哪些优点&#xff1f; SpringBootApplication注解 Spring Boot 的启动流程 Spring Boot属性加载顺序 springboot自动配置原理是什么&#xff1f;&#xff08;*&#xff09; 如何理解springboot中的start…...

Kernel[Device Tree] - 1. 设备树的由来

内核代码中&#xff0c;arch文件夹下&#xff0c;是各个架构相关的代码&#xff0c;arm也在里面。 arm子文件夹下&#xff0c;有mach-xxx的目录&#xff0c;就是针对各个芯片类型的&#xff0c;比如mach-imx就是imx系列的芯片。 再里面就是具体的芯片或SOC&#xff0c;比如ma…...

第十四天-网络爬虫基础

目录 1.什么是爬虫 2.网络协议 OSI七层参考模型 TCP/IP模型 1.应用层 2.传输层 3.网络层 3.HTTP协议 1.介绍 2.http版本&#xff1a; 3.请求格式 4.请求方法 5.HTTP响应 状态码&#xff1a; 6.http如何连接 4.Python requests模块 1.安装 2.使用get/post 3.响…...

Linux系统安装

Linux系统安装 安装包链接 链接&#xff1a;https://pan.baidu.com/s/1FdP7TH90UvKUQuiL2yeGCA 提取码&#xff1a;c49n安装包内容 虚拟机执行文件 详细安装教程 虚拟机密钥 Ubuntu 安装步骤 先点击虚拟机的.EXE文件安装&#xff0c;打开安装教程&#xff0c;有详细的说明。...

springboot-基础-thymeleaf配置+YAML语法

备份笔记。所有代码都是2019年测试通过的&#xff0c;如有问题请自行搜索解决&#xff01; 目录 配置thymeleafthymeleaf举例参数设置yaml基础知识YAML语法报错&#xff1a;Expecting a Mapping node but got 其他语法 spring boot不推荐使用jsp。thymeleaf是一个XML/XHTML/HTM…...

深入理解分库、分表、分库分表

前言 分库分表&#xff0c;是企业里面比较常见的针对高并发、数据量大的场景下的一种技术优化方案&#xff0c;所谓"分库分表"&#xff0c;根本就不是一件事儿&#xff0c;而是三件事儿&#xff0c;他们要解决的问题也都不一样&#xff0c;这三个事儿分别是"只…...

Oracle中序列

1. Sequence 定义 在Oracle中可以用SEQUENCE生成自增字段。Sequence序列是Oracle中用于生成数字序列的对象&#xff0c;可以创建一个唯一的数字作为主键。 2. 为什么要用 Sequence 你可能有疑问为什么要使用序列&#xff1f; 不能使用一个存储主键的表并每次递增吗&#xf…...

蓝牙耳机和笔记本电脑配对连接上了,播放设备里没有显示蓝牙耳机这个设备,选不了输出设备

环境&#xff1a; WIN10 杂牌蓝牙耳机6s 问题描述&#xff1a; 蓝牙耳机和笔记本电脑配对连接上了&#xff0c;播放设备里没有显示蓝牙耳机这个设备&#xff0c;选不了输出设备 解决方案&#xff1a; 1.打开设备和打印机&#xff0c;找到这个设备 2.选中这个设备&#…...

Cadence Allegro PCB设计88问解析(三十四) 之 Allegro 中 DDR等长处理

一个学习信号完整性仿真的layout工程师 在进行PCB设计时 &#xff0c;会遇到一些单端的信号要做等长处理&#xff0c;比如DDR的数据线&#xff0c;交换机之间的数据线之类的。这时需要我们建立match group&#xff0c;来做等长。下面简单介绍在Allegro中怎么做等长&#xff1a;…...

向爬虫而生---Redis 探究篇2<redis集群(1)>

前言: 经常会遇到这样的事,redis运行一段时间以后,就会出现迟钝和卡壳! 这时候,说明已经到了瓶颈期了,需要用到redis集群了! 那么,弄明白集群的几个概念是必要的,我用案例来讲,,, 正文: 当需要处理大量数据或提供高可用性和性能时&#xff0c;Redis集群是一种常见的解决方案。…...

[云原生] 二进制安装K8S(上)搭建单机matser、etcd集群和node节点

一、单机matser预部署设计 目前Kubernetes最新版本是v1.25&#xff0c;但大部分公司一般不会使用最新版本。 目前公司使用比较多的&#xff1a;老版本是v1.15&#xff0c;因为v1.16改变了很多API接口版本&#xff0c;国内目前使用比较多的是v1.18、v1.20。 组件部署&#xff…...

乘积尾零(蓝桥杯)

文章目录 乘积尾零题目描述代码 乘积尾零 题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 如下的 10 行数据&#xff0c;每行有 10 个整数&#xff0c;请你求出它们的乘积的末尾有多少个零&#xff1f; 5650 454…...

项目解决方案: 实时视频拼接方案介绍

目 录 1、实时视频拼接概述 2、适用场景 3、系统介绍 3.1拼接形式 3.1.1横向拼接 3.1.2纵向拼接 3.2前端选择 3.2.1前端类型 3.2.2推荐配置 3.3后端选择 3.3.1录像回放 3.3.2客户端展示 4、拼接方案介绍 4.1基于4K摄像机的拼接方案 4.1.1系统架构…...

雾锁王国Enshrouded服务器CPU内存配置怎么选择?

雾锁王国/Enshrouded服务器CPU内存配置如何选择&#xff1f;阿里云服务器网aliyunfuwuqi.com建议选择8核32G配置&#xff0c;支持4人玩家畅玩&#xff0c;自带10M公网带宽&#xff0c;1个月90元&#xff0c;3个月271元&#xff0c;幻兽帕鲁服务器申请页面 https://t.aliyun.com…...

yolov9,使用自定义的数据训练推理

[源码 &#x1f40b;]( GitHub - WongKinYiu/yolov9: Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information) [论文 &#x1f4d8;](arxiv.org/pdf/2402.13616.pdf) 论文摘要&#xff1a;本文介绍了一种新的目标检测…...

企业文件图纸加密有哪些?图纸文件加密防泄密软件如何选?

在现在的市场发展中&#xff0c;对于企业的图纸文件安全问题越来越重视&#xff0c;如设计图纸&#xff0c;重要文件等&#xff0c;一旦泄漏就会给企业造成巨大的经济损失。所以对企业管理者来讲&#xff0c;如何才能选择一款好用的适合本企业的图纸文件加密软件是非常重要的&a…...

phpldapadmin This base cannot be created with PLA

phpldapadmin This base cannot be created with PLA 1、问题描述2、问题分析3、解决方法&#xff1a;创建根节点 1、问题描述 安装phpldapadmin参考链接: https://blog.csdn.net/OceanWaves1993/article/details/136048686?spm1001.2014.3001.5501 刚安装完成phpldapadmin&…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...