快捷搜索:  汽车  科技

c语言使用指针的基本原则:双指针之快慢指针

c语言使用指针的基本原则:双指针之快慢指针// 快慢指针 L = 0 R = 0 while 没有遍历完 if 一定条件 L = 1 R = 1 return 合适的值典型实例:步长不等的快慢指针是指针使用两个步长不同的指针,通常快指针用于读,慢指针用于写。I 步长不等的快慢指针(两个指针步长不同),如用来排除重复元素。II 左右端点指针(两个指针分别指向头尾,并往中间移动,步长不确定),如实现二分查找。III 步长相等的快慢指针(两个指针间距相同,步长相同),如一次遍历(OnePass)求链表的中点或求单链表的倒数第k个元素。

遍历是实现许多算法的基本操作。遍历数据或链表通常通过指针(或索引)在循环内实现指针的移动来进行。

我们遍历一个数组,并输出数组每一项,我们需要一个指针来记录当前遍历的项,这个指针我们可以叫单指针(index)。在某些情况下,可能使用两个这样的指针来遍历更方便问题求解,称为双指针。

c语言使用指针的基本原则:双指针之快慢指针(1)

伪代码:

// 单指针 for(int i = 0;i < nums.size(); i ) { 输出(nums[i]); } // 双指针 int L = 0; int R = nums.size() - 1; while (L < R) { if(一定条件) return 合适的值,一般是 L 和 R 的中点 if(一定条件) L if(一定条件) R-- } // 因为 L == R 因此返回 I 和 R 都是一样的 return L

双指针是指对数据结构(如数组和链表)使用两个指针或两个索引来操作数据,其策略一般有:

I 步长不等的快慢指针(两个指针步长不同),如用来排除重复元素。

II 左右端点指针(两个指针分别指向头尾,并往中间移动,步长不确定),如实现二分查找。

III 步长相等的快慢指针(两个指针间距相同,步长相同),如一次遍历(OnePass)求链表的中点或求单链表的倒数第k个元素。

1 步长不等的快慢指针

步长不等的快慢指针是指针使用两个步长不同的指针,通常快指针用于读,慢指针用于写。

// 快慢指针 L = 0 R = 0 while 没有遍历完 if 一定条件 L = 1 R = 1 return 合适的值

典型实例:

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 int nums[] = {1 1 1 2 2 3};

函数应返回新长度 length = 5 并且原数组的前五个元素被修改为 1 1 2 2 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 int nums[] = {0 0 1 1 1 1 2 3 3};

函数应返回新长度 length = 7 并且原数组的前五个元素被修改为 0 0 1 1 2 3 3 。

你不需要考虑数组中超出新长度后面的元素。

实际上这种问题可以更抽象一步,即“删除排序数组中的重复项,使得相同数字最多出现 k 次” 。 那么这道题 k 就是 2,如果 k 为 1,则是删除重复元素。。

  • 初始化快慢指针 slow , fast ,全部指向索引为 0 的元素。
  • fast 每次移动一格
  • 慢指针选择性移动,即只有写入数据之后才移动。是否写入数据取决于 slow - 2 对应的数字和 fast 对应的数字是否一致。
  • 如果一致,我们不应该写。 否则我们就得到了三个相同的数字,不符合题意。
  • 如果不一致,我们需要将 fast 指针的数据写入到 slow 指针。
  • 重复这个过程,直到 fast 走到头,说明我们已无数字可写。

图解(红色的两个数字,表示我们需要比较的两个数字):

c语言使用指针的基本原则:双指针之快慢指针(2)

code:

#include <stdio.h> // 快慢指针(读写指针) #include <vector> using namespace std; class Solution { public: int removeDuplicates(vector<int>& nums int k) { int i = 0; for(int j=0;j<nums.size();j ) if (i < k || nums[j] != nums[i - k]) { nums[i] = nums[j]; i ; } return i; } }; template <typename TT> void print(TT tt int n) { for(int i=0;i<n;i ) printf("%d " tt[i]); printf("\n"); } int main() { int nums[] = {0 0 1 1 1 1 2 3 3}; int size = sizeof nums / sizeof *nums; vector<int> vc(nums nums size); Solution st; int n = st.removeDuplicates(vc 2); print(nums size); print(vc n); vector<int> vc2(nums nums size); n = st.removeDuplicates(vc2 1); print(vc2 n); getchar(); return 0; } /* 0 0 1 1 1 1 2 3 3 0 0 1 1 2 3 3 0 1 2 3 */2 左右端点指针

两个指针分别指向头尾,并往中间移动,步长不确定。

// 左右端点指针 L = 0 R = n - 1 while L < R if 找到了 return 找到的值 if 一定条件1 L = 1 else if 一定条件2 R -= 1 return 没找到

典型实例:二分查找:

先定义搜索区间(非常重要)

根据搜索区间定义循环结束条件

取中间元素和目标元素做对比(目标元素可能是需要找的元素或者是数组第一个,最后一个元素等)(非常重要)

根据比较的结果收缩区间,舍弃非法解(也就是二分)

如果是整体有序通常只需要nums[mid]和target比较即可。如果是局部有序,则可能需要与其周围的特定元素进行比较。

code:

#include <stdio.h> #include <vector> using namespace std; int binarySearch(vector<int>& nums int target){ if(nums.size() == 0) return -1; int left = 0 right = nums.size() - 1; while(left <= right){ int mid = left ((right - left) >> 1); if(nums[mid] == target){ return mid; } // 搜索区间变为 [mid 1 right] else if(nums[mid] < target) left = mid 1; // 搜索区间变为 [left mid - 1] else right = mid - 1; } return -1; } int main() { int arr[] = {1 2 3 4 5 6 7}; vector<int> vc(arr arr 7); printf("%d\n" binarySearch(vc 5)); getchar(); return 0; }

回文验证:

#include <stdio.h> #include <string> using namespace std; bool isPalindrome(string s) { if (s.empty()) return true; const char* left = s.c_str(); const char* end = left s.length() - 1; while (end > left) { if (!isalnum(*left)) { left; continue;} if (!isalnum(*end)) {--end; continue;} if (tolower(*left) != tolower(*end)) return false; else {--end; left;} } return true; } int main() { string s = "20122102"; string t = "abcabc"; printf("%d %d\n" isPalindrome(s) isPalindrome(t)); getchar(); return 0; }3 步长相等的快慢指针

两个指针步长相同。

// 步长相等的快慢指针 L = 0 R = k while没有遍历完 自定义逻辑 L = 1 R = 1 return 合适的值

典型实例:利用固定间距指针寻找链表中点

利用两个指针fast、slow同时指向头节点,fast指针每次走两步,slow指针每次走一步,当fast指针到达链表尽头时,slow指针就处于链表中点处。

Node* middle(Node* head) { Node* fast *slow; fast = slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; //slow即在中间位置 }

如果链表长度是奇数时,此时slow 正好为中点,如果为偶数,那么slow位置是中间偏右。

典型实例:一次遍历(OnePass)求单链表的倒数第k个元素:

#include<stdio.h> // 一次遍历(OnePass)求单链表的倒数第k个元素 #include<stdlib.h> typedef struct Node { int num; Node *next; }Linklist; Linklist * creat_linklist(); //尾插法创建含有头结点的单链表 int Search_K(Linklist *h int k) //双指针算法查找节点 { Linklist *fast = h->next; Linklist *slow = h->next; int count = 0; // 计数器 while(fast!=NULL) { fast = fast->next; if(count < k) count ; else slow = slow->next; } if(count < k) //如果K大于链表的长度情况 { printf("您要查找的节点不存在!"); return 0; } else { printf("倒数第%d个节点的数据为:%d\n" k slow->num); printf("*** 查找完成!***"); return 1; } } Node* middle(Node* head) { Node* fast *slow; fast = slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; //slow即在中间位置 } void print(Linklist* head) { while(head->next != NULL) { printf("%d " head->next->num); head = head->next; } printf("%\n"); } int main() { int k; Linklist *head; head = (Linklist *)malloc(sizeof(Linklist)); head = creat_linklist(); print(head); printf("中间节点是:%d\n" *middle(head)); printf("请输入要查找的倒数第几个节点:"); scanf("%d" &k); Search_K(head k); while(1); return 0; } Linklist * creat_linklist() { int n=0 t=1; Linklist *h *p *q; h = q =(Linklist *)malloc(sizeof(Linklist)); for(int i=0;i<100;i ) { p = (Linklist *)malloc(sizeof(Linklist)); p->num = i 1; q->next = p; q = p; } q->next = NULL; return h; }

在一些场合还需要考虑使用三个指针,如链表逆转:

ListNode* reverseList(ListNode* head) { ListNode* prev = NULL; ListNode* cur = head; ListNode* next = NULL; while(cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

ref:

https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/two-pointers

-End-

猜您喜欢: