力扣经典面试题之双指针 ( 每天更新, 每天一题 )

验证回文串

思路

一: 筛选 + 双指针验证

class Solution {
public:bool isPalindrome(string s) {// 所有大写字母 ==> 小写 去除非字母部分if(s == "") {return true;}string str = "";int s_size = s.size();for(int i = 0; i< s_size; i++) {// 大写字母if(s[i]-'0' >= 'A'-'0' && s[i]-'0' <= 'Z'-'0' ) {str += 'a'+s[i]-'A';}else if ((s[i]-'0' >= 'a'-'0' && s[i]-'0' <= 'z'-'0') || isdigit(s[i])) {str += s[i];}}// 判断回文int str_size = str.size();for(int l = 0, r = str_size-1;l < r ;l++, r-- ) {// 不相等if(str[l] != str[r]) {return false;}}return true;}
};

代码二: 巧用 API
最简单的方法是对字符串 sss 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串
第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串

class Solution {
public:bool isPalindrome(string s) {string sgood;for (char ch: s) {if (isalnum(ch)) {sgood += tolower(ch);}}string sgood_rev(sgood.rbegin(), sgood.rend());return sgood == sgood_rev;}
};

收获

这到题目, 就是简单的双指针例题
在代码中使用到一些函数,可以记一下
tolower(ch) 函数 是把大写字母转成小写字母
isdigit(ch) 函数 是判断该字符是否为数字,也就是 ‘0’ 到 ‘9’

392. 判断子序列

思路
一、 双指针
就是两个字符串都有一个指针
分别移动
二、动态规划

#include <bits/stdc++.h>
using namespace std;bool isSubsequence(string s, string t)
{// 直接暴力int s_size = s.size();int t_size = t.size();int i = 0;int j = 0;for (; i < s_size && j < t_size;){if (s[i] == t[j]){i++;}j++;}if (i == s_size){return true;}else{return false;}
}
int main()
{string s, t;s = "dfadf";t = "dfadf";cout<<isSubsequence(s,t)<<endl;return 0;
}

动态规划

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size(), m = t.size();vector<vector<int> > f(m + 1, vector<int>(26, 0));for (int i = 0; i < 26; i++) {f[m][i] = m;}for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < 26; j++) {if (t[i] == j + 'a')f[i][j] = i;elsef[i][j] = f[i + 1][j];}}int add = 0;for (int i = 0; i < n; i++) {if (f[add][s[i] - 'a'] == m) {return false;}add = f[add][s[i] - 'a'] + 1;}return true;}
};

167. 两数之和 - 输入有序数组

思路
一 、 遍历 + 二分查找 ( 有序 )
二、 直接数组左右两边双指针, 求和遍历
Code

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};}
};

写法二: 这里有空可以研究一下

简单来说就是, 有关于万能模板, 如果遇到这种左边界 或者 右边界 变化时, 需要做出什么样的改变

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {for(int i = 0;i< numbers.size() ; i++ ) {int l = i;// 左边下标int r = numbers.size()-1;    // 这里 需要减1  不减 1 就会出现数组越界    int mid = 0;while( l + 1 != r) {mid = (l+r) / 2;if(numbers[mid] < target - numbers[i]) {l = mid;} else {r = mid;}}// 判断一下if(numbers[r] == target -numbers[i]) {return {i+1,r+1};}}return {-1,-1};}
};

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0;int r = numbers.size()-1;while(l < r) {int sum = numbers[l] + numbers[r];if(sum> target) {r--;} else if(sum < target ) {l++;} else {return {l+1, r+1};}}return {-1,-1};}
};

11.盛开多水的容器

思路

class Solution {
public:int maxArea(vector<int>& height) {// 这里有个关键的点就是// 移动长板一定会变小// 移动短板就可以能变大int max = 0;int l = 0;int r = height.size()-1;while(l < r) {// 计算面积int sum = min(height[r],height[l])*(r-l);if(sum > max) {max = sum;}// 左边小if(height[r] > height[l]) {l++;} else {r--;}}return max;}
};

三数之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int num_size = nums.size();vector<vector<int>> result;// 返回 所有组合    // 排序 + 哈希sort(nums.begin(), nums.end());for(int i = 0; i< num_size; i++) {if(nums[i] > 0 ) {  // 第一个元素大于 0break;}// 去重if(i > 0 && nums[i-1] == nums[i] ) {continue;    // 继续}// 哈希查找unordered_set<int> set;for(int j = i+1; j< num_size; j++) {// 去重 元素 bif(j > i+ 2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]) {continue;}int c = 0-(nums[i] + nums[j]);if(set.find(c) != set.end()) {result.push_back({nums[i],nums[j],c});set.erase(c);} else {set.insert(nums[j]);}}}        return result;}
};

双指针 + 排序

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums)
{sort(nums.begin(), nums.end());vector<vector<int>> result;for (int i = 0; i < nums.size(); i++){int l = i + 1;int r = nums.size() - 1;if (nums[i] > 0){break;}// 去重if (i > 0 && nums[i] == nums[i - 1]){continue;}while (l < r){int sum = nums[i] + nums[l] + nums[r];if (sum > 0){r--;}else if (sum < 0){l++;}else{result.push_back({nums[i], nums[l], nums[r]});while (l < r && nums[r] == nums[r - 1])r--;while (l < r && nums[l] == nums[l + 1])l++;// 继续找符合要求组合r--;l++;}}}return result;
}int main()
{vector<int> vec = {-1,0,1,2,-1,-4};vector<vector<int>> res = threeSum(vec);for(int i=0; i<res.size(); i++) {for(int j=0; j<res[i].size(); j++) {cout<<res[i][j]<<" ";}cout<<endl;}return 0;
}