【LeetCode从零单刷】Longest Increasing Subsequence

3541 ワード

LeetCode C++ LIS 最長上昇サブシーケンス

タイトル:
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18] , The longest increasing subsequence is [2, 3, 7, 101] , therefore the length is 4 . Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
回答:
最長上昇サブシーケンス(LIS)を探して、最も基本的な方法はダイナミックプランニングです.遷移方程式はdp[i]=max{dp[j]}+1(-1解釈も非常に直感的である:dp[i]は現在のi要素を取得すれば達成できる最長LISを表す.このシーケンスを印刷する必要がある場合は、前の要素を保存するだけです.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int size = nums.size();
        if (size <= 1)  return size;
        
        vector<int> dp(size, 1);
        int maxlen;
        for (int i = 1; i < size; i++) {
            maxlen = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && maxlen < dp[j]) maxlen = dp[j];
            }
            dp[i] = maxlen + 1;
        }
        
        maxlen = 0;
        for (int i = 0; i < size; i++) {
            if (dp[i] > maxlen) maxlen = dp[i];
        }
        return maxlen;
    }
};

O(n log n)time complexityに変更する場合は?欲張り法+二分検索.
補助的な順序(ordered)スタック(キュー......タスクを完了すればよい)を追加し、できるだけ長いLISを保存します.スタックへのアクセス要件は次のとおりです.

a[0]をスタック

に入れる

スタックトップ要素top(最大要素)と読み出された要素a[i](0

-a[i]>topの場合、a[i]をスタックに入れる.

-a[i]<=topの場合、a[i]より大きいスタックの1番目の数を2分割して検索し、それをa[i]で置き換えます(スタックトップ要素が置き換えられた場合、より長いシーケンスに達する機会があることを示します).

最長シーケンス長は、スタックのサイズ

である.
xとyについて、x例:元のシーケンスは1,5,8,3,6,7である
最初は1,5,8が相次いでスタックに入り、このとき3を読み、5を3で置き換え、1,3,8を得る.さらに6を読み、8を6で置き換え、1、3、6を得る.さらに7を読み,最終スタックを1,3,6,7とした.最長増分子シーケンスは長さ4
しかし,この方法には,シーケンス長の正確性しか保証できず,スタック内が正しいシーケンスであることを保証できないという大きな欠陥がある.
例:元のシーケンスは1,5,8,2であり、スタック内の最後は1,2,8が正しいシーケンスではない.
分析してみると、正しいシーケンスが得られない場合もあるが、最後に算出された個数は間違いない.なぜだろうか.
a[i]>topの場合、総個数は直接1を加え、これは間違いない.しかし、a[i]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> LIS;
        for (int i = 0; i < nums.size(); i++) {
            if (LIS.size() == 0 || LIS[LIS.size() - 1] < nums[i]) {
                LIS.push_back(nums[i]);
            }
            else {
                int l = 0, r = LIS.size() - 1;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (LIS[m] >= nums[i]) {
                        r = m;
                    }
                    else {
                        l = m + 1;
                    }
                }
                LIS[l] = nums[i];
            }
        }
        return LIS.size();
    }
};

参考資料:
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://blog.csdn.net/yorkcai/article/details/8651895
https://leetcode.com/discuss/67888/c-clean-o-nlogn-code-using-binary-search

hdu 1009猫鼠取引!!c++

leetcodeの349.Intersection of Two Arrays(C++解法ハッシュテーブルとvector)