【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
611. 有效三角形的个数
611. 有效三角形的个数
https://leetcode.cn/problems/valid-triangle-number/
题目描述:
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

解题思路:
本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边
题目给我们nums是乱序的,如果我们一个个abc去实验就是会超时(时间复杂度O^3)
当我们将sort排序一下,这样的话假设a<b<c的情况下,我们就只要去判断a+b>c是否成立!
这里我们遍历每个c(从后往前),这样时间复杂度就变成了N^2+NlogN也就是N^2
解题代码:
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//假设a<b<cint num=0;int n=nums.size();for(int i=n-1;i>=2;i--){int left=0;int right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){num+=(right-left);right--;}else{left++;}}}return num;}
};
剑指 Offer 57. 和为s的两个数字
剑指 Offer 57. 和为s的两个数字
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
题目描述:
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

解题思路:
首先本题是升序数组,这里如果我们用暴力的话会超时
这里我们使用双指针,我们让一个指向头left一个指向尾right,这里left、right和target会有三种关系
我们假设sub=right-left
第一种情况很显然直接返回就好了我们来研究一下第二种和第三种情况:
解题代码:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();int left=0;int right=n-1;while(nums[right]>target){right--;}while(left<right){int sub=target-nums[right];if(sub==nums[left]){return {nums[left],nums[right]};}else if(sub>nums[left]){left++;}else//sub<nums[left]{right--;}}return {-1,-1};}
};
相关文章:
【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
611. 有效三角形的个数 611. 有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/ 题目描述: 给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。 解题思路: 本题是一个关于三角形是否能成立…...
通过 kk 创建 k8s 集群和 kubesphere
官方文档:多节点安装 确保从正确的区域下载 KubeKey export KKZONEcn下载 KubeKey curl -sfL https://get-kk.kubesphere.io | VERSIONv3.0.7 sh -为 kk 添加可执行权限: chmod x kk创建 config 文件 KubeSphere 版本:v3.3 支持的 Kuber…...
感觉和身边其他人有差距怎么办?
虽然清楚知识需要靠时间沉淀,但在看到自己做不出来的题别人会做,自己写不出的代码别人会写时还是会感到焦虑怎么办? 你是否也因为自身跟周围人的差距而产生过迷茫,这份迷茫如今是被你克服了还是仍旧让你感到困扰? 下…...
【C语言基础】宏定义的用法详解
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
微服务系列文章之 SpringBoot 最佳实践
Spring Boot 是一种广泛使用且非常流行的企业级高性能框架。 以下是一些最佳实践和一些技巧,我们可以使用它们来改进 Spring Boot 应用程序并使其更加高效。 Spring Boot 的四大核心 1、自动配置 针对很多Spring应用程序和常见的应用功能,Spring Boo…...
C++并发多线程--std::async、std::packaged_task和std::promise的使用
目录 1--std::async的使用 2--std::packaged_task的使用 3--std::promise的使用 1--std::async的使用 std::async用于启动一个异步任务,并返回一个std::future对象;std::future对象里含有异步任务线程入口函数的结果; std::launch::deferr…...
opencv-目标追踪
import argparse import time import cv2 import numpy as np# 配置参数 ap argparse.ArgumentParser() ap.add_argument("-v", "--video", typestr,help"path to input video file") ap.add_argument("-t", "--tracker", …...
【数据结构】 单链表面试题讲解
文章目录 引言反转单链表题目描述示例:题解思路代码实现: 移除链表元素题目描述:示例思路解析: 链表的中间结点题目描述:示例:思路解析代码实现如下: 链表中倒数第k个结点题目描述示例思路解析&…...
C++ string类的模拟实现
模拟实现string类不是为了造一个更好的轮子,而是更加理解string类,从而来掌握string类的使用 string类的接口设计繁多,故而不会全部涵盖到,但是核心的会模拟实现 库中string类是封装在std的命名空间中的,所以在模拟…...
Qt实现简单的漫游器
文章目录 Qt的OpenGL窗口GLSL的实现摄像机类的实现简单的漫游器 Qt的OpenGL窗口 Qt主要是使用QOpenGLWidget来实现opengl的功能。 QOpenGLWidget 提供了三个便捷的虚函数,可以重载,用来重新实现典型的OpenGL任务: paintGL:渲染…...
【c语言】文件操作
朋友们,大家好,今天分享给大家的是文件操作的相关知识,跟着我一起学习吧!! 🎈什么是文件 磁盘上的文件是文件。 但是在程序设计中,我们一般谈的文件有两种:程序文件、数据文件 程序文…...
【Unity】坐标转换经纬度方法(应用篇)
【Unity】坐标转换经纬度方法(应用篇) 解决地图中经纬度坐标转换与unity坐标互转的问题。使用线性变换的方法,理论上可以解决小范围内所以坐标转换的问题。 之前有写过[Unity]坐标转换经纬度方法(原理篇),在实际使用中,…...
element时间选择器el-date-picter使用disabledDate指定禁用的日期
需要的效果 <el-date-pickerclass"selectstyle"v-model"year"value-format"yyyy"type"year":picker-options"disabledCli"placeholder"选择年"> </el-date-picker>data() {return {disabledCli: {/…...
出学校干了 5 年外包,已经废了
如果不是女朋友和我提分手,我估计现在还没醒悟 本科大专,17年通过校招进入某软件公司做测试,干了接近5年的功能。 今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经…...
day-23 代码随想录算法训练营(19)part09
669.修剪二叉搜索树 思路一:根据二叉搜索树的特性进行中间值与去区间值判断,有三种情况:1.在区间中,所以左右子树都可能在区间中; 2.在区间外面的左侧,必然只有右子树可能存在区间中;3.在区间外…...
JVM编译优化
即时编译器 HotSpot虚拟机中内置了两个即时编译器,分别称为Client Compiler和Server Compiler,或者简称为C1编译器和C2编译器。Java8默认开启Server模式。用户可以使用“-client”或“-server”参数去指定编译模式。 C1编译器启动速度快,关注局部简单可靠的优化,比如方法…...
vue浏览器插件安装-各种问题
方法1:vue.js devtolls插件下载 https://blog.csdn.net/qq_55640378/article/details/131553642 下载地址: Tags vuejs/devtools GitHub npm install 或是 cnpm install 遇到的报错 设置淘宝镜像源(推荐使用nrm,这一步是为…...
maven工具-maven的使用-镜像仓库、本地仓、IDEA使用maven
Maven 一、为什么使用maven 添加第三方jar包jar包之间的依赖关系处理jar包之间的冲突获取第三方jar包将项目拆分成多个工程模块实现项目的分布式部署 二、maven简介 Maven项目对象模型(POM),可以通过一小段描述信息来管理项目的构建,报告和文档的…...
Mac鼠标增强工具Smooze Pro
Smooze Pro是一款Mac上的鼠标手势增强工具,可以让用户使用鼠标手势来控制应用程序和系统功能。 它支持多种手势操作,包括单指、双指、三指和四指手势,并且可以自定义每种手势的功能。例如,您可以使用单指向下滑动手势来启动Expos视…...
数据结构-单链表(C语言简单实现)
简介 以顺序结构进行数据存储时,它的特点就是可以用一组任意的存储单元存储数据元素,这组存储单元可以是连续的,也可以是不连续的,这些数据可以存在内存未被占用的任意位置。它也是有缺点的,就是在插入和删除时需要移…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...



