本文共 4420 字,大约阅读时间需要 14 分钟。
最近在刷leetcode,碰到了许多双指针类的题目,题目是根据githubCyC大佬,在这里总结下:所谓双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应的目的。换言之,双指针法充分使用了数组有序这一特征,从而在某些情况下能够简化一些运算。
(注:这里的指针,并非专指c中指针的概念,而是指索引,游标或指针,可迭代对象等)
题目:定给一个已按照升序个结果排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1和index2,其中index1必须小于index2 。
说明:
示例:
输入:数字= [ 2,7,11,15 ],目标= 9 输出: [1,2] 解释: 2与7之和等于目标数9.因此index1 = 1,index2 = 2。
解决方法:
使用双指针,一个指针指向值较小的元素,一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历,指向较大元素的指针从尾向头遍历。
如果两个指针指向元素的和sum == target,那么得到要求的结果;
如果sum> target,移动较大的元素,使sum变小一些;
如果sum <target,移动较小的元素,使sum变大一些。
public int[] twoSum(int[] numbers, int target) { int i = 0, j = numbers.length - 1; while (i < j) { int sum = numbers[i] + numbers[j]; if (sum == target) { return new int[]{ i + 1, j + 1}; } else if (sum < target) { i++; } else { j--; } } return null;}
问题:给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1输出:true解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0输出:true解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1输出:false解释:链表中没有环。
**解决:**使用双指针,一个指针每次移动一个节点,一个指针每次移动两个节点,如果存在环,那么这两个指针一定会相遇,好比于操场,如果一个用走,一个用跑,两个肯定相遇。
public boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode l1 = head, l2 = head.next; while (l1 != null && l2 != null && l2.next != null) { if (l1 == l2) { return true; } l1 = l1.next; l2 = l2.next.next; } return false;}
**问题:**编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
示例 1:
输入: "hello"输出: "holle"
示例 2:
输入: "leetcode"输出: "leotcede"
**解决:**使用双指针指向待反转的两个元音字符,一个指针从头向尾遍历,一个指针从尾到头遍历。
private final static HashSetvowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));public String reverseVowels(String s) { int i = 0, j = s.length() - 1; char[] result = new char[s.length()]; while (i <= j) { char ci = s.charAt(i); char cj = s.charAt(j); if (!vowels.contains(ci)) { result[i++] = ci; } else if (!vowels.contains(cj)) { result[j--] = cj; } else { result[i++] = cj; result[j--] = ci; } } return new String(result);}
**问题:**给定一个非空字符串 s
,最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"输出: True
示例 2:
输入: "abca"输出: True解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
**解决:**先写一个是否是回文的函数,然后再使用双指针,只要是回文数,头尾指针在遍历时肯定一样,如果不一样,可以去掉一个,增加i或减小j;
public boolean validPalindrome(String s) { int i = -1, j = s.length(); while (++i < --j) { if (s.charAt(i) != s.charAt(j)) { return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j); } } return true;}private boolean isPalindrome(String s, int i, int j) { while (i < j) { if (s.charAt(i++) != s.charAt(j--)) { return false; } } return true;}
问题:给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中*,*使得 num1 成为一个有序数组。
说明:
示例:
输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出: [1,2,2,3,5,6]
**解决:**使用双指针,需要从尾开始遍历,否则在nums1上归并得到的值会覆盖还未进行归并比较的值。
public void merge(int[] nums1, int m, int[] nums2, int n) { int index1 = m - 1, index2 = n - 1; int indexMerge = m + n - 1; while (index1 >= 0 || index2 >= 0) { if (index1 < 0) { nums1[indexMerge--] = nums2[index2--]; } else if (index2 < 0) { nums1[indexMerge--] = nums1[index1--]; } else if (nums1[index1] > nums2[index2]) { nums1[indexMerge--] = nums1[index1--]; } else { nums1[indexMerge--] = nums2[index2--]; } }}
问题:给定一个非负整数 c
,你要判断是否存在两个整数 a
和 b
,使得 a2 + b2 = c。
示例1:
输入: 5输出: True解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3输出: False
**解决:**一个从头遍历,一个从目标数字的开方往回遍历,如果目标数字大于实际数字,则i++;如果目标数字小于实际数字,则j–;如果目标数字等于实际数字,则找到了;
public boolean judgeSquareSum(int c) { int i = 0, j = (int) Math.sqrt(c); while (i <= j) { int powSum = i * i + j * j; if (powSum == c) { return true; } else if (powSum > c) { j--; } else { i++; } } return false;}
转载地址:http://kerwi.baihongyu.com/