双指针-【3,4,5,6,7,8】

第三题:快乐数

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/happy-number/算法思想:

1.每个节点的值是唯一的(因为会形成环),所以用节点的值充当指针。

2.快指针走两步,慢指针走一步,下次相遇时在环内。

3.如果是快乐数,则环中的数字全是1,否则都不是1(因为1的下一个就是1),直接判定相遇时节点的值即可。

4.一定会形成环,这里就不证明了,因为题目条件给了。(就算不给,也是一定成环的)。

代码实现:

class Solution {
public:int next(int n) {int res=0;while(n) {res+=(n%10)*(n%10);n/=10;}return res;}bool isHappy(int n) {int slow=n,fast=n;do {fast=next(fast);fast=next(fast);slow=next(slow);}while(fast!=slow);if(fast==1) return true;return false;}
};

第四题:盛水最多的容器

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/container-with-most-water/

算法思想:

V = Height* Width(Height取较小的那一个)

取两头,对于当中较短的边,这已经是最好的情况了(此时宽度取最大(区间长度),高度也取最大(自己本身)),将其计入后就不用再考虑了。现在区间缩小了。

如此循环下去,区间比1小时(l>=r)即可退出。

代码实现:

class Solution {
public:int maxArea(vector<int>& height) {int l=0,r=height.size()-1,res=0;while(l<r) {int NewRes=min(height[l],height[r])*(r-l);if(NewRes>res) res=NewRes;if(height[l]>height[r]) --r;else ++l;}return res;}
};

第五题:有效三角形之和

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/valid-triangle-number/算法思想:

1.排序,使数组单调递增。

2.固定最大的数(下标最小是2,否则凑不到三个数),然后从该数组左边的区间取剩下的两个数字。

3.取小区间的两头(一个最小(l),一个最大(r))

如果这两个数足够大(max太大了,min都能带动,其他的更能带的动),res+=r-l;   --r;(r已经计算完了)

如果这两个数不够大(min太小了,max都带不动),++l;( l 太小了,没有利用价值了)

当l与r相遇时,这个大数就计算完了

4.计算下一个大数,一直循环到最后一个

代码实现:

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int res=0,size=nums.size();for(int i=2;i<size;++i) {int l=0,r=i-1;while(l<r) {if(nums[l]+nums[r]>nums[i]) {res+=r-l; --r; }else ++l;}}return res;}
};

第六题:两数之和

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/算法思想:

取区间的两头(一个最小(l),一个最大(r))

如果这两个数大了(max太大了,带上最小的数还是超过了target,所以min无用) --r;

如果这两个数小了(min太小了,带上了最大的数都够不到target,所以max无用)++l;

如果相等就找到了,走人!

每一次行动都会让区间宽度减1,如果减没了(也就是两指针相遇)还没找到,那就是没有了。

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int l=0,r=price.size()-1;while(l<r){if(price[l]+price[r]==target) return {price[l],price[r]};else if(price[l]+price[r]>target) --r;else ++l;}return {};}
};

第七题:三数之和

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/3sum/算法思想:

排序+双指针

注意:去重

1.固定一个数,然后在他右边(因为本思路左边的数都计完了)的区间利用双指针解决两数之和问题。

运行双指针时去重:

对于l:如果加加完了,数值不变,则继续加加,一直到数值变化

对于r:如果减减完了,数值不变,则接着减减,一直到数值变化

2.固定第一个,在固定下一个,将数组遍历一遍。

遍历时去重:如果加加完了,数值不变,则继续加加,一直到数值变化

在连续加加减减时,要注意越界问题。

解决方案:在连续加加减减时,每变化一次,判定一次

代码实现:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> res;int size=nums.size();for(int i=0;i<size;) {if(nums[i]>0) break;int j=i+1,k=size-1;while(j<k) {if(nums[i] +nums[j]+nums[k]>0) --k;else if(nums[i]+nums[j]+nums[k]<0) ++j;else {res.push_back({nums[i],nums[j],nums[k]});++j; --k;while(j<k&&nums[j-1]==nums[j]) ++j;while(j<k&&nums[k]==nums[k+1]) --k;}}++i;while(i<size-2&&nums[i]==nums[i-1]) ++i;}return res;}
};

第八题:四数之和

算法思想:

排序+双指针

注意:去重

1.从左到右轮流固定每一个数,然后在他右边的区间利用双指针解决三数之和问题。

2.去重问题和三数之和类似,此处略。

代码实现:

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> res;int size = nums.size();for(int i=0;i<size-3;) {for(int j=i+1;j<size-2;) {int k=j+1,r=size-1;while(k<r) {if((long)nums[i]+nums[j]+nums[k]+nums[r]<target) ++k;else if((long)nums[i]+nums[j]+nums[k]+nums[r]>target) --r;else if((long)nums[i]+nums[j]+nums[k]+nums[r]==target) {res.push_back({nums[i],nums[j],nums[k],nums[r]});++k; --r;while(k<r&&nums[k]==nums[k-1]) ++k;while(k<r&&nums[r]==nums[r+1]) --r;}}++j;while(j<size-2&&nums[j]==nums[j-1]) ++j;}++i;while(i<size-3&&nums[i]==nums[i-1]) ++i;}return res;}
};

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

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

相关文章

SpringBoot上传超大文件导致OOM,完美解决办法

问题描述 上传大文件报错: Caused by: java.lang.OutOfMemoryError at java.io.ByteArrayOutputStream.hugeCapacity(ByteArrayOutputStream.java:123) ~[?:1.8.0_381] at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:117) ~[?:1.8.0_381] …

调用百度的大模型API接口实现AI对话!手把手教程!

本文介绍如何使用百度的大模型API接口实现一个AI对话项目 1 注册百度云 2 获取API接口 3 配置环境 4 代码编写与运行 5 chat models 1 注册百度云 搜索百度云&#xff0c;打开官网注册&#xff0c;充值一点点大米&#xff08;收费很低&#xff0c;大概生成几个句子花费一毛…

FRP配置内网穿透52版本以上适用

简述 适用frp配置内网穿透来说我们需要进行简单的区分&#xff0c;具有公网IP的服务器我们简称为服务端&#xff0c;内网的服务器我们可以简称为客户端&#xff0c;frp需要针对不同的服务器配置不同的文件 下载安装包 Linux下载地址 https://github.com/fatedier/frp/relea…

好的STEM编程语言有哪些?

STEM是科学&#xff08;Science&#xff09;&#xff0c;技术&#xff08;Technology&#xff09;&#xff0c;工程&#xff08;Engineering&#xff09;&#xff0c;数学&#xff08;Mathematics&#xff09;四门学科英文首字母的缩写&#xff0c;STEM教育简单来说就是在通过在…

如何通过✅ IPIDEA代理IP,轻松实现数据采集和市场拓展工作(下)

如何通过✅ IPIDEA代理IP&#xff0c;轻松实现数据采集和市场拓展工作 如何通过✅ IPIDEA代理IP&#xff0c;轻松实现数据采集和市场拓展工作前言IPIDEA爬虫实战实战Demo演示总结 如何通过✅ IPIDEA代理IP&#xff0c;轻松实现数据采集和市场拓展工作 前言 在当今全球化市场的…

微信小游戏之三消(三)道具相关方法

设计一个 game class。负责了游戏的核心控制逻辑&#xff0c;包括游戏状态管理、方块和道具的生成与效果处理&#xff0c;以及游戏的重新开始和复活流程。通过这些方法&#xff0c;脚本实现了游戏的基本玩法和用户交互。 主要游戏控制方法 gameStart()&#xff1a;开始游戏&am…

MySQL常见指令

MySQL中的数据类型 大致分为五种&#xff1a;数值&#xff0c;日期和时间&#xff0c;字符串&#xff0c;json&#xff0c;空间类型 每种类型也包括也一些不同的子类型&#xff0c;根据需要来选择。 如数值类型包括整数类型和浮点数类型 整数类型根据占用的存储空间的不同 又…

Cocos Creator2D游戏开发(7)-飞机大战(5)-让子弹飞

飞机大战(5)-碰撞及积分 参考敌机的生成 子弹由飞机生成,放在player_node节点子弹重复使用,要使用预制体;子弹新增了动画 ①创建一个预制体 命名为playerBullet_prefab ② 双击预制体将bullet1图片拖入预制体 保存,关闭(场景编辑器里面的) ③ 发射子弹 player加入代码 prop…

听说它可以让代码更优雅

一提到静态代码检查工具这个词应该比较好理解&#xff0c;所谓静态代码检查工具就是检查静态代码的工具&#xff0c;完美~ 言归正传&#xff0c;相信很多程序员朋友都听说过静态代码检查工具这个概念&#xff0c;它可能是我们IDE里的某一个插件&#xff0c;可能是计算机中的一…

RK3588+MIPI+GMSL+AI摄像机:自动车载4/8通道GMSL采集/边缘计算盒解决方案

RK3588作为目前市面能买到的最强国产SOC&#xff0c;有强大的硬件配置。在智能汽车飞速发展&#xff0c;对图像数据矿场要求越来越多的环境下&#xff0c;如何高效采集数据&#xff0c;或者运行AI应用&#xff0c;成为刚需。 推出的4/8通道GMSL采集/边缘计算盒产品满足这些需求…

Spring验证码

前言&#xff1a;使用Hutool 1.什么是Hutool&#xff1f; 2.代码复制到test类中 3.代码爆红&#xff0c;说明需要引入依赖 4.根据名取Maven仓库相关依赖 5.在pom.xml文件中进行配置 6.引入成功 7. 运行程序 打开d盘&#xff0c;发现已经生成了验证码的图片&#xff0c;路径在…

Codeforces Round 654 (Div. 2) C. A Cookie for You (模拟)

我认为这道题就是个脑筋急转弯。 首先我们知道当a b < n m的时候&#xff0c;饼干总数都不够人的总数&#xff0c;那肯定是NO。 并且注意题干&#xff0c;我们可以得知当a b的时候&#xff0c;第一类和第二类人可以任意选两种饼干中的一种。 之后我们可以分类讨论一下。 …

网格布局 HTML CSS grid layout demo

文章目录 页面效果代码 (HTML CSS)参考 页面效果 代码 (HTML CSS) <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"…

[ BLE4.0 ] 伦茨ST17H66开发-串口UART0的接收与发送

目录 一、前言 二、实现步骤 1.设置回调函数 2.关闭睡眠模式 三、效果展示 四、工程源代码 一、前言 串口通信在任何一款单片机开发中都是尤为重要的。本文涉及的开发所使用的例程依然是基于[ BLE4.0 ] 伦茨ST17H66开发-OSAL系统中添加自己的Task任务文章的工程源码&#x…

windows@powershell@任务计划@自动任务计划@taskschd.msc.md

文章目录 使用任务计划windows中的任务计划任务计划命令行程序开发windows 应用中相关api传统图形界面FAQ schtasks 命令常见用法创建计划任务删除计划任务查询计划任务修改计划任务运行计划任务 PowerShell ScheduledTasks常用 cmdlet 简介1. Get-ScheduledTask2. Register-Sc…

Git远程仓库推送

这里我只连接了两个站点的远程仓库&#xff0c;一个是国内的Gitee&#xff0c;另一个是Github&#xff0c;这两个站点的连接方式主要有两种&#xff0c;第一种就是通过https来连接远程仓库&#xff0c;另一种是通过ssh公钥来连接&#xff0c;这两个站点练接的大致过程都是一样的…

我出一道面试题,看看你能拿 3k 还是 30k!

大家好&#xff0c;我是程序员鱼皮。欢迎屏幕前的各位来到今天的模拟面试现场&#xff0c;接下来我会出一道经典的后端面试题&#xff0c;你只需要进行 4 个简单的选择&#xff0c;就能判断出来你的水平是新手&#xff08;3k&#xff09;、初级&#xff08;10k&#xff09;、中…

4 款最佳 C# 无头浏览器

摘要&#xff1a; 在当今大数据时代&#xff0c;高效的数据采集成为众多项目的关键一环。对于偏好C#语言的开发者而言&#xff0c;无头浏览器是实现网页自动化交互、数据抓取的强大工具。本文将深入探讨四款顶尖的C#无头浏览器库&#xff0c;分析它们的特性和应用场景&#xf…

怎么把C盘分成两个盘?让C盘分区更简单,赶快试试!

在日常使用电脑的过程中&#xff0c;有时我们可能希望将C盘分割成两个独立的分区&#xff0c;以便更好地管理文件和数据。这种操作需要谨慎进行&#xff0c;因为错误的分区操作可能导致数据丢失。那么&#xff0c;我们该怎么把C盘分成两个盘呢&#xff1f;下面&#xff0c;我将…

lua 游戏架构 之 游戏 AI (六)ai_auto_skill

定义一个为ai_auto_skill的类&#xff0c;继承自ai_base类。ai_auto_skill类的目的是在AI自动战斗模式下&#xff0c;根据配置和条件自动选择并使用技能。 lua 游戏架构 之 游戏 AI &#xff08;一&#xff09;ai_base-CSDN博客文章浏览阅读379次。定义了一套接口和属性&#…