java基础-双指针算法

简介: java基础-双指针算法

前言


小伙伴们,你们好呀!我是老寇!


双指针算法是基于暴力解法的优化,将时间复杂度降低到线性。


双指针算法与其说是一种算法,不如说是一种技巧,它能够缩短循环遍历的时间,提高程序的运行速度!


双指针分为两类,快慢指针和左右指针:


1.快慢指针(弗洛伊德循环查找算法),类似龟兔赛跑。


2.左右指针又称指针碰撞,就是一左一右遍历。


注:多练习,印象才更深刻


正文


快慢指针


快乐数


333.png


class Solution {
    public boolean isHappy(int n) {
      int slow = n,fast = n;
      do{
        slow = bitSquareSum(slow);
        fast = bitSquareSum(fast);
        fast = bitSquareSum(fast);
      }
      while(slow != fast);
      return (slow == 1);
    }
    private int bitSquareSum(int x) {
      int sum = 0,cur;
      while(x > 0) {
        cur = x % 10;
        x = x / 10;
        sum += cur * cur;
      }
      return sum;
    }
}


333.png



结论:较哈希集,指针只需要常数的额外空间


删除有序数组中的重复项


333.png


class Solution {
    public int removeDuplicates(int[] nums) {
      int len = nums.length;
      if(len < 2) {
        return len;
      }
      int j = 0;
      for(int i = 0; i < len; i++) {
        if(nums[j] != nums[i]) {
          nums[++j] = nums[i];
        }
      }
      return j + 1;
    }
}


111.png


结论:找对「循环不变量」是做题的关键,我理解的循环遍历是一个if条件,在本题中nums[j]是慢指针,负责数据的替换,nums[i]是快指针,负责数据的遍历。


左右指针


反转字符串


222.png


class Solution {
    public void reverseString(char[] s) {
      int left = 0,right = s.length - 1;
      char c;
      while(left < right) {
        c = s[left];
        s[left] = s[right];
        s[right] = c;
        left++;right--;
      }
    }
}


111.png


结论:较套用两层for循环,所要的时间快一点


双指针范式(作者总结)


//举栗子 数组n1,n2
//1.排序
Arrays.sort(n1);
Arrays.sort(n2);
//数组索引从0开始
int index = 0,index1 = 0,index2 = 0;
//开辟数组
int len1 = n1.length,len2 = n2.length;
int[] arr = new int[Math.min(n1,n2)];
//指针动起来
while(index1 < len1 && index2 < len2) {
   if(两个值相等) {
      index1++;
      index2++;
      arr[index++] = 其中一个值
   } else if (第一个值大) {
     index2++;
   } else {
     //第二个值大
     index1++;
    }
}
//谁小谁加+1


相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
65 3
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
169 58
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
20 0
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
160 15
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
73 3
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问