【数据结构与算法】LeetCode：双指针法
LeetCode：双指针法
双指针法通常是指使用两个指针相向而行或同向而行来遍历对象（如数组、链表或字符串），以避免多层循环，从而降低算法的时间复杂度。
正序同向而行（快慢指针）
移除元素
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] != val) { // fast_i没遇到目标值
nums[slow] = nums[fast]; // 保留 nums[fast]
// slow和fast都前进一步
slow++;
fast++;
}else{ // 遇到目标值，slow不动，fast前进一步
fast++;
}
}
return slow;
}
};
简化代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
fast++;
}
return slow;
}
};
移动零（Hot 100）
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] != 0) { // fast 指向非零数，
swap(nums[slow], nums[fast]); // 保留非零数
slow++; // slow和fast 都前进一步
}
fast++; // 指向零数 slow不动，fast前进一步
}
}
};
删除有序数组中的重复项
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast = 1, slow = 1;
while (fast < nums.size()) {
// fast 没指向重复项，slow和fast都移动
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast]; // 保留非重复项
slow++; // slow指向未保留的元素，可能是要去除的元素
}
fast++; // fast指向重复项，则不让slow移动
}
return slow;
}
};
颜色分类（Hot 100）
class Solution {
public:
void sortColors(vector<int>& nums) {
int slow = 0, fast = 0;
// 把0往前移
while(fast < nums.size()) {
if (nums[fast] == 0) {
swap(nums[fast], nums[slow]);
++slow;
}
++fast;
}
fast = slow;
// 把1往前移
while(fast < nums.size()) {
if (nums[fast] == 1) {
swap(nums[fast], nums[slow]);
++slow;
}
++fast;
}
}
};
压缩字符串
class Solution {
public:
int compress(vector<char>& chars) {
int slow = 0;
int fast = 0;
while(fast < chars.size()){
char cur = chars[fast];
int count = 0; // 重复数量
while(fast < chars.size() && chars[fast] == cur){
fast++;
count++;
}
chars[slow++] = cur; // 记录当前字符
if(count > 1){ // 记录当前字符重复数量
for(char c: to_string(count)) chars[slow++] = c;
}
}
return slow;
}
};
移除链表元素
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy_head = new ListNode(0, head);
ListNode* cur = dummy_head;
// 双指针：cur和 cur.next
while(cur->next != nullptr){
if(cur->next->val != val){
cur = cur->next;
}else{
cur->next = cur->next->next;
}
}
return dummy_head->next;
}
};
删除排序链表中的重复元素
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) return head;
// 第一个节点肯定不是重复元素
ListNode* cur = head;
// 双指针：cur和 cur.next
while(cur->next != nullptr){
if(cur->next->val != cur->val){
cur = cur->next;
}else{
cur->next = cur->next->next;
}
}
return head;
}
};
删除排序链表中的重复元素 II
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* hair = new ListNode(0,head);
ListNode* cur = hair;
while(cur->next && cur->next->next){
if(cur->next->next->val == cur->next->val) // 数值val存在重复
{
int val = cur->next->val; // 记录数值
// 去掉cur->next之后所有值为val的节点
while(cur->next && cur->next->val == val){
cur->next = cur->next->next;
}
}
else{
cur = cur->next;
}
}
return hair->next;
}
};
反转链表 （Hot 100）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while(cur){
ListNode* temp = cur->next;
cur->next = prev;
prev = cur;
cur =temp;
}
return prev;
}
};
删除链表的倒数第 N 个结点 （Hot 100）
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
// 相邻节点fast slow
ListNode* fast = head;
ListNode* slow = dummy;
// 使得slow和fast之间的节点数为n
for (int i = 0; i < n; ++i) fast = fast->next;
// 同时移动slow和fast，直到fast为nullptr
while (fast) {
fast = fast->next;
slow = slow->next;
}
// 删除倒数第n个节点
slow->next = slow->next->next;
return dummy->next;
}
};
链表的中间结点
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
// fast 速度是slow的两倍，fast达到尾部时，slow到达中间
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
K 个一组翻转链表 （Hot 100）
class Solution {
private:
void reverseGroup(ListNode*& head, ListNode*& tail,int k){
ListNode* pre = nullptr;
ListNode* cur = head;
for(int i = 0 ; i< k; i++){
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0,head);
ListNode* tail = dummy;
while(head){
ListNode* pre = tail;
for(int i = 0 ;i < k; i++){
tail = tail->next;
// 如果节点总数不是 k 的整数倍，那么最后剩余的节点保持原有顺序。
if(!tail) return dummy->next;
}
ListNode* temp = tail->next;
reverseGroup(head, tail, k);
swap(head, tail); // 子链表头变成尾，尾变成头
// 把子链表重新接回原链表
pre->next = head;
tail->next = temp;
head = temp;
}
return dummy->next;
}
};
排序链表 （Hot 100）
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr) return head;
return sort(head, nullptr);
}
// 归并排序
ListNode* sort(ListNode* head, ListNode* tail) {
// 如果链表只有一个节点，将其与后续节点断开并返回该节点
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail && fast->next != tail) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow;
return merge(sort(head, mid), sort(mid, tail));
}
// 升序合并
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) temp->next = temp1;
else if (temp2 != nullptr) temp->next = temp2;
return dummyHead->next;
}
};
倒序同向而行
合并两个有序数组（Hot 100）
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = nums1.size() - 1;
m--;
n--;
while(n >= 0){
if(m >= 0 && nums1[m] > nums2[n]) nums1[i--] = nums1[m--];
else nums1[i--] = nums2[n--];
}
}
};
寻找两个正序数组的中位数（Hot 100）
class Solution {
public:
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
std::vector<int> merged;
int i = 0, j = 0;
int m = nums1.size(), n = nums2.size();
// 合并两个数组
while (i < m && j < n) {
if (nums1[i] < nums2[j]) {
merged.push_back(nums1[i++]);
} else {
merged.push_back(nums2[j++]);
}
}
// 添加剩余的元素
while (i < m) merged.push_back(nums1[i++]);
while (j < n) merged.push_back(nums2[j++]);
int totalSize = merged.size();
if (totalSize % 2 == 1) {
// 奇数个元素，中位数是中间的那个
return merged[totalSize / 2];
} else {
// 偶数个元素，中位数是中间两个数的平均值
return (merged[totalSize / 2 - 1] + merged[totalSize / 2]) / 2.0;
}
}
};
字符串相加
class Solution {
public:
string addStrings(string num1, string num2) {
int i = num1.size() - 1;
int j = num2.size() - 1;
int add = 0;
string result = "";
while(i >= 0 || j >= 0 || add > 0){
int x = i >= 0 ? num1[i] - '0' : 0;
int y = j >= 0 ? num2[j] - '0' : 0;
int val = x + y + add;
result.push_back('0' + val % 10);
add = val / 10;
i --; j--;
}
reverse(result.begin(), result.end());
return result;
}
};
反转字符串中的单词
// https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2361551/151-fan-zhuan-zi-fu-chuan-zhong-de-dan-c-yb1r/
class Solution {
public:
std::string reverseWords(std::string s) {
std::vector<std::string> wordsVector; // 存储分割后的单词的向量
int i, j;
i = s.size() - 1; // i 从字符串末尾开始向前扫描
j = i; // j 用于标记单词的尾字符索引
while (i >= 0) {
// 跳过单词间的空格
while (i >= 0 && s[i] == ' ') i--;
j = i; // 更新单词的尾字符索引
while (i >= 0 && s[i] != ' ') i--; // 找到单词前的空格
// 将找到的单词添加到向量中（注意要避免将空格作为单词存储）
if (i != j) wordsVector.push_back(s.substr(i + 1, (j - i)));
}
std::string result;
// 将向量中的单词连接成一个字符串
for (int n = 0; n < wordsVector.size(); ++n) {
result += wordsVector[n];
if (n != wordsVector.size() - 1) result += ' '; // 添加单词间的空格
}
return result;
}
};
相向而行
有序数组的平方
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size());
int l = 0;
int r = nums.size() - 1;
int pos = nums.size() - 1;
// 非递减数组平方后，数值由两侧向中间递减
while(l <= r){
// 左侧的值比右侧的值高
if(nums[l] * nums[l] > nums[r] * nums[r]){
result[pos] = nums[l] * nums[l];
l++;
}else{ // 右侧的值比左侧的值高
result[pos] = nums[r] * nums[r];
r--;
}
pos--;
}
return result;
}
};
盛最多水的容器 (Hot100)
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0;
int r = height.size() - 1;
int result = 0;
while(l < r){
int capacity = min(height[l],height[r])*(r -l);
result = max(result, capacity);
// 宽度缩小，尝试增大最小高度
if(height[l] <= height[r]) l++;
else r--;
}
return result;
}
};
接雨水 (Hot 100)
class Solution {
public:
int trap(vector<int>& height) {
int l = 0;
int r = height.size() - 1;
int ans = 0;
int left_max = INT_MIN;
int right_max = INT_MIN;
while(l < r){
left_max = max(left_max, height[l]);
right_max = max(right_max, height[r]);
if(height[l] < height[r] ){ // 满足： height[l] < height[r] 且 height[l] <= left_max
ans += left_max - height[l];
l++;
}else{
ans += right_max - height[r];
r--;
}
}
return ans;
}
};
三数之和 (Hot 100)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
// 对数组进行排序，从左到右递增
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
// 跳过第一个数的重复元素以避免重复的三元组
// 保证i在相同值的最左，这样left才可以取相同值
if (i > 0 && nums[i] == nums[i - 1]) continue;
// a≤b≤c，保证了只有 (a,b,c)这个顺序会被枚举到
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) left++; // 如果和小于0，右移左指针，尝试增大值
else if (sum > 0) right--; // 如果和大于0，左移右指针，尝试较小值
else {
// 跳过第二个数的重复元素, 保证left为最右
while (left < right && nums[left] == nums[left + 1]) left++;
// 跳过第三个数的重复元素, 保证left为最左
while (left < right && nums[right] == nums[right - 1]) right--;
// 找到了一个和为0的组合
result.push_back({nums[i], nums[left], nums[right]});
// 继续寻找下一个组合
left++;
right--;
}
}
}
return result;
}
};
反转字符串
class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
int left = 0, right = n - 1;
while (left < right) {
swap(s[left++], s[right--]);
}
}
};
滑动窗口
滑动窗口通过双指针实现，一个指针（右指针）用于扩展窗口，另一个指针（左指针）收缩窗口。与普通的双指针不同的是，滑动窗口法的计算过程一般涉及双指针之间的值，而不仅仅是两个指针指向的值。
无重复字符的最长子串（Hot100)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0;
unordered_set<char> char_set; // 窗口内的字符
int ans = 0;
int left = 0;
for (int right = 0; right < s.size(); right++) {
while (char_set.count(s[right]) != 0) { // 重复了
char_set.erase(s[left]);
left++; // left指向s[right]最后一次出现的地方的下一个位置
}
ans = max(ans, right - left + 1);
char_set.insert(s[right]);
}
return ans;
}
};
找到字符串中所有字母异位词（Hot100)
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int s_len = s.size(), p_len = p.size();
if (s_len < p_len) return vector<int>();
vector<int> ans;
// 存放字符串中字母(a-z)出现的词频
vector<int> s_count(26);
vector<int> p_count(26);
// 当滑动窗口的首位在s[0]处时（相当于放置滑动窗口进入数组）
for (int i = 0; i < p_len; ++i) {
++s_count[s[i] - 'a']; //记录s中前p_len个字母的词频
++p_count[p[i] - 'a']; //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)
}
// 判断放置处是否有异位词
if (s_count == p_count) ans.push_back(0);
//开始让窗口向右进行滑动,遍历起始索引
for (int i = 1; i <= s_len - p_len; ++i) {
// 向右移动滑块：相当于去掉左边第一个字符，在右边加入一个字母
--s_count[s[i - 1] - 'a']; // 左边去掉的字母的词频减1
++s_count[s[i + p_len - 1] - 'a']; // 右边加入的字母的词频加1
if (s_count == p_count) { // 判断滑动后处，是否有异位词
ans.push_back(i);
}
}
return ans;
}
};
最小覆盖子串（Hot100)
class Solution {
public:
// 检查当前窗口是否覆盖目标字符串
bool check(unordered_map<char, int>& map_t,
unordered_map<char, int>& map_s) {
for (const auto& p : map_t) {
if (map_s[p.first] < p.second)
return false;
}
return true;
}
string minWindow(string s, string t) {
// 最小覆盖子串的起始位置和长度
int ans_left = -1, ans_len = INT_MAX;
// map_t：记录目标字符串t中每个字符及其出现次数，
// map_s：记录记录s在当前窗口内每个字符的出现次数
unordered_map<char, int> map_t, map_s;
// 初始化ori：记录目标字符串t每个字符及其出现次数
for (const auto& c : t)
++map_t[c];
// 窗口左右指针
int left = 0, right = 0;
// 向右扩大窗口直到右指针达到s末尾
while (right < int(s.size())) {
// 将字符s[right]加入到map_s中
if (map_t.find(s[right]) != map_t.end())
++map_s[s[right]];
// 当前窗口包含了目标字符串t中的所有字符时
while (check(map_t, map_s) && left <= right) {
if (right - left + 1 <
ans_len) { // 更新最小覆盖子串的起始位置和长度
ans_len = right - left + 1;
ans_left = left;
}
// 将左指针指向的字符从cnt中移除
if (map_t.find(s[left]) != map_t.end())
--map_s[s[left]];
// 移动左指针，缩小窗口
++left;
}
++right; // 向右扩大窗口
}
// 如果ans_left仍为-1，说明s中不存在包含t的子串，返回空字符串
// 否则，返回从ans_left开始，长度为len的子串
return ans_left == -1 ? string() : s.substr(ans_left, ans_len);
}
};
滑动窗口最大值（Hot100)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.size() == 0 || k == 0) return {};
deque<int> deque;
vector<int> result(nums.size() - k + 1);
int left = 1 - k,right = 0;
while(right < nums.size()) {
// 队列最前元素为nums[left-1]，则删除
if(left > 0 && deque.front() == nums[left - 1]) deque.pop_front();
// 单调队列 删除小于nums[right]的数，保持 deque 递减
while(!deque.empty() && deque.back() < nums[right]) deque.pop_back();
// 添加nums[right]
deque.push_back(nums[right]);
// 记录窗口最大值
if(left >= 0) result[left] = deque.front();
left++, right++;
}
return result;
}
};
原文地址：https://blog.csdn.net/weixin_44378835/article/details/138673814
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！