面试经典算法题之双指针专题

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

验证回文串

思路

一: 筛选 + 双指针验证

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

代码二: 巧用 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

收获

这到题目, 就是简单的双指针例题
在代码中使用到一些函数,可以记一下
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

动态规划

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;
                else
                    f[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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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

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};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19