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

LeetCode Hot100 1~10

目录

  • 哈希
    • 1. 两数之和
    • 2. 字母异位词分组
    • 3. 最长连续子序列
  • 双指针
    • 4. 移动零
    • 5. 盛最多水的容器
    • 6. 三数之和
    • 7. 接雨水
  • 子串
    • 8. 无重复字符的最长子串
    • 9. 找到字符中所有字母的异位词
    • 10. 和为K的子数组

哈希

1. 两数之和

利用哈希表找出当前数字还差多少 看看差值时候在哈希表中即可

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int , int> unmapNums;for (int i = 0; i < nums.size(); i++) {unmapNums[nums[i]] = i;}vector<int> ans = {};for (int i = 0; i < nums.size(); i++) {if (unmapNums.count(target - nums[i]) == 1) {if (i !=unmapNums[target - nums[i]] ) {ans.push_back(i);ans.push_back(unmapNums[target - nums[i]]);break;}}}return ans;}
};

2. 字母异位词分组

我们只需要将每个string进行排序 排序后的结果作为key 本身的str作为value即可

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string , vector<string>> unmapString;for (auto str : strs) {string key = str;sort(key.begin() , key.end());unmapString[key].push_back(str);}vector<vector<string>> ans;for (auto vStr : unmapString) {ans.push_back(vStr.second);}return ans;}
};

3. 最长连续子序列

我们只需要将所有的数字放到一个set中

之后遍历整个set 找到最长子序列开始最小的一个数 然后不停往后推即可

class Solution {
public:int longestConsecutive(vector<int>& nums) {set<int> setNums;for (auto x : nums) {setNums.insert(x);}int ans = 0;for (auto it : setNums) {if (setNums.count(it - 1)) {continue;}int cur = 1;int curNum = it;while(setNums.count(curNum + 1)) {cur += 1;curNum += 1;}ans = max(ans , cur);}return ans;}
};

双指针

4. 移动零

class Solution {
public:void moveZeroes(vector<int>& nums) {int left = 0;int right = 0;for(right = 0; right < nums.size(); right++) {if (nums[right] != 0) {nums[left] = nums[right];left++;}}for (int i = left ; i < nums.size(); i++) {nums[i] = 0;}}
};

5. 盛最多水的容器

本题依然使用双指针就可以解决

我们首先确定当宽度最大的时候能装最多的水为多少 接下来宽度减少

因为宽度确定了 所以高度要尽可能的大 于是我们移动高度较小的那一侧

class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;int ans = 0;while(left < right) {int h = min(height[left] , height[right]);int w = right - left;int cur = h * w;ans = max(ans , cur);if (height[left] < height[right]) {left++;}else {right--;}}return ans;}
};

6. 三数之和

本题主要使用双指针法来解决 整体思路比较简单 难点是如何去重

首先我们将整个数目进行排序 i 作为数目的第一号位 left作为二号位 right作为三号位 看看这三个数能够组成一个三元组

如果说大了 right –

如果说小了 left++

如果说正好 则我们将答案放到容器中

去重

  1. 对i进行去重 如果和上一个数相同 则直接continue
  2. 对left去重 在得到一个答案之后 不断往右去重
  3. right同理
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin() , nums.end());for (int i = 0 ; i < nums.size() - 2; i++) {if (i > 0 && nums[i-1] == nums[i]) {continue;}int left = i + 1;int right = nums.size() - 1;while (left < right) {if (nums[i] + nums[left] + nums[right] < 0) {left++;} else if (nums[i] + nums[left] + nums[right] > 0) {right--;}else {ans.push_back({nums[i] , nums[left] , nums[right]});while(left < right && nums[left + 1] == nums[left]) {left++;}while(left < right && nums[right - 1] == nums[right]) {right--;}left++;right--;}}}return ans;}
};

7. 接雨水

我们从一列来考虑 只需要确定两旁的高度和当前高度的占用 我们就能确定这一列能接多少雨水

于是乎我们可以使用左右指针分别确认当前位置的最小高度以及占用高度 相减即可

class Solution {
public:int trap(vector<int>& height) {int ans = 0;int n = height.size();vector<int> vpre(n , 0);vector<int> vsuf(n , 0);vpre[0] = height[0];for (int i = 1; i < height.size(); i++) {vpre[i] = max(vpre[i-1] , height[i]);}vsuf[n-1] = height[n-1];for (int i = n -2; i >=0 ; i--) {vsuf[i] = max(vsuf[i+1] , height[i]);}for (int i = 0; i < n; i++) {ans += (min(vsuf[i] , vpre[i]) - height[i]);}return ans;}
};

子串

8. 无重复字符的最长子串

简单的动态规划

需要注意的是 我们每次遍历都需要更新字符所在的位置 而不是遇到重复值再更新

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();vector<int> dp(n , 0);unordered_map<char , int> unmapStr;dp[0] = 1;unmapStr[s[0]] = 0;for (int i = 1; i < s.size(); i++) {dp[i] = dp[i-1] + 1;if (unmapStr.count(s[i])) {dp[i] = min(dp[i] , i - unmapStr[s[i]]);}unmapStr[s[i]] = i;}int ans = 0;for (auto x : dp) {ans = max(ans , x);}return ans;}
};

9. 找到字符中所有字母的异位词

我们使用一个“欠账哈希表” 来表示字符的欠账 all表示欠账的总额 (大于等于0)

然后每次L++ R++的时候我们开始还账和入账 如此反复即可

需要注意的是L++ 和R++的位置 以及入账和还账的时机和顺序

class Solution {
public:vector<int> findAnagrams(string s, string p) {if (p.size() > s.size()) {return {};}vector<int> ans;int n = p.size();unordered_map<char , int> unmapStrp1;for (auto x : p) {unmapStrp1[x]++;}int L = 0;int R = n - 1;for (int j = L ; j <= R; j++) {if (unmapStrp1.count(s[j])) {unmapStrp1[s[j]]--;}      }int all = 0;for (auto x : unmapStrp1) {if (x.second > 0) {all += x.second;}}while (R < s.size()) {if (all == 0) {ans.push_back(L);}if (unmapStrp1.count(s[L])) {unmapStrp1[s[L]]++;if (unmapStrp1[s[L]] > 0) {all++;}}R++;if (unmapStrp1.count(s[R])) {unmapStrp1[s[R]]--;if (unmapStrp1[s[R]] >= 0) {all--;}}L++;}return ans;}
};

10. 和为K的子数组

这道题目需要注意的是 我们每次更新一个前缀和就要计算一次结果 以免后面的前缀和进入哈希表后影响前面的结果

class Solution {
public:int subarraySum(vector<int>& nums, int k) {vector<int> vPre(nums.size() + 1, 0);vPre[0] = 0;int ans = 0;unordered_map<int, int> unmapVpre;unmapVpre[0]++;  // 初始时考虑前缀和为0的情况for (int i = 0; i < nums.size(); i++) {vPre[i + 1] = vPre[i] + nums[i];// 在计算前缀和之后,检查当前前缀和是否满足条件if (unmapVpre.count(vPre[i + 1] - k)) {ans += unmapVpre[vPre[i + 1] - k];}// 更新当前前缀和的出现次数unmapVpre[vPre[i + 1]]++;}return ans;}
};

相关文章:

LeetCode Hot100 1~10

目录 哈希1. 两数之和2. 字母异位词分组3. 最长连续子序列 双指针4. 移动零5. 盛最多水的容器6. 三数之和7. 接雨水 子串8. 无重复字符的最长子串9. 找到字符中所有字母的异位词10. 和为K的子数组 哈希 1. 两数之和 利用哈希表找出当前数字还差多少 看看差值时候在哈希表中即…...

npm 最新国内淘宝镜像地址源 (旧版已不能用)

注意&#xff1a;原域名https://registry.npm.taobao.org/ 在 2022.06.30 号正式下线和停止 DNS 解析 最新地址&#xff1a; #最新地址 淘宝 NPM 镜像站喊你切换新域名啦! npm config set registry https://registry.npmmirror.com 查看镜像使用状态 npm config get registr…...

DepthAI 2.29版本 发布

2024年11月29日 增加在设备运行时使用新的 dai::Device.setCalibration() 更改设备校准能力的方法&#xff0c;并使用 dai::Device.getCalibration() 进行检索校准 1&#x1f343; 新的立体深度预设属性&#xff1a; 预设 面部 高细节 机器人 2&#x1f343; 多项摄像…...

C#反序列化XML时提示XML 文档(1, 1)中有错误

最近在反序列化一个XML时&#xff0c;遇到了如下报错&#xff1a; XML 文档(1, 1)中有错误。 内部异常 XmlException: 根级别上的数据无效。 第 1 行&#xff0c;位置 1。 看描述应该是XML格式的问题&#xff0c;我把XML复制到新建的控制台程序&#xff0c;反序列化又是可以的…...

C# 中的接口:定义行为契约与实现多态性

C#中的接口&#xff08;Interfaces&#xff09;。接口是C#中一个非常重要的特性&#xff0c;它允许定义类型的行为契约&#xff0c;而不指定具体实现。通过接口&#xff0c;可以实现多态性、代码的灵活性和可扩展性。以下是一篇关于C#中接口的文章。 引言 接口&#xff08;Int…...

Redis的基础知识·

Redis是一个基于内存的key-value的结构数据库 基于内存存储 读写性能高适合存储热点数据&#xff08;热点商品 咨询 新闻&#xff09; 开启Redis 首先输入命令 redis-server.exe redis.windows.conf 然后重新打开命令行窗口 输入命令 redis-cli.exe 输入密码 …...

qt QProxyStyle详解

1、概述 QProxyStyle是Qt框架中QStyle类的一个子类&#xff0c;它提供了一种代理机制&#xff0c;允许开发者在不直接修改现有样式&#xff08;QStyle&#xff09;实现的情况下&#xff0c;对样式行为进行定制或扩展。通过继承QProxyStyle&#xff0c;开发者可以重写其虚方法&…...

AWS CLI 操作指南

AWS CLI 操作指南 世间本来就存在许多乐境&#xff0c;只是现代人为世间所累而未能予以关注&#xff0c;也就失去了许多体验乐境的机会。比如&#xff0c;忙里偷闲看云&#xff0c;以悠闲的心看悠闲的云&#xff0c;便是一种极妙的乐境。 本文将介绍如何配置 AWS CLI&#xff0…...

海盗王用golang重写的AccountServer功能

自从用golang重写了海盗王的网关gateserver以来&#xff0c;一直想把accountserver也重写了&#xff0c;但是一直没有进行。 趁上次刚写好那个golang版的更新器&#xff0c;还有些熟悉&#xff0c;于是把原来AccountServer的C代码重写读了个大概。它原版的写得太过于复杂&#…...

如何保证spring boot应用程序的安全性?

保证Spring Boot应用程序的安全性是至关重要的&#xff0c;以下是小编为大家列举的一些关键措施和最佳实践&#xff1a; 文章目录 1. 使用Spring Security2. 安全配置3. 数据加密4. 凭证管理5. 输入验证6. 异常处理7. 定期更新依赖8. 日志监控9. 审计日志10. 安全培训 1. 使用S…...

力扣 岛屿数量-200

岛屿数量-200 class Solution {//深度优先搜索 dfs public:int vis[300][300] {0};//用于标记的数组&#xff0c;标记是否遍历过int cnt 0;//岛屿计数//上下左右的移动方向数组int dx[4]{-1,1,0,0};int dy[4]{0,0,-1,1};//深度优先搜索void dfs(vector<vector<char>…...

极狐GitLab 17.6 正式发布几十项与 DevSecOps 相关的功能【三】

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 学习极狐GitLab 的相关资料&#xff1a; 极狐GitLab 官网极狐…...

十二、正则表达式、元字符、替换修饰符、手势和对话框插件、字符串截取

1. 正则表达式 1.1 基本使用 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title&g…...

【信息系统项目管理师】第3章:信息系统治理 考点梳理

文章目录 3.1 IT 治理3.1.1 IT治理基础3.1.2 IT治理体系3.1.3 IT治理任务3.1.4 IT治理方法与标准 3.2 IT 审计3.2.1 IT审计基础3.2.2 审计方法与技术3.2.3 审计流程3.2.4 审计内容 3.1 IT 治理 IT治理起到重要的统筹、评估、指导和监督作用。 信息技术审计(IT审计)作为与IT治…...

实现对图片或者视频增加隐藏水印和提取水印

好久好久没有写博客了&#xff0c;最近看见一个很有意思的文章&#xff1a;小心你的电脑被窃听&#xff0c;就是说在一些公司&#xff0c;截图都会存在水印&#xff0c;方便溯源&#xff0c;然后出于技术的好奇&#xff0c;我在github上搜了一下&#xff0c;还真有相关的github…...

uniapp配置全局消息提醒

1.H5使用根标签插入dom的方式实现。 2.app端使用plus.nativeObj.View的方式绘制实现 H5端app端 H5端 创建组件orderAlert.vue <template><div class"view"><div class"content" v-if"visible"><div class"message&q…...

卸载snap docker一直卡住:Save data of snap “docker“ in automatic snapshot set #3

在卸载 Snap 安装的 Docker 时卡住&#xff0c;通常是因为 Snap 在执行卸载时会先尝试保存一些快照&#xff08;自动或手动创建的&#xff09;&#xff0c;并且该过程可能因某些原因而卡住。为了解决这个问题&#xff0c;你可以按照以下步骤强制删除 Snap 安装的 Docker&#x…...

python学习——字典元素的访问和遍历

在Python中&#xff0c;访问和遍历字典元素的方法如下&#xff1a; 文章目录 访问字典元素1. 使用键来访问值2. 使用 get() 方法 遍历字典元素1. 遍历字典的键2. 遍历字典的值3. 遍历字典的键和值4. 使用列表推导式来创建新的列表 实操 访问字典元素 1. 使用键来访问值 # 创…...

数据结构基础之《(9)—归并排序》

一、什么是归并排序 1、整体是递归&#xff0c;左边排好序右边排好序merge让整体有序 2、让其整体有序的过程里用了排外序方法 3、利用master公式来求解时间复杂度 4、当然可以用非递归实现 二、归并排序说明 1、首先有一个f函数 void f(arr, L, R) 说明&#xff1a;在arr上…...

【深度学习】各种卷积—卷积、反卷积、空洞卷积、可分离卷积、分组卷积

在全连接神经网络中&#xff0c;每个神经元都和上一层的所有神经元彼此连接&#xff0c;这会导致网络的参数量非常大&#xff0c;难以实现复杂数据的处理。为了改善这种情况&#xff0c;卷积神经网络应运而生。 一、卷积 在信号处理中&#xff0c;卷积被定义为一个函数经过翻转…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...