c++ 类

代码实例:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
class Stack
{
public:
Stack(int size=1024);
~Stack();
void init();
bool isEmpty();
bool isFull();
void push(int data);
int pop();
private:
int* space;
int top;
};
Stack::Stack(int size)
{
space = new int[size];
top = 0;
}
Stack::~Stack()
{
delete []space;
}
//void Stack::init()
//{
// memset(space,0,sizeof(space));
// top = 0;
//}
bool Stack::isEmpty()
{
return top == 0;
}
bool Stack::isFull()
{
return top == 1024;
}
void Stack::push(int data)
{
space[top++] = data;
}
int Stack::pop()
{
return space[--top];
}
int main()
{
// Stack s;
Stack s(100);
// s.init();
if(!s.isFull())
s.push(10);
if(!s.isFull())
s.push(20);
if(!s.isFull())
s.push(30);
if(!s.isFull())
s.push(40);
if(!s.isFull())
s.push(50);
while(!s.isEmpty())
cout<<s.pop()<<endl;
return 0;
}

1、构造器(Constructor):

在类对象创建时,自动调用,完成类对象的初始化。尤其是动态堆内存的申请。
规则:
1 在对象创建时自动调用,完成初始化相关工作。
2 无返回值,与类名同,
3 可以重载,可默认参数。
4 默认无参空体,一经实现,默认不复存在。

class 类名
{
类名(形式参数)
构造体
}
class A
{
A(形参)
{}
}

比如:

Stack::Stack(int size)
{
space = new int[size];
top = 0;
}

private和public,类对象可以直接访问公有成员,但只有公有成员函数内部来访问对象的私有成员

析造器(Destructor):析构函数的作用,并不是删除对象,而在对象销毁前完成的一些清理工作。
对象销毁时期
1、栈对象离开其作用域。
2、堆对象被手动 delete.

定义:
class 类名
{
~类名()
析造体
}
class A
{
~A()
{}
}

在类对像销毁时,自动调用,完成对象的销毁。尤其是类中己申请的堆内存的释放.
规则:
1 对象销毁时,自动调用。完成销毁的善后工作。
2 无返值,与类名同,无参。不可以重载与默认参数。
3 系统提供默认空析构器,一经实现,不复存在。
Stack::~Stack()
{
delete []space;
}

this 指针

系统在创建对象时,默认生成的指向当前对象的指针。这样作的目的,就是为了带来方
便

1,避免构造器的入参与成员名相同。
2,基于 this 指针的自身引用还被广泛地应用于那些支持多重串联调用的函数中。
比如连续赋值

#include <iostream>
using namespace std;
class Stu
{
public:
Stu(string name, int age) // :name(name),age(age)
{
this->name = name;
this->age = age;
}
Stu & growUp()
{
this->age++;
return *this; // return this; ??
}
void display()
{
cout<<name<<" : "<<age<<endl;
}
private:
string name;
int age;
};
int main()
{
Stu s("wangguilin",30);
s.display();
s.growUp().growUp().growUp().growUp().growUp();
s.display();
return 0;
}

类继承

在 C++中可重用性(software reusability)是通过继承(inheritance)这一机制来实现的。如果没有掌握继承性,就没有掌握类与对象的精华

#include <iostream>
using namespace std;
class Person
{
public:
void eat(string food)
{
cout<<"i am eating "<<food<<endl;
}
};
class Student:public Person
{
public:
void study(string course)
{
cout<<"i am a student i study "<<course<<endl;
}
};
class Teacher:public Person
{
public:
void teach(string course)
{
cout<<"i am a teacher i teach "<<course<<endl;
}
};
int main()
{
Student s;
s.study("C++");
s.eat("黄焖鸡");
Teacher t;
t.teach("Java");
t.eat("驴肉火烧");
return 0;
}

类的继承,是新的类从已有类那里得到已有的特性。或从已有类产生新类的过程就是类的派生。原有的类称为基类或父类,产生的新类称为派生类或子类。派生与继承,是同一种意义两种称谓。

派生类的声明:
class 派生类名:[继承方式] 基类名
{
派生类成员声明;
};

一个派生类可以同时有多个基类,这种情况称为多重继承,派生类只有一个基类,称为单继承。下面从单继承讲起

继承方式规定了如何访问基类继承的成员。继承方式有 public, private, protected。继承方式不影响派生类的访问权限,影响了从基类继承来的成员的访问权限,包括派生类内的访问权限和派生类对象。
简单讲:
公有继承:基类的公有成员和保护成员在派生类中保持原有访问属性,其私有成员仍为基类的私有成员。
私有继承:基类的公有成员和保护成员在派生类中成了私有成员,其私有成员仍为基类的私有成员。
保护继承:基类的公有成员和保护成员在派生类中成了保护成员,其私有成员仍为基类的私有成员

pretected 对于外界访问属性来说,等同于私有,但可以派生类中可见。

#include <iostream>
using namespace std;
class Base
{
public:
int pub;
protected:
int pro;
private:
int pri;
};
class Drive:public Base
{
public:
void func()
{
pub = 10;
pro = 100;
// pri = 1000;
public;
int a;
protected:
int b;
private:
int c
};
//
int main()
{
Base b;
b.pub = 10;
// b.pro = 100;
// b.pri = 1000;
return 0;
}

派生类中的成员,包含两大部分,一类是从基类继承过来的,一类是自己增加的成员。从基类继承过过来的表现其共性,而新增的成员体现了其个性。

几点说明:
1,全盘接收,除了构造器与析构器。基类有可能会造成派生类的成员冗余,所以说基
类是需设计的。
2,派生类有了自己的个性,使派生类有了意义

派生类中由基类继承而来的成员的初始化工作还是由基类的构造函数完成,然后派生类
中新增的成员在派生类的构造函数中初始化。

派生类构造函数的语法:
派生类名::派生类名(参数总表):基类名(参数表),内嵌子对象(参数表)
{
派生类新增成员的初始化语句; //也可出现地参数列表中
}

构造函数的初始化顺序并不以上面的顺序进行,而是根据声明的顺序初始化。
如果基类中没有默认构造函数(无参),那么在派生类的构造函数中必须显示调用基类构
造函数,以初始化基类成员。

代码实现
祖父类
student.h
class Student
{
public:
Student(string sn,int n,char s);
~Student();
void dis();
private:
string name;
int num;
char sex;
};


student.cpp
Student::Student(string sn, int n, char s)
:name(sn),num(n),sex(s)
{
}
Student::~Student()
{
}
void Student:: dis()
{
cout<<name<<endl;
cout<<num<<endl;
cout<<sex<<endl;
}
父类
graduate.h
class Graduate:public Student
{
public:
Graduate(string sn,int in,char cs,float fs);
~Graduate();
void dump()
{
dis();
cout<<salary<<endl;
}
private:
float salary;
};

graduate.cpp
Graduate::Graduate(string sn, int in, char cs, float fs)
:Student(sn,in,cs),salary(fs)
{
}
Graduate::~Graduate()
{
}

 类成员
birthday.h
class Birthday
{
public:
Birthday(int y,int m,int d);
~Birthday();
void print();
private:
int year;
int month;
int day;
};

birthday.cpp
Birthday::Birthday(int y, int m, int d)
:year(y),month(m),day(d)
{
}
Birthday::~Birthday()
{
}
void Birthday::print()
{
cout<<year<<month<<day<<endl;
}

 子类
doctor.h
class Doctor:public Graduate
{
public:
Doctor(string sn,int in,char cs,float fs,string st,int iy,int im,in
t id);
~Doctor();
void disdump();
private:
string title; //调用的默认构造器,初始化为””
Birthday birth; //类中声明的类对象
};

doctor.cpp
Doctor::Doctor(string sn, int in, char cs, float fs, string st, int iy,
int im, int id)
:Graduate(sn,in,cs,fs),birth(iy,im,id),title(st)
{
}
Doctor::~Doctor()
{
}
void Doctor::disdump()
{
dump();
cout<<title<<endl;
birth.print();
}
测试代码
int main()
{
Student s("zhaosi",2001,'m');
s.dis();
cout<<"----------------"<<endl;
Graduate g("liuneng",2001,'x',2000);
g.dump();
cout<<"----------------"<<endl;
Doctor d("qiuxiang",2001,'y',3000,"doctor",2001,8,16);
d.disdump();
return 0;

c++ 内存空间和名称空间

  • 单独编译
  • 存储持续性、作用域和链接性
  • 定位和new运算符
  • 名称空间

  • 存储持续性
  • 定义命名空间:

    NameSpace 是对全局(Global scope)区域的再次划分

    命令空间的声明及 namespace 中可以包含的内容
    namespace NAMESPACE
    {
    全局变量 int a;
    数据类型 struct Stu{};
    函数 void func();
    其它命名空间 namespace
    }

    使用方法:

    直接指定 命名空间: Space::a = 5

    使用 using+命名空间+空间元素:using Space::a; a = 2000;
    使用 using +namespace+命名空间: using namespace Space;

    leetcodeday11 —盛最多水的容器

    本题用到的方法:双指针,在数组首尾部设两个指针,根据指针的值的大小,每次更新一个指针。

    给你 n 个非负整数 a1,a2,...,an每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

    说明:你不能倾斜容器。

    方法1:暴力求解,遍历就完了

    # @lc code=start
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            maxwarter=0
            for i in range(len(height)-1):
                j=i+1
                while j<=len(height)-1:
                    new=min(height[i],height[j])*(j-i)
                    maxwarter=maxwarter if new<maxwarter else new
                    j=j+1
            return maxwarter
    # @lc code=end
    

    然而:超出时间限制了

    官方方法:双指针

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    在初始时,左右指针分别指向数组的左右两端,它们可以容纳的水量为 min(1, 7) * 8 = 8。

    此时我们需要移动一个指针。移动哪一个呢?直觉告诉我们,应该移动对应数字较小的那个指针(即此时的左指针)。这是因为,由于容纳的水量是由

    两个指针指向的数字中较小值 * 指针之间的距离

    决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」不会增加,后者「指针之间的距离」会减小,那么这个乘积会减小。因此,我们移动数字较大的那个指针是不合理的。因此,我们移动 数字较小的那个指针。

    有读者可能会产生疑问:我们可不可以同时移动两个指针? 先别急,我们先假设 总是移动数字较小的那个指针 的思路是正确的,在走完流程之后,我们再去进行证明。

    所以,我们将左指针向右移动:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为min(8,7)∗7=49。由于右指针对应的数字较小,我们移动右指针:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小,我们移动右指针:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为min(8,8)∗5=40。两指针对应的数字相同,我们可以任意移动一个,例如左指针:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为min(6,8)∗4=24。由于左指针对应的数字较小,我们移动左指针,并且可以发现,在这之后左指针对应的数字总是较小,因此我们会一直移动左指针,直到两个指针重合。在这期间,对应的可以容纳的水量为:min(2,8)∗3=6,min(5,8)∗2=10,min(4,8)∗1=4。

    在我们移动指针的过程中,计算到的最多可以容纳的数量为 49,即为最终的答案。

    # @lc code=start
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            maxwarter=0
            i=0
            j=len(height)-1
            while i<j:
                new =min(height[i],height[j])*(j-i)
                maxwarter=new if new>maxwarter else maxwarter
                if height[i]>=height[j]:
                   j=j-1
                else: i=i+1
    
            return maxwarter
    # @lc code=end
    晚安

    leetcodeday9 –回文数

    给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

    回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。

    示例 1:

    输入:x = 121
    输出:true

    示例 2:

    输入:x = -121
    输出:false
    解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

    示例 3:

    输入:x = 10
    输出:false
    解释:从右向左读, 为 01 。因此它不是一个回文数。

    首先我想的是字符串方法:只要判断首尾部的字符是否相同就可

    # @lc code=start
    class Solution:
        def isPalindrome(self, x: int) -> bool:
            s=str(x)
            length=len(s)
            i=0
            while i<=length-1:
                if s[i]==s[length-1]:
                    
                   i=i+1
                   length=length-1
                else:
                    return False
            return True
    
    # @lc code=end
    

    进阶:你能不将整数转为字符串来解决这个问题吗?

    第一想法是反转数字,判断两个数字是否一致:

    # @lc code=start
    class Solution:
        def isPalindrome(self, x: int) -> bool:
            y=x
            if x<0: 
                return False
            rev=0
            while x//10>0:
                rev=rev*10+x%10
                x=x//10
            rev=rev*10+x
            return rev==y

    但是,如果反转后的数字大于int.MAX,我们将遇到整数溢出问题。

    按照第二个想法,为了避免数字反转可能导致的溢出问题,为什么不考虑只反转 int 数字的一半?毕竟,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。

    例如,输入 1221,我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”,并将其与前半部分 “12” 进行比较,因为二者相同,我们得知数字 1221 是回文。

    leetcodeday8 –字符串转换整数 (atoi)

    请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

    函数 myAtoi(string s) 的算法如下:

    • 读入字符串并丢弃无用的前导空格
    • 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
    • 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
    • 将前面步骤读入的这些数字转换为整数(即,”123″ -> 123, “0032” -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
    • 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
    • 返回整数作为最终结果。

    注意:

    • 本题中的空白字符只包括空格字符 ' ' 。
    • 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。

    示例 1:

    输入:s = "42"
    输出:42
    解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
    第 1 步:"42"(当前没有读入字符,因为没有前导空格)
             ^
    第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
             ^
    第 3 步:"42"(读入 "42")
               ^
    解析得到整数 42 。
    由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。

    示例 2:

    输入:s = "   -42"
    输出:-42
    解释:
    第 1 步:"-42"(读入前导空格,但忽视掉)
                ^
    第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
                 ^
    第 3 步:"   -42"(读入 "42")
                   ^
    解析得到整数 -42 。
    由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。

    示例 3:

    输入:s = "4193 with words"
    输出:4193
    解释:
    第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
             ^
    第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
             ^
    第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
                 ^
    解析得到整数 4193 。
    由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。

    示例 4:

    输入:s = "words and 987"
    输出:0
    解释:
    第 1 步:"words and 987"(当前没有读入字符,因为没有前导空格)
             ^
    第 2 步:"words and 987"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
             ^
    第 3 步:"words and 987"(由于当前字符 'w' 不是一个数字,所以读入停止)
             ^
    解析得到整数 0 ,因为没有读入任何数字。
    由于 0 在范围 [-231, 231 - 1] 内,最终结果为 0 。

    示例 5:

    输入:s = "-91283472332"
    输出:-2147483648
    解释:
    第 1 步:"-91283472332"(当前没有读入字符,因为没有前导空格)
             ^
    第 2 步:"-91283472332"(读入 '-' 字符,所以结果应该是负数)
              ^
    第 3 步:"-91283472332"(读入 "91283472332")
                         ^
    解析得到整数 -91283472332 。
    由于 -91283472332 小于范围 [-231, 231 - 1] 的下界,最终结果被截断为 -231 = -2147483648 。

    提示:

    • 0 <= s.length <= 200
    • s 由英文字母(大写和小写)、数字(0-9)、' ''+''-' 和 '.' 组成

    第一次尝试:根据题目要求,就硬写就完了,考虑各种情况:

    # @lc code=start
    class Solution:
        def myAtoi(self, s: str) -> int:
            s=s.lstrip()+" "
            j=0
            if s[0]=="-" and s[1] in  ["0","1","2","3","4","5","6","7","8","9"]: 
               for i in s[1:]:
                   re="-"
                   j=j+1
                   while i not in ["0","1","2","3","4","5","6","7","8","9"] or i==".":
                        return int(s[0:j]) if int(s[0:j])>-2**31 else -2**31
            elif s[0] =="+" and s[1] in  ["0","1","2","3","4","5","6","7","8","9"]:
                for i in s[1:]:
                   j=j+1
                   while i not in ["0","1","2","3","4","5","6","7","8","9"]or i==".":
                        return int(s[1:j])  if int(s[1:j])<2**31-1 else 2**31-1
            elif s[0] in  ["0","1","2","3","4","5","6","7","8","9"]:
                for i in s[1:]:
                   j=j+1
                   while i not in ["0","1","2","3","4","5","6","7","8","9"]or i==".":
                        return int(s[0:j])  if int(s[0:j])<2**31-1 else 2**31-1
            else:return 0 
                
    # @lc code=end
    

    leetcodeday7 –整数反转

    给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

    如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

    假设环境不允许存储 64 位整数(有符号或无符号)。

    示例 1:

    输入:x = 123
    输出:321
    示例 2:

    输入:x = -123
    输出:-321
    示例 3:

    输入:x = 120
    输出:21
    示例 4:

    输入:x = 0
    输出:0
     

    提示:

    -231 <= x <= 231 – 1

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/reverse-integer
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题:这里首先想到的是先转字符串,然后反转字符串,但其实这种方法不能满足系统32位的限制。

    因此参考官方解法,是一种纯数学方法,代码比较简单,但数学推导复杂:

    记 rev 为翻转后的数字,为完成翻转,我们可以重复「弹出」x 的末尾数字,将其「推入」rev 的末尾,直至 x 为 0。

    要在没有辅助栈或数组的帮助下「弹出」和「推入」数字,我们可以使用如下数学方法:

    // 弹出 x 的末尾数字 digit
    digit = x % 10
    x /= 10

    // 将数字 digit 推入 rev 末尾
    rev = rev * 10 + digit

    题目需要判断反转后的数字是否超过 3232 位有符号整数的范围 \([-2^{31},2^{31}-1]\),例如 x=2123456789x=2123456789 反转后的 \(\textit{rev}=9876543212>2^{31}-1=2147483647\),超过了 32 位有符号整数的范围。

    因此我们需要在「推入」数字之前,判断是否满足

    −231≤rev⋅10+digit≤231−1

    若该不等式不成立则返回 0。

    但是题目要求不允许使用 6464 位整数,即运算过程中的数字必须在 3232 位有符号整数的范围内,因此我们不能直接按照上述式子计算,需要另寻他路。

    我们需要在「推入」数字之前,判断是否满足 :

    $$
    \left\lceil\frac{-2^{31}}{10}\right\rceil \leq \operatorname{rev} \leq\left\lfloor\frac{2^{31}-1}{10}\right\rfloor
    $$

    是否成立,若不成立则返回 0

    # @lc code=start
    class Solution:
        def reverse(self, x: int) -> int:
            INT_MIN, INT_MAX = -2**31, 2**31 - 1
    
            rev = 0
            while x != 0:
                # INT_MIN 也是一个负数,不能写成 rev < INT_MIN // 10
                if rev < INT_MIN // 10 + 1 or rev > INT_MAX // 10:
                    return 0
                digit = x % 10
                # Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果,因此这里需要进行特殊判断
                if x < 0 and digit > 0:
                    digit -= 10
    
                # 同理,Python3 的整数除法在 x 为负数时会向下(更小的负数)取整,因此不能写成 x //= 10
                x = (x - digit) // 10
                rev = rev * 10 + digit
            
            return rev
    
            # @lc code=end

    leetcodeday5 –最长回文子串

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

    示例 1:

    输入:s = “babad”
    输出:”bab”
    解释:”aba” 同样是符合题意的答案。
    示例 2:

    输入:s = “cbbd”
    输出:”bb”
    示例 3:

    输入:s = “a”
    输出:”a”
    示例 4:

    输入:s = “ac”
    输出:”a”
     

    提示:

    1 <= s.length <= 1000
    s 仅由数字和英文字母(大写和/或小写)组成

    思路:根据回文串的特点: 回文串中心向两边的元素对称,遍历str每个元素,以该元素为中心,判断i-1和i+1是否一致,如果一致,继续判断i-2和i+2,知道不一致或者达到边界停止,并记录substr长度,但是还必须考虑回文串中心是两个相同的元素的情况。

    # [5] 最长回文子串
    #
    
    # @lc code=start
    class Solution:
        def longestPalindrome(self, s: str) -> str:
            length=len(s)
            mx=""
            if length ==1:
               return s
            if length ==2 and s[0]==s[1]:
                return s
            elif length ==2 and s[0]!=s[1]:
                return s[0]
    #对于回文串中心是单个元素
            for i in range(length):
                start =end = i
                if i ==0: mx=s[0]
                else: 
                    for j in range(i):
                        start -=1
                        end +=1
                        #if start>=0 and end<length: 
                        #   print(i-j-1,i+j+1)
                        if start>=0 and end<length and s[i-j-1]==s[i+j+1]:
    
                            mx=s[i-j-1:i+j+1+1] if 2*j+3>len(mx) else mx
                        else:break
        
    #对于回文串中心是相邻两个元素的情况: 
            for i in range(length):
                end = i
                start =i-1
                if i ==0: continue
                if i ==1 and s[0]==s[1]: 
                    
                    mx=s[0:2] if 2>len(mx) else mx
                    print(mx)
                    continue
                elif s[i]==s[i-1]: 
                    mx=s[i-1:i+1] if 2>=len(mx) else mx
                    print(mx)
                    for j in range(i):
                        start -=1
                        end +=1
                        
                        if start>=0 and end<length and s[i-1-j-1]==s[i+j+1]:
    
                            mx=s[i-1-j-1:i+j+1+1] if 2*j+4>len(mx) else mx
                        else:break
                else:continue
            return mx                  
                   
    # @lc code=end
    

    再来看看官方解法:

    方法一:动态规划
    思路与算法

    对于一个子串而言,如果它是回文串,并且长度大于 22,那么将它首尾的两个字母去除之后,它仍然是个回文串。例如对于字符串 “ababa”,如果我们已经知道 “bab” 是回文串,那么“ababa” 一定是回文串,这是因为它的首尾两个字母都是“a”。

    class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
           return s    
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
    
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界,左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界,就可以退出当前循环
                if j >= n:
                    break
    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
    
                # 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

    方法二:中心扩展算法

    思路与算法

    我们仔细观察一下方法一中的状态转移方程:

    可以发现,所有的状态在转移的时候的可能性都是唯一的。也就是说,我们可以从每一种边界情况开始「扩展」,也可以得出所有的状态对应的答案。

    边界情况即为子串长度为 11 或 22 的情况。我们枚举每一种边界情况,并从对应的子串开始不断地向两边扩展。如果两边的字母相同,我们就可以继续扩展,例如从 P(i+1,j-1)P(i+1,j−1) 扩展到 P(i,j)P(i,j);如果两边的字母不同,我们就可以停止扩展,因为在这之后的子串都不能是回文串了。

    聪明的读者此时应该可以发现,「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为:我们枚举所有的「回文中心」并尝试「扩展」,直到无法扩展为止,此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值,即可得到最终的答案

    class Solution:
       def expandAroundCenter(self, s, left, right):
           while left >= 0 and right < len(s) and s[left] == s[right]:
                 left -= 1
                 right += 1
           return left + 1, right - 1
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

    方法三:Manacher 算法
    还有一个复杂度为 O(n) 的 Manacher 算法。然而本算法十分复杂,一般不作为面试内容。这里给出,仅供有兴趣的同学挑战自己。

    为了表述方便,我们定义一个新概念臂长,表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ,其臂长为 length。

    下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串我们将会在最后与长度为奇数的情况统一起来。

    思路与算法

    在中心扩展算法的过程中,我们能够得出每个位置的臂长。那么当我们要得出以下一个位置 i 的臂长时,能不能利用之前得到的信息呢?

    答案是肯定的。具体来说,如果位置 j 的臂长为 length,并且有 j + length > i,如下图所示:

    当在位置 i 开始进行中心拓展时,我们可以先找到 i 关于 j 的对称点 2 * j – i。那么如果点 2 * j – i 的臂长等于 n,我们就可以知道,点 i 的臂长至少为 min(j + length – i, n)。那么我们就可以直接跳过 i 到 i + min(j + length – i, n) 这部分,从 i + min(j + length – i, n) + 1 开始拓展。

    我们只需要在中心扩展法的过程中记录右臂在最右边的回文字符串,将其中心作为 j,在计算过程中就能最大限度地避免重复计算。

    那么现在还有一个问题:如何处理长度为偶数的回文字符串呢?

    我们可以通过一个特别的操作将奇偶数的情况统一起来:我们向字符串的头尾以及每两个字符中间添加一个特殊字符 #,比如字符串 aaba 处理后会变成 #a#a#b#a#。那么原先长度为偶数的回文字符串 aa 会变成长度为奇数的回文字符串 #a#a#,而长度为奇数的回文字符串 aba 会变成长度仍然为奇数的回文字符串 #a#b#a#,我们就不需要再考虑长度为偶数的回文字符串了。

    注意这里的特殊字符不需要是没有出现过的字母,我们可以使用任何一个字符来作为这个特殊字符。这是因为,当我们只考虑长度为奇数的回文字符串时,每次我们比较的两个字符奇偶性一定是相同的,所以原来字符串中的字符不会与插入的特殊字符互相比较,不会因此产生问题。

    class Solution:
        def expand(self, s, left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return (right - left - 2) // 2
    
        def longestPalindrome(self, s: str) -> str:
            end, start = -1, 0
            s = '#' + '#'.join(list(s)) + '#'
            arm_len = []
            right = -1
            j = -1
            for i in range(len(s)):
                if right >= i:
                    i_sym = 2 * j - i
                    min_arm_len = min(arm_len[i_sym], right - i)
                    cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
                else:
                    cur_arm_len = self.expand(s, i, i)
                arm_len.append(cur_arm_len)
                if i + cur_arm_len > right:
                    j = i
                    right = i + cur_arm_len
                if 2 * cur_arm_len + 1 > end - start:
                    start = i - cur_arm_len
                    end = i + cur_arm_len
            return s[start+1:end+1:2]

    leetcodeday6 –Z 字形变换

    将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

    比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:

    P A H N
    A P L S I I G
    Y I R
    之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”PAHNAPLSIIGYIR”。

    请你实现这个将字符串进行指定行数变换的函数:

    string convert(string s, int numRows);
     

    示例 1:

    输入:s = “PAYPALISHIRING”, numRows = 3
    输出:”PAHNAPLSIIGYIR”


    示例 2:
    输入:s = “PAYPALISHIRING”, numRows = 4
    输出:”PINALSIGYAHRPI”
    解释:
    P I N
    A L S I G
    Y A H R
    P I
    示例 3:

    输入:s = “A”, numRows = 1
    输出:”A”
     

    提示:

    1 <= s.length <= 1000
    s 由英文字母(小写和大写)、’,’ 和 ‘.’ 组成
    1 <= numRows <= 1000

    第一次尝试:分别求奇数和偶数列的对应的字符串下标

    假设:numrows=5,对应位置如果没有元素,设为-1

    $$\begin{bmatrix} 0 & -1 &8 & -1 & 16 \\ 1 & 7 & 9 & 15 & 17 \\ 2 & 6 & 10 & 14 & 18 \\ 3 & 5 & 11 & 13 & 19 \\ 4 & -1 & 12 & -1 & 20 \end{bmatrix}$$

    因为一般是对行操作,所以先将其转置:

    $$\begin{bmatrix} 0 & 1 &2 & 3 & 4 \\ -1 & 7 & 6 & 5 & -1 \\ 8 & 9 & 10 & 11 & 12 \\ -1 & 15 & 14 & 13 & -1 \\ 16& 17 & 18 & 19 & 20 \end{bmatrix}$$

    先求偶数行,因为每行首元素:值为 nextstart+(numRows-1)*2 ,因此每一行的值为List[i]=[j for j in range(nextstart,nextstart+numRows)]

    奇数行:为上一行的尾元素的顺延,奇数行首尾元素为-1:

    List[i][0]=-1
    List[i][numRows-1]=-1
    List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1]

    接下来转置回来,将二维转一维,然后去掉数组中的-1和值大于序列长度的位置:

    List=[i for item in List for i in item if i!=-1 and i<length]

    最后根据一维数组对应位置的值就是新字符串对应下标的字符

    for j in range(length):
                string[j]=s[List[j]]
            return "".join(string) 
    

    其中numrows=1的 情况要单独考虑

    # @lc code=start
    class Solution:
        def convert(self, s: str, numRows: int) -> str:
            length=len(s)
            if length<=numRows or numRows==1 :
                return s
    
            row=(length//((numRows-1)*2)+1)*2
            List=[[-1 for m in range(numRows)] for l in range(row)]
            nextstart=0
        #第i行
            for i in range(row):
    #如果是偶数行:
    
                if(i % 2) == 0:
                    List[i]=[j for j in range(nextstart,nextstart+numRows)]
                    nextstart=nextstart+(numRows-1)*2
                else:
                    List[i][0]=-1
                    List[i][numRows-1]=-1
                    List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1][numRows-1]+1+numRows-2))[::-1]
            List=list(list(i) for i in zip(*List))
            List=[i for item in List for i in item if i!=-1 and i<length]
            string=list(range(length))
            for j in range(length):
                string[j]=s[List[j]]
            return "".join(string) 
                

    改进:

    方法一:按行排序
    思路

    通过从左向右迭代字符串,我们可以轻松地确定字符位于 Z 字形图案中的哪一行。

    算法

    我们可以使用 \(\text{min}( \text{numRows}, \text{len}(s))\) 个列表来表示 Z 字形图案中的非空行。

    从左到右迭代 s,将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

    只有当我们向上移动到最上面的行或向下移动到最下面的行时,当前方向才会发生改变。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/zigzag-conversion
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    c++ 函数进阶

    • 内联函数
    • 引用变量
    • 如何按引用传递参数
    • 默认参数
    • 函数重载指函数参数的数目和类型 不同,不能通过返回类型区别两个同名函数。函数重载不可以根据返回类型区分
    • 函数模板具体化

    1、内联函数

    常规函数和内联函数之间主要的不同是在于c++编译器如何将他们组合到程序中。

    定义内联函数:

    • 在函数声明前 加上关键字 inline
    • 在函数定义前加上关键字 inline

    c语言使用宏来实现内联函数功能:

    #define SQUARE(X) X*X

    2、引用变量

    int & rate = rats

    引用是变量的别名,主要作用是用于函数的形参,通过将引用变量用作参数,函数将使用原始数据,而不是副本。

    c++使用&来声明引用,int & 表示指向int的引用

    函数默认参数

    char * left(const char *str,int n =1)

    参数n的默认值为1,如果不传递n,就默认为一,否则传递的值将覆盖1

    函数重载:

    void print(const char *str,int width);
    void print(double d,int width)
    void print(long l, int width)

    c++允许定义函数名相同的函数,但必须是输入参数的数量和类型不同,如果只是返回类型相同,c++认为这两个是一个函数。

    函数模板: template <typename Anytype> 可以理解为 anyname就是我们的一种数据类型,根据实际情况函数中可以使用不同的数据类型

    定义函数模板:

    template <typename Anytype>
    void Swap(Anytype &a,Anytype &b)
    {
           函数体
    }
    or
    
    
    template <class  Anytype>
    void Swap(Anytype &a,Anytype &b)
    {
           函数体
    }
    
    

    调用:直接 使用 Swap(int x,int y)

    类模板:

    template<typenameT>
    classStack
    {
    }

    GAN系列之—Deep Convolutional GAN(DCGAN)

    DCGAN 的判别器和生成器都使用了卷积神经网络(CNN)来替代GAN 中的多层感知机,同时为了使整个网络可微,拿掉了CNN 中的池化层,另外将全连接层以全局池化层替代以减轻计算量。

    去卷积(反卷积,Deconvolution)

    从上图中可以看到,生成器G 将一个100 维的噪音向量扩展成64 * 64 * 3 的矩阵输出,整个过程采用的是微步卷积的方式。作者在文中将其称为fractionally-strided convolutions,并特意强调不是deconvolutions。

    去卷积(链接:反卷积)又包含转置卷积和微步卷积,两者的区别在于padding 的方式不同,看看下面这张图片就可以明白了:

    3. 训练方法

    DCGAN 的训练方法跟GAN 是一样的,分为以下三步:

    (1)for k steps:训练D 让式子【logD(x) + log(1 – D(G(Z)) (G keeps still)】的值达到最大

    (2)保持D 不变,训练G 使式子【logD(G(z))】的值达到最大

    (3)重复step(1)和step(2)直到G 与D 达到纳什均衡

    4. 相比于GAN 的改进

    DCGAN 相比于GAN 或者是普通CNN 的改进包含以下几个方面:

    (1)使用卷积和去卷积代替池化层

    (2)在生成器和判别器中都添加了批量归一化操作

    (3)去掉了全连接层,使用全局池化层替代

    (4)生成器的输出层使用Tanh 激活函数,其他层使用RELU

    (5)判别器的所有层都是用LeakyReLU 激活函数

    5. 漫游隐空间

    通过使用插值微调噪音输入z 的方式可以导致隐空间结构发生变化从而引导生成图像发生语义上的平滑过度,比如说从有窗户到没窗户,从有电视到没电视等等。

    6. 语义遮罩

    通过标注窗口,并判断激活神经元是否在窗口内的方式来找出影响窗户形成的神经元,将这些神经元的权重设置为0,那么就可以导致生成的图像中没有窗户。从下图可以看到,上面一行图片都是有窗户的,下面一行通过语义遮罩的方式拿掉了窗户,但是空缺的位置依然是平滑连续的,使整幅图像的语义没有发生太大的变化。

    7. 矢量算法

    在向量算法中有一个很经典的例子就是【vector(“King”) – vector(“Man”) + vector(“Woman”) = vector(“Queue”)】,作者将该思想引入到图像生成当中并得到了以下实验结果:【smiling woman – neutral woman + neutral man = smiling man】