奇幻物语

课外小知识

常用的字符编码方式：
ASCII：表示纯英文，1个字节表示，第一位固定为0，其余七位表示128个字符。
扩展ASCII：表示欧洲文字的，1个字节表示，第一位也加入使用。
GBK：表示汉字。
Unicode：包含世界上所有字符的总集。
UTF-8：Unicode的实现之一，1-4个变长字节表示符号。

Why C Important?

C is work for UNIX delevopment, all the UNIX systems and their softwares were programmed by C.

C provides lots of basic data structures: char, int, float; pointer, array, struct and union. Also provides basic logic structures: statements, if-else, switch, while/for, do break. Its function can return in reference, struct, union or pointer, even using in recursive.

During preprocess period, program text will be replaced by Macro and compile in condition.

总览&ch1&ch2读书记录

new = 内存分配(malloc) + 构造函数
裸指针： 容易忘记delete， 指针容易到处传递，没法明确谁来执行释放。
智能指针shared_ptr: 引入计数器，创建为1，传参拷贝+1，对象析构则-1，变为0时自动释放。
智能指针相互引用问题：引入weaked_ptr，不增加引用计数。
智能指针兼容裸指针问题：重载了->和*运算符，用get()获得裸指针。

如果C源程序出现在多个文件中，那么对它的编译和装入要比将整个单一源做更多说明，但这是操作系统的任务，而非语言属性。

++操作只能用于变量，(i+j)++为非法。

位运算：&屏蔽某些位，|打开某些位，^异或，～取反， << >>移位

前言：努力做西湖区最好的算法题解。分为算法专题、91天学算法、精选题解、高频考题（简单-中等-困难）

算法专题

数据结构

线性结构：使用连续内存，序列。利于查询，不利于插入删除
非线性结构：使用间断内存，通过地址指针连接,链表。运行时动态生成

队列、栈都是受限序列。非线性结构是为了高效兼顾静态操作和动态操作，如树堆。
堆是一种优先队列，二叉查找树（查找快），AVL平衡树优化深度的BST，及后面的红黑树。

链表

链表基本操作,画图理解：注意头尾指针情况
插入节点：
1.temp = 待插位置前驱节点.next
2.待插位置前驱节点.next = 待插指针
3.待插指针.next = temp

删除节点：
1.待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next

遍历：
cur = head
while(cur!=nullptr){
print(cur)
cur = cur.next
}

前序遍历递归伪代码

1
2
3
4
5
6
7

dfs(cur){
  if cur == nullptr
    return
  print(cur.val)
  return dfs(cur.next)
}

一个原则：画图

两个考点：

1.指针修改
比如链表反转，数组直接遍历两两交换

1
2
3
4
5
6
7
8
9
10
11
12
13

void reverse(head, tail)
{
  cur = head
  pre = nullptr
  while(cur!=tail)
  {
    next = cur->next
    cur->next = pre
    pre = cur
    cur = next
  }
  return tail
}

2.链表拼接
容易穿来穿去。
链表的价值：不必要求物理内存连续性，对插入和删除友好。

三个注意： 覆盖90%错误

• 出现了环，造成死循环
• 分不清边界，造成边界条件出错
• 搞不懂递归做法

关于链表环：

• 题目链表可能有环，判断是否有，以及位置（快慢指针）
• 本来没环，被你操作出现环（先画图，看操作；仅仅画出一个子结构即可）

关于边界：

• 如果题目的头节点可能移除，考虑使用虚拟节点，使头节点变成中间节点
• 题目返回不是原本的头节点，而是尾节点或者中间节点，要注意指针变化

前后序

前序：先处理节点，再左右
中序：先左，再处理，再右
后序：先左右，最后处理节点

由于链表天生具有递归性，可以引入递归思维。

如果前序遍历，可以想象前面链表处理好了，这种情况下处理当前；如果后序，则想象后面处理好了，这种情况下处理当前。

四个技巧

虚拟头作用：

• 头节点变成中间节点，简化判断
• 在合适时候断开，返回链表中间节点

快慢指针：

• 一个先走，一个后走
• 一个快走，一个慢走

穿针引线：先穿再引，即记录后续改动的，再变更之前的

树专题

导读

声明为explicit的构造函数更佳，避免不明确的自动隐式转换
对象使用“=”会自动调用copy构造函数
命名尽可能带有意义的缩写：lhs, rhs; pw,pa; rw,ra;等
关于线程的点：当C++受到全世界关注时，多线程程序还没诞生。因此C++的多线程更多考虑线程安全性。

内置类型pass-by-value高效，自定义类型pass-by-reference高效。

chap1 Accustoming to C++

C++的四大组成部分：

• 原生C，C语言的区别在于没有：模板，异常及重载
• 面向对象C++特性：类、封装、继承、多态、虚函数
• 模板C++特性：泛型编程
• STL算法库
  根据应用场合所需使用其中的主要成分。

const, enum, inline rather than #define

使用#define则预处理器解释，编译器不可见,因此也没有进符号表，可能导致编译器无法跟踪具体错误。
static char倾向用const string，类中的static int用enum {num=5}; enum hack

• 对于简单常量，使用const或者enum
• 对于#define函数宏，使用内联函数

尽可能使用const

const char* p = pa; // const data
char* const p = pa; // const ptr
规律：星号左侧const为const data, 星号右侧const为const ptr

因此，下面f1和f2是一致的

1
2

void f1(const Widget* pw);
void f2(Widget const * pw);

const 迭代器不得改变指向，但是指向的内容值可以改动。
const return可以预防”无意义的赋值动作”错误。
const成员函数目的：1.让接口容易理解，指导是否可以改动对象内容 2.使操作const对象成为可能，因为改善C++程序效率根本方法是pass by reference-to-const

1
2
3
4
5
6
7

// non-const
char& operator[](int pos)
{ return text[pos];}

// const
const char& operator[](int pos) const
{ return text[pos];}

非const操作可读可写，const操作只针对const对象的读取；

bitwise const（C++）与Logical const的思考：
引入mutable成员变量使在const成员函数中依然可变，从而打破bitwise const，达到Logical const；
但mutable不能解决所有const难题，如指向的外部指针需要做边界检验、日志访问信息、完善性检验等，则在类内部产生一个争议的怪物。不利于代码重复、编译加快及维护。一个办法是non-const operator[]调用其const operator[]兄弟，减少重复代码，但是需要两次转型：一次将*this从原型转型为const &,从而避免递归调用non const版本自身；一次是在返回值移除const。从而用const operator[]实现出non-const版本。反向做法则带有风险：曾经承诺不改动的对象被改动了。因此const成员函数调用non-const函数是错误行为，因为non const可能改变成员。

总结：熟悉const在指针/迭代器上；在指针迭代器及引用指向的对象身上；在函数参数和返回类型上；在成员函数上的使用细则。

• 声明const帮助编译器识别错误用法，const可施加于任何作用域内的对象、函数参数、函数返回类型、函数本身。
• 编译器实施bitwise constness,但编程时应该使用logical constness
• const和non-const成员函数有着实质等价的实现时，可令non-const版本调用const版本避免代码重复。

确定对象被使用前被初始化

构造函数总是使用成员初始化列表
static对象：声明周期从构造到程序结束，包括global对象，namespace作用域内的对象、class内、函数内、file作用域内声明为static的对象。
区别于static的stack,heap-based对象属于动态内存。

其中的问题c++对”定义在不同编译单元内的non-local static对象“初始化相对次序无法明确定义。因为决定初始化次序相当困难，常见形式多个编译单元的non-local static对象经有“模板隐式具现化 implicit template instantiations”形成。

解决方法：将每个non-local static对象搬到自己专属函数内，函数返回一个reference指向它所包含的对象。即singleton设计模式。

记住：

• 为内置型对象进行手工初始化，因为C++编译器不能保证初始化
• 构造函数使用成员初始化列表，且尽量确保次序一致
• 解决“跨编译单元的初始化次序”问题，用local static对象替换non-local static对象

chap2 构造/析构/赋值运算

了解C++默默编写及调用哪些函数

空类会自动声明一个default构造函数，copy构造函数,一个copy assignment操作符和析构函数

若不想使用自动函数，则明确拒绝

一种做法将不想被自动调用的函数主动声明为private(iostream库做法，只有private声明);如果外部调用则编译器报错，如果member或friend函数调用则链接器报错。
更绝的做法专门为阻止copying动作设计一个基类，通过private继承，避免member/friend函数访问。

为多态基类声明virtual析构函数

从而确保对象derived成分被销毁，避免资源泄漏及败坏数据结构。

virtual函数实现细节不重要，重要的是带来对象体积的增强，引入virtual table pointer.因此也不能滥用virtual析构

一般使用心得：只有当class内含有至少一个virtual函数时，才为它声明virtual析构函数

注意的是：不要企图继承string, STL容器作为多态基类，因为这些均是带有“non-virtual析构函数”的class

1
2
3
4
5
6

class AWOV{
  public:
    virtual ~AWOV() = 0;  // 声明pure virtual析构
};

AWOV::~AWOV(){} // 需要明确定义，因为有一系列调用动作

记住：

• 多态基类应该声明virtual析构函数，如果class带有任何virtual函数，则应该拥有一个virtual析构函数
• class设计不是作为基类或者多态基类使用，就不要声明virtual析构函数，因为增大对象的体积

别让异常逃离析构函数

C++不禁止从析构抛出异常，但如果多个对象析构同时抛出多个异常，则容易导致不明确行为。解决方法：1.析构中抛出异常即abort程序 2.吞下异常，虽然覆盖了失败原因的重要信息，但有时候程序继续运行很重要 3.较佳策略重新设计接口，让client在普通函数中对抛出的异常作反应

绝不在构造和析构过程调用virtual函数

因为这类调用从不下降至derived class

令operator= 返回一个reference to *this

从而实现连锁形式,令外防止自我赋值问题

1
2
3
4
5
6
7
8
9
10
11
12
13

e.g.
class Widget{
public:
  Widget& operator=(const Widget& rhs)
  {
    if(this== &rhs)
      return *this;
    
    delete pb;
    pb = new Bitmap(*rhs.pb);
    return *this;
  }
};

记住：

• 确保自我赋值=和copy有良好行为
• 确定多个对象为同一对象时仍然正确

复制对象勿忘每一个成分

• copying函数应该确保复制“对象所有成员变量”及“所有base class成分”
• 不要尝试以某copying函数实现另一个copying函数。可将共同功能放入第三个函数中，被两个copying函数调用

chap 2 资源管理（C++重要问题）

主要原则：一旦使用了，将来必须还给系统。
资源包括：内存、文件描述器、互斥锁、图形界面的字型和笔刷、数据库连接以及网络sockets。

为了警惕调用create动态内存之后，delete的语句有可能被控制流略过，可靠的做法依赖C++的“析构函数自动调用机制”，将资源放进对象内。

记住：

• 防止资源泄漏，使用RAII对象
• 两个常用的RAII classes分别是tr1::shared_ptr和auto_ptr,
  RAII（资源获取即初始化）:1.设计类封装资源 2.在构造函数初始化 3.在析构中销毁 4.使用时声明类

“当一个RAII对象被复制，该如何处理”：

• 一种是禁止复制，copying声明为private
• 对底层资源进行“引用计数法”，一并复制管理的资源

关于资源管理类

• APIs往往要求访问原始资源，所以每个RAII类应该提供一个“取得其所管理资源”的办法
• 对原始资源的访问可能由显式转换或隐式转换而得，一般而言显示转换较安全，但隐式转换对客户比较方便

new和delete采取相同形式

核心问题：被删除的指针所指是单一对象或者对象数组？

避免对数组形式左typedefs，容易引起new []和delete []一致性问题。由于STL的string和vector，因此C数组需求几乎为零。

应该以独立语句将newed对象存储于智能指针内，如果不如此，一旦异常抛出有可能导致难以觉察的资源泄漏。

chap 3 设计与声明

让接口容易正确使用，不易被误用

接口种类：function、class、template，都是客户与你的代码互动的方式。

理想上，如果客户企图使用某个接口却没有获得他所预期的行为，这个代码不该通过编译；如果通过编译，则API的作为就该是客户所想要的。

tricks:使用特定类型作为接口参数,使用shared_ptr强迫RAII

记住：

• 好的接口容易正确使用，应该在所有接口中努力达成这些性质
• “促进正确使用”的办法包括接口的一致性以及内置类型行为兼容
• “阻止误用”的办法包括建立新类型，限制类型上的操作，束缚对象值以及消除客户的资源管理责任
• shared_ptr支持定制型删除器，可防范DLL问题，可被用来自动解除互斥锁

设计class犹如设计type

设计包括：重载函数和操作符、控制内存的分配和归还、定义对象的初始化和终结
设计规范的一些问题：

• 新type的对象应该如何被创建和销毁
• 对象初始化和赋值有什么差别
• 新type的对象如果被passed by value意味着什么
• 新type的“合法值”是什么
• 新type需要配合某个继承图系吗
• 新type需要什么样转换
• 什么样的操作符和函数对新type是合理的
• 什么样的标准函数应该驳回
• 谁该取用新type的成员
• 什么是新type的“未声明接口”
• 你的新type有多么一般化
• 你真的需要一个新type吗

记住：class的设计就是type的设计，定义之前确定你已经考虑过本条款覆盖的所有主题

用pass-by-reference-to-const替换pass-by-value

Pass-by-value还可能引起切割问题，某些特化信息丢失。

记住：

• 对于内置类型以及STL迭代器和函数对象，使用pass-by-value比较适当
• 对于其他struct, type, class用pass-by-reference-to-const更高效
• 绝不返回pointer或者reference指向local stack对象，直接返回对象pass-by-value更安全

将成员变量声明为private

不声明为public有三点：
1.统一接口为函数，必须带括号参数，不容易混乱
2.可控制变量的读写访问权限
3.封装原则，改动底层数据结构无须改动接口
如果public成员改动一发牵全身，需要重写代码、重新测试、重新编写文档、重新编译。
只有两种访问权限：private(提供封装)和其他（不提供封装）

记住：

• 切记将成员声明为Private,可赋予客户访问数据一致性、可细微划分访问控制、允诺约束条件获得保证，提供class作者充分的实现弹性
• Protected并不比Public更具封装性

宁用non-member、non-friend替换member函数

封装原则：改变事物只影响有限客户。另外的角度，愈多函数可访问，数据的封装性愈低。

c++ standard分装多个头文件以及多个命名空间同样为了封装性，降低编译依赖性。

如果需要为某个函数所有参数进行类型转换，那么这个函数必须是non-member.

写一个不抛异常的swap函数

第七课 图搜索

指南简介

谷歌开源项目主要是C++，因此开放编程指南方面合并代码，总共五万字指南涉及广泛，论证严密。指南不仅列出怎么做以及为什么这么做，同时告诫什么情况可以破例以及权衡其中利弊。

背景

由于C++强大的特性，容易产生难以阅读和维护的问题，有时候需要限制部分特性以保持代码清爽。

头文件

头文件：每个.cc对应一个.h，main和单元测试除外

自给自足原则（self-contained）：一个头需要包含自身所需的其他头，同时使用#define保护；若非如此，头需要特定平台的symbols则用.inc扩展名。

所有头应使用#define防止多重包含，保证唯一性。

使用前置声明

先声明，后面再定义。

优点：

• 节省编译时间，多余#include迫使编译器展开文件，处理更多输入
• 节省重新编译时间，#include使代码因头文件无关改动而重新编译多次

缺点：

• 隐藏了依赖关系，头文件改动时跳过必要的重新编译过程
• 可能被库的后续更改所破坏
• 声明来自std::的symbol，其行为未定义
• 难以判断何时使用前置声明还是#include，极端情况甚至暗暗改变代码含义

总结：

• 尽量避免前置声明那些定义在其他项目中的实体
• 函数：总是使用#include
• 类模板：优先使用#include

内联函数

只有10行以内才定义内联，直接代码展开

优点：目标代码高效，关键函数可内联
缺点：滥用会使代码量增大
总结：

• 谨慎对待析构函数内联，隐含的成员和基类析构会被调用
• 内联包含循环或switch语句的函数常常得不偿失
• 编译器不会把虚函数和递归函数内联

#include路径及顺序

项目内头文件应按项目源码目录树结构排列，避免使用UNIX特殊的快捷目录.或..
e.g. #include “dir2/foo2.h”头文件的次序:

• 1.dir2/foo2.h
• 2.C系统文件
• 3.C++系统文件
• 4.其他库的.h文件
• 5.本项目内的.h文件

条件编译

1
2
3

#ifdef LANG_CXX11
#include <initializaer_list>
#endif

译者笔记：

• 避免多重包含是最基本的要求
• 前置声明是为了降低编译依赖，防止修改文件头引起多米诺效应
• 内联函数合理使用可提高代码效率
• 独立内联头-inl.h可提高代码可读性
• 使用完整项目路径可减少隐藏依赖，保证内部错误及时发现
• 前置声明的类为不完全类型，只能定义指向的指针或引用
• 类内部函数自动内联，建议独立放入.cc文件，贯彻声明与定义分离原则
• #include中插入空行以分离头文件，C库，C++库以及其他库.h和本项目.h

作用域

命名空间将全局作用域细分为独立作用域，可有效防止全局命名冲突
内联命名inline namespace只允许用于跨版本的ABI兼容性

默认命名空间：main存在的常用的，其他空间调用可::func
匿名空间：无名namespace{},主要用途：1.定义符号限于文件内部使用，不被外部引用 2.类似static修饰整个空间内容

关于使用命名空间的策略标准：

• 允许鼓励匿名命名空间，避免运行时命名冲突
• 不在std空间声明任何东西，会引起不可移植性
• 尽量不用using namespace name;污染命名空间
• 允许使用空间别名
• 禁止内联命名空间

嵌套类

即成员类用法
缺点：嵌套类只能在外围类的内部做前置声明，即任何使用Foo::Bar*的指针头文件必须包含Foo的整个声明。
用法：不要定义为公有，除非是接口的一部分。

第五课 双序列DP

再次强调，可能为DP的问题： 记忆化搜索

• Max/Min问题
• True/False问题
• 计数问题
  可能不是DP问题的
• 需要所有“具体”的方案
• 输入是“集合”而非“序列”

例题：a,b两串的Longest Common Sequence的长度
state: dp[i][j], a前i子串匹配b前j子串的LCS长度
function: dp[i][j] = dp[i-1][j-1] + 1 if a[i]==b[j]
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) if a[i]!=b[j]
init: dp[i][0]=0, dp[0][j] = 0;
ans:dp[a.size()][b.size()]

重点：序列a,b挑出i,j子序列的dp

• dp[i][j]定义
• dp[i][j]的转换以及从i,j为结尾的情况考虑

总结：

• 归纳可能使用或不使用DP的规律
• DP四要素：状态，转换方程，初始化和答案
• 三种常见面试DP：矩阵，单序列，双序列
• 奇技淫巧：初始化首行首列， N个数开N+1位置的数组

背包问题

定义：n个整数，装m的背包
state: f[i][j]“前i”个数，能否组成和为j
function: f[i][j] = f[i-1][j-a[i]] or f[i-1][j]
init: f[x][0] = true; f[0][1-m] = false;
ans: f[n][x]为true 的最大值的x

当前行只跟上一行i-1有关：滚动数组优化，用模2; 如与i-1, i-2有关，则模3；如此类推。

TO DO：较难，待补充具体解法

第六课 链表

目标：

• Dummy Node哨兵节点
• 相关基本技巧
• 快慢指针：删N节点，找环

1. head!=nullptr head->next!=nullptr
2. 删除：pre.next = cur.next
3. 头节点要改变，引入dummy node；可不用单独判断链表头的情况，代码更简洁
4. swap(pre, now) 翻转链表

Dummy Node常用场合

1.有序链表去重复元素
2.翻转链表
3.合并两个有序链表
4.分割链表

归并排序链表：

• 1.找中点，快慢指针
• 2.拆分左右
• 3.排序序列
• 4.合并

合并K个链表：

• 用priority_queue<ListNode*, vector<ListNode*> , comp>最大堆来优化
• 分治两两合并

copy随机链表，每个节点带next和random：

• hash记录克隆节点（遍历一次）
• 基于节点克隆边

Intro yourself

要点：适当的内容表达，元气健康的兴趣，

第三课 分治

先序： 根 左 右
后序： 左 右 根
中序： 左 根 右

遍历方法：

• 递归方法：一句话描述递归函数，如把根节点放入res里；
• 优化成非递归：借助栈的数据结构，动手背诵；
• 分治，分解攻克：问题分成两半，或者多份，分别解决再合并答案；带return value的递归方法; 二叉树的通用解法

递归方法：退出条件，节点为空如何处理；问题分成左右两半怎么处理；分治方法递归一般带相同返回类型参数。

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

// 递归法：
    vector<int> preorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> res;
        preorder(root, res);
        return res;
    }
     // 递归方法：把根节点放入res里
     void preorder(TreeNode* root, vector<int>& res)
     {
         if(root == nullptr)
         {
             return ;
         }
         res.push_back(root->val);
         preorder(root->left, res);
         preorder(root->right, res);
     }

// 非递归法
// 分治法
vector<int> preorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> res;
        if(root == nullptr)
            return res;
        
        // divide
        vector<int> left = preorderTraversal(root->left);
        vector<int> right = preorderTraversal(root->right);

        // conquer
        res.push_back(root->val);
        res.insert(res.end(), left.begin(), left.end());
        res.insert(res.end(), right.begin(), right.end());

        return res;
    }

DFS分治法解决归并排序，快速排序以及大部分二叉树问题。
树型分析法来分析复杂度:如归并排序为O(nlogn),logn层，每层合并需遍历每个元素n,O(1)分，O（n)治，需要额外O（N）空间，保证稳定排序；快速排序一样为O(nlogn),用O（n)分，O(1)治，不是稳定排序。一个先局部后整体，一个先整体后局部的分治方法。

BFS广度优先搜索

逐层执行的实现方法：

• 两个queue: 导来导去
• 一个queue+dummy node:加入层分割符
• 单queue(best)： 一层一层往下走

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

vector<vector<int>> levelOrder(TreeNode *root) {
        // write your code here 基本功：唯手熟耳
        vector<vector<int>> res;

        if(root == nullptr)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> level;
            int size = q.size();  // 提前取size,因为q.size()会变化
            for(int i=0 ; i< size; i++)
            {
                TreeNode* head = q.front();
                q.pop();
                level.push_back(head->val);
                if(head->left != nullptr)
                    q.push(head->left);
                if(head->right != nullptr)
                    q.push(head->right);
            }
            res.push_back(level);
        }
        return res;
    }

要求掌握：

• 递归：遍历和分治
• 非递归实现： 前序和中序
• 利用queue的BFS实现

第四课 DP

动态规划：利用已经计算的结果求解新的结果
结合分治方法，带脑子搜索；脑子可以是二维数组，也可以是哈希表，的记忆化搜索。动规本质解决了重复计算的搜索。

动规的问题解法：1.递归 2.分治 3.记忆搜索 4.循环求解 5.自底向上（逆向） 6.自顶向下（正向）

动规常见题目状态类型：

• 矩阵DP （10%）
• 序列（40%)
• 双序列DP（40%）
• Backpack(10%)

极有可能是动规的题目条件：

• 1.Maximum/Minimum
• 2.Yes/No
• 3.Count(*)

极不可能为动规：

• 求出所有”具体”的方案，而非“个数”
• 输入是无顺序的“集合”而非“序列”

DP四要素：

• 状态 State: 存储小规模问题的结果
• 方程 Function: 状态联系，小的状态计算大的状态
• 初始化 Initialization: 最小的状态，起点
• 答案 Answer: 最大的状态，终点

对于二维matrix，初始化第0行和第0列。

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

// Matrix DP
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
        // write your code here
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();

        vector<vector<int>> f(row, vector<int>(col,0));
        
        for(int i=0; i<row; i++)
        {
            if(obstacleGrid[i][0] == 0)
                f[i][0] = 1;
            else
                break;
        }
        for(int j=0; j<col; j++)
        {
            if(obstacleGrid[0][j] == 0)
                f[0][j] = 1;
            else
                break;
        }

        for(int i=1; i<row; i++)
            for(int j=1; j<col; j++)
            {
                if(obstacleGrid[i][j] == 0)
                    f[i][j] = f[i-1][j] + f[i][j-1]; 
                else
                    f[i][j] = 0;
            }   

        return f[row-1][col-1];

    }

与贪心的区别：DP先决策，再执行；贪心直接基于当前执行。一般做题用贪心都是不符要求的。
与分治的区别：分治需要递归；DP着重解决重复运算；
如果路径上下左右则无法DP，属于图论。

五大常用算法：分治、贪心、DP、回溯、穷举

分治问题特征：

• 问题规模缩小到一定可容易解决
• 问题可分解为若干规模小的相同问题
• 重要特征：分解的子问题的解可合并为大问题的解
• 各子问题相互独立，不含公共子子问题
  若不满足第三条，可考虑贪心或DP。

DP问题性质：

• 最优化：问题的最优解包含在子问题的最优解中

题目

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。  

示例 1：

输入：nums = [1,2,3,1]
输出：true
示例 2：

输入：nums = [1,2,3,4]
输出：false
示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true  

解法

一.个人方法，使用map<int, string>作hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        map<int, string> mmap;
        string flag = "y";
        for(int i=0; i<nums.size(); i++)
        {
            if(mmap[nums[i]] == flag)
                return true;
            mmap[nums[i]] = flag;
        }
        return false;
    }
};

二.先排序，然后检查相邻是否相等重复

1
2
3
4
5
6
7
8
9

bool containDuplicate(vector<int>& nums){
  sort(nums.begin(), nums.end());
  int n = nums.size();
  for(int i=0; i<n-1;i++){
    if(nums[i] == nums[i+1])
      return true;
  }
  return false;
}

三.用unordered_set的哈希表

1
2
3
4
5
6
7
8
9

bool containDuplicate(vector<int>& nums){
  unordered_set<int> s;
  for(int x:nums){
    if(s.find(x)!=s.end())
      return true;
    s.insert(x);
  }
  return false;
}

相关知识

map

关联容器，一对一，第一个关键字只能出现一次，内部为自建红黑数（非严格平衡二叉树），可对数据自动排序。
map的特点时增删节点开销小，迭代器可以修改value,但不能修改key.查找数据复杂度为Log(N)

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

#include <map>

// 初始化
std::map<int, string> mStudent;

// 构建
mStudent.insert(pair<int, string>(1,"stu_one"));
mStudent.insert(pair<int, string>(2,"stu_two"));
mStudent.insert(map<int, string>::value_type(3,"stu_three")); 
mStudent[4] = "stu_four";  // 可覆盖旧有

// 遍历
map<int, string>::iterator iter;
for(iter = mStudent.begin(); iter != mStudent.end(); iter++)
  cout <<iter->first<<' ' << iter->second << endl;

pair<map<int, string>::iterator, bool> Insert_Pair;

// insert方法如旧有则插入失败
// first为map的迭代器，second为true/false
Insert_Pair = mStudent.insert(pair<int, string>(1,"stu_one"));

int nSize = mStudent.size();  // 长度

// 查找
// 1.count
// 2.find
map<int, string>::iterator iter;
iter = mStudent.find(1);
if(iter==mStudent.end())
  cout <<"not found";
else
  mStudent.erase(iter);   // 删除erase

// 自定义sort
// 1.数据结构的<重载  2.sort的仿函数

 C++ maps是一种关联式容器，包含“关键字/值”对

 begin()         返回指向map头部的迭代器

 clear(）        删除所有元素

 count()         返回指定元素出现的次数

 empty()         如果map为空则返回true

 end()           返回指向map末尾的迭代器

 equal_range()   返回特殊条目的迭代器对

 erase()         删除一个元素

 find()          查找一个元素

 get_allocator() 返回map的配置器

 insert()        插入元素

 key_comp()      返回比较元素key的函数

 lower_bound()   返回键值>=给定元素的第一个位置

 max_size()      返回可以容纳的最大元素个数

 rbegin()        返回一个指向map尾部的逆向迭代器

 rend()          返回一个指向map头部的逆向迭代器

 size()          返回map中元素的个数

 swap()           交换两个map

 upper_bound()    返回键值>给定元素的第一个位置

 value_comp()     返回比较元素value的函数

unordered_set

基于哈希表的unordered_set和unordered_map区别于基于红黑树的set和map，内部无须，查找效率O（1）用空间换时间。原型为unordered_set,key为任意基本类型，然后经过默认hash(key)转成size_t作为bucker.具体用法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <unordered_set>

// 初始化和插入
std::unordered_set<int> ms{1,2,3,4,5};
ms.insert(6);
ms.insert(7); // 注意没有ms.at()或者ms[idx]的表述

// 遍历
for(auto &s: ms)
  cout << s << endl;


// 删除
ms.erase(2);  //若无则什么也不发生，返回删除元素个数

// 计数
cout << ms.count(2); // 0

// 查找
ms.find(3);  // 返回查找迭代器，若无则返回ms.end()

第一课 Intro

strStr问题

常见问题： 上来直接说KMP算法（过难）
可以确认面试的考察点，比如时间复杂度和空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution{
  /*
    return a index to first occurence of target in source, or -1 if not exist
  */
  public int strStr(String s1, String s2){
    if(s1==null || s2==null) return -1;
    int j;
    for(int i=0; i<s1.length()-s2.length()+1;i++)
    {
      for(j=0; j<s2.length();j++)
        if(s1.charAt(i+j)!=s2.charAt(j)) break;
      if(j==s2.length()) return i;
    }
  return -1;
  }
}

面试误区：

• 做过的题肯定能过
• 算法想出来就能过
• 代码写出来就能过

面试官眼中的求职者：可能是未来的同事

• 你的代码看起来舒服吗？需要多少时间REVIEW
• 你的Coding习惯好吗？不会未来疲于帮你debug，动不动搞挂网站
• 你的沟通能力好吗？和你交流费劲吗

主要考察编程的基本功：

• 程序风格（缩进，括号，变量名）
• Coding习惯（异常检查，边界处理）
• 沟通（让面试官时刻明白你的意图）
• 测试（主动写出合理的TestCase)

面试技巧：

• 在白纸能写吗
• 刷过的题，吃透了多少

明确一点：算法，其实很简单。类似于高考做题，刷题需要总结

• 归类相似的题目
• 找出适合的模板程序
• 掌握递归算法，掌握区分度

第二课 BST

二分搜索通用模板

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

int binarySearch(vector<int> &A, int target)
{
  if(A.size()==0)
    return -1;
  
  int start  = 0;
  int end = A.size()-1;
  int mid;

  while(start+1 < end)
  {
    mid = start + (end-start)/ 2;
    if(A[mid] == target)
      end = mid;  // 为准确找到第一个出现的target
    else if(A[mid] <target)
      start = mid;
    else
      end = mid;
  }
  if(A[start] == target)
    return start;
  if(A[end] == target)
    return end;
  
  return -1;
}

相关题目：二分查找first order/ last order, 二分查找区域， 二分插入数值， 增长矩阵二分查找等
注意带重复元素不能用二分
三步翻转法