300.md

【中规中矩】1100. 长度为 K 的无重复字符子串(三种语言实现滑动窗口）

解法1：标准dp转移方程，dp[i]表示以nums[i]结尾的必须包含nums[i]的子序列的最长长度。O(N^2) time, O(N) space

解法2: 了解知识，不建议初学者看。

解法3：贪心思想，用尽可能小的元素组成递增序列，才能方便让后面续接更多的元素。NlgN super fast solution

用下面这个理解走一遍程序理解明白了： Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

class Solution1 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int N = nums.size();
        vector<int> dp(N, 1);
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                // dp[i] means the LIS ending at i
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }

        return res;
    }
};

// 解法2: 了解知识，不建议初学者看。
class Solution2 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int N = nums.size();
        vector<int> top(N, 0);
        int piles = 0;
        for (int i = 0; i < N; i++) {
            int poker = nums[i];
            int left = 0, right = piles;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            // No suitable piles, create a new one
            if (left == piles) {
                piles++;
            }
            top[left] = poker;
        }

        return piles;
    }
};

// 解法3：贪心思想，用尽可能小的元素组成递增序列，才能方便让后面续接更多的元素。
// NlgN super fast solution
class Solution3 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int N = nums.size();
        if (N == 0) {
            return 0;
        }

        int res = 0;
        vector<int> dp;
        dp.push_back(nums[0]);

        for (int i = 1; i < N; i++) {
            auto iter = lower_bound(dp.begin(), dp.end(), nums[i]);
            if (iter == dp.end()) {
                dp.push_back(nums[i]);
            } else {
                *iter = nums[i];
            }
        }

        return dp.size();
    }
};

class Solution1:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [1] * N
        res = 0
        for i in range(0, N):
            for j in range(0, i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])

        return res


class Solution2:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        l = 1
        dp = []
        for i in range(0, n):
            if (not dp) or nums[i] > dp[-1]:
                dp.append(nums[i])
            else:
                r = bisect.bisect_left(dp, nums[i], 0, len(dp))
                dp[r] = nums[i]
        return len(dp)

点我赞赏作者

github 题解