破解面试难题:面试经典150题 之双指针法详解与代码实现

news/2024/7/20 18:00:32/文章来源:https://blog.csdn.net/m0_68987050/article/details/139237869

面试经典 150 题 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台icon-default.png?t=N7T8https://leetcode.cn/studyplan/top-interview-150/

125. 验证回文串

125. 验证回文串

 STL容器

思路:

  1. 遍历输入的字符串,将其中的字母字符转换为小写,并保留数字字符,放入另一个字符串 s1 中。
  2. 将 s1 复制给另一个字符串 s2
  3. 将 s1 反转,得到逆序字符串。
  4. 比较原字符串 s1 和逆序字符串 s2 是否相等,若相等则返回 true,否则返回 false
class Solution {
public:bool isPalindrome(string s) {string s1;for(auto &c : s) {if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { s1 += tolower(c);} else if(c >= '0' && c <= '9'){ s1 += c;}}string s2;s2=s1;reverse(s1.begin(),s1.end());if(s1 == s2)return true;elsereturn false;}
};
双指针

思路:

  1. 遍历输入的字符串,将其中的字母字符转换为小写,并保留数字字符,放入另一个字符串 s1 中。
  2. 初始化两个指针 left 和 right 分别指向 s1 的开头和结尾。
  3. 使用双指针方法,依次比较 left 和 right 指向的字符,如果不相等,则返回 false;如果相等,则继续向中间移动指针。
  4. 如果遍历完成后都没有出现不相等的情况,说明该字符串是回文字符串,返回 true
class Solution {
public:bool isPalindrome(string s) {string s1;for(auto &c : s) {if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { s1 += tolower(c);} else if(c >= '0' && c <= '9'){ s1 += c;}}int left = 0;int right = s1.length()-1;while(left<right){if(s1[left] != s1[right])return false;++left;--right;}return true;}
};

 392. 判断子序列

 392. 判断子序列

思路:

  1. 初始化两个指针 i 和 j 分别指向字符串 s 和 t 的起始位置。
  2. 遍历字符串 t,当字符 t[j] 等于字符 s[i] 时,将两个指针都向后移动一位。
  3. 如果最终 i 移动到了 s 的末尾,说明 s 是 t 的子序列,返回 true;否则,返回 false
class Solution {
public:bool isSubsequence(string s, string t) {int i = 0, j = 0;while(i<s.size()&&j<t.size()){if(s[i]==t[j])i++;j++;}   if(i==s.size())return true;return false;}
};

 167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

思路:

  1. 使用双指针,一个指针 i 指向数组的起始位置,另一个指针 j 指向数组的末尾位置。
  2. 在每次迭代中,计算指针 i 和指针 j 指向的元素之和 numbers[i] + numbers[j]
  3. 如果和大于目标值 target,则将指针 j 向左移动一位,以减小和的值。
  4. 如果和小于目标值 target,则将指针 i 向右移动一位,以增加和的值。
  5. 如果和等于目标值 target,则找到了符合条件的数对,将它们的索引加1并加入结果数组中,然后退出循环。(因为只有一对正确的答案)
  6. 最终返回结果数组。
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {vector<int>res;int i=0;int j=numbers.size()-1;while(i<j){if(numbers[i]+numbers[j]>target)j--;else if(numbers[i]+numbers[j]<target)i++;else{res.push_back(i+1);res.push_back(j+1);break;}}return res;}
};

 11. 盛最多水的容器

11. 盛最多水的容器

思路:

  1. 使用双指针,一个指针 i 指向数组的起始位置,另一个指针 j 指向数组的末尾位置。
  2. 在每次迭代中,计算当前容器的容量,即 (j - i) * min(height[i], height[j])
  3. 每次计算完容量后,更新记录的最大容量 mx,将当前容量与 mx 比较取较大值。
  4. 如果 height[i] < height[j],则移动指针 i 向右一位;否则移动指针 j 向左一位。
  5. 重复步骤 2 到 4,直到指针 i 和 j 相遇为止。
  6. 返回记录的最大容量 mx
class Solution {
public:int maxArea(vector<int>& height) {int i=0;int j=height.size()-1;int mx=0,s=0;while(i<j){s=(j-i)*min(height[i],height[j]);mx=max(mx,s);if (height[i] < height[j]) {i++;} else {j--;}}return mx;}
};

15. 三数之和

15. 三数之和

思路:

  1. 首先对数组进行排序,这样可以方便地使用双指针来遍历数组。
  2. 然后使用三个指针 ileftright 分别指向排序后数组中的每个元素、当前元素的下一个元素和数组末尾元素。
  3. 在每一轮循环中,固定指针 i,并初始化 left = i + 1 和 right = n - 1,其中 n 是数组的长度。
  4. 在 left 和 right 指针确定的范围内,使用双指针技巧来寻找和为 0 的两个数。
  5. 如果找到了满足条件的三元组,则将其加入结果集中,并且需要注意去重。
  6. 继续遍历数组,直到 i 指针到达倒数第三个元素为止。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;int n = nums.size();sort(nums.begin(), nums.end());for (int i = 0; i < n - 2; ++i) {if (i > 0 && nums[i] == nums[i - 1])continue;int left = i + 1;int right = n - 1;int target = -nums[i]; while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {res.push_back({nums[i], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1])left++;while (left < right && nums[right] == nums[right - 1])right--;left++;right--;}else if (sum < target) {left++;} else {right--;}}}return res;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1054319.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

排序进阶----插入排序,希尔排序

各位看官们好&#xff0c;接下来鄙人想与大家分享的实现被称为六大排序之一的插入排序。其实关于这六大排序在我们最开始就已经接触过了。我们在最开始学习c语言的时候&#xff0c;我们要学习到其中之一的冒泡排序。虽然现在看起来冒泡排序确实是没有太大的实际效果&#xff0c…

【物联网实战项目】STM32C8T6+esp8266/mqtt+dht11+onenet+uniapp

一、实物图 前端uniapp效果图&#xff08;实现与onenet同步更新数据&#xff09; 首先要确定接线图和接线顺序&#xff1a; 1、stm32c8t6开发板连接stlinkv2下载线 ST-LINK V2STM323.3V3.3VSWDIOSWIOSWCLKSWCLKGNDGND 2、ch340串口连接底座&#xff08;注意RXD和TXD的连接方式…

kali下载zsteg和stegpy

1.kali下载zsteg 从 GitHub 上克隆zsteg到kali git clone https://github.com/zed-0xff/zsteg 切换目录 cd zsteg 用于安装名为 zsteg 的 Ruby Gem 包 gem install zsteg 2.kali下载stegpy 下载网站内的stegpy-master压缩包GitCode - 开发者的代码家园 并拉到kali中 切换到s…

【豆伴匠】L1-L12更新完,一站式解决文史积累、阅读、写作难题,弯道超车,寒假必备

合抱之木&#xff0c;生于毫末&#xff1b; 九层之台&#xff0c;起于垒土&#xff1b; 千里之行&#xff0c;始于足下。 豆伴匠是什么&#xff1f; 豆伴匠内容包括&#xff1a;人、文、史、作四个模块&#xff0c;全面覆盖文史知识及读写技巧。 目前&#xff0c;豆伴匠有L…

【MySQL】SQL 基础

文章目录 【 1. SQL 的书写规则 】1.1 大小写规则1.2 常量的表示1.3 注释1.4 HELP 系统帮助 【 2. 常用数据库函数 】2.1 SHOW DATABASES 显示数据库2.2 CREATE DATABASE 创建数据库2.3 ALTER DATABASE 修改数据库2.4 DROP DATABASE 删除数据库2.5 USE 选择数据库 【 3. RDBMS …

PyTorch张量索引用法速查

作为数据科学家或软件工程师&#xff0c;你可能经常处理大型数据集和复杂的数学运算&#xff0c;这些运算需要高效且可扩展的计算。PyTorch 是一个流行的开源机器学习库&#xff0c;它通过 GPU 加速提供快速灵活的张量计算。在本文中&#xff0c;我们将深入研究 PyTorch 张量索…

【架构-19】架构风格比较

独立构件风格(Independent Components): 适用场景:需要灵活扩展和组合的复杂大数据应用 特点: 高度解耦:各组件之间高度独立,可单独开发和部署 灵活性和可扩展性:易于根据需求添加或替换组件 复杂度高:需要管理多个独立的组件及其交互 通信开销:组件间需要通过网络通信,可能会…

深入探索C++继承机制:从概念到实践的全面指南

目录 继承的概念及定义 继承的概念 继承的定义 定义格式 继承方式和访问限定符 继承基类成员访问方式的变化 默认继承方式 基类和派生类对象赋值转换 继承中的作用域 派生类的默认成员函数 继承与友元 继承与静态成员 继承的方式 菱形虚拟继承 菱形虚拟继承原理 继承…

超详细的前后端实战项目(Spring系列加上vue3)前端篇+后端篇(三)(一步步实现+源码)

好了&#xff0c;兄弟们&#xff0c;继昨天的项目之后&#xff0c;开始继续敲前端代码&#xff0c;完成前端部分&#xff08;今天应该能把前端大概完成开启后端部分了&#xff09; 昨天补充了一下登录界面加上了文章管理界面和用户个人中心界面 完善用户个人中心界面 修改一…

华为设备WLAN配置之AP上线

WLAN基础配置之AP上线 配置WLAN无线网络的第一阶段&#xff0c;AP上线技术&#xff1a; 实验目标&#xff1a;使得AP能够获得来自AC的DHCP地址服务的地址&#xff0c;且是该网段地址池中的IP。 实验步骤&#xff1a; 1.把AC当作三层交换机配置虚拟网关 sys Enter system view,…

halcon SVM 缺陷检测分类

一、概述 训练数据 二、算子解释 compactness Halcon 算子 compactness_halcon compactness-CSDN博客 *计算输入区域的紧凑度 compactness (Region, Compactness) 原理解释 convexity 每个输入区域的凸度 Halcon 算子 convexity_halcon convexity-CSDN博客 *计算每个输…

Unity LayerMask避坑笔记

今天使用Physics2D.OverlapAreaNonAlloc进行物理检测时候&#xff0c;通过LayerMask.NameToLayer传入了int值的LayerMask&#xff0c;结果一直识别不到&#xff0c;经过Debug才找到问题&#xff0c;竟是LayerMask的“值”传输有问题&#xff0c;记录一下。 直接贴代码输出结果&…

《SpringBoot》系列文章目录

SpringBoot是由Pivotal团队提供的全新框架&#xff0c;旨在简化新Spring应用的初始搭建以及开发过程。以下是一些关于SpringBoot的详细介绍&#xff1a; 设计目的&#xff1a;SpringBoot通过特定的方式来进行配置&#xff0c;使得开发人员不再需要定义样板化的配置&#xff0c…

HNU-计算机体系结构-实验1-RISC-V流水线

计算机体系结构 实验1 计科210X 甘晴void 202108010XXX 1 实验目的 参考提供为了更好的理解RISC-V&#xff0c;通过学习RV32I Core的设计图&#xff0c;理解每条指令的数据流和控制信号&#xff0c;为之后指令流水线及乱序发射实验打下基础。 参考资料&#xff1a; RISC-…

【引领光子学革命:机器学习与深度学习重塑设计与应用新纪元】

光子器件的逆向设计&#xff1a;利用深度学习技术&#xff0c;可以优化多参数光子器件的设计。通过大量的数据分析和模式识别&#xff0c;深度学习算法能够预测和优化光子器件的性能&#xff0c;从而缩短设计周期并降低设计成本。 超构表面与超材料设计&#xff1a;在新型光学材…

浅谈金融行业数据安全分类分级

数据安全管理是一项从上而下的、多方配合开展的工作。在进行数据安全管理组织架构建设时&#xff0c;需要从上而下建设&#xff1b;从而全面推动数据安全管理工作的执行和落地&#xff1b;以保证数据安全的合法合规、并长效推动业务的发展和稳定运行。 金融行业机构应设立数据…

Hexo博客部署到云服务器

1、本地搭建hexo 本地搭建hexo过程详见hexo官网&#xff0c;步骤比较详细&#xff0c;按照步骤搭建即可 2、hexo主题 我使用的Butterfly主题&#xff0c;主题配置请查看Butterfly安装文档 3、部署到云服务器 3.1、服务器环境 nginx 搭建 使用云服务商提供的远程登陆登录进…

vscode远程登录阿里云服务器【使用密钥方式--后期无需再进行密码登录】【外包需要密码】

1&#xff1a;windows主机上生成【私钥】【公钥】 1.1生成公钥时不设置额外密码 1.2生成公钥时设置额外密码【给外包人员使用的方法】 2&#xff1a;在linux服务器中添加【公钥】 3&#xff1a;本地vscode连接linux服务器的配置 操作流程如下 1.1本地终端中【生成免密登录…

《TCP/IP网络编程》(第十一章)进程间通信

进程间通信意味着两个不同的进程间可以交换数据&#xff0c;它使得不同的进程能够协同工作&#xff0c;实现复杂的系统功能。 1.通过管道实现进程间通信 下图是基于 管道&#xff08;PIPE&#xff09; 的进程间通信结构模型 管道不属于进程的资源&#xff0c;属于操作系统的资…

[UE5]安卓调用外置摄像头拍照(之显示画面)

目录 部分参考文献&#xff08;有些有用的我没标&#xff0c;没放上来&#xff09; 要点 总蓝图 结果 部分参考文献&#xff08;有些有用的我没标&#xff0c;没放上来&#xff09; 【UE】获取USB摄像头画面_虚幻捕获硬件摄像头-CSDN博客 UE4安卓调用摄像头拍照确保打…