精华内容
下载资源
问答
  • JAVA双指针

    2020-03-31 09:59:07
    双指针主要分为快慢指针和左右指针两种。 快慢指针解决链表含环问题以及相差问题。 左右指针解决数组问题,左=0,右=length-1,二分查找等问题。 快慢指针 1.判断有无环:快指针一步走两个,慢指针一步一个,如果...

    双指针主要分为快慢指针和左右指针两种。
    快慢指针解决链表含环问题以及相差问题。
    左右指针解决数组问题,左=0,右=length-1,二分查找等问题。


    快慢指针


    1.判断有无环:快指针一步走两个,慢指针一步一个,如果有环,最后指针会相遇;如果无环快指针先遇到null;
    2.快慢指针可以寻找链表的中点(左右指针也可以)
    3.相差问题,寻找链表的倒数第k个元素
    快指针先走k步,然后快慢指针同时同速前进,当快指针遇到null时,慢指针到达倒数第k个节点。

    Leetcode

    在这里插入图片描述


    左右指针


    1.二分查找、有序的两数之和、反转数组
    2.快速排序

        private static int partition(int[] array, int left, int right) {
            int key = array[left];
            int index = left;
            while (left < right) {
    
                while (left < right && array[right] <= key) {
                    --right;
                }
    
                while (left < right && array[left] >= key) {
                    ++left;
                }
    
                swap(array, left, right);
            }
            swap(array, right, index);
            return right;
        }
    
        private static void swap(int[] cost, int i, int j) {
            int temp = cost[i];
            cost[i] = cost[j];
            cost[j] = temp;
        }
    
    展开全文
  • java双指针的简单理解

    2019-04-17 17:55:00
    JAVA中并没有像C/C++指针地概念,所以这里所说的双指针是指索引,游标或可迭代对象等。 双指针在链表中也有很多用处,比如前面写到过的找出链表中的倒数第k个结点,就巧妙地利用到了双指针,此外,判断链表中是否...

    一、什么是双指针

    双指针我所理解地是在遍历对象时,不是使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行遍历,从而达到相应的目的。

    在JAVA中并没有像C/C++指针地概念,所以这里所说的双指针是指索引,游标或可迭代对象等。

    双指针在链表中也有很多用处,比如前面写到过的找出链表中的倒数第k个结点,就巧妙地利用到了双指针,此外,判断链表中是否有环也可以使用双指针,设两个快慢指针,让快指针一次移动两步,慢指针一次移动一步,若链表中有环,那么快指针与慢指针一定能够相遇,若两者没有相遇,说明链表中没有环。还有如果要给出链表中的中间的结点,也可以使用快慢指针,让快指针一次移动两步,慢指针一次移动一步,当快指针刚好到达链表的末尾时,慢指针所指向的正好是中间的结点(对于奇数个结点,就是中间中的一个,若是偶数个结点,是中间结点中的后一个,即length / 2);

           由此看出,双指针的思想就是建立两个指针,这两个指针可以使相同方向,一般前进的速度不同或者两者的前进顺序不一致;也可能是相反的方向,通过使用相关的变量控制来达到我们的目的。

    二、例子:

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

    注意:答案中不可以包含重复的三元组。

    例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

    满足要求的三元组集合为:

    [

      [-1, 0, 1],

      [-1, -1, 2]

    ]

     

    1.思路:

    1. 将数组进行排序。
    2. 将三数问题转换成两数问题(构建for循环)。
    3. 对于两数问题使用双指针求解。

    2.代码

    public List<List<Integer>> threeSum(int[] nums) {
               Arrays.sort(nums);
            List<List<Integer>> ls = new ArrayList<>();
     
            for (int i = 0; i < nums.length - 2; i++) {
                if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {  // 跳过可能重复的答案
     
                    int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
                    while (l < r) {
                        if (nums[l] + nums[r] == sum) {
                            ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
                            while (l < r && nums[l] == nums[l + 1]) l++;
                            while (l < r && nums[r] == nums[r - 1]) r--;
                            l++;
                            r--;
                        } else if (nums[l] + nums[r] < sum) {
                            while (l < r && nums[l] == nums[l + 1]) l++;   // 跳过重复值
                            l++;
                        } else {
                            while (l < r && nums[r] == nums[r - 1]) r--;
                            r--;
                        }
                    }
                }
            }
            return ls;
        }

     

    转载于:https://www.cnblogs.com/xiaobaidashu/p/10725175.html

    展开全文
  • 算法学习之双指针(java版)

    千次阅读 2020-07-10 21:29:44
    算法学习之双指针(java版) 数组或字符串相关的问题经常需要运用双指针来求解。而双指针又分为快慢指针和左右指针。其中快慢指针主要用于解决链表问题,而左右指针用于解决数组问题。 概念 快慢指针 顾名思义,快慢...

    算法学习之双指针(java版)

    数组或字符串相关的问题经常需要运用双指针来求解。而双指针又分为快慢指针和左右指针。其中快慢指针主要用于解决链表问题,而左右指针用于解决数组问题。

    概念

    快慢指针

    顾名思义,快慢指针是指一个指针走的快,一个指针走得慢。

    左右指针

    左右指针是指双指针中一个指针在数组的最左侧,而另一个在最右侧。通过判断,可以分别让两侧的指针向中间移动,以求解问题。

    例题

    判断链表是否有环(快慢指针)

    思路:快指针每次走两步,慢指针每次走一步。如果链表中存在环,总有那么一个时刻快指针比慢指针多走了一圈,此时他们相遇。

    boolean hasCycle(ListNode head){
      ListNode fast, slow;
      fast = slow = head;
      while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow == fast){
          return true;
        }
      }
      return false;
    }
    

    判断链表是否有环并返回其实位置(快慢指针)

    思路:快指针是慢指针的两倍速度,当相遇时,慢指针走了k步,快指针走了2k步,其中k就是一圈的长度。假设相遇点距离环起点距离为m,那么k-m是起点到head的距离。当slow从起点走k-m步,fast继续走k-m步时,fast指针走了3k-m步,正好处于起点位置,slow也在起点位置,两者相遇。
    图片来自labuladong
    [图片来自labuladong的算法小抄]

    ListNode detectCycle(ListNode head){
    	ListNode slow, fast;
    	slow = fast = head;
    	while(fast != null && fast.next != null){
    		fast = fast.next.next;
    		slow = slow.next;
    		if(slow == fast) break;
    	}
    	slow = head;
    	while(slow!=fast){
    		slow = slow.next;
    		fast = fast.next;
    	}
    	return slow;
    }
    

    两数之和(左右指针)

    给定一个按升序排列的有序数组,找到两个数使得它们相加之和等于目标数
    输入:nums=[2, 7, 11, 15], target = 9
    输出: [1, 2]

    思路:这题用到左右指针。初始化left=0, right=nums.length,当nums[left]+nums[right]>target时,right指针向左移动,减小两数之和。相反的情况时,left指针向右移动,增加两数之和。

    int[] twoSum(int[] nums, int target){
      int len = nums.length;
      int left = 0, right = len-1;
      while(left<right){
        if(nums[left]+nums[right]==target){
          return new int[]{left+1,right+1};
        }else if(nums[left]+nums[right]<target){
          left++;
        }else{
          right--;
        }
      }
      return new int[]{-1, -1};
    }
    

    总结

    双指针的精髓就是左右指针的不同节奏移动,根据不同的条件对不同的指针进行操作。

    申明:本博文是看了labuladong的算法小抄之后个人的理解以及总结。

    展开全文
  • github:https://github.com/xiaozhengwei/Algorithms-And-DataStructure class Solution { public void reverseString(char[] s) { int length = s.length; if (length <...

    github:https://github.com/xiaozhengwei/Algorithms-And-DataStructure

    class Solution {
    
       public void reverseString(char[] s) {
            
            int length = s.length;
            
            if (length <= 1) {
                return;
            }
            
            for (int start = 0,end = s.length - 1; start < end; start++, end--) {
                char c = s[end];
                s[end] = s[start];
                s[start] = c;
            }
    
        }
    
    }

     

    展开全文
  • 双指针技巧 一 双指针技巧 —— 情景一 问题:反转数组中的元素。 分析:其思想是将第一个元素与末尾进行交换,再向前移动到下一个元素,并不断地交换,直到它到达中间位置。我们可以同时使用两个指针来完成迭代:...
  • 方法一,先排序再比较 按字符串长度从小到大排序,然后再用双指针法,指针j指向的字符串与指针i指向的字符串进行contains判断,如果包含, 则将指针i指向的字符串添加到集合中,break本次内循环,跳到外循环继续...
  • leetcode删除有序数组中的重复项,Java双指针解法。
  • 洛谷P1147题题解,Java语言描述
  • 题目 给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以 通过删除给定字符串的某些字符来得到。...看解析前,先看看java中是如何判断字符串的字典序列的: 使用 String.compareTo 方法:
  • 双指针,start指针记录子串的开始,end指针记录子串的结尾。 2.end指针遍历整个字符串,将字符串和下标放在HashMap中。在遍历过程中记录并更新 子串的长度。 3.end指针遍历的时候,如果end指针指向的地址的值在...
  • import java.util.Arrays; public class qucik_sort { public static void main(String[] args) { // TODO Auto-generated method stub int[] scores={5,4,6,3,7,2,8,1,9,10}; int[] scores1={4,2,3}; /...
  • JAVA双向链表反转实现

    2018-06-10 06:25:14
    通过java实现的双向链表,及反转功能,可能对面试有用哦
  • Java生成密钥的实例 1个目标文件 摘要:Java源码,算法相关,密钥 Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生钥的密钥对(keyPair)、如何保存公钥的字节数组、...
  • 关于双指针/滑动窗口的理解 一句话: 双指针/滑动窗口 比 遍历 节省了时间,删去了不需要遍历的数据 参考 剑指offer<和为S的连续正数序列>
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    本人从事Java开发已多年,平时有记录问题解决方案和总结知识点的习惯,整理了一些有关Java的知识体系,这不是最终版,会不定期的更新。也算是记录自己在从事编程工作的成长足迹,通过博客可以促进博主与阅读者的共同...
  • Two Sum(初谈双指针

    千次阅读 2016-04-10 12:59:21
    昨天晚上遇到这么一个题目,然后听到了关于“双指针”的使用。好了,言归正传,先来看一看这个题目:Given an array of integers, return indices of the two numbers such that they add up to a specific target....
  • 6.继续遍历尾指针和头指针。并交换符合条件的两个数。 7.直到头尾两指针相遇,将相遇部位的元素和第一个元素a交换位置,完成排序。 递归部分: 首先检查头尾两个指针是否相遇,如果相遇则结束整个方法。 在每次...
  • Java基础知识面试题(2020最新版)

    万次阅读 多人点赞 2020-02-19 12:11:27
    文章目录Java概述何为编程什么是Javajdk1.5之后的三大版本JVM、JRE和JDK的关系什么是跨平台性?原理是什么Java语言有哪些特点什么是字节码?采用字节码的最大好处是什么什么是Java程序的主类?应用程序和小程序的...
  • java中,提供了静态数组和动态数组两种。静态数组需要提前初始化好,并且初始化后长度不能被改变了,比如int[] temp = new int[7];也可以使用动态数组List temp = new ArrayList<>(); 对角线遍历 给定一个含有 ...
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~ 本套Java面试题大全,全的不能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java ...
  • LeetCode:Valid Palindrome双指针 java

    千次阅读 2013-12-30 18:47:40
    LeetCode 上的这道题其实很简单,双指针比较即可,其中有些过程要注意,比如大小写要去掉,标点去掉,空格去掉,还有 ` 这种玩意也要去掉,因为用正则表达式是无法将该玩意去掉的,所以只能单独去掉,之后就Accept...
  • 我用java调用c++的函数,函数中用到了一个双指针作为参数,我应该怎么样传入一个双指针的变量,java中没有指针的概念
  • 入门常用算法之指针
  • 双指针 双指针比较灵活,可以大大降低时间复杂度,可用在数组,单链表等数据结构中。 快慢指针:一快一慢,步长一大一小,看慢指针是否能追上快指针。例如,是否有环问题,单链表找中间节点问题。 对撞指针:一左...
  • 双指针快速排序

    千次阅读 2017-10-24 18:38:04
    同样去一个数位基准数进行递归分区,两个指针分别从头和尾开始遍历数据,如果头不大于基准数,尾不小于基准数则不改位置,否则尾数与头交换。实现思路两个循环,循环执行条件第一个是尾数不小于基准数,且尾下标大于...
  • 最开始的思路不是双指针,简单的想两轮循环判断和。 class Solution { public int[] twoSum(int[] numbers, int target) { for(int i=0;i<numbers.length;i++){ for(int j=i+1;j<numbers.length;j++){ if...
  • 数组相关的算法问题,一般都可以使用双指针完成操作,有异步指针、快慢指针等,其实就是一种升维的思想,通过一个指针访问数组就相当于一维,用两个指针操作数组,就会出现两个数组同时存在的效果,这就是升维的一种...
  • JAVA双向链表

    千次阅读 2019-04-19 16:29:58
    java双向链表操作 双向链表的每一个结点都有一条指向其后继结点的next指针和一条指向其前结点的pre指针。 双向链表的插入图示: 双向链表的删除图示: import java.io.IOException; import java.util.Scanner; ...
  • 所谓双指针,指的是在遍历对象的过程中,不是使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行遍历,从而达到相应的目的。双指针的使用可以降低程序的时间复杂度或者空间复杂度,总之是一种有效的...
  • 算法中快慢指针的应用(Java)

    千次阅读 2019-03-29 16:53:51
    快慢指针就是指两个指针在移动的过程中,慢的指针每次移动一步,而快的指针每次移动两步。 快慢指针的应用一 (判断一个链表是否有环): 问题来源:leetcode-141题,环形链表 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 92,346
精华内容 36,938
关键字:

java双指针

java 订阅