题目列表

最大上升子序和

最大子序和

最长回文子串

不同路径

最长回文子序列

正则表达式匹配

最大上升子序列和

题目描述

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。

输入描述:

1
2
输入包含多组测试数据。
每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。

输出描述:

1
对于每组测试数据，输出其最大上升子序列和。

输入

1
2
7
1 7 3 5 9 4 8

输出

1
18

解题思路

从前往后依次计算当前位置的最大子序列和：

​ sum[当前位置] = max( arr[当前位置] , sum[之前] + arr[当前位置])

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	vector<int> arr;
	vector<int> sum;
	sum.resize(1000);
	int length, resMax = 0;
	cin >> length;
	while (!cin.eof() && length--)
	{
		int temp;
		cin >> temp;
		arr.push_back(temp);
	}
	for (int end = 0; end < arr.size() - 1; end++)
	{
		sum[end] = arr[end];
		for (int first = 0; first < end; first++)
		{
			if (arr[first] < arr[end])
			{
				sum[end] = max(sum[end] , arr[end]+sum[first]);
			}
		}
		resMax = max(resMax, sum[end]);
	}
	for (auto it : sum)
		cout << it << "  ";
	cout << resMax << endl;




	return 0;
}

最大子序和

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。`进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
	vector<int> sonSum(nums.size());
	sonSum[0] = nums[0];
	int res = sonSum[0];
	for (int i = 1; i < nums.size(); i++)
	{
		sonSum[i] = max(nums[i], sonSum[i - 1] + nums[i]);
		res = max(res, sonSum[i]);
	}
	return res;
    }
};

最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

代码（时间复杂度高）

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
class Solution {
public:
    string longestPalindrome(string str) {
                //空字符串直接返回0
        if (str.length() == 0) {
            return str;
        }
        //记录下manacher字符串的长度，方便后面使用
        int len = (int)(str.length() * 2 + 1);
        //开辟动态数组chaArr记录manacher化的字符串
        //开辟动态数组pArr记录每个位置的回文半径
        char *chaArr = new char[len];
        int* pArr = new int[len];
        int index = 0;
        for (int i = 0; i < len;i++) {
            chaArr[i] = (i & 1) == 0 ? '#' : str[index++];
        }
        //到此完成对原字符串的manacher化
        //R是最右回文边界，C是R对应的最左回文中心，maxn是记录的最大回文半径
        int R = -1;
        int C = -1;
        int maxn = 0;
        int start=0;
        //开始从左到右遍历
        for (int i = 0; i < len; i++) {
            //第一步直接取得可能的最短的回文半径，当i>R时，最短的回文半径是1，反之，最短的回文半径可能是i对应的i'的回文半径或者i到R的距离
            pArr[i] = R > i ? min(R - i, pArr[2 * C - i]) : 1;
            //取最小值后开始从边界暴力匹配，匹配失败就直接退出
            while (i + pArr[i]<len && i - pArr[i]>-1) {
                if (chaArr[i + pArr[i]] == chaArr[i - pArr[i]]) {
                    pArr[i]++;
                }
                else {
                    break;
                }
            }
            //观察此时R和C是否能够更新
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            //更新最大回文半径的值
            if(maxn<pArr[i]){
                maxn = pArr[i];
                start=(i-maxn+1)/2;
            }
            
        }
        //记得清空动态数组哦
        delete[] chaArr;
        delete[] pArr;
        return str.substr(start,maxn-1);
    }
};

解法二（动态规划）

  • 建立dp[i][j]数组存入s[i:j]这个区间的字符是否是回文串
  • 判断当前区间s[i:j]是否是回文串只需要判断当前s[i]==s[j] && dp[i+1][j-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
class Solution {
public:
string longestPalindrome(string s) {
    int n = s.size();
    //建立dp数组  
    vector<vector<int> > dp(n, vector<int>(n));
    string ans;
    for(int l = 0 ; l < n; ++l)
    {
        for (int i =0;i + l < n; ++i)
        {
            int j = i + l;
            if(l == 0) {
                dp[i][j] = 1;
            } else if(l == 1) {
                dp[i][j] = (s[i] == s[j]);
            } else {
                dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
            }
            //如果发现长度更长的，则更新ans
            if(dp[i][j] && l + 1 > ans.size()){
                ans = s.substr(i , l + 1);
            }
        }
    }
    return ans;
}
};

不同路径

62不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

img

示例 1:

1
2
3
4
5
6
7
8
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例2：

1
2
输入: m = 7, n = 3
输出: 28

解法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int uniquePaths(int m, int n) {
    //动态创建一个二维路径答案表
    int **dp = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * m);
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0) {     //最上一行或者最左一列
                dp[i][j] = 1;
            }
            else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    return dp[n-1][m-1];
    }
};

解法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static int a[101][101] = { 0 };//静态变量放在class外面（类似全局变量），并初始化。
class Solution {
public:

int uniquePaths(int m, int n) {
	if (m == 1 || n == 1)
		return 1;
	if (m == 2)
		return n;
	if (n == 2)
		return m;
	if (a[m][n] > 0)//计算过就直接返回。
		return a[m][n];
	a[m - 1][n] = uniquePaths(m - 1, n);
	a[n][m - 1] = a[m - 1][n];//由于本题的对称性，可以直接复制到对称位置
	a[m][n-1] = uniquePaths(m, n - 1);
	a[n - 1][m] = a[m][n - 1];//由于本题的对称性，可以直接复制到对称位置
	a[m][n] = a[m - 1][n] + a[m][n-1];
	return  a[m][n];//递归法
	}
};

最长回文子序列

516. 最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:

1
2
3
4
5
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。

示例 2:

1
2
3
4
5
输入:
"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。

状态转移

1
2
3
4
5
6
if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for (int i = 0 ; i < n; i++)
            dp[i][i] = 1;
        for (int i = n - 1; i >= 0; i--){
            for (int j = i + 1; j < n; j++){
                //状态转移方程
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j-1]+2;
                else
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
};

正则表达式匹配

10. 正则表达式匹配

强烈推荐大佬的讲解↓！！！

作者：labuladong
链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/

代码

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
class Solution {
public:
    map<string,bool> memo;
    bool dp(string& s, int i,string& p,int j){
        int m = s.size(), n = p.size();
    // base case
    if (j == n) {
        return i == m;
    }
    if (i == m) {
        if ((n - j) % 2 == 1) {
            return false;
        }
        for (; j + 1 < n; j += 2) {
            if (p[j + 1] != '*') {
                return false;
            }
        }
        return true;
    }
    // 记录状态 (i, j)，消除重叠子问题
    string key = to_string(i) + "," + to_string(j);
    if (memo.count(key)) return memo[key];
    bool res = false;
    if (s[i] == p[j] || p[j] == '.') {
        if (j < n - 1 && p[j + 1] == '*') {
            res = dp(s, i, p, j + 2)
               || dp(s, i + 1, p, j);
        } else {
            res = dp(s, i + 1, p, j + 1);
        }
    } else {
        if (j < n - 1 && p[j + 1] == '*') {
            res = dp(s, i, p, j + 2);
        } else {
            res = false;
        }
    }
    // 将当前结果记入备忘录
    memo[key] = res;
    
    return res;
    }
    bool isMatch(string s, string p) {
        return dp(s,0,p,0);
    }
};

一和零

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

1
2
3
4
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

1
2
3
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int S = strs.size();
        vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
        for (int l = 0; l < S; ++l) {
            int zero = 0;
            int one = 0;
            for (int i = 0; i < strs[l].size(); ++i) {
                if (strs[l][i] == '0') ++zero;
                else ++one;
            }
            for (int i = m; i >= zero; --i) {
                for (int j = n; j >= one; --j) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i - zero][j - one]);
                }
            }
        }
        return dp[m][n];
    }
};

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

思路

  1. 计算爬上n-1阶楼梯的方法数量。因为再爬1阶就到第n阶

  2. 计算爬上n-2阶楼梯体方法数量。因为再爬2阶就到第n阶 那么f(n)=f(n-1)+f(n-2);

代码

1
2
3
4
5
6
7
8
9
10
11
12
int climbStairs(int n) {
        if(n==0||n==1)
            return n;
        vector<int> dp(n);
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;i < n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1];
}