0%


LeetCode 常见题型

题型 知识点 题目
回文/子串/子序列 滑动窗口 #3 #76
动态规划 #3 #5 #128
并查集 #128
中心扩散 #5
模式匹配/转换 循环/分治 #6 #932
动态规划 #10 #32 #72
栈/队列/回溯 #17 #32 #1239 #1255
位压缩 #32 #1255
排序/堆/分治 #692
广度优先搜索 #127
求值/中位数/XX数 二分查找/数组 #4
动态规划/分治/递归 #53 #509 #932
排序/双指针 #295
单调栈 #503
容器/股票/航班预订/上下车/加油站 双指针 #11 #42 #121
一次遍历 #121 #134
动态规划 #121
差分 #1094 #1109
最短距离/路径/岛屿/区域 递归/动态规划 #62 #63 #64 #94 #145 #337
DFS/BFS #102 #130 #200 #684 #1319 #面试16.19
并查集 #130 #200 #547 #685 #1319
任务管理/进程操作 排序/桶思想 #621
并查集 #582

LeetCode 常用算法

算法 说明
排序/数组/堆/二分查找/分治
循环/队列/栈/回溯
滑动窗口/双指针
深度优先搜索
广度优先搜索
动态规划
并查集
哈希表
位运算

C++ STL 库常用知识点

STL库用法 说明
string substr/str.find(“abc”)!=string::npos;
vector vector<vector> vec(10, vector(10, 0));
stack/queue/list
map/unordered_set
set/unordered_map
algorithm

从常见题型入手练习,掌握常见算法应用及常用 STL 库函数用法。

现代C++新特性

https://blog.csdn.net/lycheng1215/article/details/100367277

使用花括号初始化变量

代码:三种初始化变量的方式

1
2
3
4
int a = 1.1;
int b(1.2);
int c{ 1.3 }; // WRONG
123

使用花括号初始化变量的特点有两个:

  1. 允许以相同的方式初始化所有变量,这一点我们之后再进行进一步的讨论;
  2. 当发生收缩转换时,编译器将会报错而非警告。
零初始化

使用花括号进行初始化时,若想要让默认值为 0,可以省略 0。

代码:零初始化

1
2
3
4
5
int a = 0;
int b(0);
int func(); // a function here!
int c{}; // 0 by default, OK!
1234

注意在使用圆括号进行初始化时并不能省略这个 0,否则这表示的将会是一个函数。

使大整型字面量更加易读

代码:数字分隔符

1
2
auto a{ 1'0'0'0'0000'0000 };
1
二进制的整型字面量

代码:二进制整型字面量

1
2
auto a{ 0b1011 }, b{ 0B1011 };
1
size_t 类型

sizeof 运算符得到的结果是一个 size_t 类型的整数,size_t 的宽度取决于目标平台。size_t 是无符号的。

一般而言,size_t 可以直接被使用。它还在 cstddef 头文件中被定义。

浮点数的特殊情况:NaN(Not a Number)和 infinity

有关它们的运算法则,可以在需要时进行测试或查阅。

可以使用 cmath 中的 std::isinf() 函数和 std::isnan() 函数判断一个浮点数是否是 NaN 或者 infinity。

显式类型转换

代码:显式类型转换

1
2
int a{ static_cast<int>(1.1) };
1
获得数值的上下界

使用 limits 头文件中的 numeric_limits 类获取我们需要的值。

代码:numeric_limits

1
2
3
4
5
6
constexpr auto a = std::numeric_limits<int>::min();
constexpr auto b = std::numeric_limits<int>::max();
constexpr auto c = std::numeric_limits<double>::min();
constexpr auto d = std::numeric_limits<double>::max();
constexpr auto e = std::numeric_limits<double>::lowest();
12345
不要混合使用 coutwcout

是否使用宽字符输出,取决于第一个输出操作是使用的 cout 还是 wcout

autostd::initializer_list

仅在 C++ 17 中满足下列规则:

1
2
3
4
5
auto a{ 1 }; // int
auto b = { 1 }; // std::initializer_list<int>
auto c = { 1, 2 }; // std::initializer_list<int>
auto d{ 1, 2 }; // WRONG!
1234
运算结果至少是 int,不会是 short
强类型的枚举

代码:新的枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
enum OldOne
{
ichi,
ni,
sann
};
OldOne a = OldOne::ichi;
a = static_cast<OldOne>(2);
a = sann;
enum class NewOne
{
ICHI = 1,
NI,
SANN
};
NewOne b = NewOne::ICHI;
b = static_cast<NewOne>(2);
b = SANN; // WRONG
return 0;
}
12345678910111213141516171819202122
switch 定义变量的限制

switch 中,如果变量被定义的同时被初始化,就不能绕过变量的定义而进入变量的作用域。

代码:错误的 switch

1
2
3
4
5
6
7
8
switch (0)
{
case 1:
int a{ 1 };
default:
break;
}
1234567

以上代码中,在 default 后面是可以访问变量 a,即在作用域范围内,但是在进入 default 时,变量 a 并没有被初始化,这是不允许的。

ifswitch 语句的初始化

代码:如果我是 for

1
2
3
if (int i{ 1 }; i <= 10);
switch (int i{ 1 }; i);
12
使用 std::array 代替普通数组

需要包含 array 头文件。

使用 std::size 获取数组的大小

支持普通数组和 array

使用 auto*

如果要用指针初始化一个变量,建议使用 auto* 而非 auto,因为在使用 auto* 时,若给定值不是一个指针,编译将不会通过。

常量指针与指向常量的指针

const 在类型前,指向常量的指针,即指针可以指向别处,但修改不了被指向的地方。

const 在星号后,常量指针,即指针本身不可指向别处,但可以修改被指向的地方。

new[]

在使用类似于 new int[3] { 0, 1, 2 } 的代码时,不能省略表示大小的 3

指向数组的指针

代码:奇怪的 new

1
2
3
4
5
6
7
8
int main()
{
auto a{ new int[3][4] {} };
int(*b)[4]{ new int[3][4] {} }; // note (*b)
delete[] a;
delete[] b;
}
1234567

只有第一维能够是动态的,后面的维度必须是 constexpr 的。

智能指针

包含 memory 头文件
unique_ptr<T>

该对象储存唯一的地址,并且这个地址被该对象独占。释放该对象时,其对应的指针也会释放。

代码:unique_ptr

1
2
std::unique_ptr<int> p{ new int {233} };
1
使用 std::make_unique<T>

代码:make_unique

1
2
auto p{ std::make_unique<int>(666) };
1
创建指向数组的指针

代码:指向数组的智能指针

1
2
3
std::unique_ptr<int[]> p{ std::make_unique<int[]>(10) };
p[0] = 1;
12
get 方法

使用 get 方法能够获得智能指针包含的地址。使用 get 函数,务必保证不会长时间保存得到的指针。

reset 方法

reset 方法可以修改智能指针指向的值,并且在此之前对已有的指针进行删除操作。

代码:reset 方法

1
2
3
auto p{ std::make_unique<int>(233) };
p.reset(new int{ 666 });
12
release 方法

使用 release 方法可以将已经存在的指针宣布由自己管理,智能指针不再插手,将被设为指向 nullptr

代码:release 方法

1
2
3
4
auto p{ std::make_unique<int>(233) };
auto* t = p.release();
delete t;
123
share_ptr<T>

share_ptr 在内部对同一个地址有一个引用计数。与 unique_ptr 不同的是,可以用一个 share_ptr 对另一个 share_ptr 进行赋值。

share_ptr 没有 release 方法和 get 方法,其他内容大同小异。

std::string::data 方法

在 C++ 17,data 方法将返回一个非 const 的指针,而在之前的标准中得到的指针是 const 的。

std::string 字面量

首先使用 using namespace std::string_literals;,然后在字符串字面量后面加上后缀 s,就能得到一个 std::string 对象。

1
2
3
using namespace std::string_literals;
"literal"s;
12
std::to_string 函数

该函数能将基本类型转换为 std::string

std::stoi 函数

该系列函数将 std::string 转换为数字。

原始字符串

代码:原始字符串

1
2
LR"Row";
R"row";

stl容器的遍历删除

https://zhuanlan.zhihu.com/p/67026112

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
32
33
34
35
36
37
38
#include <vector>
#include <map>
#include <iterator>
#include <iostream>
#include <algorithm>

int main(int argc, char *argv[])
{
//vector遍历删除
std::vector<int> v(8);
std::generate(v.begin(), v.end(), std::rand);
std::cout << "after vector generate...\n";
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "\n"));

for (auto x = v.begin(); x != v.end(); )
{
if (*x % 2)
x = v.erase(x);
else
++x;
}

std::cout << "after vector erase...\n";
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "\n"));

//map遍历删除
std::map<int, int> m = {{1,2}, {8,4}, {5,6}, {6,7}};

for (auto x = m.begin(); x != m.end(); )
{
if (x->first % 2)
m.erase(x++);
else
++x;
}

return 0;
}

std::vector的底层实现

https://zhuanlan.zhihu.com/p/67026112

  • vector是动态扩容的,2的次方往上翻,为了确保数据保存在连续空间,每次扩充,会将原member悉数拷贝到新的内存块; 不要保存vector内对象的指针,扩容会导致其失效 ;可以通过保存其下标index替代。

  • 运行过程中需要动态增删的vector,不宜存放大的对象本身 ,因为扩容会导致所有成员拷贝构造,消耗较大,可以通过保存对象指针替代。

  • resize()是重置大小;reserve()是预留空间,并未改变size(),可避免多次扩容; clear()并不会导致空间收缩 ,如果需要释放空间,可以跟空的vector交换,std::vector .swap(v),c++11里shrink_to_fit()也能收缩内存。

  • 理解at()和operator[]的区别 :at()会做下标越界检查,operator[]提供数组索引级的访问,在release版本下不会检查下标,VC会在Debug版本会检查;c++标准规定:operator[]不提供下标安全性检查。

仿函数(函数指针

https://blog.csdn.net/K346K346/article/details/82818801

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class StringAppend
{
public:
explicit StringAppend(const string& str) : ss(str) { }
void operator() (const string& str) const
{
cout<<str<<' '<<ss<<endl;
}
private:
const string ss;
};

int main()
{
StringAppend myFunctor2("and world!");
myFunctor2("Hello");
}

类模板与函数模板

https://blog.csdn.net/EmSoftEn/article/details/50421124

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
template <class T> // declare a template, type T, no semicolon
class Compare {
public:
Compare(T a, T b)
{
x = a;
y = b;
}
T max()
{
return (x>y) ? x : y;
}
T min()
{
return (x<y) ? x : y;
}
T test();
private:
T x;
T y;
};

template <class T>
T Compare<T>::test()
{
T a;
return a;
}

或许我最大的缺点就是兴趣过于广泛、无所精通,以至于年过而立一事无成,至今依然在思索如何将这短板变成长处,比如写不动代码时去做一个知识面颇宽的产品经理。
我的其中一项爱好是广播,爱听广播、加入过校园广播电台、也自己做过播客。做播客其实涉及很多东西,比如我做的是故事配乐朗读(录播节目),首先要准备故事素材;然后需要一个编辑把文字内容润色为可以用声音演绎的版本;再需要一位主播(那时候的主播跟现在的主播不是一个意思哦)和一位录音师,把文稿录制成音频;接着做配乐设计并进行分轨编辑、混音等;最后还要有一个平台把节目发布出去并向目标听众推广;当然还需要一套录音设备和软件,这里就不细说了。可以看到,从产生一个想法到节目最终被听众听到,中间有很多环节。很多优秀的播客节目都是一个颇具规模的团队在运作,比如糖蒜广播、逻辑思维等。而像我这样完全出于个人爱好的 Podcaster 往往都是单枪匹马在战斗,不妨看看我的超级团队:

阅读全文 »

这是一个用Python+Tensorflow实现的聊天机器人程序,使用seq2seq模型训练。示例所用训练数据集是IMDB600多部电影中的英文台词对话部分,训练时间为3天左右(2012款MacBook Pro i7),目前仅支持英文。另外程序包含一个简单的Python+Flask WebUI,并实现了微信公众号对接功能。

操作说明

execute.py为Python主程序,程序有三种模式:训练、测试和服务,可通过修改配置文件seq2seq.ini来改变模式:

  • 选择运行模式:
    • 训练模式:mode = train
    • 测试模式:mode = test
  • 前台进程方式启动程序:python execute.py
  • WEB服务方式启动程序:python webui/app.py
    • 需预先安装Flask环境:setup.sh/requirements.txt
    • 通过脚本启动后台服务:sh webui/startup.sh
阅读全文 »

背景

对于C++程序员来说,做一个漂亮的界亮程序通常都比较痛苦,QT相对于MFC来说是一种非常好的选择,尤其是QT被Digia公司收购以后,接连升级了多个版本,逐步兼容Windows、Linux、Mac OS、iOS和Android平台,很好。 在Windows平台使用Qt常用的方法有两种,一种是VS+插件的方法,另一种是使用Qt提供的Creator程序(需要安装C++编译器和调试器),笔者在工作中两种方式都用过,比较喜欢第二种,从认同感上讲各方面都喜欢Qt,排斥微软。但今天要说的问题是在使用第一种方法时遇到的。 当我们觉得Qt自带的控件Ui不能满足需求时,可以用C++强大的继承方式自己改造、创造控件。这里提醒大家,为了提高代码的重用性,创建自定义控件时不要先用QtDesigner绘制好控件再去改写它的类,而是要直接创建一个继承自Qt控件的类,界面元素通过代码创建。当然,在我说这些之前你可能不知道这些,用错误的方法创建了一个控件,现在你想在另外一个工程里重用它,有两种情景,我们一步一步来解决。

阅读全文 »

  1. Ctrl + Tab:快速切换已打开的文件
  2. Ctrl + 左键:快速转到声明/定义(同F2)
  3. Alt + (1-7):快速打开/关闭对应的输出窗口
  4. Ctrl + M:快速添加/删除书签
  5. Ctrl + E,2:快速添加上下布局的分栏
  6. Ctrl + E,3:快速添加左右布局的分栏
  7. Ctrl + E,1:快速删除所有的分栏
  8. F2:快速切换到选中对象的声明/定义
  9. F4:快速在头文件(.h)和实现文件(.cpp)之间进行切换
  10. Ctrl + /:快速注释/取消注释选定内容
  11. Ctrl + i:自动缩进选中代码
  12. Ctrl + shift + ↑:将当前行的代码向上移动一行
  13. Ctrl + shift + ↓:将当前行的代码向下移动一行
  14. Alt + ←:快速返回 15、Alt + →:快速前进