当前位置：首页 > article >正文

力扣最长回文字串-5

article 2024/12/1 4:35:51

最长回文字串-5

//双指针，暴力解法
class Solution {
public:
    bool is(string s, int l, int r) // 判断是否为回文
    {
        while (l < r) {
            if (s[l] != s[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    string longestPalindrome(string s) {
        int Max = 0;//用来判断找出最长字串
        int templ = 0, tempr = 0;//用来记录最长字串的头和尾
        char str[1001];//字符数组用来输出找到的最长字串
        for (int i = 0; i < s.length(); i++) {//循环控制左指针l，
            int l = i, r = l + 1;//左值针l初始化为i，右指针初始化为l+1
            while (r < s.length()) {
                if (s[l] != s[r]) {//如果两字符不等，r向右移动
                    r++;
                } else {
                    if (is(s, l, r) && Max < r - l + 1) {//如果是回文并且大于Max记录的之前的最长回文字符串
                        Max = r - l + 1;//Max赋值为新的最长回文字符串的长度
                        templ = l;//记录最长字符串的第一个字符的索引
                        tempr = r;//记录最长字符串的最后一个字符的索引
                    }
                    r++;//向右移动
                }
            }
        }
        int index = 0;
        for (int i = templ; i <= tempr; i++) {
            str[index++] = s[i];
        }
        return str;
    }
};

// 优化，中心扩展法
class Solution {
public:
    string longestPalindrome(string s) {
        char str[1001];
        int Max = 0;// 最大回文长度
        int templ = 0, tempr = 0; // 存储最长回文子串的起始和结束位置

        // 中心扩展法
        for (int i = 0; i < s.length(); i++) {
            // 对于每个字符，检查以该字符为中心的回文（奇数长度）
            int l = i, r = i;
            while (l >= 0 && r < s.length() && s[l] == s[r]) {
                if (r - l + 1 > Max) {
                    Max = r - l + 1;
                    templ = l;
                    tempr = r;
                }
                l--;
                r++;
            }

            // 对于每对相邻字符，检查以这对字符为中心的回文（偶数长度）
            l = i, r = i + 1;
            while (l >= 0 && r < s.length() && s[l] == s[r]) {
                if (r - l + 1 > Max) {
                    Max = r - l + 1;
                    templ = l;
                    tempr = r;
                }
                l--;
                r++;
            }
        }

        int index = 0;
        for (int i = templ; i <= tempr; i++) {
            str[index++] = s[i];
        }
        return str;
    }
};

每日问题

什么是 C++ 中的多继承？它有哪些优缺点？

C++ 中的多继承

多继承（Multiple Inheritance）是指一个类（子类）可以继承自多个父类（基类）。在 C++ 中，类可以有多个父类，从而继承多个类的属性和行为。

语法示例

#include <iostream>
using namespace std;

// 第一个基类
class Base1 {
public:
    void method1() {
        cout << "Method from Base1" << endl;
    }
};

// 第二个基类
class Base2 {
public:
    void method2() {
        cout << "Method from Base2" << endl;
    }
};

// 派生类
class Derived : public Base1, public Base2 {
public:
    void derivedMethod() {
        cout << "Method from Derived" << endl;
    }
};

int main() {
    Derived d;
    d.method1();    // 从 Base1 继承的方法
    d.method2();    // 从 Base2 继承的方法
    d.derivedMethod();  // 自己的方法
    return 0;
}

输出：

Method from Base1
Method from Base2
Method from Derived

在这个示例中，Derived 类继承了 Base1 和 Base2 两个类，能够访问它们的方法。

多继承的优缺点

优点

代码复用：

多继承允许一个子类从多个基类继承行为和属性，从而实现代码的重用。可以将多个基类的功能组合在一个子类中，避免重复编写代码。

更加灵活的类设计：

通过多继承，C++ 提供了更大的灵活性，允许类组合多个功能而不需要通过组合（组合是一种设计模式，也能实现类似的功能）。这使得可以根据需要选择合适的基类来扩展子类的功能。

类功能的组合：

当某些类具有独立的功能时，可以通过多继承将这些功能组合到一个类中，创建更强大的新类。

模拟现实世界中的类关系：

在现实世界中，某个实体可能具有多种功能，C++ 的多继承机制可以模拟这种现象。例如，动物既可以是“哺乳动物”，也可以是“飞行物”，通过多继承可以很好地表示这种双重身份。

缺点

1.菱形继承问题（钻石问题）：

最著名的缺点就是 菱形继承（Diamond Problem）。当多个基类继承自同一个父类时，子类将通过多个路径继承父类的同一成员，可能导致不明确或不一致的继承。此问题会导致数据冗余和二义性，且如果处理不当，可能引发不期望的行为。

示例：菱形继承问题

class A {
public:
    int value;
};

class B : public A {
public:
    void methodB() {
        cout << "Method from B" << endl;
    }
};

class C : public A {
public:
    void methodC() {
        cout << "Method from C" << endl;
    }
};

class D : public B, public C {  // D 继承了 B 和 C
public:
    void methodD() {
        cout << "Method from D" << endl;
    }
};

D 类通过 B 和 C 继承了 A，但 D 可能会遇到访问 A 中成员 value 时的二义性问题，因为 B 和 C 都继承了 A，而且没有明确指定哪个 value 是 D 的成员。

解决方案：虚拟继承

使用 虚拟继承（virtual）来解决菱形继承问题，使得基类 A 的数据成员只被继承一次。

class A {
public:
    int value;
};

class B : virtual public A {
public:
    void methodB() { cout << "Method from B" << endl; }
};

class C : virtual public A {
public:
    void methodC() { cout << "Method from C" << endl; }
};

class D : public B, public C {  // 使用虚拟继承
public:
    void methodD() { cout << "Method from D" << endl; }
};

2.增加复杂度：

多继承往往使得类的层次结构更加复杂，理解和维护起来更具挑战性。每个类的行为可能受到多个基类的影响，这使得类的功能可能更加难以预测。

3.命名冲突和二义性：

如果不同的基类定义了相同名称的成员（变量、函数等），则子类在访问这些成员时会发生二义性冲突，编译器会无法决定应该调用哪个基类的成员。为解决这个问题，C++ 允许使用作用域解析运算符（::）明确指定调用哪个基类的成员。

示例：命名冲突

class A {
public:
    void show() { cout << "A's show" << endl; }
};

class B {
public:
    void show() { cout << "B's show" << endl; }
};

class C : public A, public B {
public:
    void callShow() {
        A::show();  // 使用作用域解析指定调用 A 类的 show
        B::show();  // 使用作用域解析指定调用 B 类的 show
    }
};

4.难以管理的复杂接口：

多继承可能导致不同基类的接口混合在一个子类中，这会使得类的接口变得复杂。如果一个类需要继承多个不同功能的基类，那么它的接口可能会变得不清晰。

总结

优点：

提高代码的重用性。

提供更灵活的设计，可以模拟现实世界中多重身份的类关系。

避免重复代码，允许类继承多个独立的功能。

缺点：

菱形继承问题：可能导致二义性、数据冗余和难以维护的复杂性。

需要谨慎管理命名冲突和接口的复杂性。

增加了类的复杂性，使得代码理解和维护变得更加困难。

解决方案：

使用虚拟继承来解决菱形继承问题。

使用作用域解析符来解决命名冲突。

在设计时，尽量避免过度使用多继承，或者结合其他设计模式（如组合、接口等）来管理复杂性。

什么是虚继承？为什么要使用虚继承？

虚继承 (Virtual Inheritance)

虚继承是 C++ 中用于解决菱形继承问题（即“钻石问题”）的一种技术。在 C++ 中，当多个类继承自同一个基类并且这些类再被子类继承时，可能会出现重复继承同一个基类的情况，这会导致数据冗余和二义性。为了避免这个问题，C++ 引入了虚继承的概念。

虚继承的定义

虚继承的作用是确保一个基类只会被派生类继承一次。即使有多个类通过不同路径继承同一个基类，最终派生类只会拥有基类的一份成员。这样解决了菱形继承问题，避免了重复数据和二义性问题。

虚继承的语法

在 C++ 中，通过 virtual 关键字来声明虚继承。

class A {
public:
    int value;
};

class B : virtual public A {
public:
    void methodB() {
        std::cout << "Method from B" << std::endl;
    }
};

class C : virtual public A {
public:
    void methodC() {
        std::cout << "Method from C" << std::endl;
    }
};

class D : public B, public C {
public:
    void methodD() {
        std::cout << "Method from D" << std::endl;
    }
};

在上面的代码中，B 和 C 都虚继承自 A，即使 D 同时继承了 B 和 C，它也只会有一份 A 的成员。

为什么要使用虚继承？

虚继承的主要作用是解决菱形继承问题，具体包括以下几个方面：

1. 菱形继承问题（钻石问题）

假设有一个类 A，它有两个派生类 B 和 C，然后又有一个类 D 同时继承自 B 和 C，那么 D 类会出现问题：

数据冗余：D 会同时继承 B 和 C 中各自的 A 部分，这样会有两个 A 对象，浪费内存。

二义性：当 D 访问 A 的成员时，编译器不知道该访问 B 中的 A 还是 C 中的 A，从而产生二义性。

这种问题在多继承中很常见，尤其是当多个类继承了同一个基类时，派生类通过不同的路径重复继承了相同的成员。

菱形继承问题的示例：

class A {
public:
    int value;
};

class B : public A {
public:
    void methodB() {
        std::cout << "Method from B" << std::endl;
    }
};

class C : public A {
public:
    void methodC() {
        std::cout << "Method from C" << std::endl;
    }
};

class D : public B, public C {
public:
    void methodD() {
        std::cout << "Method from D" << std::endl;
    }
};

在上面的代码中，D 类通过 B 和 C 继承了两个 A 类的副本。这样，D 会有两份 A 的成员变量 value，并且访问 A 时会产生二义性错误。

2. 虚继承解决菱形继承问题

通过虚继承，C++ 可以保证当一个类通过多个路径继承同一个基类时，基类只有一份副本。这样既解决了数据冗余的问题，也避免了二义性问题。

虚继承解决方案：

class A {
public:
    int value;
};

class B : virtual public A {
public:
    void methodB() {
        std::cout << "Method from B" << std::endl;
    }
};

class C : virtual public A {
public:
    void methodC() {
        std::cout << "Method from C" << std::endl;
    }
};

class D : public B, public C {
public:
    void methodD() {
        std::cout << "Method from D" << std::endl;
    }
};

解释：

B 和 C 都虚继承自 A，这意味着 D 继承 B 和 C 时，A 只会被继承一次。也就是说，D 只有一个 A 类的副本。

如果 D 访问 A 的成员时，编译器知道只有一个 A 成员，避免了二义性。