LeetCode第二弹：总结了双指针的经典题目
题目列表
合并两个有序数组
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2])
nums1[p--] = nums1[p1--];
else
nums1[p--] = nums2[p2--];
}
while (p2 >= 0)
nums1[p--] = nums2[p2--];
}
};
环形链表
- 设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次
- 如果有环的存在，则slow指针一定和fast指针相遇
- 第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步，也就是说比 slow 多走了 k 步(也就是环的⻓度)。
- 设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
- 巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。
- 所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速 前进，k - m 步后就会相遇，相遇之处就是环的起点了。
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr)
return false;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
};
两数之和 II - 输入有序数组
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
for (int i = 0, j = numbers.size() - 1; i < numbers.size(); i++) {
while (i < j && numbers[i] + numbers[j] > target)
j--;
if (i < j && numbers[i] + numbers[j] == target) {
res.push_back(i + 1);
res.push_back(j + 1);
break;
}
}
return res;
}
};
反转字符串中的元音字母
class Solution {
public:
string str = "aeiou";
bool check(char c) {
return str.find(tolower(c)) != -1;
}
string reverseVowels(string s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
while (i < j && !check(s[i]))
i++;
while (i < j && !check(s[j]))
j--;
swap(s[i], s[j]);
}
return s;
}
};
通过删除字母匹配到字典里最长单词
class Solution {
public:
/**
* @brief 比较函数：返回长度最长且字典顺序最小的字符串
* @param a
* @param b
* @return true
* @return false
*/
static bool cmp(string &a, string &b) {
if (a.size() != b.size())
return a.size() > b.size();
else
return a < b;
}
string findLongestWord(string s, vector<string>& d) {
if (d.empty())
return "";
vector<string> res;
// 找到所有的情况
for (string str : d) {
int i = 0, j = 0;
while (j < s.size()) {
if (str[i] == s[j])
i++;
j++;
}
if (i == str.size())
res.push_back(str);
}
if (res.empty())
return "";
sort(res.begin(), res.end(), cmp);
return res[0];
}
};
平方数之和
class Solution {
public:
bool judgeSquareSum(int c) {
if (c == 0)
return true;
int low = 0;
int high = (int)sqrt(c);
while (low <= high) {
long long temp = (long long)low * low + high * high;
if (temp == c)
return true;
else if (temp > c)
high--;
else
low++;
}
return false;
}
};
验证回文字符串 Ⅱ
class Solution {
public:
bool validPalindrome(string s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
if (s[i] != s[j])
// 两种情况求“或”
return helper(s, i + 1, j) || helper(s, i, j - 1);
}
return true;
}
/**
* @brief 判断字符串从i ~ j之间是否是回文串
* @param s
* @param i
* @param j
* @return true
* @return false
*/
bool helper(string &s, int i, int j) {
bool res = true;
while (i < j) {
if (s[i] != s[j])
res = false;
i++;
j--;
}
return res;
}
};
