一、 快慢指针
1. 有序数组原地去重
(1)题目
点击链接
(2)代码
class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 0, fast = 0;while (fast < nums.size()){if (nums[fast] == nums[slow]) fast ++;else{slow ++;nums[slow] = nums[fast];fast ++;}}return slow + 1;}
};
2. 移除元素
点击链接
(1)题目
(2)代码
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0, fast = 0;while (fast < nums.size()){if (nums[fast] == val) fast ++;else{// 与上面题目相区别:// 第一个元素也可能是要被移除的元素,上面的题目不可能有这种情况// 所以不能让slow先走一步,再去赋值// 而是:只要fast探路探到的元素与val不一致,就把该元素赋值给num[slow]// 然后slow ++; fast ++;nums[slow] = nums[fast];slow ++;fast ++;}}return slow;}
};
二、左右指针
1. 反转字符串
(1)题目
点击链接
(2)代码
class Solution {
public:void reverseString(vector<char>& s) {for (int i = 0, j = s.size() - 1; i < j; i ++, j --)swap(s[i], s[j]);for (auto elem : s) cout << elem << ' ';}
};
2. 有序数组两数之和
(1)题目
点击链接
(2)代码
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0, r = numbers.size() - 1;while (l <= r){int sum = numbers[l] + numbers[r];if (sum == target)return vector<int>{l + 1, r + 1};else if (sum < target) l ++;else r --;}return vector<int>{-1, -1};}
};
3. 最长回文子串
(1)题目
点击链接
(2)代码
class Solution {
public:string panlindrome(string s, int l, int r){while (l >= 0 && r < s.size() && s[l] == s[r])l --, r ++;string res = s.substr(l - 1, r - l + 1);return res;}string longestPalindrome(string s) {string res;for (int i = 0; i < s.size(); i ++){// 寻找奇数子串s1string s1 = panlindrome(s, i, i);// 寻找偶数子串s2string s2 = panlindrome(s, i, i + 1);// 取最大的为最长回文子串if (s1.size() > res.size()) res = s1;if (s2.size() > res.size()) res = s2;}return res;}
};