- About
- Contact Us
- Privacy
- Terms of Service
- Copyright Complaint
- Language
- Legacy mode
- Theme
- 京ICP备2025123107号-1
- Worker 0, 144ms
- Powered by Hydro v4.18.0 Community
本题为2024年4月13日美团实习开发岗机考原题
美团机考的介绍点击这里
小美有一个数字串x，她将x的所有非空子序列都取了出来，将其中满足相邻数位两两不同的子序列都加入了集合S 中。
她想知道集合S的大小最终有多大，请你帮她计算一下吧。
(注意:根据数学知识我们知道，集合中的元素具有互异性，即两两不同) (在本题中，子序列可以存在前导0，也就是说如“011”和“00011”是不同的)
输入包含一行一个数字串 x(0≤x≤101000000)，表示塔子哥的数字x。 (x可能含有前导 0)
输出包含一行一个整数，表示集合的大小。 (由于结果可能很大，因此你只要输出答案对 1000000007取的结果)
输入
12121
输出
9
本题关键在于：相邻数位两两不同，那么也就意味着，对于任意一个数c，我们需要更新集合的大小，一定是在集合中寻找不是以c为结尾的那些子序列，然后往它们后面增加一个c ，放入集合中.
此时我们定义状态:dp[i][j] 代表考虑了前i个数位，并且结尾为数字j(0≤j≤9) 的子序列个数。
转移:
假设当前位置i的数字为c
①不是以c为结尾的那些子序列，直接转移到本位置上。
dp[i][j]=dp[i−1][j]②以c为结尾的子序列 ,等于之前所有不是以c为结尾的子序列 + 1 , + 1 是因为自身也独自形成一个子序列
dp[i][j]=∑k=j0→9dp[i−1][k]+dp[i−1][j]
最终答案 : ∑j=09dp[n][j]
s = input()
n = len(s)
# dp[i][j] 代表前i个字符中以j为结尾的相邻两两不同的子序列个数
dp = [[0] * 10 for _ in range(n + 1)]
# 初始化
mod = 10 ** 9 + 7
dp[0][int(s[0])] = 1
for i in range(1, n):
tot = 0 # 总数
now = int(s[i])
# 遍历前一个位置的所有字符
for j in range(10):
# 如果不是当前字符 . 直接等于上一个字符的个数
if j != now:
dp[i][j] = dp[i - 1][j]
tot = (tot + dp[i - 1][j]) % mod
# 对于当前字符，我们需要重新计算
# 等于 总数 - 之前的字符的个数 + 1
# 1是因为当前字符自己也是一个子序列
dp[i][now] = (tot - dp[i - 1][now] + 1 + mod) % mod
print(sum(dp[n - 1]) % mod)
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
string s;
cin >> s;
int n = s.length();
// dp[i][j] 代表前i个字符中以j为结尾的相邻两两不同的子序列个数
vector<vector<long long>> dp(n + 1, vector<long long>(10, 0));
// 初始化
dp[0][s[0] - '0'] = 1;
for (int i = 1; i < n; ++i) {
long long tot = 0; // 总数
int now = s[i] - '0'; // 当前字符
// 遍历前一个位置的所有字符
for (int j = 0; j < 10; ++j) {
// 如果不是当前字符 . 直接等于上一个字符的个数
if (j != now) {
dp[i][j] = dp[i - 1][j];
}
tot = (tot + dp[i - 1][j]) % MOD;
}
// 对于当前字符，我们需要重新计算
dp[i][now] = (tot - dp[i - 1][now] + 1 + MOD) % MOD;
}
// 输出所有结尾位置的子序列个数的和
long long result = 0;
for (int j = 0; j < 10; ++j) {
result = (result + dp[n - 1][j]) % MOD;
}
cout << result << endl;
return 0;
}
import java.util.*;
public class Main {
static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int n = s.length();
// dp[i][j] 代表前i个字符中以j为结尾的相邻两两不同的子序列个数
long[][] dp = new long[n + 1][10];
// 初始化
dp[0][s.charAt(0) - '0'] = 1;
for (int i = 1; i < n; ++i) {
long tot = 0; // 总数
int now = s.charAt(i) - '0'; // 当前字符
// 遍历前一个位置的所有字符
for (int j = 0; j < 10; ++j) {
// 如果不是当前字符 . 直接等于上一个字符的个数
if (j != now) {
dp[i][j] = dp[i - 1][j];
}
tot = (tot + dp[i - 1][j]) % MOD;
}
// 对于当前字符，我们需要重新计算
dp[i][now] = (tot - dp[i - 1][now] + 1 + MOD) % MOD;
}
// 输出所有结尾位置的子序列个数的和
long result = 0;
for (int j = 0; j < 10; ++j) {
result = (result + dp[n - 1][j]) % MOD;
}
System.out.println(result);
sc.close();
}
}