亲宝软件园·资讯

展开

双指针法

胖墩哥 人气: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();
}

加载全部内容

相关教程
猜你喜欢
用户评论