春招冲刺百题计划|双指针

Java基础复习

  1. Java数组的声明与初始化
  2. Java ArrayList
  3. Java HashMap
  4. Java String 类
  5. Java LinkedList
  6. Java Deque继承LinkedList
  7. Java Set
  8. Java 队列
  9. 优先队列:第二题用到了
  10. Java数组划分
  11. Java数组转ArrayList
  12. String 转数字
  13. String

这一部分,代码随想录写得超级好!(快慢指针)

第一题:26. 删除有序数组中的重复项在这里插入图片描述

class Solution {
    public int removeDuplicates(int[] nums) {
        // 快慢指针:慢指针负责确定位置,快指针负责寻找元素
        int slow = 0;
        for(int fast=0; fast<nums.length; fast++){
            if(nums[slow]!=nums[fast]){
                nums[++slow] = nums[fast];
            }
        }
        return slow+1;
    }
}

第二题:31. 下一个排列在这里插入图片描述

这题解出来,全凭能不能琢磨出来规律。个人觉得还是很复杂的。
给定一个数组,除非是降序的(最大的排列了),就直接反转。
其他情况,要按照以下步骤来执行:
1.从尾部开始查找,找到第一个下降的点a[i]
2.从尾部开始查找,找到最后一个满足a[j]>a[i]的点a[j],交换两者。
3.翻转a[i+1:n-1]。

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length, k = n - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) swap(nums, l++, r--);
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

但是,这题和双指针有什么关系呢?

第三题:88. 合并两个有序数组

在这里插入图片描述

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n==0){
            return;
        }
        if(m==0){
            for(int i=m; i<n+m; i++){
                nums1[i] = nums2[i-m];
            }
        }
        int p1=m-1, p2=n-1, p3=n+m-1;
        while(p1>=0&&p2>=0){
            if(nums1[p1]>nums2[p2]){
                nums1[p3--] = nums1[p1--];
            }else{
                nums1[p3--] = nums2[p2--];
            }
        }
        if(p1>=0){
            for(int i=p3; i>=0; i--){
                nums1[i] = nums1[p1--];
            }
        }else{
            for(int i=p3; i>=0; i--){
                nums1[i] = nums2[p2--];
            }
        }
        

    }
}

从后往前。如果从前往后会遇到nums1的元素被覆盖的问题,要是再来一个数组存储的话,还不如直接建一个sorted数组。因此,从后往前,保证nums1的元素不被覆盖。

第四题:189. 轮转数组

在这里插入图片描述
有一个额外的数组来辅助是最简单的,难点就在于如何原地轮转。
以下是额外数组的做法:

class Solution {
    public void rotate(int[] nums, int k) {
        //最简单就是额外来一个数组,就非常简单。
        int[] results = new int[nums.length];
        k = k%nums.length;
        for(int i=0; i<nums.length; i++){
            results[(i+k)%nums.length] = nums[i];//向右k,就是向左n-k。
        }
        for(int i=0; i<nums.length; i++){
            nums[i] = results[i];
        }
    }
}

翻转一下!(这一题,还有一个推导的解法用到了指针的概念,但是!你怎么能放在双指针章节迷惑人!!!)
在这里插入图片描述

class Solution {
    //官方题解:找规律,能够环状替换,要数学推导,不管了。
    //官方题解2:数组翻转(好像经常遇到。)
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }

}

第五题:165. 比较版本号

在这里插入图片描述

class Solution {
    public int compareVersion(String version1, String version2) {
        //先划分开来
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");

        //转成数字,并对齐长度
        ArrayList<Integer> al1 = new ArrayList<>();
        ArrayList<Integer> al2 = new ArrayList<>();

        for(int i=0; i<v1.length; i++){
            al1.add(Integer.parseInt(v1[i]));
        }
        for(int i=0; i<v2.length; i++){
            al2.add(Integer.parseInt(v2[i]));//String 如何转数字
        }
        int n = Math.max(v1.length, v2.length);
        while(al1.size()<n) al1.add(0);
        while(al2.size()<n) al2.add(0);
        //比较
        for(int i=0; i<n; i++){
            if(al1.get(i)>al2.get(i)){
                return 1;
            }
            if(al1.get(i)<al2.get(i)){
                return -1;
            }
        }
        return 0;
        //Arrays.toString(v1)
    }
}

双指针的目的是为了节省空间。个人觉得题解的代码很优雅!

class Solution {
    public int compareVersion(String version1, String version2) {
        int n = version1.length(), m = version2.length();
        int i = 0, j = 0;
        while (i < n || j < m) {
            int x = 0;
            for (; i < n && version1.charAt(i) != '.'; ++i) {
                x = x * 10 + version1.charAt(i) - '0';
            }
            ++i; // 跳过点号
            int y = 0;
            for (; j < m && version2.charAt(j) != '.'; ++j) {
                y = y * 10 + version2.charAt(j) - '0';
            }
            ++j; // 跳过点号
            if (x != y) {
                return x > y ? 1 : -1;
            }
        }
        return 0;
    }
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/compare-version-numbers/solutions/970416/bi-jiao-ban-ben-hao-by-leetcode-solution-k6wi/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

第六题:125. 验证回文串

算是超经典题目了。
在这里插入图片描述

class Solution {
    public boolean isPalindrome(String s) {
        if(s.length()==0){
            return true;
        }
        //还要先处理。
        s = s.toLowerCase();
        int l=0, r=s.length()-1;
        while(l<s.length()&&(s.charAt(l)>'z'||s.charAt(l)<'a')&&(s.charAt(l)>'9'||s.charAt(l)<'0')) l++;
        while(r>=0&&(s.charAt(r)>'z'||s.charAt(r)<'a')&&(s.charAt(r)>'9'||s.charAt(r)<'0')) r--;
        while(l<r){
            System.out.println(s.charAt(l) + " " + s.charAt(r));
            if(s.charAt(l)!=s.charAt(r)){
                return false;
            }
            l++;
            r--;
            while(l<s.length()&&(s.charAt(l)>'z'||s.charAt(l)<'a')&&(s.charAt(l)>'9'||s.charAt(l)<'0')) l++;
            while(r>=0&&(s.charAt(r)>'z'||s.charAt(r)<'a')&&(s.charAt(r)>'9'||s.charAt(r)<'0')) r--;
        }
        return true;
    }
}

第七题:295. 数据流的中位数

在这里插入图片描述
难度在于插入后排序,取出中位数定位。

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

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

相关文章

LabVIEW阀门运动PCT测试

开发了一套基于LabVIEW的阀门运动PCT&#xff08;Pressure-Composition-Temperature&#xff09;测试方法。该系统通过控制阀门运动&#xff0c;实现对氢气吸附和解吸过程的精确测量和控制。所用硬件包括NI cDAQ-9174数据采集模块、Omega PX309压力传感器、SMC ITV2030电动调节…

【java算法专场】滑动窗口(下)

目录 水果成篮 算法分析 算法步骤 示例 算法代码 找到字符串中所有字母异位词 算法分析 算法步骤 示例 算法代码 优化 算法代码 串联所有单词的子串 算法分析 算法步骤 示例 算法代码 最小覆盖子串 算法分析 算法步骤 示例 算法代码 算法分析 这道题其实…

Python数据分析案例52——基于SSA-LSTM的风速预测(麻雀优化)

案例背景 又要开始更新时间序列水论文的系列的方法了&#xff0c;前面基于各种不同神经网络层&#xff0c;还有注意力机制做了一些缝合模型。 其实论文里面用的多的可能是优化算法和模态分解&#xff0c;这两个我还没出专门的例子&#xff0c;这几天正好出一个优化算法的例子来…

go-高效处理应用程序数据

一、背景 大型的应用程序为了后期的排障、运营等&#xff0c;会将一些请求、日志、性能指标等数据保存到存储系统中。为了满足这些需求&#xff0c;我们需要进行数据采集&#xff0c;将数据高效的传输到存储系统 二、问题 采集服务仅仅针对某个需求开发&#xff0c;需要修改…

树莓派pico入坑笔记,esp01/01s使用

目录 关于树莓派pico和circuitpython的更多玩法&#xff0c;请看树莓派pico专栏 说明 关于at指令 WiFi的at指令 UDP的at指令 样例程序 调试助手端输入指令 sta端程序 效果 进阶使用 库函数说明 样例代码 关于树莓派pico和circuitpython的更多玩法&#xff0c;请看树…

TensorFlow系列:第四讲:MobileNetV2实战

一. 加载数据集 编写工具类&#xff0c;实现数据集的加载 import keras""" 加载数据集工具类 """class DatasetLoader:def __init__(self, path_url, image_size(224, 224), batch_size32, class_modecategorical):self.path_url path_urlself…

H5的Canvas如何画N叉树数据结构

大家好。我是猿码叔叔&#xff0c;一位有着 5 年Java工作经验的北漂&#xff0c;业余时间喜欢瞎捣鼓&#xff0c;学习一些新东西来丰富自己。看过上一篇 Java 方法调用关系的老铁们&#xff0c;也许遗留了不少疑问&#xff0c;这Java方法调用关系可视化页面就这&#xff1f;这方…

护网HW面试——redis利用方式即复现

参考&#xff1a;https://xz.aliyun.com/t/13071 面试中经常会问到ssrf的打法&#xff0c;讲到ssrf那么就会讲到配合打内网的redis&#xff0c;本篇就介绍redis的打法。 未授权 原理&#xff1a; Redis默认情况下&#xff0c;会绑定在0.0.0.0:6379&#xff0c;如果没有采用相关…

基于SpringBoot的校园志愿者管理系统

你好呀&#xff0c;我是计算机学姐码农小野&#xff01;如果有相关需求&#xff0c;可以私信联系我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot框架 工具&#xff1a;MyEclipse、Tomcat 系统展示 首页 个人中心 志愿者管理 活动信息…

黑马头条微服务学习day01-环境搭建、SpringCloud微服务(注册发现、网关)

文章目录 项目介绍环境搭建项目背景业务功能技术栈说明 nacos服务器环境准备nacos安装 初始工程搭建环境准备主体结构 app登录需求分析表结构分析手动加密微服务搭建接口定义功能实现登录功能实现 Swagger使用app端网关nginx配置 项目介绍 环境搭建 项目背景 业务功能 技术栈说…

数据结构(Java):树二叉树

目录 1、树型结构 1.1 树的概念 1.2 如何判断树与非树 1.3 树的相关概念 1.4 树的表示形式 1.4.1 孩子兄弟表示法 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树的存储 2.5 二叉树的遍历 1、树型结构 1.1 树的概念 树型结构是一种非线…

MySQL复合查询(重点)

前面我们讲解的mysql表的查询都是对一张表进行查询&#xff0c;在实际开发中这远远不够。 基本查询回顾 查询工资高于500或岗位为MANAGER的雇员&#xff0c;同时还要满足他们的姓名首字母为大写的J mysql> select * from emp where (sal>500 or jobMANAGER) and ename l…

数据湖仓一体(一) 编译hudi

目录 一、大数据组件版本信息 二、数据湖仓架构 三、数据湖仓组件部署规划 四、编译hudi 一、大数据组件版本信息 hudi-0.14.1zookeeper-3.5.7seatunnel-2.3.4kafka_2.12-3.5.2hadoop-3.3.5mysql-5.7.28apache-hive-3.1.3spark-3.3.1flink-1.17.2apache-dolphinscheduler-3.1.9…

[Vulnhub] Sedna BuilderEngine-CMS+Kernel权限提升

信息收集 IP AddressOpening Ports192.168.8.104TCP:22, 53, 80, 110, 111, 139, 143, 445, 993, 995, 8080, 55679 $ nmap -p- 192.168.8.104 --min-rate 1000 -sC -sV PORT STATE SERVICE VERSION 22/tcp open ssh OpenSSH 6.6.1p1 Ubuntu 2ubuntu2 …

C++20中的consteval说明符

在C20中&#xff0c;立即函数(immediate function)是指每次调用该函数都会直接或间接产生编译时常量表达式(constant expression)的函数。这些函数在其返回类型前使用consteval关键字进行声明。 立即函数是constexpr函数&#xff0c;具体情况取决于其要求。与constexpr相同&…

半小时获得一张ESG入门证书【详细中英文笔记一】

前些日子&#xff0c;有朋友转发了一则小红书的笔记给我&#xff0c; 标题是《半小时获CFI官方高颜值免费证书 ESG认证》。这对考证狂魔的我来说&#xff0c;必然不能错过啊&#xff0c;有免费的羊毛不薅白不薅。 ESG课程的 CFI 官方网址戳这里&#xff1a;CFI 于是信心满满的…

清华大学孙富春教授团队开发了多模态数字孪生环境,辅助机器人获得复杂的 3C 装配技能

中国是全球3C产品&#xff08;电脑、通信和消费电子&#xff09;的主要生产国&#xff0c;全球70%的3C产品产能集中在中国。3C智能制造装备的突破与产业化&#xff0c;对于提升我国制造产业的全球竞争力意义重大。 机器人在计算机、通信和消费电子 &#xff08;3C&#xff09; …

常用的设计模式和使用案例汇总

常用的设计模式和使用案例汇总 【一】常用的设计模式介绍【1】设计模式分类【2】软件设计七大原则(OOP原则) 【二】单例模式【1】介绍【2】饿汉式单例【3】懒汉式单例【4】静态内部类单例【5】枚举&#xff08;懒汉式&#xff09; 【三】工厂方法模式【1】简单工厂模式&#xf…

springboot 程序运行一段时间后收不到redis订阅的消息

springboot 程序运行一段时间后收不到redis订阅的消息 问题描述 程序启动后redis.user.two主题正常是可以收到消息的&#xff0c;发一条收一条&#xff0c;但是隔一段时间后&#xff1b;就收不到消息了&#xff1b; 此时如果你手动调用发送另外一个消息订阅redis.user.two2&…