leetcode解题报告:最系列

Longest Substring Without Repeating Characters

题目描述:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring"pwke" is a subsequence and not a substring.

Solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        std::vector<int> map(256,-1);
        for (int i = 0, j = 0; i < s.size(); ++i)
        {
            //if (map[s[i]] >= 0)
                j = std::max(j, map[s[i]] + 1);
            map[s[i]] = i;
            if (maxLen < i - j + 1)
                maxLen = i - j + 1;
        }
        return maxLen;
    }
};

思想

更新于2018-3-12 20:45 于北邮小灰楼实验室

使用动态规划的思路解答。设数组dp[i]表示以字符s[i]结尾的最长子串的起始位置,再设置map,保留字符s[i]上一次出现的位置,如果字符s[i]为第一次出现,那么字符s[i]上一次出现的位置为-1。如果字符s[i]上一次出现的位置在以s[i-1]为结尾的最长子串的起始位置的前面,那么以s[i]为结尾的最长子串的起始位置等于以s[i-1]为结尾的最长子串的起始位置,即等于dp[i] = dp[i-1];如果字符s[i]上一次出现的位置在以s[i-1]为结尾的最长子串的起始位置的后面,那么以s[i]为结尾的最长子串的起始位置就是字符s[i]上一次出现位置的下一个,即dp[i] = map[s[i]]+1。综上所述,dp[i]=max(dp[i-1], map[s[i]]+1)。按此思路写成如下代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() <= 1) // 处理不需要计算的情况
            return s.size();
        std::vector<int> map(256, -1);
        std::vector<int> dp(s.size(), 1);
        int maxLen = 1;
        map[s[0]] = 0;
        dp[0] = 0; // 预处理第一个值
        for(int i = 1; i < s.size(); ++i)
        {
            dp[i] = std::max(dp[i-1], map[s[i]]+1);
            map[s[i]] = i; // 记得更新上一次出现的位置
            if(maxLen < i - dp[i] + 1)
                maxLen = i - dp[i] + 1;
        }
        return maxLen;
    }
};

 

Longest Palindromic Substring

题目描述:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

 

Example:

Input: "cbbd"

Output: "bb"

思路:

遍历字符串中的每一个字符。在遍历的过程中,分别假设回文长度是奇数还是偶数,然后以该字符或该字符以及下一个字符为中心向两边搜索,检查是否满足回文条件,并记录最长的回文长度以及起始下标。

Solution:

class Solution {
private:
    int maxLen = 0;
    int startIdx;
public:
    string longestPalindrome(string s) {
        if(s.size() < 2)
            return s;
        for(int i = 0; i < s.size() - 1; ++i)
        {
            extendPalindrome(s, i, i); // odd
            extendPalindrome(s, i, i + 1); // even
        }
        return s.substr(startIdx, maxLen);
    }
    
    void extendPalindrome(const string& s, int i, int j)
    {
        while(i>=0&&j<s.size())
        {
            if( s[i] == s[j])
            {
                --i;
                ++j;
            }
            else
            {
                break;
            }
        }
        if(maxLen < j - i - 1)
        {
            maxLen = j - i - 1;
            startIdx = i + 1;
        }
    }
    
};

Longest Increasing Subsequence

In computer sciencepatience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array.

——摘自维基百科

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?

方法一:动态规划

最优子结构:令dp[0...n]表示以下标为i的元素为最大值的最长递增子序列的长度。若要求解以a[i]为结尾的最长递增子序列长度,先求解以a[j]为结尾的最长递增子序列长度,如果a[i]的数值比a[j]还要大,则dp[i] = max(dp[i], dp[j] + 1)。写成递归公式为:

dp[i]=1, if i = 0;

dp[i] = max(dp[i], dp[j] + 1), for j = 0...i-1 if a[j] < a[i]

dp[i] = 1, otherwirse

对应代码如下

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 1);
        int res = 1;
        for (int i = 1; i < nums.size(); ++i){
                        // 每次外部循环,确定以当前位置为末尾元素的最长子序列;
            for (int j = 0; j < i; ++j){
                if (nums[j] < nums[i]){
                    dp[i] = max(dp[i], 1+dp[j]);
                                // 通过遍历 j 实现对 dp[i] 的更新
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

方法二:时间复杂度为O(n log n)的算法

详细的解释请参考:Longest Increasing Subsequence Size (N log N)

Solution:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for (auto it = nums.begin(); it < nums.end(); ++it)
        {
            auto in = std::lower_bound(dp.begin(), dp.end(), *it);
            if (in == dp.end())
                dp.push_back(*it);
            else
                *in = *it;
        }

        return dp.size();
    }
};

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 2 =

19 − 17 =