双指针法
双指针法：一般是指的在遍历对象的过程中，不是使用单个指针进行访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。
一般双指针法有两种表现方式：
同向移动：在同向移动时，指针互相之间间隔一个距离进行移动
相向移动：在相向移动中，双指针一个指针在开头，另外一个指针在结尾，根据满足的条件进行移动指针；
同向移动案例
案例一（移动零）
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]输出: [1,3,12,0,0]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/move-zeroes著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
两种解题思路：
1.第一种暴力赋值的方法，遍历数组，统计零的个数，然后赋值原来的数组
2.双指针思想；遍历数组，用 i 和 j 一起记录，将数组中非零的数据移动到前面，用 j 记录移动的位置；
解题代码：
第一种:
class Solution {public: void moveZeroes(vector<int>& nums) { if(nums.empty()) { return ; } vector<int>res; int sum = 0; for(int i=0;i<nums.size();i++) { if(nums[i] == 0) { sum +=1; } else { res.push_back(nums[i]); } } while(sum>0) { res.push_back(0); sum--; } nums = res; }};
复制代码
第二种：（双指针法）
class Solution {public: void moveZeroes(vector<int>& nums) { if(nums.empty()) { return ; } int i=0,j=0; for(;i<nums.size();i++) { if(nums[i] != 0) { nums[j] = nums[i]; j++; } } for(int i=j;j<nums.size();j++) { nums[j] = 0; } }};
复制代码
相向移动案例
案例一（ 两数之和 II - 输入有序数组）
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2]解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解题思路：
双指针法：第一个指针指向开头，第二个指针指向结尾，根据两个指针所指的数据的和与目标值进行比较，移动指针
解题代码：
class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int>res; if(numbers.size() == 0) { return res; } //双指针 int len = numbers.size(); for(int i=0,j=len-1;i<len,j>=0,j>i;) { if(numbers[i]+numbers[j] > target) { j--; } else(numbers[i]+numbers[j] < target) { i++; } else { return {i+1,j+1}; } } return res; }};
复制代码
这个题优化的话，可以使用二分法的方式；每次使用target的值与中间值进行比较，变换最高值和最低值进行移动，这样效率更高；
class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { for (int i = 0; i < numbers.size(); ++i) { int low = i + 1, high = numbers.size() - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (numbers[mid] == target - numbers[i]) { return {i + 1, mid + 1}; } else if (numbers[mid] > target - numbers[i]) { high = mid - 1; } else { low = mid + 1; } } } return {-1, -1}; }};
复制代码
案例二(回文链表)
请判断一个链表是否为回文链表。
示例 1:
示例 2:
解题思路：
双指针法：首先将指针进行移动，由于是回文链表，我们将两个指针移动至链表中间，然后将其中一个链表进行翻转，然后比较每个链表的值进行遍历；
注：如果长度是奇数，则向后遍历的链表需要多移动一位；
这个题思路既涉及到了同向指针移动和相向指针移动；
解题代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL) { return true; } ListNode* slow = head; ListNode* fast = head; ListNode* pre = NULL; while(fast!= NULL && fast->next != NULL) { //为了让指针指向中间 fast = fast->next->next; //翻转链表 ListNode* tmp = slow->next; slow->next = pre; pre = slow; slow = tmp; } //如果fast不是空，则是是奇数 if(fast != NULL) { slow = slow->next; } while(pre && slow) { if(pre->val != slow->val) { return false; } pre = pre->next; slow = slow->next; } return true; }};
复制代码
案例三（验证回文串）
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"输出: true 示例 2:
输入: "race a car"输出: false
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-palindrome著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
双指针法：首先去除掉无用字符，然后将一个指针指向靠头，另外一个指针指向结尾，一个从左往右，一个从右往左进行遍历操作，每次相等即为回文字符串，否则为非回文字符串；
解题代码：
class Solution {public: bool isPalindrome(string s) { string res; for(auto ch:s) { if(isalnum(ch)) { res += tolower(ch); } } int begin = 0; int end = res.size()-1; while(begin < end) { if(res[begin] != res[end]) { return false; } begin++; end--; } return true; }};
复制代码
首发微信公众号：后台服务器开发
评论