LeetCode 295. 数据流的中位数
原题链接
题目描述
思路
代码
C++
class MedianFinder {
priority_queue<int, vector<int>, greater<int>> up;
priority_queue<int> down;
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if ( down.empty() || num <= down.top() )
{
down.push(num);
if ( down.size() > up.size() + 1 )
{
up.push(down.top());
...
C++运算符重载
运算符重载(操作符重载):可以为运算符增加一些新的功能。
class Point
{
friend Point operator+(const Point &, const Point &);
private:
int x, y;
public:
int get_x() { return this->x; }
int get_y() { return this->y; }
Point(int x, int y) : x(x), y(y) { }
void display()
{
printf("(%d, %d)\n", this->x, this->y);
}
};
Point operator+(const Point &p1, const Point &p2)
{
return Point(p1.x + p2 ...
C++拷贝构造函数
拷贝构造函数的英文:Copy Constructor。
拷贝构造函数是构造函数的一种。
当利用已存在的对象创建一个新对象时(类似于拷贝),就会调用新对象的拷贝构造函数进行初始化。
拷贝构造函数的格式是固定的,接收一个const引用作为参数。
class Car
{
private:
int price;
int length;
public:
Car(int price = 0, int length = 0) : price(price), length(length) { }
// 拷贝构造函数
Car(const Car &car) : price(car.price), length(car.length)
{
printf("Car(Car &car)\n");
}
void display()
{
printf("price = %d, length = %d\ ...
C++特殊成员
静态成员(static)
被static修饰的成员变量/函数。
可以通过对象(对象.静态成员)、对象指针(对象指针->静态成员)、类访问(类名::静态成员)。
静态成员变量
静态成员变量存储在数据段(全局区,类似于全局变量),整个程序运行过程中只有一份内存。
对比全局变量,它可以设定访问权限(public、 protected、 private),达到局部共享的目的。
必须初始化,必须在类外面初始化,初始化时不能带static,如果类的声明和实现分离(在实现.cpp中初始化)。
静态成员函数
内部不能使用this指针(this指针只能用在非静态成员函数内部)。
不能是虚函数(虚函数只能是非静态成员函数)。
内部不能访问非静态成员变量/函数,只能访问静态成员变量/函数。
非静态成员函数内部可以访问静态成员变量/函数。
构造函数、析构函数不能是静态。
当声明和实现分离时,实现部分不能带static。
class Car
{
public:
static int price;
static void run()
{
...
C++中的多态
父类指针、子类指针
父类指针可以指向子类对象,是安全的。(继承方式必须是public)
子类指针指向父类对象是不安全的。
struct A
{
int a;
};
struct B : A
{
int b;
};
int main()
{
// 父类指针指向子类对象
A *a = new B();
delete a;
return 0;
}
多态
多态是面向对象非常重要的一个特性。
同一操作作用于不同的对象,可以有不同的解释,产生不同的执行结果。
在运行时,可以识别出真正的对象类型,调用对应子类中的函数。
使用函数重载来实现传入不同类型的对象,调用同名的函数的,做不同的事情。
struct Dog
{
void speak()
{
printf("Dog::speack\n");
}
void run()
{
printf("D ...
C++中的继承与多继承
继承
可以让子类拥有父类的所有可访问成员(变量/函数)。
C++没有像Java的基类。
语法
在类名后面写个:再接上父类类名即可。Student : Person
struct Person
{
int id;
void run(){ }
};
struct Student : Person
{
int score;
void study() { }
};
struct Worker : Person
{
int salary;
void work() { }
};
关系描述:Person:父类(superclass,超类),Student:子类(subclass,派生类)。
内存布局:像上面的代码,Wroker这个类型的对象占用8个字节,以为父类占4个字节,自己占4个字节。父类的成员变量在前面,子类的在后面。
成员访问权限
成员访问权限、继承方式有3种
public:公共的,任何地方都可以访问(st ...
C++命名空间
可以用来避免命名冲突。
使用namespace 名字来定义一个命名空间。使用的时候,在全局变量、函数或类前面加上空间名字::即可指定命名空间。
class Person
{
private:
int age;
public:
void set_age(int);
int get_age();
};
namespace zhoupb
{
int a;
void fun() { }
class Person
{
private:
int id;
public:
Person(/* args */);
~Person();
void set_id(int id);
int get_id();
};
Person::Person(/* args */) { }
Person::~Pe ...
C++中的类
类
C++中可以使用struct和class来定义一个类。
struct Person
{
int age;
void run()
{
// ...
}
};
class Person1
{
int age;
void run()
{
// ...
}
};
int main()
{
// 创建对象
Person p1;
Person1 p2;
p1.age = 10;
p2.age = 20; // 错误,因为属性权限是private
// 通过指针访问
Person *p3 = &p1;
p3->age = 20;
return 0;
}
C++对象占用的内存空间大小取决于成员变量占用内存空间的总和。成员函数只有一份内存,而且这份内存,不属于对象。
C++对象 ...
C++内存空间的布局
每个应用都有自己独立的内存空间,其内存空间一般都有:代码段(代码区)、数据段(全局区)、栈空间、堆空间。
代码段(代码区)
用于存放代码。
数据段(全局区)
用于存放全局变量等。
栈空间
每调用一个函数,就会给它分配一段连续的栈空间,等函数调用完后,就会回收空间。
堆空间
在程序运行过程,为了能够自由控制内存的生命周期、大小,会经常使用堆空间的内存。
堆空间的申请和释放
如果内存够用,会分配一块连续的内存空间出来。
malloc和free
void * malloc(size_t size)
void free(void *)
int main()
{
int *p = (int *)malloc(4);
*p = 4;
free(p);
char *chs = (char *)malloc(4);
for ( int i = 0; i < 4; i++ )
*(chs + i) = (char) ('A' + i);
// chs[i] = i + 1;
...
C++ const与引用
const
被const修饰的变量不可被修改,在定义的时候,就必须赋值。
如果修改的类、结构体(的指针),其成员已不可以被修改。
struct Date
{
int year;
int month;
int day;
};
int main()
{
const int a = 1;
a = 2; // 错误
const Date d = { 2021, 7, 3 };
Date d1 = { 2021, 8, 3 };
d = d1; // 错误
d.year = 2015; // 错误
Date *p = &d1; // 如果改成 Date *p = &d1,下面3行操作全部都会报错
p->year = 2015; // d1.year: 2015;
(*p).month = 5; // d1.month: 5;
*p = d; // p->year: ...
