算法刷题篇

[TOC]

最长回文子串

以下方法中：

• maxlen：表示最长回文子串的长度

• begin：表示最长回文子串的起始位置

暴力解法

因为字符串大小在1000以内，所以可以直接暴力

从左到右，遍历每一个字符作为回文子串首字符，然后判断长度为2，3….的子串是否是回文子串

class Solution {
public:
	//判断s[i,j]是否是回文子串
    bool isvalid(string &s, int i, int j){
        int left = i;
        int right = j;
        while(left < right){
            if(s[left++] != s[right--])
                return false;
        }
        return true;
    }

    string longestPalindrome(string s) {
        int n = s.length();
        int maxlen = 1;
        int begin = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(j-i+1>maxlen && isvalid(s,i,j)){
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxlen);
    }
};

$$
时间复杂度：O(n^3)==空间复杂度：O(1)
$$

动态规划

对于长度大于2回文串，去掉首尾的字符仍然是回文串。如回文串’abcba’，去掉两边的’a’，剩下的部分’bcb’仍然是回文串。

所以如果我们要判断一个字符串s[i…j]是否是回文串，我们只需要：

• 判断s[i] == s[j]，若不相等则不是回文串，若相等则进行第2步判断
• 判断s[i+1,…,j-1]是否是回文串，若是则s[i…j]也是回文串

定义dp[i][j]：表示s[i,…,j]是否是回文串

状态转移方程：j-1 - (i+1) + 1 = j-i-1>=2 ==> j-i>=3(保证s[i+1,…,j-1]子串的长度不小于2)
$$
dp[i][j]= \begin{cases}
false,& \text{s[i] != s[j]}
\\ dp[i+1][j-1], & \text{s[i] = s[j]}
\end{cases}
$$
边界条件：

• 长度为1的子串dp[i][i]肯定是回文串，dp[i][i]=true
• 长度为2的子串，dp[i][i+1] = (s[i]==s[i+1]?true:false)

注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int maxlen = 1;
        int begin = 0;
        bool dp[n][n];
        //长度为1的子串一定是回文串
        for(int i=0;i<n;i++) 
            dp[i][i] = true;
        //列举右边界(这里也可以列举子串长度，然后根据左边界计算出右边界)
        //这里之所以先列举右边界是因为右边界可以限制长度，由状态转移方程可知：
        //我们要先判断长度较小的子串是否是回文串
        for(int j=1;j<n;j++){
            //列举左边界
            for(int i=0;i<j;i++){
                if(s[i]!=s[j]){
                    dp[i][j] = false;
                } else {
                    if(j-i>=3)
                        dp[i][j] = dp[i+1][j-1];
                    else   
                        dp[i][j] = true;
                }
                if(dp[i][j] && j-i+1>maxlen){
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxlen);
    }
};

$$
时间复杂度：O(n^2)==空间复杂度：O(n^2)
$$

中心扩散法

对于回文串，其结构是轴对称的，所以我们可以以每一个字符为中心向两边扩散，但是这里得分两种情况。

• 1、回文串长度为奇数：’aca’ ==> 我们以第2个字符向两边扩散，返回长度len1
• 2、回文串长度为偶数：’acca’ ==> 我们以第2，3个字符向两边扩散，返回长度len2
• 然后取长度最大的那个，maxlen=max(len1,len2)，begin = i - (maxlen-1)/2

class Solution {
public:
    //从i,j位置向两边扩散
    //当i==j时，则是奇数的情况
    //当i==j-1时，则是偶数的情况
    int find(string &s, int i, int j){
        int left = i;
        int right = j;
        while(left>=0 && right<s.length() && s[left] == s[right]){
            left--,right++;
        }
        return right-left-1;
    }
    string longestPalindrome(string s) {
        int n = s.length();
        int maxlen = 1;
        int begin = 0;
        
        for(int i=0;i<n;i++){
            int len1 = find(s,i,i);
            int len2 = find(s,i,i+1);
            int len = max(len1,len2);
            if(len>maxlen){
                maxlen = len;
                begin = i - (maxlen-1)/2; //i减去长度的一半就是begin
            }
        }
        return s.substr(begin, maxlen);
    }
};

$$
时间复杂度：O(n^2)==空间复杂度：O(1)
$$

Manacher算法

见Manacher算法博文>_<!!!

正则表达式匹配

定义dp[i][j]：表示 s 的前 i 个字符是否能被 p 的前 j 个字符匹配；

状态转移方程：

• 若p[j-1] == s[i-1] || p[j-1] == '.'，dp[i][j] = dp[i-1][j-1]

• 若p[i-1] == '*'

  • 若p[j-2] != s[i-1] && p[j-2] != '.'，dp[i][j] = dp[i][j-2]
  • 若p[j-2] == s[i-1] || p[j-2] == '.'，dp[i][j] = dp[i][j-2]||dp[i-1][j]
    • 分析如下：

/*
eg：
s：a a a a
		 i
		 
p：a a b a *
		   j
我们知道a*表示a出现0次或者多次，那么分情况讨论
1）a出现0次，则相当于：
s：a a a a
		 i
p：a a b 
	   j-2
所以：dp[i][j] = dp[i][j-2]

2）a出现多次，则相当于：
这里相当于i回退一个(跟完全背包很像)
s：a a a a
         i
p：a a b a *
           j
所以：dp[i][j] = dp[i-1][j]

上面两种情况，有一种情况匹配即可！！！
*/

• others：dp[i][j] = false

边界条件：

• dp[0][0] = true，dp[0][1] = false

• 当 i = 0，j >= 2时：

  • dp[0][j] = p[j-1] == '*' ? dp[0][j-2] : false，因为 s 为空，所以我们只能让 p 中的 * 不断的消去字符

• 当 i !=0，j = 0时：dp[i][0] = false

这里也可以通过状态转移方程去大致确定边界条件：

• 比如在这里，我们求dp[i][j]，时用到了dp[i-1][j-1],dp[i][j-2],dp[i-1][j]，且下标出现了 i-1,j-1,j-2，所以 i ,j 都从1开始，为啥 j 不从2开始呢？因为用到j-2的条件是p[j-1] = '*'，而p[0]不可能为*，所以当 j = 1时，不会使用j-2。所以 i，j都从1开始，那么显然dp[0][j],dp[i][0]等值就需要我们一开始就去填充。
• 所以代码中的memset(dp, false, (m+1)*(n+1))就包含了给dp[i][0]赋值，给others情况赋值

coding：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();
        bool dp[m+1][n+1];
        memset(dp, false, (m+1)*(n+1));
        dp[0][0] = true;
        for(int j = 2; j <= n; j++)
            dp[0][j] = dp[0][j-2] && p[j-1] == '*';
        for(int i = 1; i <= m; i++){
            for(int j = 1; j<= n ; j++){
                if(p[j-1] == s[i-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1];
                else if(p[j-1] == '*') {
                    if(p[j-2] != s[i-1] && p[j-2] != '.') dp[i][j] = dp[i][j-2];
                    else dp[i][j] = dp[i][j-2] || dp[i-1][j];
                }
            }
        }
        return dp[m][n];
    }
};

括号生成

暴力解法

n值很小，直接dfs暴力解：

//l表示当前左括号的数量，r表示当前右括号的数量
//如何l==n且r==n说明成功生成一个括号组合
//如果l<r即当前左括号已经小于右括号的数量，那么也就没必要继续下去了
	//比如'()))',那么不管后面怎么添加左右括号，前面都无法匹配了，也就无效组合
//左右括号应当各一半，所以l>n或r>n直接无效
//每次有两种情况，添加一个左括号或者右括号
class Solution {
public:
    void dfs(vector<string> &ans, string s, int l, int r, int n){
        if(l == n && r == n){
            ans.push_back(s);
            return;
        }

        if(l < r || l > n || r > n) return;

        dfs(ans, s + '(', l + 1, r, n);
        dfs(ans, s + ')', l, r + 1, n);
    }

    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        dfs(ans, "", 0, 0, n);
        return ans;
    }
};

动态规划

<!_!>，实在是太菜了，根本想不会dp呢，只会暴力>-<

打家劫舍系列

打家劫舍Ⅰ

其实就是01问题：对于每一个房屋，我们都只有选或者不选两种选择，而约束就是相邻的房屋不能同时选择

定义dp[i]：表示对于前 i 间房屋，我们能够获得的最大金额（这里的 i 定义为房屋下标即数组下标）

状态转移方程：对于第 i 间房屋，我们有两种选择：

• 选择第 i 间房屋，则第 i-1间房屋则不能选择（这里我们没有提第 i+1间房屋，是因为dp[i]的定义是：前 i 间房屋，与后面的房屋无关），此时：dp[i] = dp[i-2] + nums[i]
• 不选择第 i 间房屋，则前 i-1 间房屋可以获得的最大金额与前 i 间相同，因为第 i 间不选，此时：dp[i] = dp[i-1]
• 然后取两者最大值即可：dp[i] = max(dp[i-2]+nums[i], dp[i-1])

边界条件：在状态转移方程中出现了i-1,i-2，所以 i 从2开始；所以我们需要把dp[0],dp[1]填充；易知：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])（注意dp[i]中对 i 的定义是数组下标）

coding：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int dp[n];
        dp[0] = nums[0];
        dp[1] = nums[0]>nums[1]?nums[0]:nums[1];
        for (int i = 2; i < n; i++){
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
};

打家劫舍Ⅱ

易知最左边和最右边的值不可能同时取得，所以把nums[0,…,n-1]分成两部分nums[1,…,n-1]、nums[0,…,n-2]，这两部分别是打家劫舍I，两边分开算，然后取最大值即可。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        if(n == 2) return nums[0]>nums[1]?nums[0]:nums[1];
        if(n == 3)
            return (nums[0]>nums[1]?nums[0]:nums[1])>nums[2]?(nums[0]>nums[1]?nums[0]:nums[1]):nums[2];

        int dp[n-1][2];
        //dp[n-1][0] ---> nums[0,...,n-1]
        //dp[n-1][1] ---> nums[1,...,n-2]
        dp[0][0] = nums[0];
        dp[1][0] = nums[0]>nums[1]?nums[0]:nums[1];
        dp[0][1] = nums[1];
        dp[1][1] = nums[1]>nums[2]?nums[1]:nums[2];

        for(int i=2; i<n-1; i++){
            dp[i][0] = max(dp[i-2][0]+nums[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-2][1]+nums[i+1], dp[i-1][1]);
        }
        return max(dp[n-2][0], dp[n-2][1]);
    }
};

删除并获得点数

对于该题：如果我们选取了数 x，则 x-1 与 x+1都不能在选取，只要我们选择了x，那么nums中所有的 x 我们都可以选取。x的范围在1~10000之间，所以这题我们可以转换为打家劫舍问题。

我们就认为房屋数量为10001个，每个房屋 i 的金额s为：nums中 i 的个数为 c 个，s = i * c。最终我们所求就为dp[10000]。

coding：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        int sum[10001] = {0};
        int dp[10001] = {0};
        for (int i = 0; i < n; i++)
            sum[nums[i]] += nums[i];
        dp[0] = sum[0];
        dp[1] = sum[0]>sum[1]?sum[0]:sum[1];
        for (int i = 2; i < 10001; i++) {
            dp[i] = max(dp[i-2]+sum[i], dp[i-1]);
        }
        return dp[10000];
    }
};

跳跃游戏

分析可知：我们只需要关注nums[i] == 0的位置，对于nums[i] == 0的位置，如果 i 前面的任何一个位置都无法跳过 i (即跳到 i 前面)，那么就无法到达最终下标；

这里我们从后往前遍历，为什么从后往前呢？其实都行

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return true;
        bool iscanJump = true;
        for(int i = n-2; i>=0 && iscanJump; i--){
            if(!nums[i]){ //如果当前位置为0，则需要判断i前面的是否有位置可以跳过i
                iscanJump = false;
                for(int j = i-1; j>=0 && !iscanJump; j--)
                    //nums[j] > i -j 则表示nums[j]中的值大于i与j的距离，即从j位置可以跳过i
                    if(nums[j] > i - j) iscanJump = true;
            }
        }
        return iscanJump;
    }
};