[Java][算法 双指针]Day 02---LeetCode 热题 100---04~07

LeetCode 热题 100---04~07

第一题:移动零

思路

找到每一个为0的元素 然后移到数组的最后  但是需要注意的是  要在给定的数组原地进行修改  并且其他非零元素的相对顺序不能改变  我们采用双指针法

定义两个指针i和j  i和j一开始分别都在0索引位置  然后判断j所在位置元素数值  如果等于0 则往下走一位 反之 则将数值赋值到i位置 j和i同时向下走一位

这样子 i总在j后面  j所到的非零元素 都会按照相对顺序依次赋值到i的位置  当j走到重点  i必然还没走到重点(除非整个数组没有0元素) 此时j会停止 而其他非零元素已经全部到达i的前方位置

接下来只需要遍历一遍i~j  将这部分的元素置零即可  大致过程如下(最后将两箭头之间的元素置零即可)

第二题:盛最多水的容器

解法一  暴力法(超时)

最简单直接的方法就是双重for嵌套  依次遍历 两两求体积 最后取最大值即可

思路是可行的 但是在数据量大的情况下 时间超时也是没办法的

class Solution {
    public int maxArea(int[] height) {
        if(height.length==1 || height.length==0) return 0;
        int max=0;
        for (int i = 0; i < height.length; i++) {
            for(int j=i+1;j<height.length;j++){
                int v=(j-i)*Math.min(height[i],height[j]);
                if(v>max) max=v;
            }
        }
        return max;
    }
}

解法二 双指针法

首先  我们直到  求两个板子能装水的体积 就是 Min(板A,板B)*AB之间的距离

那么 按照这个思路  我们让AB分别从数组最两端开始 那么可以确定的是我们之后每次都只向内移动变化 那么 AB之间的距离 这个变量就是单调递减的  那么剩下的变化因素就是 Min(板A,板B)

A,B板的移动 都会影响该数值   现在我们来分析 假设我们A板是较短的那块板子

当我们移动A板  即移动短板  A'板的长度可能长于也可能短于A板

如果A'短于A板子 那么Min(A',B)肯定是A'  比Min(A,B)小  AB距离变小 那么整个体积肯定减小

如果A'长于A板子  那么Min(A',B)等于A'或者B(需要看A'和B哪个长)  但是无论如何肯定会比Min(A,B)大  但是AB之间的距离减小 所以最后两者的乘积 体积V的变化情况就不一定了 所以是可能变大 可能变小 可能不变

当我们移动B板  即移动短板  B'板的长度可能长于也可能短于B板

如果B'短于B板子 那么Min(A,B')可能是A也可能是B'   比Min(A,B)小  AB距离变小 那么整个体积肯定减小

如果B'长于B板子  因为短板效应 那么Min(A,B')还是等于A  但是AB之间距离减小 所以体积一定减小

综上  移动长版  体积一定减小  移动短板  体积可能变大

所以 我们双指针可以分别从两端开始  每次移动短的那一块 然后记录出最大体积值即可

class Solution {
    public int maxArea(int[] height) {
        if(height.length==0||height.length==1) return 0;
        int i=0;int v=0;int j=height.length-1;int max=0;
        while(i<j){
            if(height[i]>height[j]){
                v=height[j]*(j-i);
                j--;
            }else{
                v=height[i]*(j-i);
                i++;
            }
            if(v>max) max=v;
        }
        return max;
    }
}

第三题:三数之和

思路

首先是要记得特殊情况直接判断length小于3和数组为null直接范围[]

然后 如果整个数组的最小数都大于0 那么也可以直接返回  所以这就需要我们实现排序

然后对于正常情况  即我们要找到三个数  使其和等于0  最简单直接的 当然是for循环的嵌套 

很容易理解和实现 但是时间复杂度肯定是很大的

为了简化寻找的过程 我们只需要一个循环数 其他的都用固定表达式表示即可

假设我们对数组进行了排序   我们让i从0开始遍历  然后定义变量j=i+1 g=length-1作为双指针  我们在用i遍历的时候  每到一个位置 我们需要在j和g之间遍历找数据

每次计算出nums[i]+nums[j]+nums[g]来判断是否等于0  因为整个数组是有序的 那么我们就可以根据和0的大小比较来直到该如何移动j和g 小于动j  大于动g

(思想类似于[Java][算法 哈希]Day 01---LeetCode 热题 100---01~03-CSDN博客中第一大题的移动思想)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3||nums==null) return new ArrayList<>();
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(nums);
        int i=0;
        for(i=0;i<nums.length;i++){
            // 去重
            if(i>0 && nums[i]==nums[i-1]) continue;
            int j=i+1,g=nums.length-1;
            if(nums[i]>0) break;
            while(j<g){
                int sum=nums[i]+nums[j]+nums[g];
                if(sum==0){
                    list.add(Arrays.asList(nums[i],nums[j],nums[g]));
                     while(j < g && nums[j] == nums[j+1]) {
                        j++;
                    }
                    while(j< g && nums[g] == nums[g-1]){
                        g--;
                    }
                    j++;g--;
                }else if(sum>0){
                    g--;
                }else if(sum<0){
                    j++;
                }
            }
        }
        return list;
    }
}

第四题:接雨水

思路

对于这个题目 我们不应该集中想法去整体求值 而应该去想办法如何单独求出每一个的值 然后相加

对于每一个位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关,我们分别称这两个柱子高度为 l_max 和 r_max位置 i 最大的水柱高度就是 min(l_max, r_max)*height[i]

根据这个思路 我们就知道 需要在遍历的时候  找到该位置的左右两边的最高的柱子  然后又选左右两边最高的中的较小的那个

解法一:暴力法

int trap(int[] height) {
    int n = height.length;
    int res = 0;
    for (int i = 1; i < n - 1; i++) {
        int l_max = 0, r_max = 0;
        // 找右边最高的柱子
        for (int j = i; j < n; j++)
            r_max = Math.max(r_max, height[j]);
        // 找左边最高的柱子
        for (int j = i; j >= 0; j--)
            l_max = Math.max(l_max, height[j]);
        // 如果自己就是最高的话,
        // l_max == r_max == height[i]
        res += Math.min(l_max, r_max) - height[i];
    }
    return res;
}

 解法二:双指针法

我们利用双指针  一个从最左边移动 一个从最右边移动 边走边算的模式 

每次走到一个点 先比较该点数值和历史记录的最大值  用于及时更新最大值

更新完最大值之后 比较两边的最大值  取出较小的那个进行计算 最后再移动小的那个

(因为计算是去小数值的 那么计算完之后代表该次计算完成  只有移动小的才能保证不忽略 不重复)

class Solution {
    int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int l_max = 0, r_max = 0;

        int res = 0;
        while (left < right) {
            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);

            // res += min(l_max, r_max) - height[i]
            if (l_max < r_max) {
                res += l_max - height[left];
                left++;
            } else {
                res += r_max - height[right];
                right--;
            }
        }
        return res;
    }
}

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

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

相关文章

PWM输入输出

PWM&#xff08;Pulse Width Modulation&#xff09;即脉冲宽度调制&#xff0c;在具有惯性的系统中&#xff0c;可以通过对一系列脉冲的宽度进行制&#xff0c;来等效地获得所需要的模拟参量&#xff0c;常应用于电机控速、开关电源等领域。 PWM参数 PWM 中有三个重要参数&…

关于CSDN的原力分增长规则,一点个人经验

本文章编写于 2024年2月9日 从2022年开始到现在&#xff0c;官方的原力分增减规则已经改过好几版了&#xff0c;有一些规则描述比较模糊&#xff0c;这里总结了一些个人经验。 原力值增长点&#xff1a; 1.每日发布文章一篇10分&#xff0c;两篇15分&#xff0c;上限15分&am…

Qt QML学习(一):Qt Quick 与 QML 简介

参考引用 QML和Qt Quick快速入门全面认识 Qt Widgets、QML、Qt Quick 1. Qt Widgets、QML、Qt Quick 区别 1.1 QML 和 Qt Quick 是什么关系&#xff1f; 1.1.1 从概念上区分 QML 是一种用户界面规范和标记语言&#xff0c;它允许开发人员创建高性能、流畅的动画和具有视觉吸引…

Red Panda Dev C++ Maker 使用说明

https://download.csdn.net/download/HappyStarLap/88804678https://download.csdn.net/download/HappyStarLap/88804678 下载https://download.csdn.net/download/HappyStarLap/88804678&#xff1a; ​ 这个&#xff0c;就是我们将运行的文件。 ​ 里面加了许多我…

解决“org.apache.catalina.startup.Catalina.stopServer 未配置关闭端口。通过OS信号关闭服务器。服务器未关闭“

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 问题描述 项目部署至Tomcat服务器报错&#xff1a;org.apache.catalina.startup.Catalina.stopServer 未配置关闭端口。通过OS信号关闭服务 器。服务器未关闭&#xff1b;图…

分享90个行业PPT,总有一款适合您

分享90个行业PPT&#xff0c;总有一款适合您 90个行业PPT下载链接&#xff1a;https://pan.baidu.com/s/1bHvhk_42-IFAjNdjPPtMZw?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集整理更不易…

猫头虎分享已解决Bug || 备份失败(Backup Failures):BackupFailureException, DataBackupError ❌

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

熔断机制解析:如何用Hystrix保障微服务的稳定性

微服务与系统的弹性设计 大家好,我是小黑,在讲Hystrix之前,咱们得先聊聊微服务架构。想象一下,你把一个大型应用拆成一堆小应用,每个都负责一部分功能,这就是微服务。这样做的好处是显而易见的,更新快,容错性强,每个服务可以独立部署,挺美的对吧?但是,问题也随之而…

236. 二叉树的最近公共祖先 - 力扣(LeetCode)

题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以…

uni-app x,一个纯原生的Android App开发工具

uni-app x&#xff0c;下一代uni-app&#xff0c;一个神奇的产品。 用vue语法、uni的组件、api&#xff0c;以及uts语言&#xff0c;编译出了kotlin的app。不再使用js引擎和webview。纯纯的kotlin原生app。 uni-app x&#xff0c;让“跨平台开发性能不如原生”的这条曾广为流…

ad18学习笔记十八:如何放置丝印层敷铜?

我画板的时候&#xff0c;需要把板卡顶面丝印层的一个矩形区域&#xff0c;画成白色&#xff0c;但是这个区域内有好几个焊盘&#xff0c;丝印涂色的地方需要避开这几个焊盘&#xff0c;我觉得不能简单的在丝印层画一个矩形完事&#xff0c;最好让丝印层的这个区域&#xff0c;…

图书系统的Web实现(含源码)

源码地址https://gitee.com/an-indestructible-blade/project 注意事项&#xff1a; BorrowBooksWeb\src\main\resources路径下的application.yml文件里面的url&#xff0c;username&#xff0c;password这三个属性和自己的数据库保持一致。 浏览器访问url:http://127.0.0.1:…

Python环境下基于指数退化模型和LSTM自编码器的轴承剩余寿命预测

滚动轴承是机械设备中关键的零部件之一&#xff0c;其可靠性直接影响了设备的性能&#xff0c;所以对滚动轴承的剩余使用寿命(RUL)进行预测是十分必要的。目前&#xff0c;如何准确地对滚动轴承剩余使用寿命进行预测&#xff0c;仍是一个具有挑战的课题。对滚动轴承剩余寿命评估…

Java项目maven打包的包名设置(finalname标签的使用)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…

如何在 emacs 上开始使用 Tree-Sitter(windows)

文章目录 如何在emacs上开始使用Tree-Sitter&#xff08;windows&#xff09; 如何在emacs上开始使用Tree-Sitter&#xff08;windows&#xff09; 参考&#xff1a;“How to Get Started with Tree-Sitter”。 首先要有一个可运行的emacs&#xff0c;并且它支持Tree-Sitter&…

Django前后端分离之后端实践

django-admin startproject djweb 生成djweb项目 django-admin startapp news 生成news应用 配置models文件 class NewInfo(models.Model):title models.CharField(max_length30)content models.TextField()b_date models.DateField()read models.IntegerFie…

在windows的控制台实现贪吃蛇小游戏

欢迎来到博主的文章 博主id&#xff1a;代码小豪 前言&#xff1a;看懂这篇文章需要具有C语言基础&#xff0c;还要对单链表具有一定的理解。如果你只是想要试玩这个游戏&#xff0c;可以直接在文章末尾找到源码 由于实现贪吃蛇需要调用Win32 API函数&#xff0c;这些函数我会…

PneumoLLM:少样本大模型诊断尘肺病新方法

PneumoLLM&#xff1a;少样本大模型诊断尘肺病新方法 提出背景PneumoLLM 框架效果 提出背景 论文&#xff1a;https://arxiv.org/pdf/2312.03490.pdf 代码&#xff1a;https://github.com/CodeMonsterPHD/PneumoLLM/tree/main 历史问题及其背景&#xff1a; 数据稀缺性问题&a…

大型秒杀中如何减库存?JAVA 架构知识

目前来看&#xff0c;业务系统中最常见的就是预扣库存方案&#xff0c;像你在买机票、买电影票时&#xff0c;下单后一般都有个“有效付款时间”&#xff0c;超过这个时间订单自动释放&#xff0c;这都是典型的预扣库存方案。而具体到秒杀这个场景&#xff0c;应该采用哪种方案…

【leetcode热题100】分隔链表

给你一个链表的头节点 head 和一个特定值 x &#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。 示例 1&#xff1a; 输入&#xff1a;head [1,4,3,2,5,2], x 3 输出&am…