8 `- d( M( {6 J& u$ ?. P! Wg、树 * @2 R1 O+ k3 i: E [; r内存结构:内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续 0 H0 c2 {- }* b实现难度:较难+ U; h' n# ?9 `2 Y! E1 B
下标访问:不支持8 ?" W2 j# h+ R* @1 q
分类:二叉树 和 多叉树 / A7 c3 c5 \' }插入时间复杂度:看情况而定 . g: C& f t$ } q4 Y查找时间复杂度:理论上 O ( l o g 2 n ) O(log_2n)O(log 7 x! F0 K' @5 C8 F* S$ ~9 p
2 ! ]( V ^5 o8 u" a, c : \& L7 l7 B [- y- B n)0 S+ v0 n- u% ]) w3 ]- O
删除时间复杂度:看情况而定/ @& u8 T3 n. \- v+ W8 s# y
( ?# {6 _, f4 J5 D+ u
. N; k }. k0 V
1、二叉树 ; h. U M% f. q. T/ d7 i! R6 V3 C二叉树的种类较多,比如:二叉搜索树、平衡树。平衡树又可以分为 AVL 树、红黑树、线段树、堆。最平衡的树莫过于满二叉树了。 + z U* B4 R" f% z5 _2 c4 F其中,堆也是一种二叉树,也就是我们常说的优先队列。 9 n' m% I1 z$ |. y! Z: x2、多叉树) w/ w* _9 \' B6 c4 N/ b( ]
B树和B+树是多叉树,当然我们平时学到的并查集其实也是个多叉树,更加严谨一点,应该称之为森林。 3 P- j4 n. J2 U$ Oh、图+ ]" B$ n4 D6 ?6 F$ o5 C4 [
内存结构:不一定% a) R! D c& x# V0 K
实现难度:难 % f; L# h8 v1 `0 Q& r) o2 y下标访问:不支持 , @3 L/ T2 N F分类:有向图、无向图 8 \4 i9 y( d# K插入时间复杂度:根据算法而定 9 o; B* B7 M; ]- X: f查找时间复杂度:根据算法而定 4 K+ |# r7 j( F! z9 w删除时间复杂度:根据算法而定 $ G6 f% S! b4 G, @) z& m7 |- M& y& }; C! G( C2 ~8 u& L$ O8 q+ k
- P/ P r) q1 h1、图的概念 ! s+ v T9 }* f" l6 K在讲解最短路问题之前,首先需要介绍一下计算机中图(图论)的概念,如下: # {4 q& C+ T, b, z) R" a图 G GG 是一个有序二元组 ( V , E ) (V,E)(V,E),其中 V VV 称为顶点集合,E EE 称为边集合,E EE 与 V VV 不相交。顶点集合的元素被称为顶点,边集合的元素被称为边。0 w, N3 `; w; U! ]+ G" j. m: y) S
对于无权图,边由二元组 ( u , v ) (u,v)(u,v) 表示,其中 u , v ∈ V u, v \in Vu,v∈V。对于带权图,边由三元组 ( u , v , w ) (u,v, w)(u,v,w) 表示,其中 u , v ∈ V u, v \in Vu,v∈V,w ww 为权值,可以是任意类型。6 b: V/ k" J1 k5 S. d9 w- c2 R- z
图分为有向图和无向图,对于有向图, ( u , v ) (u, v)(u,v) 表示的是 从顶点 u uu 到 顶点 v vv 的边,即 u → v u \to vu→v;对于无向图,( u , v ) (u, v)(u,v) 可以理解成两条边,一条是 从顶点 u uu 到 顶点 v vv 的边,即 u → v u \to vu→v,另一条是从顶点 v vv 到 顶点 u uu 的边,即 v → u v \to uv→u; 3 `; z7 S/ X/ |2、图的存储" W/ s/ j6 U& w/ D1 k8 F- a
对于图的存储,程序实现上也有多种方案,根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例,讲解四种存储图的方案。& h" O: u, b) U# D( ~6 `! a
+ e! T2 P1 M3 }" G3 P0 E
3 y" K# g, U& `- v ~% z0 w; m8 R$ X
1)邻接矩阵7 e+ l6 p2 h! n9 H
邻接矩阵是直接利用一个二维数组对边的关系进行存储,矩阵的第 i ii 行第 j jj 列的值 表示 i → j i \to ji→j 这条边的权值;特殊的,如果不存在这条边,用一个特殊标记 ∞ \infty∞ 来表示;如果 i = j i = ji=j,则权值为 0 00。3 a/ C1 R* X1 R/ H; N- D
它的优点是:实现非常简单,而且很容易理解;缺点也很明显,如果这个图是一个非常稀疏的图,图中边很少,但是点很多,就会造成非常大的内存浪费,点数过大的时候根本就无法存储。* w; `% k" v4 c, b5 R! M+ C# W
[ 0 ∞ 3 ∞ 1 0 2 ∞ ∞ ∞ 0 3 9 8 ∞ 0 ] \left[ N V. s$ z! o: U. H: }6 v
01∞9∞0∞8320∞∞∞30 . D( t2 K4 K8 L# u) S0∞3∞102∞∞∞0398∞0 M. g/ X9 X6 d0 i2 D, r% m5 C\right] , v, e% Z0 x4 D⎣( P' ^* d# K. a% u0 N5 j3 h H
⎢ * |; ^& w9 ^7 Z) F& ^0 v⎢ ) z) M+ u" ^# H" x4 r5 e! J* [⎡ % w' u- Q2 o3 V* ~0 @" @ 4 v/ k1 z3 c* |, P/ }* y. B! J
# O2 p" e) I* B6 K+ j. y9 e) J0* r2 \; M0 p3 j& J5 ~3 T: B
1( i `2 n& O, H/ _
∞% e2 o; i+ c( p5 @4 s- K, B: u
97 L, f* S5 Y8 K; _) n
/ \. V5 H( G. \% T
! s" H$ r7 g/ f! p8 h
∞) d. q. _7 Z7 s! t6 Y5 z: {7 ?
08 [! X8 F4 I j4 z; w! F
∞1 I6 F2 ^. L. W0 U# i" n- r/ _: y
8 ! V1 |* i; Z5 R* S% j + h# i. ?3 t5 T * z9 L& N D7 s7 D* n! y" I3 2 C. C( L, L4 P2. ^: Z/ s# }$ J" G& k$ C: v( H. v
0, T1 `1 o! `: K* R3 h
∞ % ?* d% [9 L7 l* Q7 ? O1 H* ? M* G" M! L % s) m5 _, R. L' X- Q) o" u4 z
∞' G8 W# G7 v) D& R7 t
∞; c& p2 q: H- ~ B. f
34 J* t/ ?& I0 F$ N8 n
0) W' _2 Z) s0 r1 g5 m7 f
4 P5 w' m: m8 w9 c* a
* U$ B6 o( t/ x
⎦ ! |0 ?5 h1 K1 l' h% W& u⎥7 a. q2 c; y8 J
⎥ , l: Z2 G* O2 O( c6 Q6 W# N; o# E⎤ # A' L3 r2 U+ n/ ^6 [1 W , U5 Z6 A( c7 n( l" V; O6 J
+ g+ t% ?9 Z6 q% A6 L; n2)邻接表1 K) S6 u' d9 y3 d, a
邻接表是图中常用的存储结构之一,采用链表来存储,每个顶点都有一个链表,链表的数据表示和当前顶点直接相邻的顶点的数据( v , w ) (v, w)(v,w),即 顶点 和 边权。& \- S! G2 z% Y& N( A8 I: k
它的优点是:对于稀疏图不会有数据浪费;缺点就是实现相对邻接矩阵来说较麻烦,需要自己实现链表,动态分配内存。 . x8 S% N0 _2 P9 \! _& q& V. e如图所示,d a t a datadata 即 ( v , w ) (v, w)(v,w) 二元组,代表和对应顶点 u uu 直接相连的顶点数据,w ww 代表 u → v u \to vu→v 的边权,n e x t nextnext 是一个指针,指向下一个 ( v , w ) (v, w)(v,w) 二元组。 # }: |, ]- ~* g, L - T+ h! i2 Y. G- d& O X5 H6 K8 e* a( ^9 }! {- \ I- x: t+ a
在 C++ 中,还可以使用 vector 这个容器来代替链表的功能; " e# w8 M% T1 x! I Y( P vector<Edge> edges[maxn]; * S6 ?, l% T% Y M- V/ h. X1( |& H" t7 s3 ] u! `7 {
3)前向星0 Y _9 u) B& |9 g$ ]2 C3 C
前向星是以存储边的方式来存储图,先将边读入并存储在连续的数组中,然后按照边的起点进行排序,这样数组中起点相等的边就能够在数组中进行连续访问了。 8 @; B) R* w0 \( z4 C. [它的优点是实现简单,容易理解;缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序,带来了时间开销,实用性也较差,只适合离线算法。2 A3 g4 y' t7 R+ i
如图所示,表示的是三元组 ( u , v , w ) (u, v, w)(u,v,w) 的数组,i d x idxidx 代表数组下标。& g& Y! A9 ^ s1 s Z* p7 `/ @5 {9 e
8 O8 h6 i: P" m0 z/ K1 f 1 g9 R/ v. x% m( x j! n那么用哪种数据结构才能满足所有图的需求呢? 2 {" @0 V0 V* z! ?, Z/ X9 |接下来介绍一种新的数据结构 —— 链式前向星。 . P, i5 `6 F. i4)链式前向星4 j% v P) H# P$ J' ~( c! B$ j
链式前向星和邻接表类似,也是链式结构和数组结构的结合,每个结点 i ii 都有一个链表,链表的所有数据是从 i ii 出发的所有边的集合(对比邻接表存的是顶点集合),边的表示为一个四元组 ( u , v , w , n e x t ) (u, v, w, next)(u,v,w,next),其中 ( u , v ) (u, v)(u,v) 代表该条边的有向顶点对 u → v u \to vu→v,w ww 代表边上的权值,n e x t nextnext 指向下一条边。 ) m7 f9 g( J4 x2 [* j具体的,我们需要一个边的结构体数组 edge[maxm],maxm表示边的总数,所有边都存储在这个结构体数组中,并且用head来指向 i ii 结点的第一条边。 % z, Z* y0 y7 h2 L; }边的结构体声明如下: : S. n* s* Q9 ]3 S9 M% \! _4 ?struct Edge {% ^4 @, u' Y- v
int u, v, w, next;& [0 `; L5 P: F
Edge() {}7 S; |( q5 k$ S( p& `0 d5 \! a1 K; p
Edge(int _u, int _v, int _w, int _next) :: @/ h6 I; x% Y2 z
u(_u), v(_v), w(_w), next(_next) 3 K8 e3 q' l1 Y6 B$ c& E# k { A U0 Q w; ?0 b
} 6 W# R; d4 K' f# b3 R}edge[maxm]; ^/ {) G/ q& K6 I m- s
1 4 ~4 q0 b$ E+ K& ^2( D) ^' q- I- N) V0 g5 N) N) a+ }$ {
3. H6 J# R8 f; G. w
4 + L. U/ T+ S" K+ w* K5 2 z' G3 M" t, q1 n6 # t3 D, z' @3 i* ~, |& Y- O- t5 L7 ) G1 Y& l; I6 o: b- M" u8/ L% v1 g. v' r9 h
初始化所有的head = -1,当前边总数 edgeCount = 0; $ Z" P# ?: b. X7 ^每读入一条 u → v u \to vu→v 的边,调用 addEdge(u, v, w),具体函数的实现如下:! S8 G: G; b; q8 z g
void addEdge(int u, int v, int w) {) i1 m0 l1 V. ~! P9 A
edge[edgeCount] = Edge(u, v, w, head);3 c/ o7 W4 U N, `' M
head = edgeCount++;# x2 M4 ?! P& u' h
} , ~/ s, @. |' v8 _16 X) L9 P, |$ f" P {, E0 _
2 9 V# E' t9 D1 o: U30 L1 x" @8 N$ m
4 * W7 j/ M% l5 `" d: k这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w)(u,v,w),就在原有的链表结构的首部插入这条边,使得每次插入的时间复杂度为 O ( 1 ) O(1)O(1),所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现,空间上没有浪费,时间上也是最小开销。 6 ~+ M" A7 _" F9 e5 F b调用的时候只要通过head就能访问到由 i ii 出发的第一条边的编号,通过编号到edge数组进行索引可以得到边的具体信息,然后根据这条边的next域可以得到第二条边的编号,以此类推,直到 next域为 -1 为止。6 h/ ` W9 U. p6 c
for (int e = head; ~e; e = edges[e].next) { # R5 d/ W- H9 D8 m int v = edges[e].v; ( Z- ~, p) N! @ ValueType w = edges[e].w;% ^3 J" s% D0 P; f/ a1 G
...$ k3 U' w q$ ~7 w @
}5 q/ T$ B/ k2 d3 B |% R8 t
1 ; Z+ J! |% q) Q, ~. \. e' B9 \, L2: j) t8 F" `/ J4 s7 Z8 X* F1 V- [4 R
35 x0 o, K) o& n
4 ; G9 `: |, s% H K; ~5 " |2 ?9 k2 R0 e% N/ b文中的 ~e等价于 e != -1,是对e进行二进制取反的操作(-1 的的补码二进制全是 1,取反后变成全 0,这样就使得条件不满足跳出循环)。 ! v3 g1 |2 y8 N* ~. G8 c7 d4、算法入门 5 f8 _3 w! Y9 r# v6 c算法入门,其实就是要开始我们的刷题之旅了。先给出思维导图,然后一一介绍入门十大算法。 $ y; u6 E/ I6 R, g0 l2 o6 ^3 `* k+ b
, O O0 @9 T# ^% V7 ^# q入门十大算法是 枚举、排序、模拟、二分、双指针、差分法、位运算、贪心、迭代、分治。 3 G3 z _& Z0 O; m对于这十大算法,我会逐步更新道这个专栏里面:《LeetCode算法全集》。 5 [ W" H! R' E2 \- `( b1、枚举 ( |- ?+ t) f! G/ X枚举可以简单理解成for循环,从一个数组中遍历查找一个值,就是枚举;从一个数组中找到一个最大值,就是枚举;求数组所有数的和,也是枚举。 & k. B7 y1 @' f" a, `' f对于枚举而言,基本就是循环语句的语法学会,这个算法就算学会了。 2 f1 P) n; H9 q5 A, C2、排序# E3 Z) ^" f1 u, k
既然是入门,千万不要去看快排、希尔排序这种冷门排序。 & A% a6 x5 b' X( ~. W7 ?9 _冒泡排序、选择排序、简单插入排序 原理好懂,先看懂再说,其他不管。因为这三者都是基于枚举的。 - B* H% W' q5 w+ P7 MC中有现成qsort排序函数,C++中有现成 sort排序函数,直接拿来用,等算法进阶时再回头来看快速排序的算法实现。0 P( N) u+ n$ G6 v, O" w7 T( ]
3、模拟 0 |4 y% j5 |0 }( |模拟就是要求做什么,你就做什么,完全不要去考虑效率问题。 ) J5 C; ?# [5 S4 C3 N6 i- y- v- I不管时间复杂度 和 空间复杂度,放手去做!) d+ k( b: j# N9 L
但是,有时候模拟题需要一些复杂的数据结构,所以模拟题难起来也可以很男,难上加难。 2 d) o- U" a1 u+ t/ d% h4、二分 3 U& T8 O9 q1 o, J) L二分一般指二分查找,当然有时候也指代二分枚举。 3 `+ M) O$ l) J例如,在一个有序数组中查找值,我们一般这个干: - I1 x! J' E# @9 y1)令初始情况下,数组下标从 0 开始,且数组长度为 n nn,则定义一个区间,它的左端点是 l = 0 l=0l=0,右端点是 r = n − 1 r = n-1r=n−1; - e- B" G9 c, w% {$ H( S: d" l3 @2)生成一个区间中点 m i d = ( l + r ) / 2 mid = (l + r) / 2mid=(l+r)/2,并且判断 m i d midmid 对应的数组元素和给定的目标值的大小关系,主要有三种: , |! N2 S# _) f; `! T" U 2.a)目标值 等于 数组元素,直接返回 m i d midmid; 4 v+ C5 }; W* b8 D- [% U 2.b)目标值 大于 数组元素,则代表目标值应该出现在区间 [ m i d + 1 , r ] [mid+1, r][mid+1,r],迭代左区间端点:l = m i d + 1 l = mid + 1l=mid+1;% k3 l4 k4 R8 I1 Y
2.c)目标值 小于 数组元素,则代表目标值应该出现在区间 [ l , m i d − 1 ] [l, mid-1][l,mid−1],迭代右区间端点:r = m i d − 1 r = mid - 1r=mid−1; - n2 b; z) p% _3)如果这时候 l > r l > rl>r,则说明没有找到目标值,返回 − 1 -1−1;否则,回到 2)继续迭代。 7 s, @9 E; W+ w; N# M, W5、双指针7 e# ]6 D$ A6 g$ o( q1 T$ W# c' R
双指针,主要是利用两个下标在一个数组上,根据问题的单调性,进行指针偏移,由于每个指针只往后偏移,所以时间复杂度可以达到 O ( n ) O(n)O(n),由于思想非常简单,所以出题时,热度不低。 3 L f1 S2 a! T$ s& O" ` ' F7 i- e4 Q" W5 N* `" M* A 8 H- I. ]/ F H+ Z6、差分法: n: B0 d- I% Y% t' [' j0 l3 X' b
差分法一般配合前缀和。 1 l* K0 j6 @3 Z9 t4 y: D对于区间 [ l , r ] [l, r][l,r] 内求满足数量的数,可以利用差分法分解问题; ( j8 T9 ]) `- f5 s c5 X: h假设 [ 0 , x ] [0, x][0,x] 内的 g o o d n u m b e r good \ numbergood number 数量为 g x g_xg 8 G; F! C+ ^9 o% lx( E0 s3 |) H6 O4 x) ]' T- c1 A2 O/ H
8 P% V7 z& P: i( U6 \
,那么区间 [ l , r ] [l, r][l,r] 内的数量就是 g r − g l − 1 g_r - g_{l-1}g + p1 T% i2 U! b" M3 f1 l( rr ! @0 e! g0 H. W+ u0 \* ] 0 s) h9 P- ^# E: j( Q* Y
−g 4 E+ H9 X5 j- al−19 t! u s; U5 C& Q+ ]3 ]' ?
* X2 l4 w3 y; q9 W ;分别用同样的方法求出 g r g_rg 0 Y7 e9 P: t( l: t' M8 Lr % X" Q8 U$ i8 T. x8 P/ a " b# \8 ~$ o- T( \9 M 和 g l − 1 g_{l-1}g . ]4 B* D$ o0 ]8 L* `" r5 W. m* Z
l−1 * r. m# C- V7 W% q! \# t , I$ ^* [% q: J6 A ,再相减即可; $ b V# E, q; O. [ 6 X9 P7 H% V4 `0 ~* g9 V ~. X4 b# \ a$ [3 _5 s3 O1 {/ }9 p& L
7、位运算% `9 S: U3 c( k0 a: q
位运算可以理解成对二进制数字上的每一个位进行操作的运算。9 r1 K* _* x. U+ x3 T
位运算分为 布尔位运算符 和 移位位运算符。5 h! C) E, _ ^
布尔位运算符又分为 位与(&)、位或(|)、异或(^)、按位取反(~);移位位运算符分为 左移(<<) 和 右移(>>)。6 m7 T* {$ l& ?; {( V
如图所示:% j1 @1 t% i& J6 N& |" h