题目链接：编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

方法一：二维数组+动态规划

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < dp[0].size(); j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].size(); j++) {
                // dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                // if (word1[i - 1] == word2[j - 1]) {
                //     dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                // }
                dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp.back().back();
    }
};

题目链接：最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

方法一：二维数组+动态规划

class Solution {
public:
    int f[1010][1010];
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                f[i+1][j+1] = text1[i] == text2[j] ? f[i][j] + 1 : max(f[i][j+1],f[i+1][j]); 
            }
        }
        return f[n][m];
    }
};

题目链接：最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

方法一：中心扩散

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int bestL = 0, bestLen = 1;

    for (int i = 0; i < n; ++i) {
        int l = i - 1, r = i + 1;

        // 吃掉与中心相同的连续字符（处理 "aaaa" 这类）
        while (l >= 0 && s[l] == s[i]) --l;
        while (r < n && s[r] == s[i]) ++r;

        // 再向两边扩展
        while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; }

        int len = r - l - 1;
        int start = l + 1;
        if (len > bestLen) { bestLen = len; bestL = start; }
    }
    return s.substr(bestL, bestLen);
}

方法一优化

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int bestL = 0, bestLen = 1;

    for (int i = 0; i < n; ) {
        int l = i, r = i;
        while (r + 1 < n && s[r + 1] == s[i]) ++r;  // 合并重复中心
        i = r + 1;                                  // 关键：跳到下一段

        // 扩展
        while (l - 1 >= 0 && r + 1 < n && s[l - 1] == s[r + 1]) { --l; ++r; }

        int len = r - l + 1;
        if (len > bestLen) { bestLen = len; bestL = l; }

        // 可选剪枝：如果剩余长度不足以超越 bestLen
        if ((n - i) * 2 + 1 <= bestLen) break;
    }
    return s.substr(bestL, bestLen);
}

题目链接：数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

方法一：堆

class MedianFinder {
public:
    priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半
    priority_queue<int, vector<int>, less<int>> B; // 大顶堆，保存较小的一半
    MedianFinder() { }
    void addNum(int num) {
        if (A.size() != B.size()) {
            A.push(num);
            B.push(A.top());
            A.pop();
        } else {
            B.push(num);
            A.push(B.top());
            B.pop();
        }
    }
    double findMedian() {
        return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;
    }
};

题目链接：寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

方法一：二分

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2,nums1);
        int m = nums1.size();
        int n = nums2.size();
        int half = (m+n+1)/2;
        int l = -1,r = m+1;
        while (l + 1 < r) {
            int mid1 = (l+r) / 2;
            int mid2 = half - mid1;
            int A_left = (mid1 == 0) ? INT_MIN : nums1[mid1-1];
            int A_right = (mid1 == m) ? INT_MAX : nums1[mid1];

            int B_left = (mid2 == 0) ? INT_MIN : nums2[mid2-1];
            int B_right = (mid2 == n) ? INT_MAX : nums2[mid2];

            if (A_left <= B_right && B_left <= A_right) {
                int leftMax = max(A_left,B_left);
                if ((m+n) % 2 == 1) {
                    return (double)leftMax;
                }
                int rightMin = min(A_right, B_right);
                return (leftMax + rightMin) / 2.0;
            }else if(A_left > B_right) {
                r = mid1;
            }else {
                l = mid1;
            }
        }
        return 0.0;
    }
};