算法刷题记一（双指针）

桃扇骨 2023-01-17 11:58 152阅读 0赞

### 文章目录 ###

*   *  1、两数之和 II - 输入有序数组（7/21-167）
     *  2、平方数之和（7/21-633）
     *  3、反转字符串中的元音字母（7/21-345）
     *  4、验证回文字符串 Ⅱ（7/21-680）
     *  5、合并两个有序数组（7/27-88）
     *  6、环形链表（7/27-141）
     *  7、通过删除字母匹配到字典里最长单词（7/27-524）

> leetcode官网：[https://leetcode-cn.com/problems][https_leetcode-cn.com_problems]  
> CS-Notes：[https://www.cyc2018.xyz/][https_www.cyc2018.xyz]

--------------------

## 1、两数之和 II - 输入有序数组（7/21-167） ##

![在这里插入图片描述][43bce63b71e9e48d5c5999db750acaeb.png]  
![在这里插入图片描述][c9ee0ac3e7a214c65d926c4b1b046022.png]

--------------------

解题思路：

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target，那么得到要求的结果；
    如果 sum > target，移动较大的元素，使 sum 变小一些；
    如果 sum < target，移动较小的元素，使 sum 变大一些。

数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。

![在这里插入图片描述][15974b70d66aa89c78f7710f3dd804e2.gif]

--------------------

java代码实现：

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            if(numbers == null) return null;
            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;
        }
    }

## 2、平方数之和（7/21-633） ##

![在这里插入图片描述][a3b1a586e9da0e0f973a1c3f084a739f.png]  
![在这里插入图片描述][1cd609160fc37df426564449bb96f60b.png]

--------------------

解析：

可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。

本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。

本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。

因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。

--------------------

Java实现：

class Solution { 
        public boolean judgeSquareSum(int c) { 
            int left = 0, right = (int)Math.sqrt(c);
            while(left <= right) { 
                int sum = left*left + right*right;
                if(sum == c) { 
                    return true;
                }else if(sum < c) { 
                    ++left;
                }else { 
                    --right;
                }
            }
            return false;
        }
    }

![在这里插入图片描述][493a0dfd501c3249fff7cf1bd827b14a.png]

## 3、反转字符串中的元音字母（7/21-345） ##

![在这里插入图片描述][2784e306a352d183ad6757a816717771.png]

--------------------

解析：

使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。

为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。

时间复杂度为 O(N)：只需要遍历所有元素一次
    空间复杂度 O(1)：只需要使用两个额外变量

![在这里插入图片描述][0b7d8893768580bd6959e91314f2523b.png]  
![在这里插入图片描述][a4fb1fd1eb23f064f885363890518bb2.gif]

--------------------

Java实现：

class Solution { 
        //元音字母集合
        private final static HashSet<Character> vowels = new HashSet<>( //创建HashSet集合对象
            Arrays.asList('a','e','i','o','u','A','E','I','O','U')
        );
    
        public String reverseVowels(String s) { 
            if(s == null) return null;
            int left = 0, right = s.length() -1;
            char[] result = new char[s.length()];
            while(left <= right) { 
                char cl = s.charAt(left);  // charAt返回第i个位置的字符
                char cr = s.charAt(right);
                if(!vowels.contains(cl)) { 
                    result[left++] = cl;   //如果不包含就存如直接数组
                } else if(!vowels.contains(cr)) { 
                    result[right--] = cr;  //如果不包含就存如直接数组
                } else { 
                    result[left++] = cr;   //当左右两边都包含就先交换再存入数组
                    result[right--] = cl;
                }
            }
            return new String(result); 
        }
    }

![在这里插入图片描述][8537c3e0fdab1da3ff715c2c2e24c102.png]

## 4、验证回文字符串 Ⅱ（7/21-680） ##

![在这里插入图片描述][a9c38c433b801c1929bd28d2b2a8ce96.png]  
![在这里插入图片描述][fd93bf639d23894a8bc41165a497c00d.png]

--------------------

解析：

所谓的回文字符串，是指具有左右对称特点的字符串，例如 “abcba” 就是一个回文字符串。

使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。  
![在这里插入图片描述][665d214daf52a800d16bd5a0d1d6fd1d.gif]  
本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。  
![在这里插入图片描述][2415f7208c6611041a5cebf78f9b90e1.gif]

--------------------

Java实现：

class Solution { 
        public 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;
        }
    
        private boolean isPalindrome(String s, int i, int j) { 
            while (i < j) { 
                if (s.charAt(i++) != s.charAt(j--)) { 
                    return false;
                }
            }
            return true;
        }
    
    }

![在这里插入图片描述][d69e4365ea11e464fe518f49dca9d863.png]

## 5、合并两个有序数组（7/27-88） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]

--------------------

解析：

需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。

--------------------

Java实现：

class Solution { 
        public void merge(int[] nums1, int m, int[] nums2, int n) { 
            int i1 = m-1, i2 = n-1;
            int i3 = m+n-1;
            while(i2 >= 0){ 
                if(i1 < 0){ 
                    nums1[i3--] = nums2[i2--];
                }else if(i2 < 0){ 
                    nums1[i3--] = nums1[i1--];
                }else if(nums1[i1] > nums2[i2]){ 
                    nums1[i3--] = nums1[i1--];
                }else{ 
                    nums1[i3--] = nums2[i2--];
                }
            } 
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]

## 6、环形链表（7/27-141） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]

--------------------

解析：

使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。

--------------------

Java实现：

/**
     * Definition for singly-linked list.
     * class ListNode { 
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { 
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution { 
        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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 6]

## 7、通过删除字母匹配到字典里最长单词（7/27-524） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 8]

--------------------

解析：

通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。

--------------------

Java实现：

class Solution { 
        public String findLongestWord(String s, List<String> dictionary) { 
            String longsetWord = "";
            for(String targer : dictionary){ 
                int l1 = longsetWord.length(), l2 = targer.length();
                if(l1 > l2 || (l1 == l2 && longsetWord.compareTo(targer) < 0)){  //longsetWord.compareTo(targer)如果此字符串小于字符串参数，则返回一个小于 0 的值；
                    continue;
                }
                if(isSubstr(s,targer)){ 
                    longsetWord = targer;
                }
            }
            return longsetWord;
        }
    
        //判断两个字符串是否相等
        private boolean isSubstr(String s, String targer) { 
            int i = 0, j = 0;
            while(i < s.length() && j < targer.length()) { 
                if(s.charAt(i) == targer.charAt(j)) {   // s.charAt(i) 表示：获取s中下标为i的字符
                    j++;
                } 
                i++;
            }
            return j == targer.length();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 9]

[https_leetcode-cn.com_problems]: https://leetcode-cn.com/problems
[https_www.cyc2018.xyz]: https://www.cyc2018.xyz/
[43bce63b71e9e48d5c5999db750acaeb.png]: /images/20221021/0757b3f3a3ca4105a13f8568a31b2a12.png
[c9ee0ac3e7a214c65d926c4b1b046022.png]: /images/20221021/a4920c4aa7504d66a1f69248b4adaa65.png
[15974b70d66aa89c78f7710f3dd804e2.gif]: /images/20221021/2367520a2ef5494c9ec717cdd07a5157.png
[a3b1a586e9da0e0f973a1c3f084a739f.png]: /images/20221021/a89c28510317449c9bcb4224fb172e7d.png
[1cd609160fc37df426564449bb96f60b.png]: /images/20221021/a4732ad1d8644117a997e352d8fcb8aa.png
[493a0dfd501c3249fff7cf1bd827b14a.png]: /images/20221021/44ddbaab686c4e099994385ae2b2f29f.png
[2784e306a352d183ad6757a816717771.png]: /images/20221021/2935a546636d45eb8f40a46f09f652db.png
[0b7d8893768580bd6959e91314f2523b.png]: /images/20221021/ed274147c70b4aa3be9edb0376a5880d.png
[a4fb1fd1eb23f064f885363890518bb2.gif]: /images/20221021/6762f7d6528845d987e1d68cfca9e696.png
[8537c3e0fdab1da3ff715c2c2e24c102.png]: /images/20221021/cbc87961cb2b49f49dbb16861d4300af.png
[a9c38c433b801c1929bd28d2b2a8ce96.png]: /images/20221021/537698d252f94cf5928688db06c42156.png
[fd93bf639d23894a8bc41165a497c00d.png]: /images/20221021/94f9ea62f0854ead97bbe7dcbf3c5dae.png
[665d214daf52a800d16bd5a0d1d6fd1d.gif]: /images/20221021/95e0f8e633a343c5adb71e1adab6b88d.png
[2415f7208c6611041a5cebf78f9b90e1.gif]: /images/20221021/ecaec8d7767347359c47311b9635c7dd.png
[d69e4365ea11e464fe518f49dca9d863.png]: /images/20221021/ad79f8e0ce3a4d4f990112b05ce30e0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]: /images/20221021/6d4f9def05124166b98ffde7ef294fab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]: /images/20221021/226104e68ed74e16b5d522a261f19775.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]: /images/20221021/a7b5d72c081d473384d0f8e6e7439f39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]: /images/20221021/e4a02b43112643f385038a723ed77774.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]: /images/20221021/226d7cd3268f4a7b94ca850ae5a531ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]: /images/20221021/fe27b750fe234df387ba83e832c86fd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 6]: /images/20221021/014b078af1b24194b1f36d6cacd5279c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 7]: /images/20221021/cc718cb124f94b24b7c76379645551d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 8]: /images/20221021/301087736b934a56aa0c49eb85f23ddd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 9]: /images/20221021/bffcfc1b38dc4541919ab1f52cbd858a.png