【c++笔试强训】（第十二篇）

数组中的最⻓连续⼦序列（排序+模拟）

题目解析

讲解算法原理

编写代码

字⺟收集（动态规划-路径问题）

题目解析

讲解算法原理

编写代码

数组中的最⻓连续⼦序列（排序+模拟）

题目解析

1.题目链接：数组中的最长连续子序列_牛客题霸_牛客网

2.题目描述

描述

给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

数据范围： 1 \le n \le 10^51≤n≤105，数组中的值满足 1\le val \le 10^81≤val≤108

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

示例1

输入：

[100,4,200,1,3,2]

返回值：

4

示例2

输入：

[1,1,1]

返回值：

1

备注：

1 \leq n \leq 10^51≤n≤105
1 \leq arr_i \leq 10^81≤arri≤108

讲解算法原理

解法：
算法思路：
排序+模拟
但是要注意处理数字相同的情况！

编写代码

c++算法代码：

class Solution
{
public:int MLS(vector<int>& arr) {sort(arr.begin(), arr.end());int n = arr.size(), ret = 0;for(int i = 0; i < n; ){int j = i + 1, count = 1;while(j < n){if(arr[j] - arr[j - 1] == 1){count++;j++;}else if(arr[j] - arr[j - 1] == 0){j++;}else{break;}}ret = max(ret, count);i = j;}return ret;}
};

java算法代码：

import java.util.*;
public class Solution
{public int MLS (int[] arr) {Arrays.sort(arr);int n = arr.length, ret = 0;for(int i = 0; i < n; ){int j = i + 1, count = 1;while(j < n){if(arr[j] - arr[j - 1] == 1){count++;j++;}else if(arr[j] - arr[j - 1] == 0){j++;}else{break;}}ret = Math.max(ret, count);i = j;}return ret;}
}

字⺟收集（动态规划-路径问题）

题目解析

1.题目链接：字母收集_牛客题霸_牛客网

2.题目描述

描述

有一个 n*mn∗m 的矩形方阵，每个格子上面写了一个小写字母。
小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。
小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。
她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？

输入描述：

1 \leq n,m \leq 5001≤n,m≤500
接下来的 nn 行每行一个长度为 mm 的、仅有小写字母构成的字符串，代表矩形方阵。

输出描述：

小红最大可能的得分。

示例1

输入：

3 2
ab
cd
ef

输出：

1

说明：

选择下、下、右）这条路径即可，可以收集到 acef 这四个字母各一次，获得 0+0+1+0=1 分。

示例2

输入：

2 3
lle
ove

输出：

11

讲解算法原理

解法：
算法思路：
基础的路径问题的dp模型。

编写代码

c++算法代码：

#include <iostream>
using namespace std;
const int N = 510;
char g[N][N];
int dp[N][N];
int m, n;
int main()
{cin >> m >> n;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){cin >> g[i][j];}}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){int t = 0;if(g[i][j] == 'l') t = 4;else if(g[i][j] == 'o') t = 3;else if(g[i][j] == 'v') t = 2;else if(g[i][j] == 'e') t = 1;dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + t;}}cout << dp[m][n] << endl;return 0;
}

Java算法代码：

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), m = in.nextInt();char[][] arr = new char[n + 1][m + 1];for(int i = 1; i <= n; i++){char[] s = in.next().toCharArray();for(int j = 1; j <= m; j++){arr[i][j] = s[j - 1];}}int[][] dp = new int[n + 1][m + 1];for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){int t = 0;if(arr[i][j] == 'l') t = 4;else if(arr[i][j] == 'o') t = 3;else if(arr[i][j] == 'v') t = 2;else if(arr[i][j] == 'e') t = 1;dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + t;}}System.out.println(dp[n][m]);}
}