Your Site Title

Leetcode - 双指针

 
  • Mar 13, 2020

two sum

link

在有序数组中找到两个数，使之和为目标

code1

哈希表记录值对应的下标，每次从已记录的hash中寻找是否存在构成和的另一个值。因为下标在访问后才记录进hash，因此不会出现重复下标的情况。时间复杂度O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> hash;
        
        for(int i=0; i<nums.size(); i++) {
            int other = target - nums[i];
            if(hash.find(other)!=hash.end()){
                ans.push_back(i);
                ans.push_back(hash[other]);
                break;
            }
            hash[nums[i]] = i;
        }
        
        return ans;
    }  
};

code2

循环遍历

        for(int i=0; i<nums.length-1; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i, j};
                }
            }
        }

两数平方和

给一个数，判断这个数能否是两个数的平方和

Link

code1

首先查找范围应该是$0到\sqrt x$

        int a = (int) Math.sqrt(c);
        int limit = a/2;
        while (a >= limit){
            double b = Math.sqrt(c - a * a);
            if (b - (int)b == 0) return true;
            else a--;
        }
        return false;

code2

改进，双指针

        int i = 0;
        int j = (int) Math.sqrt(c);
        while (i <= j){ //eg：1*1 + 1*1 = 2
            int res = i*i + j*j;
            if (res == c) return true;
            else if(res > c) --j;
            else ++i;
        }
        return false;

反转字符串中的元音字符

Link

code1

从首部和尾部向内搜索成对出现的元音交换

public static String reverseVowels(String s){
        int length = s.length();
        int i = 0;
        int j = length-1;
        char[] chars = s.toCharArray();
        Set<Character> vowels = new TreeSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

        while (i <= j){
            while(i<length&&!vowels.contains(chars[i])) ++i;
            while(j>-1&&!vowels.contains(chars[j])) --j;

            if (i > j) break;

            char t = chars[i];
            chars[i] = chars[j];
            chars[j] = t;
            i++;j--;
        }
        return String.copyValueOf(chars);
    }

code2

遇元音的指针等待，反过来，不遇元音就前进

    public static String reverseVowels(String s){
        int i = 0;
        int j = s.length()-1;
        char[] chars = s.toCharArray();
        Set<Character> vowels = new TreeSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

        while(i<=j){
            char ci = chars[i];
            char cj = chars[j];

            if (!vowels.contains(ci)) {
                i++;
            }else if (!vowels.contains(cj)){
                j--;
            }else{
                chars[i++] = cj;
                chars[j--] = ci;
            }
        }

        return String.copyValueOf(chars);
    }

回文字符串

Link

code

问题点就是遇到删除左或者删除右都可行，但是只有一种是回文的情况。

class Solution {
    public boolean isPalindrome(String s){
        for (int i=0; i<s.length()/2; i++){
            if (s.charAt(i) != s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }
    public boolean validPalindrome(String s) {
        int i=0;
        int j=s.length()-1;
        while (i<j && s.charAt(i) == s.charAt(j)){i++; j--;};
        if (i>=j) return true;
        return isPalindrome(s.substring(i, j)) || isPalindrome(s.substring(i+1, j+1));
    }
}

归并两个有序数组

Link

code

正面写，顺着比较大小挨个放

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0; int j = 0; int k = 0;
        int[] nums3 = new int[m+n];
        while (i < m && j < n){
            if (nums1[i] < nums2[j]){
                nums3[k++] = nums1[i++];
            }else{
                nums3[k++] = nums2[j++];
            }
        }
        if (i == m){
            while(j < n) nums3[k++] = nums2[j++];
        }else{
            while(i < m) nums3[k++] = nums1[i++];
        }
        for (k = 0; k<m+n; k++){
            nums1[k] = nums3[k];
        }
    }
}

code

倒过来写，从数组的尾部开始填。因为正着写不新建数组的话有一个缺点就是插入元素会产生覆盖

int i = m - 1;
int j = n - 1;
int k = m+n - 1;
while (i>-1 && j>-1) 
    nums1[k--] = (nums1[i] < nums2[j]) ? nums2[j--] : nums1[i--];
while (j>-1) 
    nums1[k--] = nums2[j--];

判断链表是否存在环

Link

code

跑的人比走的人快，超圈

关于空指针的问题，首先head不能为空，然后正在的俩人不能为空（同时验证走的下一步不是空的），跨两步的人中间跨的一步不能为空

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode v = head;
        ListNode v2 = head;
        
        if(head == null)
            return false;
        
        while(v != null && v2 != null && v2.next != null){
            v = v.next;
            v2 = v2.next.next;
            if (v == v2) return true;
        }
        return false;
    }
}

最长子序列

其中的关键是判断子串的算法

 	/**
     * 最长子序列
     * https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/
     * 在父串中左右扫描，直到子串中每一个字符都在父串中被找到
     */
public String findLongestWord(String s, List<String> d) {
    String res = ""; int length=0;
    for (String per : d) {
        int i = 0, j = s.length() - 1;
        int m = 0, l = per.length() - 1;
        while (i <= j && m<l+1 && m<per.length()) { //由于需要使m、l交错，所以要保证索引
            char c1 = s.charAt(i++), c2 = s.charAt(j--), c3 = per.charAt(m), c4 = per.charAt(l);

            if (c1 == c3 && m != l+1) { //为了防止m==l时，m或l指向的值没有被检测
                m++;
            }
            if (c2 == c4 && m != l+1) {
                l--;
            }
        }
        if (m == l+1 && (per.length() > length || (per.length() == length && per.compareTo(res) < 0))) {
            res = per;
            length = per.length();
        }
    }
    return res;
}

大佬的写法

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String longest = "";
        for (String dictWord : d) {
            int i = 0;
            for (char c : s.toCharArray()) 
                if (i < dictWord.length() && c == dictWord.charAt(i)) i++;

            if (i == dictWord.length() && dictWord.length() >= longest.length()) 
                if (dictWord.length() > longest.length() || dictWord.compareTo(longest) < 0)
                    longest = dictWord;
        }
        return longest;
    }
}

结论上都是一样的，判断子串，判断长度，判断字典序；

Search