wap网站开发联系电话,seo站点是什么意思,做商城的网站程序,某公司网站源码双指针法前言167.两数之和 II - 输入有序数组88.合并两个有序数组142. 环形链表 II633.平方数之和680. 验证回文字符串 Ⅱ27. 移除元素344. 反转字符串剑指 Offer 05. 替换空格151. 翻转字符串里的单词206.反转链表125. 验证回文串19. 删除链表的倒数第 N 个结点面试题 02.02. …
双指针法前言167.两数之和 II - 输入有序数组88.合并两个有序数组142. 环形链表 II633.平方数之和680. 验证回文字符串 Ⅱ27. 移除元素344. 反转字符串剑指 Offer 05. 替换空格151. 翻转字符串里的单词206.反转链表125. 验证回文串19. 删除链表的倒数第 N 个结点面试题 02.02. 返回倒数第 k 个节点前言
双指针主要用于遍历数组两个指针指向不同的元素从而协同完成任务。也可以延伸到多个数组的多个指针。
若两个指针指向同一数组遍历方向相同且不会相交则也称为滑动窗口两个指针包围的区域即为当前的窗口经常用于区间搜索。
若两个指针指向同一数组但是遍历方向相反则可以用来进行搜索待搜索的数组往往是排好序的。
167.两数之和 II - 输入有序数组 题解
这道题还是比较简单的因为数组已经排好序了所以我们很容易就想到一个方法
我们可以使用两个指针s,ls,ls,l其中sss指向最小值lll指向最大值。当两指针的和小于目标值时sss指针向右移动当两指针的和大于目标值时lll指针向左移动这样一定可以得到最优解就是这样。
代码
//过于简单我就不写注释了。
vectorint twoSum(vectorint numbers, int target)
{int l 0, r numbers.size() - 1, sum;while (l r) {sum numbers[l] numbers[r];if (sum target) break;if (sum target) l;else --r;}return vectorint{l 1, r 1};
}
88.合并两个有序数组 题解 因为这两个数组已经排好序我们可以把两个指针分别放在两个数组的末尾即 nums1 的 m m 1 位和 nums2 的 n n 1 位。每次将较大的那个数字复制到 nums1 的后边然后向前移动一位。 因为我们也要定位 nums1 的末尾所以我们还需要第三个指针以便复制。 在以下的代码里我们直接利用 m 和 n 当作两个数组的指针再额外创立一个 ppp 指针起 始位置为 mn,n1m n ,n 1mn,n1。每次向前移动 mmm 或 nnn 的时候也要向前移动 ppp。这里需要注意如果 numnumnum 的数字已经复制完不要忘记把 nums2 的数字继续复制如果 nums2 的数字已经复制完剩余 nums1 的数字不需要改变因为它们已经被排好序。
这道题用图更好理解所以推荐查看leetcode官方解题
注意 a 和 a都是a1,但是a 返回a然后再将a1 a返回a1。
代码
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int p m-- n-- -1; //这里厨初始化p m n -1,就指向nums1的最后一位然后n--m--。while(m0 n0){nums1[p--] nums1[m] nums2[n] ? nums1[m--] : nums2[n--];//三目运算符 }while(n 0){nums1[p--] nums2[n--]; }}
};142. 环形链表 II 题解 这道题可以使用快慢指针解决快指针fastfastfast慢指针slowslowslow快指针每次走两步满指针每次走一步如果链表中存在环路那么快指针和慢指针一定会相遇。 当 slow 和 fast 第一次相遇时我们将 fast 重新移动到链表开头并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时相遇的节点即为环路的开始点。
代码
class Solution {
public:ListNode *detectCycle(ListNode *head) {if (head NULL || head-next NULL)//这种情况下一定没环{return NULL;}ListNode* fasthead;ListNode* slowhead;//初始哈快慢指针while (fast-next !NULL fast-next-next ! NULL)//确保环存在{fastfast-next-next;//快指针一次走两步slowslow-next;//慢指针一次走一步。if (fastslow)//如果快慢指针相遇{slowhead;//慢指针移到链表头while (slow ! fast){slowslow-next;fastfast-next;}//指针再次相遇即为环路开始点。return slow;}}return NULL;//如果不存在环路返回NULL。}
};633.平方数之和 题解 因为CCC为两个数的平方值和所以这两个数都小于sqrt(C)sqrt(C)sqrt(C)我们初始化两个指针一个初始化为0另一个初始化为sqrt(C)1sqrt(C)1sqrt(C)1因为sqrt()sqrt()sqrt()向下取整所以要加1。如果两数平方值的和大于CCC右指针向左移动如果小于左指针向右移。
代码 class Solution {
public:bool judgeSquareSum(int c) {unsigned int left 0,right sqrt(c)1;//初始化左右指针unsigned int powSum;//两数平方的和while(rightleft){powSum left*leftright*right;if(powSumc) return true;else if(powSumc) --right;else if(powSumc) left;}return false;}
};680. 验证回文字符串 Ⅱ 题解
代码
//太简单不写注释
class Solution {
public:bool checkPalindrome(const string s, int low, int high) {for (int i low, j high; i j; i, --j) {if (s[i] ! s[j]) {return false;}}return true;}bool validPalindrome(string s) {int low 0, high s.size() - 1;while (low high) {char c1 s[low], c2 s[high];if (c1 c2) {low;--high;} else {return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low 1, high);}}return true;}
};
27. 移除元素 题解
先来个暴力解法
class Solution {
public:int removeElement(vectorint nums, int val) {int size nums.size();for(int i 0;i size;i){if(nums[i]val){for(int j i1;jsize;j){nums[j-1] nums[j];}--i;--size;}}return size;}
};暴力解法是可以通过的但是你能满足吗你不能满足 下面是双指针法
代码
class Solution {
public:int removeElement(vectorint nums, int val) {int slowIndex 0;for(int fastIndex 0;fastIndexnums.size();fastIndex){if(val ! nums[fastIndex])//如果快指针指向val的值慢指针就会停止直到快指针指向不同的值。{nums[slowIndex] nums[fastIndex];}}return slowIndex;}
};344. 反转字符串
题解
其实这道题可以直接用C的库函数解决但这样没有什么意义。
我们定义两个指针也可以说是索引下表一个从字符串前面一个从字符串后面两个指针同时向中间移动并交换元素。
代码
class Solution {
public:void swap(char i,char j){//这是一种不常见的交换元素方式根据^异或的性质a ^ a 0。参见《深入理解计算机系统》i ^ j;j ^ i;i ^ j;}void reverseString(vectorchar s) {for(int i 0,js.size()-1;is.size()/2;i,--j){swap(s[i],s[j]);} }
};
剑指 Offer 05. 替换空格
题解 如果想把这道题目做到极致就不要只用额外的辅助空间了
首先扩充数组到每个空格替换成 “%20” 之后的大小。
然后从后向前替换空格也就是双指针法过程如下
iii指向新长度的末尾jjj指向旧长度的末尾。 代码
class Solution {
public:string replaceSpace(string s) {int count 0; // 统计空格的个数int sOldSize s.size();for (int i 0; i s.size(); i) {if (s[i] ) {count;}}// 扩充字符串s的大小也就是每个空格替换成%20之后的大小s.resize(s.size() count * 2);int sNewSize s.size();// 从后先前将空格替换为%20for (int i sNewSize - 1, j sOldSize - 1; j i; i--, j--) {if (s[j] ! ) {s[i] s[j];} else {s[i] 0;s[i - 1] 2;s[i - 2] %;i - 2;}}return s;}
};
151. 翻转字符串里的单词 206.反转链表 代码
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur head;ListNode* pre NULL;while(cur) {temp cur-next; // 保存一下 cur的下一个节点因为接下来要改变cur-nextcur-next pre; // 翻转操作// 更新pre 和 cur指针pre cur;cur temp;}return pre;}
};
125. 验证回文串 代码
class Solution {
public:bool isPalindrome(string s) {string str;for(auto i : s){if(isalnum(i))//先除了字母和数字之外的其他字符//isalnum()函数用来判断是否是字母或者是数字{str tolower(i);}}for(int i 0,j str.size()-1; ij; i,--j)//通过前后两个指针判断是否对称。{if(str[i] ! str[j]){return false;}}return true;}
};
19. 删除链表的倒数第 N 个结点 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if(!head-next) return nullptr;//如果链表就一个元素那也只能去掉一个所以就返回nullptr。ListNode* fast head;ListNode* slow head;//初始化快指针//快指针先走n步然后慢指针在和快指针同步走这样的话当快指针走到链表结尾时慢指针刚好到达我们要去掉的元素之前的一个元素//这样slow-next slow - next -next就可以从链表中去掉要除去的元素了。for(int i 0; in;--n){fastfast-next;if(!fast)//如果快指针为nullptr说明点前题目要去除的元素为第一个元素那么直接返回链表的第二个元素就可以了。{return head-next;}}while(fast-next){slow slow-next;fast fast-next;}slow-next slow-next-next;return head;}
};面试题 02.02. 返回倒数第 k 个节点 题解 这种题的双指针解法大同小异没有什么新意… 代码 * Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode* fast head;ListNode* slow head;for(int i 0;ik;--k){fast fast-next;if(!fast){return head - val;}}while(fast){fast fast-next;if(!fast){return slow-next-val;}slow slow-next;}return -1;//这块有一点不完美//因为程序不可能运行到这所以返回啥都可以。}
};持续更新中…
