双指针法
胖墩哥 人气:1双指针法：
双指针法，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。
这里的指针，并非专指c中指针的概念，而是指索引，游标或指针，可迭代对象。
LeetCode双指针题解：
1.有序数组的Two Sum
Leetcode ：167. Two Sum II - Input array is sorted (Easy)
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2题目描述：在有序数组中找出两个数，使它们的和为 target。
思路描述：
该题是经典的双指针法，指针i和指针j，i和j分别指向头和尾，
如果两个指针指向的元素和sum==target，那么得到要求的结果；
如果sum>target,移动较大的元素，使sum变小一些,j--；
如果sum<target，移动较小的元素，是sum变大一些，i++；代码实现：
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int num = numbers[i] + numbers[j];
if (num == target) {
return new int[]{i + 1, j + 1};
} else if (num < target) {
i++;
} else {
j--;
}
}
return null;
}2.两数平方和
633. Sum of Square Numbers (Easy)
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5题目描述：判断一个数是否为两个数的平方和
思路描述：
首先，一个数的平方和，那么另外两个数肯定 <= Math.sqrt(num)，则使用双指针法来测试
指针i指向0,指针j指向Math.sqrt(num)
如果两个指针指向的元素和sum==target，那么得到要求的结果；
如果sum>target,移动较大的元素，使sum变小一些,j--；
如果sum<target，移动较小的元素，是sum变大一些，i++；代码实现：
public static boolean judgeSquareSum(int c) {
int i = 0;
int j = (int) Math.sqrt(c);
while (i <= j) {
int num = i * i + j * j;
if (num == c) {
System.out.println(i + " " + j);
return true;
} else if (num < c) {
i++;
} else {
j--;
}
}
return false;
}3.反转字符串中的元音字符
345. Reverse Vowels of a String (Easy)
Given s = "leetcode", return "leotcede".题目描述：
将给定的字符串中的元音字符进行互换位置
思路描述：
使用双指针指向待反转的两个元音字符，
指针i从头向尾遍历，指针j从尾到头遍历。
如果两个同时指向元音，互换位置,i++,j--
否则只有i指针指向元音，则j--,i不变
否则只有j指针指向元音，则i++,j不变
否则都没有指向元音，则i++，j--代码实现：
public static String reverseVowels(String s) {
List<Character> characters = Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
int i = 0, j = s.length() - 1;
char[] chars = s.toCharArray();
while (i <= j) {
if (characters.contains(chars[i]) && characters.contains(chars[j])) {
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
i++;
j--;
} else if (characters.contains(chars[i])) {
j--;
} else if (characters.contains(chars[j])) {
i++;
} else {
i++;
j--;
}
}
return new String(chars);
}
4. 回文字符串
680. Valid Palindrome II (Easy)
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
题目描述：可以删除一个字符，判断是否能构成回文字符串。
思路详解：
如果字符串的起始字符和结束字符相同（即 s[0]==s[s.length-1]），则内部字符是否为回文（s[1], s[2], ..., s[s.length - 2]）将唯一地确定整个字符串是否为回文。
如果字符串的起始字符和结束字符不同，则判断（s[1], s[2], ..., s[s.length - 1]）或者（s[0], s[2], ..., s[s.length - 2]）是否是回文，如果两个都不是，那么必定不是回文。
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return ispalindrome(s, i, j - 1) || ispalindrome(s, i + 1, j);
}
}
return true;
}
//判断是否string是否是回文串
private static boolean ispalindrome(String string, int i, int j) {
while (i < j) {
if (string.charAt(i++) != string.charAt(j--)) {
return false;
}
}
return true;
}
5.归并两个有序数组
88. Merge Sorted Array (Easy)
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
题目描述：把归并结果存到第一个数组上。
思路描述：
使用Arrays.cpoy(A,m)来复制A产生一个临时数组tem,使用双指针，指针i指向数组tem，指针j指向数组B;
while( i<tem.length()&& j<tem.length()) ,则比较指针i,j指向的元素大小，小的放在A数组中
如果上面循环终止时候，i或者j还没有指向终点位置，则继续循环。
while(i< tem.length()) ,i指向的元素赋值给数组A
while(j<B.length()),j指向的元素赋值给数组A。
代码实现：
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int[] tem = Arrays.copyOf(nums1, m);
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (tem[i] < nums2[j]) {
nums1[k++] = tem[i++];
} else {
nums1[k++] = nums2[j++];
}
}
while (i < m) {
nums1[k++] = tem[i++];
}
while (j < n) {
nums1[k++] = nums2[j++];
}
}
第二种逻辑：
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
int[] tem = Arrays.copyOf(nums1, m);
int i = 0, j = 0, k = 0;
while (i < m || j < n) {
if (i < m && j < n) {
if (tem[i] < nums2[j]) {
nums1[k++] = tem[i++];
} else {
nums1[k++] = nums2[j++];
}
} else if (i < m) {
nums1[k++] = tem[i++];
} else if (j < n) {
nums1[k++] = nums2[j++];
}
}
}
6.判断链表是否存在环
141. Linked List Cycle (Easy)
思路描述：
使用双指针法，一个指针慢，一个指针快，如果存在环，那么这两个指针肯定会相遇。
代码实现：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
//这里的判断一定是 fast.next == null
if (slow == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
7.最长子序列
524. Longest Word in Dictionary through Deleting (Medium)
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"
题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。
思路描述1：
暴力法：
对字符串s 进行拆解，把所有情况均表示出，再遍历进行查找，则问题得到解决，时间复杂度很高。
思路描述：
首先根据要求，对字符串进行排序，排序规则：先根据字符串的长度进行排序，长度相等时，根据字符串的首字符的字典序进行排序。
对排序后的字符进行遍历，第一个符合子序列的字符串即是所求字符串。
判断字符串sub是不是s的子串，是使用双指针法：
开始循环：i<s.length() && j<target.length()
一个指针指向s,一个指针指向sub,同时出发
如果指针指向的位置字符相同，则两个指针同时+1，
如果不同，那么只有s指针+1，
循环终止时候，如果sub指针指向了sub的末尾，那么sub肯定是s的子串
代码实现：
public String findLongestWord(String s, List<String> d) {
//对字符串进行排序，规则是先按长度排序，长度相同时，再按照字符串字典序排序
Collections.sort(d, (o1, o2) -> o2.length() == o1.length() ? o1.compareTo(o2) : o2.length() - o1.length());
for (String s1 : d) {
if (findLongestWord2(s, s1)) {
return s1;
}
}
return "";
}
public boolean findLongestWord2(String s, String target) {
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
加载全部内容