数组字符串中的经典算法

综合编程 2016-04-15

数组字符串中的经典算法


最长公共序列(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

责编内容by:To be a better coder (源链)。感谢您的支持!

您可能感兴趣的

raft-java —— 分布式一致性算法 Raft 的 Java 实现... raft-java Raft implementation library for Java. 参考自 Raft论文 和Raft作...
:聊聊 FaceID 背后的深度学习视觉算法 在上周发布的iPhoneX中,最吸引我的,不是那蠢萌的兔耳朵,而是苹果的FaceID。在苹果用FaceID取代TouchID的背后,是强大的视觉算法支持,让iP...
【万字总结】图解堆算法、链表、栈与队列(多图预警)... 堆算法 什么是堆 堆(heap),是一类特殊的数据结构的统称。它通常被看作一棵树的数组对象。在队列中,调度程序反复提取队列中的第一个作业并运行...
The Breadth-First-Search Algorithm I remember when I was younger I used to play the game of hide-and-seek a lo...
机器学习单挑数学界:最新算法仲裁数列之美(附论文)... e iπ + 1 = 0 ,这是数学史上最美妙的公式之一 —— 欧拉公式。 它揭示了表面看似无关的数学领域之间的深层联系,是数学界的伟大奇观之一。而这...