Leetcode 1713. 得到子序列的最少操作次数（DAY 191）

╰半夏微凉° 2022-09-16 08:49 86阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷dp超时 TLE 76 / 82）
     *  代码实现（首刷自解优化 二分 + 贪心优化）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷dp超时 TLE 76 / 82） ##

--------------------

class Solution { 
    public:
        int minOperations(vector<int>& target, vector<int>& arr) { 
            int last_pos = -1;
            unordered_map<int,int> map,cnt;
            list<int> list;
            int max_save = 0;
            for(int i=0;i<target.size();++i)    map[target[i]] = i;
            for(const auto& num:arr)
            { 
                if(map.find(num) == map.end())  continue;
                auto pos = map[num];
                if(!pos) cnt[pos] = 1;
                else
                { 
                    int tmp = cnt[pos];
                    for(int i=0;i < pos;++i)
                        tmp = max(tmp,cnt[i] + 1);
                    cnt[pos] = tmp;
                    max_save = max(max_save,tmp);
                } 
            }
            return target.size() - max_save;
        }
    };

--------------------

## 代码实现（首刷自解优化 二分 + 贪心优化） ##

--------------------

class Solution { 
    public:
        int minOperations(vector<int>& target, vector<int>& arr) { 
            int last_pos = -1;
            unordered_map<int,int> map,cnt;
            vector<int> v;
            int max_save = 0;
            for(int i=0;i<target.size();++i)    map[target[i]] = i;
            for(const auto& num:arr)
            { 
                if(map.find(num) == map.end())  continue;
                auto pos = map[num];
                if(v.empty())    v.emplace_back(pos);
                else
                { 
                    auto iter = lower_bound(v.begin(),v.end(),map[num]);
                    if(iter == v.end()) v.emplace_back(pos);
                    else    *iter = pos;
                } 
                max_save = max(static_cast<int>(v.size()),max_save);
            }
            return target.size() - max_save;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/47833d1c97864d64821e19e94bfb1c98.png