当前位置: 首页 > 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&…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...