系统故障预测

02 Oct 2024 in Algorithm Pageviews

solve actually problem!

某设备定义了一系列系统事件，当事件发生时会将该事件 ID 记录到日志中，该日志的数据全集称为原始事件序列，根据经验可知，当某一些特征事件出现时，往往预示系统存在需要解决的潜在问题。

现在给定一组原始事件序列 events (元素可重复)，以及一个特征序列 traits (元素不重复)，请在events中从左往右按照匹配规则找到一个匹配特征序列的 最短连续子序列; 如果存在多个最短的，则返回最早匹配到的连续子序列。

匹配规则：对于events 中的某个连续子序列，当从中去除 n 个(n >= 0) 元素后，且不破坏余下元素的相对位置所形成的新序列和特征序列 traits 相同时，则该连续子序列是匹配特征序列的。

注：输入至少保证存在一个匹配的连续子序列。

输入

第一个参数是数组 events，代表原始事件序列，1 < events.length <= 1000

第二个参数是数组 traits，代表特征序列，1 < traits.length <= 20

0 <= events[i], traits[i] <= 1000

输出

一个连续子序列

样例1

输入：

[4,8,4,3,6,6,8] [4,6,8]

输出：

[4,3,6,6,8]

解释：

如event中的一个连续子序列[4,3,6,6,8]，去除其中元素3和任意一个6后，且余下元素保持相对顺序不变，所形成的新序列[4,6,8]和特征序列相同，因此所选择的连续子序列[4,3,6,6,8]是匹配特征序列的。

代码实现如下：

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> MatchLogTrait(const vector<int> &events, const vector<int> &traits)
    {
        vector<int> dp(events.size());
        for (auto len = 0; len < events.size(); len++) {
            for (auto i = 0; i + len < events.size(); i++) {
                if (events[i + len] != traits[dp[i]]) {
                    continue;
                }
                dp[i]++;
                if (dp[i] == traits.size()) {
                    vector<int> result(events.begin() + i, events.begin() + i + len + 1);
                    return result;
                }
            }
        }
        return vector<int>();
    }
    
    vector<int> MatchLogTrait2(const vector<int> &events, const vector<int> &traits)
    {
        if (traits.size() == 1) {
            return {traits[0]};
        }
        
        int left = 0;
        int right = 0;
        int minLen = events.size();
        for (int l = 0; l < events.size(); l++) {
            if (events[l] != traits[0]) {
                continue;
            }
            for (int r = 0, idx = 1; r < events.size() && (r - l + 1 < minLen); r++) {
            	if (events[r] != traits[idx]) {
                    continue;
                }
                
                idx++;
                if (idx == traits.size()) {
                    right = r;
                    left = l;
                    minLen = min(minLen, r - l + 1);
                    break;
                }
            }
        }
        return vector<int>(events.begin() + left, events.begin() + right + 1);
    }
};