【算法——双指针】

922. 按奇偶排序数组 II

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

main:vector<int>nums = { 3,1,2,4 };int i = 0, j = 1;int n = nums.size() - 1;while (j < nums.size() && i < nums.size())   //如果奇偶任一方排好了,另一方自然排好了{//判断最后一个元素奇偶if (nums[n] % 2 != 0) {swap(nums[j], nums[n]);    j += 2;  //来到下一个奇数位置}else {swap(nums[i], nums[n]);i += 2;  //来到下一个偶数位置}}

287. 寻找重复数

快慢指针

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

main:vector<int>nums = {}; int slow = nums[0];int fast = nums[nums[0]];while (slow != fast)     //一开始快指针一次2步,慢指针一次1步{fast = nums[nums[fast]];slow = nums[slow];}fast = 0;    //二者第一次相遇后,快指针重置为初始位置while (slow != fast)     //快慢都一次一步{fast = nums[fast];slow = nums[slow];}//最后返回fast和slow都可以

42. 接雨水

算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili

思想:每个格子上方的水量进行累加,首先求这个格子左边的最大格子和右边的最大值。

如果左边比右边小,那么左边就是一个兜底,我当前格子装水量就是左减当前格子数。

右比左小同理,右边就是兜底。

总结:

	min(left_max, max_right)-nums[i]
特例:当前格子数比左右都大,就直接为0,这时候没有人兜底了
最终式子:max(min(left_max, max_right)-nums[i],0)

两侧最大值怎么求? 

mainvector<int>nums = { 0,1,0,2,1,0,1,3,2,1,2,1 };int n = nums.size();vector<int>lmax(n);lmax[0] = nums[0];for (int i = 1; i < n; i++)        //左侧最大值不断继承lmax[i] = max(nums[i], lmax[i - 1]);vector<int>rmax(n);rmax[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0 ; i--)   //右侧最大值不断继承rmax[i] = max(nums[i], rmax[i + 1]);int sum = 0;for (int i = 1; i < n - 1; i++)     //计算sum += max(min(lmax[i - 1], rmax[i + 1]) - nums[i], 0);cout << sum;

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

计算机毕业设计之:基于微信小程序的校园流浪猫收养系统(源码+文档+讲解)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

「漏洞复现」灵当CRM marketing/index.php SQL注入漏洞

0x01 免责声明 请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;作者不为此承担任何责任。工具来自网络&#xff0c;安全性自测&#xff0c;如有侵权请联系删…

如何使用ssm实现社区流浪动物救助领养系统的设计与开发+vue

TOC ssm666社区流浪动物救助领养系统的设计与开发vue 第一章 课题背景及研究内容 1.1 课题背景 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的信息管理看到了革命性的曙光&#xff0c;因为传统信息管理从时效性&#xff0c;还是安…

Python编码系列—Python策略模式:灵活应对变化的算法策略

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

微软AI核电计划

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

Django学习实战篇六(适合略有基础的新手小白学习)(从0开发项目)

前言&#xff1a; 上一章中&#xff0c;我们完成了页面样式的配置&#xff0c;让之前简陋的页面变得漂亮了些。 整理一下目前已经完成的系统&#xff0c;从界面上看&#xff0c;已经完成了以下页面: 首页分类列表页标签列表页口博文详情页 这离我们的需求还有些距离&#xff0…

Python | Leetcode Python题解之第423题从英文中重建数字

题目&#xff1a; 题解&#xff1a; class Solution:def originalDigits(self, s: str) -> str:c Counter(s)cnt [0] * 10cnt[0] c["z"]cnt[2] c["w"]cnt[4] c["u"]cnt[6] c["x"]cnt[8] c["g"]cnt[3] c["h…

【完整梳理验证】企业微信第三方应用接入全流程java版

企业微信第三方应用接入全流程java版 1. 概念与流程1.1 概念1、企业内部应用2、`第三方应用`3、代开发自建应用1.2 流程1.2.1 全局流程1.2.2 应用配置1.2.3 数据流程2. 核心文档2.1 理解第三方应用开发流程和概念2.1.1 应用开发阶段2.1.2 应用推广阶段2.1.3 基本流程1)前期应用…

C++ | Leetcode C++题解之第421题数组中两个数的最大异或值

题目&#xff1a; 题解&#xff1a; struct Trie {// 左子树指向表示 0 的子节点Trie* left nullptr;// 右子树指向表示 1 的子节点Trie* right nullptr;Trie() {} };class Solution { private:// 字典树的根节点Trie* root new Trie();// 最高位的二进制位编号为 30static…

leetcode第十题:正则表达式匹配

给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个前面的那一个元素 所谓匹配&#xff0c;是要涵盖 整个 字符串 s 的&#xff0c;而不是部分字符串。 示例 1&#xff1a; 输入&#xff1a;s…

TMS320F28335的定时器中断实验

TTMS320F28335 的 CPU 定时器有 3 个且均为 32 位,分别是 Timer0、Timer1、Timer2, 其中 Timer2 是为操作系统 DSP/BIOS 保留的,当未移植操作系统时,可用来做普 通的定时器。这三个定时器的中断信号分别为 TINT0,TINT1,TINT2,分别对应中断向量于 INT1,INT13,INT14。 1 …

使用 NCache 将 Java 微服务扩展到极致性能

微服务已成为软件开发领域的一种变革性架构方法&#xff0c;提供了从整体结构到更加模块化和可扩展的系统的范式转变。微服务的核心是将复杂的应用程序分解为更小的、可独立部署的服务&#xff0c;这些服务可以无缝通信&#xff0c;从而提高敏捷性、灵活性和易维护性。这种分散…

动态规划day38|322. 零钱兑换(背包满了吗?最小值怎么表示?)、279. 完全平方数、139. 单词拆分、多重背包要点、背包问题大总结

动态规划day38|322. 零钱兑换&#xff08;背包满了吗&#xff1f;最小值怎么表示&#xff1f;&#xff09;、279. 完全平方数、139. 单词拆分、多重背包要点、背包问题大总结 322. 零钱兑换279. 完全平方数139. 单词拆分多重背包要点背包问题大总结 322. 零钱兑换 给你一个整数…

后端-项目创建与sql

1.创建文件 1.在webcontent下创建.html文件 2. 在java resources下创建包&#xff0c;右键包创建servlet服务生.(要是创建普通的类&#xff0c;里面的注解里的东西不能重复&#xff09; 注意&#xff1a;class的名字要和文件名一样&#xff0c;注解里的servlet是独一无二的。 …

最新 idea 2024 入门使用详细教程

IntelliJ IDEA&#xff1a;这是一款由JetBrains公司开发的Java集成开发环境&#xff08;Integrated Development Environment&#xff09;&#xff0c;被广泛认为是目前Java开发者最好的集成开发工具之一。它支持Java、Groovy、Kotlin等多种编程语言&#xff0c;并且提供了丰富…

HCIA--实验十七:EASY IP的NAT实现

一、实验内容 1.需求/要求&#xff1a; 通过一台PC&#xff0c;一台交换机&#xff0c;两台路由器来成功实现内网访问外网。理解NAT的转换机制。 二、实验过程 1.拓扑图&#xff1a; 2.步骤&#xff1a; 1.PC1配置ip地址及网关&#xff1a; 2.AR1接口配置ip地址&#xff1…

Java免税商品优选商城:Spring Boot实战

第二章 系统开发关键技术 2.1 JAVA技术 Java主要采用CORBA技术和安全模型&#xff0c;可以在互联网应用的数据保护。它还提供了对EJB&#xff08;Enterrise JavaBeans&#xff09;的全面支持&#xff0c;java servlet AI&#xff0c;JS&#xff08;java server ages&#xff09…

Tomcat中BIO和NIO的区别(Tomcat)

BIO Tomcat中BIO的模型和理论很简单&#xff0c;例图如下 1.Acceptor线程死循环阻塞接收客户端的打过来的socket请求 2.接收到请求之后打包成一个SocketProcessor&#xff08;Runnable&#xff09;&#xff0c;扔到线程池中读取/写入数据 参数配置 1.Acceptor默认线程是1&#…

2024年1月Java项目开发指南17:自动接口文档配置

Knife4j 文档 &#xff1a;https://doc.xiaominfo.com/ 有能力的建议自己去看文档配置&#xff0c;本文仅做参考&#xff0c;因为官方文档会更新&#xff0c;本文不会&#xff0c;以后说不定本文就过时了。 ok&#xff0c;我们继续。虽然本文是2024年1月Java项目开发指南17&…

JVM面试题-说一下JVM主要组成部分及其作用

总体来说&#xff0c;方法区和堆是所有线程共享的内存区域&#xff1b;而虚拟机栈、本地方法栈和程序计数器的运行是线程私有的内存区域&#xff0c;运行时数据区域就是我们常说的JVM的内存。 类加载子系统&#xff1a;根据给定的全限定名类名(如&#xff1a;java.lang.Object…