Jepson's Blog

描述

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围：0 <= |str1|,|str2| <= 20000

要求：空间复杂度 O(n^2)，时间复杂度 O(n^2)

示例

输入："1A2C3D4B56","B1D23A456A"
返回值："123456"

思路

普通的最长公共子序列只需要返回长度，这道题需要返回子序列，而且受空间复杂度限制不能开二维string数组记录。

需要用dp的结果倒推出子序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

string LCS(string s1, string s2) {
    // write code here
    int l1 = s1.length();
    int l2 = s2.length();
    s1 = "+"+s1;
    s2 = "-"+s2;
    int dp[l1+1][l2+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            if(s1[i]==s2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    string ans;
    for(int i=l1,j=l2;dp[i][j]>=1;){
        if(s1[i]==s2[j]){
            ans = s1[i]+ans;
            i--;
            j--;
        }else{
            if(dp[i-1][j]>dp[i][j-1]) i--;
            else j--;
        }
    }
    if(ans.length()==0) ans = "-1";
    return ans;
}

指针和引用的区别

1. 指针所指向的内存空间在程序运行过程中可以改变，而引用所绑定的对象一旦绑定就不能改变。（是否可变）

2. 指针本身在内存中占有内存空间，引用相当于变量的别名，在内存中不占内存空间。（是否占内存）

   *引用的实现实际上是占用内存空间的，但程序把它按照不占用内存空间来处理。

   实际在内存空间上，引用本身也占用一块内存，里面存储着所引用的变量的地址，大小与指针相同，字面上也表现为unsigned long int型。只是经过编译器处理后，访问这块内存时将直接转而访问其指向的内存。因此在程序中无法读取到这块内存本身。

3. 指针可以为空，但是引用必须绑定对象。（是否可为空）

4. 指针可以有多级，但是引用只能一级。（是否能为多级）

友元函数的作用

友元提供了不同类的成员函数之间、类的成员函数与一般函数之间进行数据共享的机制。通过友元，一个不同函数或另一个类中的成员函数可以访问类中的私有成员和保护成员。

private,public,protected的访问范围

private: 只能由该类中的函数、其友元函数访问,不能被任何其他访问，该类的对象也不能访问

protected: 可以被该类中的函数、子类的函数、以及其友元函数访问,但不能被该类的对象访问

public: 可以被该类中的函数、子类的函数、其友元函数访问,也可以由该类的对象访问

注：友元函数包括两种：设为友元的全局函数，设为友元类中的成员函数

类的继承后方法属性变化

使用private继承,父类的所有方法在子类中变为private;

使用protected继承,父类的protected和public方法在子类中变为protected,private方法不变;

使用public继承,父类中的方法属性不发生改变;

1. 分配空间

   创建类对象首先要为该对象分配内存空间。不同的对象，为其分配空间的时机未必相同。全局对象、静态对象、分配在栈区域内的对象，在编译阶段进行内存分配；存储在堆空间的对象，是在运行阶段进行内存分配。

2. 初始化

   首先明确一点：初始化不同于赋值。初始化发生在赋值之前，初始化随对象的创建而进行，而赋值是在对象创建好后，为其赋上相应的值。这一点可以联想下上一个问题中提到：初始化列表先于构造函数体内的代码执行，初始化列表执行的是数据成员的初始化过程，这个可以从成员对象的构造函数被调用看的出来。

3. 赋值

   对象初始化完成后，可以对其进行赋值。对于一个类的对象，其成员变量的赋值过程发生在类的构造函数的函数体中。当执行完该函数体，也就意味着类对象的实例化过程完成了。（总结：构造函数实现了对象的初始化和赋值两个过程，对象的初始化是通过初始化列表来完成，而对象的赋值则才是通过构造函数的函数体来实现。）

注：对于拥有虚函数的类的对象，还需要给虚表指针赋值。

没有继承关系的类，分配完内存后，首先给虚表指针赋值，然后再列表初始化以及执行构造函数的函数体，即上述中的初始化和赋值操作。

有继承关系的类，分配内存之后，首先进行基类的构造过程，然后给该派生类的虚表指针赋值，最后再列表初始化以及执行构造函数的函数体，即上述中的初始化和赋值操作。

1. 为什么拷贝构造函数必须为引用？

   避免拷贝构造函数无限制的递归，最终导致栈溢出。

   因为如果拷贝构造函数的参数不是引用的话，那么就是值传递。而值传递本身又会调用拷贝构造函数，拷贝构造函数又是值传递，值传递又会调用拷贝构造函数……导致无限递归下去。

2. 构造函数的隐式调用

   对已经实例化的对象赋值调用的是赋值函数，对还没实例话的对象赋值调用的是拷贝构造函数，这里使用的就是拷贝构造函数的隐式调用。

   如：

    A a;
    a = b; 调用的是赋值函数
   
    A a(b); 调用的也是拷贝构造函数
   
    A a = b; 调用的是拷贝构造函数（隐式调用）
   

3. C++类对象的初始化顺序

   构造函数调用顺序：

    1. 按照派生类继承基类的顺序，即派生列表中声明的顺序，依次调用基类的构造函数；
    2. 按照派生类中成员变量的声名顺序，依次调用派生类中成员变量所属类的构造函数；
    3. 执行派生类自身的构造函数。
   

   综上可以得出，类对象的初始化顺序：基类构造函数–>派生类成员变量的构造函数–>自身构造函数

   注：

    基类构造函数的调用顺序与派生类的派生列表中的顺序有关；
    成员变量的初始化顺序与声明顺序有关；
    析构顺序和构造顺序相反。
   

4. 为什么用成员初始化列表会快一些？

   原因：用户自定义类型如果使用类初始化列表，直接调用该成员变量对应的构造函数即完成初始化；如果在构造函数中初始化，因为 C++ 规定，对象的成员变量的初始化动作发生在进入构造函数本体之前，那么在执行构造函数的函数体之前首先调用默认的构造函数为成员变量设初值，在进入函数体之后，调用该成员变量对应的构造函数。因此，使用列表初始化会减少调用默认的构造函数的过程，效率高。