算法篇------动态规划2

动态规划的理解和概念，解题步骤上篇已经说过了。
这里就不再重复赘述了。

1，回文串分割(较难)

牛客网：回文串分割

代码：
时间复杂度 O（n ^ 3） -->可以优化，提前用数组存放前（0，i个）字符是否为回文串(那就是O（n ^ 2）了）
空间复杂度O（n ）

class Solution {
public:
    bool isPal(const string& s, int begin, int end)
    {
         while(begin < end)
         {
             if(s[begin] != s[end])
                 return false;

            begin++;
            end--;
         }

         return true;
    }

    int minCut(string s) 
    { 
        int len = s.size();

        //别人都说多开一个空间方便计算，我就不多开---哈哈
        //因为个人感觉其实也方便多少,而且方便理解下标含义
        vector<int> v(len, 0);  
        
        //n个字符最多切割n - 1次变成回文串
        for(int i = 1; i < len; i++)
              v[i] = i;
        

        for(int i = 1; i < len; i++)
        {
            //前n个字符是回文串，不需要切割
            if(isPal(s, 0, i))
            {
                v[i] = 0;
                continue;
            } 
            
            //(0,j)切割次数 + (j + 1, i)是回文串就+1。
            for(int j = i; j >= 0; j--)
            {
               if(isPal(s, j, i))
                v[i] = min(v[i], v[j-1] + 1);
            }
        }
        
        return v[len-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

2，编辑距离（中等）

牛客网：编辑距离

代码：
时间复杂度： O（n ^ 2）
空间复杂度： O (n ^ 2)

class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        int row = word1.size() + 1;
        int col = word2.size() + 1;
        vector<vector<int>> vv(row, vector<int>(col, 0));

        for(int i = 1; i < row; i++)
          vv[i][0] = i;

        for(int j = 1; j < col; j++)
          vv[0][j] = j;

        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                //删除或者插入操作
                vv[i][j] = min(vv[i-1][j], vv[i][j-1]) + 1;
                
                //数组下标的索引位置 -1
                //各自增加一个字符
                //word1[3] 和  word2[5] 表示 word1的前3个字符word2的前5个字符的最短编辑距离
                if(word1[i-1] != word2[j - 1]) 
                {
                    vv[i][j] = min(vv[i][j], vv[i-1][j-1] + 1);
                }
                else
                {
                    vv[i][j] = min(vv[i][j], vv[i-1][j-1] );
                }
            }
        }

        return vv[row-1][col-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38

3，不同的子序列（中等）

不同的子序列

代码：
时间复杂度：O（n ^2）
空间复杂度： O（n ^ 2）

class Solution {
public:

    int numDistinct(string S, string T) 
    {
        int row = S.size() + 1;
        int col = T.size() + 1;
        vector<vector<int>> vv(row, vector<int>(col, 0));

        for(int i = 0; i < row; i++)
            vv[i][0] = 1;
        
        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                //父字符串新增的不同，只能退回前i- 1个去查找
                if(S[i - 1] != T[j - 1])
                {
                     vv[i][j] = vv[i-1][j];
                }
                else // 如果新增相同，前i-1个肯定可以，那么各自去掉一个相同的也行
                {
                    vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
                }
            }
        }

        return vv[row-1][col-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
25
26
27
28
29
30
31
32

4，通配符匹配（中等）

牛客网：通配符匹配

看题要仔细
‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任何字符序列（包括空序列）。
数据范围：字符串长度满足 0 \le n \le 10000≤n≤1000

意味着，要区分大小写。 并且字符串会出现空的情况
而且极限情况就是：
“*” “” 一个星和一个空的情况 。

代码：
时间复杂度：O（n^2）
空间复杂度：O（n^2）

class Solution {
public:
    bool isMatch(string s, string p) 
    {
       int row = p.size() + 1;
       int col = s.size() + 1;
       vector<vector<bool>> vv(row, vector<bool>(col ,false));
       vv[0][0] = true;  //空和空的匹配

       for(int i = 1; i < row; i++)
       {
           if(p[i-1] == '*')
               vv[i][0] = true;
          else
             break;
       }
      
       for(int i = 1; i < row; i++)
       {
           for(int j = 1; j < col; j++)
           {
               if(p[i - 1] ==  s[j - 1] || p[i - 1 ] == '?')
                 vv[i][j] = vv[i-1][j-1];
               else if(p[i-1] == '*')
                 vv[i][j] = (vv[i-1][j] || vv[i][j-1] || vv[i-1][j-1]);
           }
       }

       return vv[row-1][col-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
25
26
27
28
29
30
31

这个题其实也可以不用动态规划去求解，而是转而用递归的方法去求解可能会更好一些。

class Solution {
public:
    bool match(const char* p, const char* s)
    {
        //同时走到空， 肯定是匹配的
        if(*p == '\0' && *s == '\0')
               return true;
        //这个情况比较特殊
        if(*p == '*' && *s == '\0')
           return match(p+1, s);
        //一个为空，一个不为空，肯定不匹配了
        if(*p == '\0' || *s == '\0')
           return false;

        if(*p == *s)
           return match(p + 1, s  + 1);
        else if(*p == '?')
           return match(p  + 1, s + 1);
        else if(*p == '*')
        {
            //多个* 的作用其实和一个星作用一样
            while(*p == '*')
               p++;

            p--;
            //匹配多个， 匹配一个， 不匹配
            return match(p, s + 1) || match(p + 1, s + 1) || match(p + 1, s);
        }


        return false;
    }

    bool isMatch(string s, string p) 
    {
         return match(p.c_str(), s.c_str());    
    }
};
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
36
37
38

下面看一盗类似的题：

5，字符串通配符

牛客网：字符串通配符

这个题目稍微增加了一丢丢难度，就是这个： 对于@#￥%，，，，这个的特殊字符匹配不了
但是字符串长度都大于 1
：匹配0个或以上的字符（注：能被和?匹配的字符仅由英文字母和数字0到9组成，下同）

代码：

#include 
#include 
using namespace std;

bool match(const char* p, const char* s)
{
    if(*p == '\0' && *s == '\0')
       return true;
    
    if(*p == '\0' || *s == '\0')
       return false;

    if(tolower(*p) == tolower(*s))
       return match(p + 1, s + 1);
    else if(*p == '?')
    {
        if(isdigit(*s) || isalpha(*s))
           return match(p + 1, s + 1);
        else
           return false;
    }
    else if(*p == '*')
    {
        while(*p == '*')
             p++;
        
        p--;

        if(!isdigit(*s) && !isalpha(*s)) //s不是数字或者字母， *只能匹配0个
           return match(p + 1, s);
        else
           return match(p + 1, s + 1) || match(p, s + 1) || match(p + 1, s);
    }

    return false;
}

int main()
{
     string s,p;
     cin >> s >> p;
     bool ret = match(s.c_str(), p.c_str());
     if(ret)
        cout << "true" << endl;
     else
        cout << "false" << 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49

6，跳石板

牛客网：跳石板

代码：

#include 
#include 
#include 
using namespace std;

//获取可以跳的距离
vector<int> get_prime(int n)
{
    vector<int>  v;
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
        {
            v.push_back(i);
            if(n / i != i)
               v.push_back(n/i);
        }
    }

    return v;
}

int Jump(int n , int m)
{
     vector<int> ans(m + 1, INT32_MAX);
     ans[n] = 0; //给一个初始状态

     for(int i = n; i <= m; i++)
     {
         if(ans[i] == INT32_MAX) //如果这个位置是最大值，表明走不到这里
             continue;     

         vector<int> v = get_prime(i);
         for(int j = 0; j < v.size(); j++)
         {
            if(i + v[j] <= m)     //i 表示当前位置 ，v[j]是i的约数，表示可以跳的距离，相加后就变成了可以跳到的位置
               ans[i + v[j]] = min(ans[i] + 1, ans[i + v[j]]);
         }
     }
     
    if(ans[m] == INT32_MAX)
          return -1;

     return ans[m];
}

int main()
{
     int n = 0, m = 0;
     cin >> n >> m;
     cout << Jump(n, m) << 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54