阿里笔试题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) 详解+例题模板 (全)

• LeetCode 32，并不Hard的难题，解法超级经典，带你领略动态规划的精彩

题

台阶问题
最长上升子序列
最长有效括号