阿里笔试题320
阿里笔试题320#
第二题
稍微加了一点 为了便于验证结果输出了最后的字符串
如何是oj提交去掉即可
题目描述
小明在学旋律,每段旋律都可以用字符串来表示,并且旋律的每个
字符的ASCALL码递增的比如以下4段旋律:
aaa bcd bcdef zzz
现在就是要求,小明能够吧这些旋律拼接起来组成最长的旋律.
比如上述例子输出 11 最长的旋律为
aaabcdefzzz
因为每段旋律都是递增的所以:
只需要判断前一个字符串的最后一个字符, 与后一个字符串的第一个字符就可以进行比较
所以还是最长上升子序列, 只不过要输出
思路
对每个字符串进行排序, 先按最后一个字符排序, 如果相同就按照第一个字符排序
然后按照最长上升字符串的思路做就可了
#include <bits/stdc++.h>
#define ends " "
using namespace std;
const int length = 1e6 + 5;
vector<string> strs = {"aaa", "bcd", "bcdef", "zzz"};
int lengthOfMusic(vector<string> &);
bool cmp(const string &a, const string &b) {
if (*a.end() < *b.end()) {
return true;
} else if (*a.end() == *b.end()) {
return *a.begin() < *b.begin();
} else {
return false;
}
}
int main() {
// int n;
// cin >> n;
// strs.resize(n);
// for (int i = 0; i < n; i++) {
// cin >> strs[i];
// }
// 先排序
sort(strs.begin(), strs.end(), cmp);
// 然后利用最长上升子序列的方式求解
lengthOfMusic(strs);
return 0;
}
int lengthOfMusic(vector<string> &nums) {
vector<int> dp(nums.size());
vector<int> pre(nums.size()); // pre 数组 该子序列最后一个字母的上一个字母的标号
if (nums.size() == 1) {
cout << nums[0];
return nums[0].length();
}
for (int i = 0; i < nums.size(); i++) {
dp[i] = strs[i].length();
pre[i] = i;
}
int ans = 1;
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j].back() <= nums[i].front())
if (dp[j] + strs[i].length() > dp[i]) {
dp[i] = dp[j] + strs[i].length();
pre[i] = j;
}
}
}
int tmp = dp[0];
// tmp 得到最长上升子序列的最大值
// ans 保存最长字符串的最后一个字母的标号
for (int i = 1; i < nums.size(); i++) {
if (dp[i] > tmp) {
tmp = dp[i];
ans = i;
}
}
stack<int> sk;
while (true) {
sk.push(ans);
ans = pre[ans];
if (pre[ans] == ans) {
sk.push(ans);
break;
}
}
while (!sk.empty()) {
cout << nums[sk.top()];
sk.pop();
}
return tmp;
} 一点感悟,
还好没有参加 3 20 场不然铁定凉凉, 好菜
我之前完全不懂dp, 是什么都不知道那种, 完全不会, 最简单的dp都没写过
这两天学了学dp, 才勉强做出来, 这篇文章写给跟我一样的小白, 连看不懂大佬题解都看不懂的那种
我是怎么学习 dp 的
*下面是我看过的一些东西 这两天按照下面的顺序看, 看完再把 *PS: 加星号的可以先不看, 不影响做出这个题
爬楼梯问题
国王金矿问题
最长上升子序列问题
- 最长有效括号
这些问题做一下, 并且把不同解法研究明白, 全部用代码实现一下
就应该差不多会做这个题了, 从一个连动态规划是什么都不知道的小白
总算入了点dp的门了, 至少没有那么懵逼了
我是真的小白, 算法题这方面是真的菜, 有问题麻烦大佬门可以指出来
谢谢大佬们了
漫画：什么是动态规划？
最长上升子序列 (LIS) 详解+例题模板 (全)
