数组字符串中的经典算法

数组字符串中的经典算法


最长公共序列(LCS)

例:“abcde”和“decba”,我们用二维数组来记录中间结果。

a b c d e
d 0 0 0 1 0
e 0 0 0 0 1
c 0 0 1 0 0
b 0 1 0 0 0
a 1 0 0 0 0

矩阵斜对角线最长的就是最长公共序列,而我们就是要求最长的由1组成的斜对角线,在矩阵要填1时等于其左上角元素加1。

a b c d e
d 0 0 0 1 0
e 0 0 0 0 2
c 0 0 1 0 0
b 0 1 0 0 0
a 1 0 0 0 0

这样矩阵中的最大元素就是最长公共序列的长度。在构造这个二维数组过程中,我们只需要一行的数据即可,所以可以用一维数组来代替这个矩阵(降低空间复杂度)。

const string LCS(const string& str1, const string& str2)
{
    int x_len = str1.size();
    int y_len = str2.size();
    int max_val = 0, pos = 0;

    vector last_row(x_len);
    last_row.assign(x_len, 0);
    vector cur_row(x_len);

    for (int i = 0; i < y_len; i++) {
        string s = str2.substr(i, 1);
        cur_row.assign(x_len, 0);
        for (int j = 0; j  0 ? last_row[j-1] + 1 : 1;
                if (cur_row[j] > max_val) {
                    max_val = cur_row[j];
                    pos = j;
                }
            } else {
                cur_row[j] = 0;
            }
        }
        last_row = cur_row;
    }
    return str1.substr(pos-max_val+1, max_val);
}


最大子序列和(数组中和最大的连续子序列)

  • 动态规划:只要前i项的和还没有小于0那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。但是你可能需要谨慎一些,在整个数组都为负的情况下,所以初始的和最大值赋值不当的话可能会出问题。

    int max_sum(int* arr, int size)
    {
        int max_val = 1 << 31;
        int sum = 0;
        for (int i = 0; i < size; i++) {
            if (sum < 0) {
                sum = arr[i];
            } else {
                sum += arr[i];
            }
            max_val = max(sum, max_val);
        }
        return max_val;
    }
    
To be a better coder稿源:To be a better coder (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合编程 » 数组字符串中的经典算法

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录