LeetCode题解（1）：双指针法

发表于 | 分类于
字数统计: 1.6k | 阅读时长 ≈ 7

LeetCode 题解（1）：双指针法

learn from cyc2018 and LeetCode

双指针法指的是：在遍历对象的过程中，不使用单个指针进行访问，而是用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。双指针问题的本质是由于两个或者多个元素有相互作用或者相关联。

167. TWO SUM II - Input array is sorted (easy)

问题描述

在有序数组中找到两个数字，使其和为一特定值。函数返回两个数的索引，其中索引 1 小于索引 2。

你可以假设每次输入只有一组特定解，并且不能使用同一元素两次。

1
2
3
4
// example
// Input: numbers = [2, 7, 11, 15], target = 9
// Output: [1, 2]
// Explanation: 2 + 7 = 9 => index1 = 1, index2 = 2

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> index = {0, numbers.size() - 1};
        while(index[0] != index[1]){
            int tmp = numbers[index[0]] + numbers[index[1]];
            if(tmp == target){
                ++ index[0];
                ++ index[1];
                return index;
            }
            else if(tmp > target)
                -- index[1];
            else
                ++ index[0];
        }
        return {-1,-1};
    }
};

相关问题

1. TWO SUM (easy)

653. TWO SUM IV - Input is a BST (easy)

633. Sum of Squared Numbers (easy)

问题描述

给定一个非负整数 $c$ ，判断是否存在两个整数 $a$ 和 $b$ 使得：$a^2 + b^2 = c$

1
2
3
4
// example
// Input: 5
// Output: True
// Explanation: 1*1 + 2*2 = 5

题解

失败经历（一）

限定两个边界分别为 $0$ 和 $sqrt(c)$，结果出现如下错误：

1
2
3
// Input: 2147482647
// line 7: int tmp = i*i + j*j;
// Line 7: Char 17: runtime error: signed integer overflow: 829921 + 2146654224 cannot be represented in type 'int' (solution.cpp)

正解

将类型由 int 改为 long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool judgeSquareSum(int c) {
        long i = 0;					// type: long
        long j = sqrt(c);			// type: long
        while(i <= j){
            long tmp = i*i + j*j;	// type: long
            if(tmp == c)
                return true;
            else if(tmp > c)
                -- j;
            else
                ++ i;
        }
        return false;
    }
};

相关问题

367. Valid Perfect Square (easy)

345. Reverse Vowels of a String (easy)

问题描述

翻转字符串中的元音字母。

1
2
3
// example
// input: "leetcode"
// output: "leotcede"

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string reverseVowels(string s) {
        int i = 0;
        int j = s.size() - 1;
        string vowels = "aeiouAEIOU";
        while(1){
            while(i < s.size()){
                if(vowels.find(s[i]) == vowels.npos)
                    ++ i;
                else
                    break;
            }
        while(j > 0){
            if(vowels.find(s[j]) == vowels.npos)
                -- j;
            else
                break;
        }
            if(i >= j)
                return s;
            else{
                char tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
                ++ i;
                -- j;
            }
        }
        return s;
    }
};

相关问题

344. Reverse String (easy)

680. Valid Palindrome II (easy)

问题描述

给定非空字符串s，最多可以删除一个字符。判断你是否能把它变成回文。

1
2
3
4
5
6
7
8
// example
// Input: "aba"
// Output: true

// Input: "abca"
// Output: true

// The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

题解

采用分治法可以很好的解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool validPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        while(i < j){
            if(s[i] != s[j])
                return palindrome(s, i, j - 1) || palindrome(s, i + 1, j);
            ++ i;
            -- j;
        }
        return true;
    }
private:
    bool palindrome(string s, int i, int j){
        while(i < j){
            if(s[i] != s[j])
                return false;
            ++ i;
            -- j;
        }
        return true;
    }
};

相关问题

125. Valid Palindrome (easy)

88. Merge Sorted Array (easy)

问题描述

归并两个有序数组 $nums1$ 和 $nums2$ 。将 $nums2$ 中数据归并至 $nums1$ 中。

  • $nums1$ 和 $nums2$ 中元素个数分别为：$m$，$n$
  • $nums1$ 中空间足够大
1
2
3
// example
// Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// Output: [1,2,2,3,5,6]

题解

失败经历（一）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> tmp;
        int i = 0;
        int j = 0;
        while(i < m && j < n){
            if(nums1[i] > nums2[j]){
                tmp.push_back(nums2[j]);
                ++ j;
            }
            else if(nums1[i] < nums2[j]){
                tmp.push_back(nums1[i]);
                ++ i;                
            }
            else{
                tmp.push_back(nums2[j]);
                ++ j;
                tmp.push_back(nums1[i]);
                ++ i;
            }
        }
        while(i < m){
            tmp.push_back(nums1[i]);
            ++ i;
        }
        while(j < n){
            tmp.push_back(nums2[j]);
            ++ j;
        }
        nums1 = tmp;
    }
};

结果为：

Runtime 过长。

正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<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--];
        }
        
    }
};

从尾开始遍历，防止在 $nums1$ 上归并得到的值覆盖尚开始归并的值。

相关问题

21. Merge Two Sorted Lists (easy)

977. Squares of a Sorted Array (easy)

986. Interval List Intersections (medium)

141. Linked List Cycle (easy)

问题描述

判断一个链表中是否有环。

题解

失败经历（一）

不会做。。

正解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL)
            return false;
        ListNode *p1 = head;
        ListNode *p2 = head->next;
        while(p2 != NULL && p2->next != NULL && p1 != NULL){
            if(p2 == p1)
                return true;
            p2 = p2->next->next;
            p1 = p1->next;
        }
        return false;
    }
};

结果显示时间复杂度与空间复杂度都不太好，需要进一步优化。

但是查了一下似乎这种情况已经是最优解了，时间复杂度为 $O(n)$ 空间复杂度为 $O(1)$ 。所以换了一个版本：

1
2
3
4
5
6
7
8
9
bool hasCycle(ListNode *head) {
	ListNode *slow = head, *fast = head;
	while (fast && fast->next) {
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast) return true;
	}
	return false;
}

发现速度已经足够了。

相关问题

142. Linked List Cycle II (medium)

202. Happy Number (easy)

524. Longest Word in Dictionary through Deleting (medium)

问题描述

给定一个字符串和一个字符串字典，在字典中查找可以通过删除给定字符串的一些字符来形成的最长字符串。如果有多个可能的结果，则返回词序最小的最长单词。如果没有可能的结果，返回空字符串。

1
2
3
// example
// Input: s = "abpcplea", d = ["ale", "apple", "monkey", "plea"]
// Output: "apple

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        string longestWord = "";
        for(int i = 0; i < d.size(); ++ i){
            if(d[i].size() < longestWord.size())
                continue;
            if(d[i].size() == longestWord.size() && d[i] > longestWord)
                continue;
            if(contain(s, d[i]))
                longestWord = d[i];
        }
        return longestWord;
        
    }
private:
    bool contain(string s, string target){
        int i = 0;
        int j = 0;
        while(i < s.size() && j < target.size()){
            if(s[i] == target[j])
                ++ j;
            ++ i;
        }
        if(j == target.size())
            return true;
        return false;
    }
};

相关问题

720. Longest Word in Dictionary (easy)