QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4412|回复: 1
打印 上一主题 下一主题

❤️两万字《算法 + 数据结构》全套路线❤️(建议收藏)

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2021-7-8 15:06 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta

    + x7 f4 z* K% p2 N# O❤️两万字《算法 + 数据结构》全套路线❤️(建议收藏)
    ) _  m& ~8 ]6 j5 L' O- W' r. x
    % s6 O9 Q# X0 |6 v前言
    0 g7 n5 }: A" H2 l% R# B  所谓活到老,学到老,虽然我感觉自己已经学了很多算法了,但是昨天熬夜整理完以后发现,自己还是个弟弟,实在忍不住了,打算把 算法学习路线 发出来,我把整个算法学习的阶段总结成了五个步骤,分别为: 基础语法学习(重要)、语法配套练习、数据结构、算法入门、算法进阶。本文梳理了这五个大项的思维导图,在下文会有详细介绍。5 D. h* c+ `; g/ y; H2 e
      希望各位能够找到自己的定位,通过自己的努力在算法这条路上越走越远。) I7 O3 S9 S- `7 u: x
      刚开始切勿心浮气躁,千万不要给自己立 flag,说一定要把这么多东西都学会。就算你的精力旺盛,日夜操劳,时间也是有限的。所以,首先是明确我们要做什么,然后制定好一个合理的 目标 ,再一点一点将要学习的内容逐步付诸实践才是最重要的。0 ?/ r- y$ W4 g6 \) L, ^5 ]( X/ @
      每日一篇C语言打卡,目前更新到:光天化日学C语言(20)- 赋值运算符与赋值表达式 | 让代码变得更加简介(建议收藏)。0 |6 s4 k, }3 z1 f6 o: T, g

    2 w7 e1 J9 D4 U4 a

    7 ?# N5 s7 f2 b- X8 k1 V3 H6 X' `
    0 @+ Y' J; ~: q/ d4 o0 p8 b" I. ], Q

    2 j4 t! b! e0 r, F  u. t3 l, E
    3 R! p% p; `1 [( `5 {5 r2 L

    , m$ N, w0 o2 L, n$ s4 O/ G

      b# f6 U& p! c; h/ J* Q. R图片较大,文章中有拆解,需要原图可以留言找我要哈' U& }1 i/ q2 S: i3 s0 l, O+ _* Y
    1、基础语法学习
    ' I9 g! i+ |( n" ]算法是以编程语言为基础的,所以选择一门编程语言来学习是必须的。' E5 H& G/ c2 t& W, V
    因为作者本身是C/C++技术栈的,所以就拿C语言来举例子吧。如果是 Java、Python 技术栈,可以跳过 C语言相关的内容。这一小节,先给出学习路线图,然后我再来讲,每部分应该如何去学。
    ' t  Z2 C* @  K; s/ v+ _% I8 O6 `) \+ e9 W; t- C7 M* J# M

    ! H6 q6 V5 ^5 @4 P
    4 W$ N/ l7 ?% a
    5 {. q; c$ U& U- M+ B5 t
    1)HelloWorld" Q% o& z* |) G5 S
    无论是 Java、Python、C/C++,想要上手一门语言,第一步一定是 HelloWorld,先不要急着去配环境。如果环境配了几个小时,可能一开始的雄心壮志就被配环境的过程消磨殆尽,更加不要谈日后的丰功伟业了。  Y6 {, c  K6 Y) H( P: u+ T
    2)让自己产生兴趣
    . v7 b5 D) [1 E* \/ Z所以,我们需要让这件事情从一开始就变得 有趣,这样才能坚持下去。比如找一个相对较为有趣的教程,这里我会推荐这个:《光天化日学C语言》。听名字就比较搞笑,可能作者本身也不是什么正经人,哈哈哈!虽然不能作为一个严谨的教程去学,起码可以对搞笑的内容先产生兴趣。从而对于语言本身有学习下去的动力。
    8 C  o0 `) }3 F1 ^# o刚才提到的这个系列,可以先收藏起来。回头再去看,它讲述的是 对白式 的 C语言教学,从最简单的输出 HelloWorld 这个字符串开始讲起,逐渐让读者产生对C语言的兴趣。这个系列的作者是前 WorldFinal 退役选手,一直致力于 将困难的问题讲明白 。我看了他的大部分教程,基本都能一遍看懂。算了,不装了,摊牌了,因为我就是这个作者。( \  g& m; V0 ]& t1 L
    3)目录是精髓% V4 l! k' Q. v: _- v1 |
    然后,我们大致看下你选择的教程的前几个章节,那些标题是否有你认知以外的名词出现,比如以这个思维导图为例,前几个章节为:( L- \: l6 q! `: A. f+ s/ Y
    1、第一个C语言程序4 C6 W" A' y0 j" t- n* o$ \4 S
    2、搭建本地环境/ U$ C7 X6 S! V; d- C6 K+ o% w4 V; D
    3、变量
    9 z0 ]- W0 K2 b9 Z2 n; n4、标准输出& W& S& [( G4 f8 c, H1 K
    5、标准输入" N. g: R$ }# p1 T- E' M
    6、进制转换入门: {( @. I! T1 j1 e* T) |3 x# x
    7、ASCII字符* F. Z6 ?" p* u0 j% ~5 z+ i
    8、常量$ V' Y3 P5 }7 ~# x

    ' R2 L- d% x# `3 D8 C- w& @" E8 H

    6 A* u: c6 ^# d6 `4 N+ l如果你觉得这些名词中有 3 / 4 以上是没有什么概念的。那么,可能需要补齐一些数学、计算机方面的基础知识。反之,我们就可以继续下一步了。" p. f2 G2 c1 b
    4)习惯思考并爱上它
    % o1 v3 i5 s& e只要对一件事情养成习惯以后,你就会发现,再难的事情,都只是一点一点积累的过程。重要的是,每天学习的过程一定要吃透,养成主动思考的好习惯。因为,越到后面肯定是越难的,如果前期不养成习惯,后面很可能心有余而力不足。0 Y; }$ x4 V/ w% B! B) I  N7 f
    就像刷题,一旦不会做就去找解题报告,最后就养成了看解题报告才会做题的习惯。当然这也是一种习惯,只不过不是一种好习惯罢了。
    * ^; M- n( L1 l8 V0 l7 U5)实践是检验真理的唯一标准
    5 J& e1 f& H) y: g光看教程肯定是不行的,写代码肯定还是要动手的,因为有些语法你看一遍,必定忘记。但是写了几遍,永世难忘。这或许就是写代码的魅力所在吧。% V) F; `' S1 m$ D1 P: O# q4 t
    所以,记得多写代码实践哟 (^U^)ノ~YO
    - i# G$ T' ^9 Y$ u8 W. s% B! _9 i6)坚持其实并没有那么难
    $ u$ T# U$ a0 c每天把教程上的内容,自己在键盘上敲一遍,坚持一天,两天,三天。你会发现,第四天就变成了习惯。所以坚持就是今天做了这件事情,明天继续做。
    . t9 Y' g- h2 s% C# b( z/ Q7)适当给予正反馈
    + A7 m3 K( k1 F/ Y8 H  _+ {' {然而,就算再有趣的教程,看多了都会乏味,这是人性决定的,你我都逃不了。能够让你坚持下去的只有你自己,这时候,适当给予自己一些正反馈就显得尤为重要。比如,可以用一张表格将自己的学习计划记录下来,然后每天都去分析一下自己的数据。1 F, ~8 Z" U, b1 L. y6 N5 `- g
    当然,你也可以和我一样,创建一个博客,然后每天更新博文,就算没有内容,也坚持日更,久而久之,你会发现,下笔如有神,键盘任我行!更新的内容,可以是自己的学习笔记,心路历程 等等。
    ; m  n( ]4 C! U! d. {* X) K看着每天的粉丝量呈指数级增长,这是全网对你的认可,应该没有什么会是比这个更好的正反馈了。% D: _& I  ]6 j$ L; X  |
    8)学习需要有仪式感
    4 [/ f4 b1 ~( A/ d+ H" @/ V那么,至此,不知道屏幕前的你感想如何,反正正在打字的我已经激情澎湃了。已经全然忘记这一章是要讲C语言基础的了!/ W& e' a6 X7 I! H
    介于篇幅,我会把C语言基础的内容,放在这个专栏 《光天化日学C语言》 里面去讲,一天更新一篇,对啊,既然说了要坚持,要养成习惯,我当然也要做到啦~如果你学到了哪一章,可以在评论区评论 “打卡” ,也算是一种全网见证嘛!
    * z+ g0 n2 x- Y+ U我也很希望大家的学习速度能够超越我的更新速度。4 W+ r6 k+ `2 m
    2、语法配套练习
    " F/ Z9 H. L* o  Z! {5 W8 E# ]1 F学习的过程中,做题当然也是免不了的,还是应征那句话:实践是检验真理的唯一标准。
    8 e3 [7 [% @7 ^+ S* [- ~1 j4 K# S' I而这里的题库,是我花了大量时间,搜罗了网上各大C语言教程里的例题,总结出来的思维导图,可以先大致看一眼:
    6 c+ I. j7 ]5 E' ~, ^( a6 g
    7 k  V# q+ W& Q' d0 I

    8 \3 g) v; J. o5 b+ F
    - ^6 |( i2 k6 @
    % P* M# y: I# g8 v2 r* s- x
    从数学基础、输入输出、数据类型、循环、数组、指针、函数、位运算、结构体、排序 等几个方面,总结出的具有概括性的例题 100 道 《C语言入门100例》,目前还在更新中。
    ' C  \- F; `  B' ~' K/ D  b5 t. b这里可以列举几个例子:
    ( Q5 U) a" }, X9 ^6 B1、例题1:交换变量的值
    8 ~) x! p7 S- @! A  Q7 R4 F- s+ X7 R+ x一、题目描述& f! ~3 A. F0 f- i$ t; s. V/ G
      循环输入,每输入两个数 a aa 和 b bb,交换两者的值后输出 a aa 和 b bb。当没有任何输入时,结束程序。. ~0 N; k: M/ Z1 s
    & W* G0 m- c3 e/ L

    ) J# y1 m; e4 [, f: Z8 D5 K/ f% j) M, U9 z2 u! }2 W

    6 m# ~; _7 m; D5 {* g* T二、解题思路
    $ N5 R: r! A* \5 V5 [- Y  e- ?难度:🔴⚪⚪⚪⚪8 L+ n; R+ P; X0 ^# D  z& t

    & a3 ?- i7 E* b
    " o: e8 v8 X  x9 g  z- p' T
    这个题的核心是考察如何交换两个变量的值,不像 python,我们可以直接写出下面这样的代码就实现了变量的交换。
    ! S; }. k* O5 D8 o: Ca, b = b, a- s: L- V# b$ K) n0 x
    1- t' ]% O# P: U3 S# o
    在C语言里,这个语法是错误的。- m, Q$ A! N! d" R0 M9 I
    我们可以这么理解,你有两个杯子 a aa 和 b bb,两个杯子里都盛满了水,现在想把两个杯子里的水交换一下,那么第一个想到的方法是什么?
    5 u3 [. U6 f- t0 ]3 P6 u当然是再找来一个临时杯子:" |! _% U8 _. n
      1)先把 a aa 杯子的水倒进这个临时的杯子里;( s3 u5 M# `" M9 X& D6 r
      2)再把 b bb 杯子的水倒进 a aa 杯子里;9 f6 F' T2 {3 K1 [$ z6 G
      3)最后把临时杯子里的水倒进 b bb 杯子;8 B' u  K7 Z+ p" j

    : E7 x3 X, i6 r& {2 B' Z1 q

    - D6 I8 ?- `5 A$ R1 _这种就是临时变量法,那么当然,还有很多很多的方法,接下来就让我们来见识一下吧。( E& G+ W0 p# \$ a/ ]5 p% w
    0 ^9 J+ _  A. N' m8 I. [

    7 i2 T. p# Q3 a# W8 p: N6 G0 `) W三、代码详解
    9 `/ f& c" z8 E8 N  Y9 g* a1、正确解法1:引入临时变量
    ( P* [( s* h( g  S/ i  I9 F  @- }' Q#include <stdio.h>
    . v8 l; Q3 X6 k: e7 M! Oint main() {
    3 M( x2 V3 d) e6 L6 ?- [    int a, b, tmp;
    5 h" K- P9 s0 p5 F        while (scanf("%d %d", &a, &b) != EOF) {
    & O  W; X& A8 z  R: g            tmp = a;   // (1)
    9 d( ^& @% X+ s            a = b;     // (2)
    % @. v3 z  W' n( \            b = tmp;   // (3)) Q6 K$ Y; @2 K1 ?5 _
                printf("%d %d\n", a, b);
    * Q9 }5 N8 I! O& e        }/ e! N8 n6 a' R5 e7 q5 p8 G* E9 P
            return 0;% s' X6 N* o2 I% L
    }
    : L5 p8 i  B# l9 L/ b9 `1
    ' Y1 f# K' m* a8 H/ V  r2
    . @( ~& f8 `7 H3* x7 Z* R, V0 F) L
    4: y/ v2 b' ^7 }0 T! q! ]2 z
    5! W* P% g& o8 o+ _! x
    6
    , k( ]- l: M+ g  ^6 K! |7* O* }* ?# D) n8 R
    83 y+ q; r* F2 n% T0 D" r, W
    9& d3 Y  ~4 n% M- d9 x7 R+ g
    10/ H9 L! ^: D6 N! G0 ?
    11
    : f# f$ D' g" ^" M0 x* ?; L( z% b( 1 ) (1)(1) tmp = a;表示把 a aa 杯子的水倒进这个临时的杯子里;
    9 Z7 a0 S3 @2 C: F) V9 |, B( 2 ) (2)(2) a = b;表示把 b bb 杯子的水倒进 a aa 杯子里;" _/ v2 D) A, U/ k0 x' k" |1 K. `
    ( 3 ) (3)(3) b = tmp;表示把临时杯子里的水倒进 b bb 杯子里;; I) T1 M4 y4 ?, J  f
    这三步,就实现了变量 a aa 和 b bb 的交换。5 |/ d# ~! _$ q0 k$ y
    2、正确解法2:引入算术运算
    : b8 V  O. r; A  v! y#include <stdio.h>+ z0 g/ b' j6 I
    int main() {3 B$ w! F& `9 t; ]4 `1 k
        int a, b;% U, e8 O" Q# D4 A) e
            while (scanf("%d %d", &a, &b) != EOF) {4 j9 c4 N% B/ R! ^' {
                a = a + b;   // (1)
    ) R# z7 Y- O- K4 I1 M" Y9 X            b = a - b;   // (2)
    5 ^- O0 [% U6 G- O3 R            a = a - b;   // (3)
    * _# s- f. g% Y9 ^* Y' R- I/ D            printf("%d %d\n", a, b);$ [3 J8 H: O; ]6 ]& l1 e" |
            }. X; Q0 }- B* I7 c; h& n8 T# }' p
            return 0;2 I/ C0 Q0 C$ D7 y
    }
    ! \* R# t. S9 W* C' p  s1 T% N2 y; E1% a1 V4 N% h/ q
    2  ^- ^$ }: v6 A# c/ M, w+ q8 Q0 b
    3
    - e/ b) F% e  I4
    6 z  q) l" V+ o% j5
    9 e: \: D) j) S" y' X6- O1 L- D; |# B6 K" z
    7
    ; E7 A! L( i; y5 z; {" j8+ f! d/ U/ ?6 K- @7 }9 q
    9" m/ m4 T! c' z
    10
    * F$ l9 A6 T; G# e8 V7 C3 ?11: u% p: k" e( e) z
    ( 1 ) (1)(1) a = a + b;执行完毕后,现在最新的a的值变成原先的a + b的值;& R0 n/ O# ^* u* P) [2 U& Q
    ( 2 ) (2)(2) b = a - b;执行完毕后,相当于b的值变成了a + b - b,即原先a的值;$ t- n. `$ k& f6 T" g0 L
    ( 3 ) (3)(3) a = a - b;执行完毕后,相当于a的值变成了a + b - a,即原先b的值;
    0 a* ?. c" W) z从而实现了变量a和b的交换。; @) l/ n8 x% K; [
    3、正确解法3:引入异或运算4 Q8 I& m! V4 j- u
    首先,介绍一下C语言中的^符号,代表的是异或。
    ; k/ v4 ^) V% N0 w二进制的异或,就是两个数转换成二进制表示后,按照位进行以下运算:
    ! \% g3 o# `! o5 N) n( G左操作数        右操作数        异或结果5 [: u* v* _( F3 P5 q: O3 C! r, F
    0        0        0
    8 V0 K  |" D+ P' f1        1        0: Q% D# A4 l% O# J3 ^5 Q4 ?& l# R
    0        1        1" j$ J( D9 R5 B3 n* a  G
    1        0        1# k) Y' |' v$ J% ~  v8 [5 Y
    也就是对于 0 和 1,相同的数异或为 0,不同的数异或为 1。
    ) J8 ~" s* d9 @; ~1 C% i( i! y' C这样就有了三个比较清晰的性质:
    $ I% N9 |! M0 m1)两个相同的十进制数异或的结果一定位零。* s8 N- z, l) U* E
    2)任何一个数和 0 的异或结果一定是它本身。# Q1 t4 W: i; q0 M9 u$ s, U+ O: p
    3)异或运算满足结合律和交换律。
    : T& _  \1 I! X% @* z1 z#include <stdio.h>1 |- }9 C# N) W* z* y6 l9 I
    int main() {3 C6 _7 K2 P( G) }+ i2 T, }1 M8 P, q
        int a, b;
    $ ~  m' w' W- z* H        while (scanf("%d %d", &a, &b) != EOF) {
    7 C: }% d+ D( n) C; c% ]2 y            a = a ^ b;   // (1)' p# x8 y( c1 w& y4 W2 k( x: p7 j+ g" v8 Q
                b = a ^ b;   // (2)' p$ m+ D7 F8 d! L8 \2 m0 H
                a = a ^ b;   // (3)
      R" l) b" f. g            printf("%d %d\n", a, b);( l7 Z8 v2 k- L
            }
    ! d" v8 [3 w8 |1 f2 I0 T" Q$ K# q+ X        return 0;* Q6 W% r9 c% [) [' b7 d! I2 S
    }5 g! p  {3 }2 s0 }8 P' H. D  _
    1- o5 I( U# X, S( e0 Q+ p, Y' y2 D
    2  ?0 ^3 j" Z8 S2 W! M) \" s
    3
    2 R) p, K+ R4 q' U4
    2 s, f4 s/ B2 C+ G  W5: {  O" ~& ?9 m% I
    6
      t/ [& S: h' l. q3 l, P( M7  d: ?# I1 J* A. s
    81 u/ ^' i; [7 a  w9 z6 c( B
    94 ~3 Q. ?0 _* l; _& l, y6 F1 }  z
    10
    ; u+ M$ \3 y& s5 f3 ]* X11& Q+ F4 S+ }" A2 L6 g
    我们直接来看 ( 1 ) (1)(1) 和 ( 2 ) (2)(2) 这两句话,相当于b等于a ^ b ^ b,根据异或的几个性质,我们知道,这时候的b的值已经变成原先a的值了。
    4 ?7 V8 x; d  v: a& F1 K而再来看最后一句话,相当于a等于a ^ b ^ a,还是根据异或的几个性质,这时候,a的值已经变成了原先b的值。/ N1 L" Y1 V2 b( v
    从而实现了变量a和b的交换。
    , Q3 I& Y0 G- {! s2 K9 _
    4 Z2 w! h: E6 H* t- j* a( E
    " N6 H2 A' e5 B! S% F( t4 m
    4、正确解法4:奇淫技巧
    3 g* V5 i: f% E* X' C当然,由于这个题目问的是交换变量后的输出,所以它是没办法知道我程序中是否真的进行了交换,所以可以干一些神奇的事情。比如这么写:7 {% u9 X8 N; e- C6 ^$ Z+ A
    #include <stdio.h>
    & k# e- a0 E+ {$ n' p8 Nint main() {
    % b; T1 n+ Q# {% \# b4 P    int a, b;6 L  \1 z) p  V4 U9 p
            while (scanf("%d %d", &a, &b) != EOF) {
    $ G" p6 M8 I' K# q$ f$ F* `( K            printf("%d %d\n", b, a);
    6 R% y, _5 p! `/ G' T* v        }
    4 M, F8 w% _  Z& G        return 0;  ]0 a- t/ x& a- G7 k, `' L& J
    }, ~7 y' [( R' }' c( |
    1/ B" i: u" k1 n3 Z
    2
    ! O* |! r. Q& Y30 n7 o3 @5 T$ B! X* }: f
    4
    3 h3 ~9 u, V% S- p  H+ d5
    1 r2 e; p: Z2 l9 w$ x6
    : Z. n& K9 y; i7 K# ~7
    , W, M- O3 O2 ]- \3 T! l$ j8' T' S! }) ~  U% {2 k( i
    你学废了吗 &#129315;?. R! r0 y6 D( B( g! t% Q
    2、例题2:整数溢出
    ( ^9 m  _: L4 l9 n一、题目描述% P- `- R, T& Y$ E
      先输入一个 t ( t ≤ 100 ) t (t \le 100)t(t≤100),然后输入 t tt 组数据。每组输入为 4 个正整数 a , b , c , d ( 0 ≤ a , b , c , d ≤ 2 62 ) a,b,c,d(0 \le a,b,c,d \le 2^{62})a,b,c,d(0≤a,b,c,d≤2 7 G7 X! S) b0 u1 Y+ z0 O5 t
    62
    2 |+ _8 @' Y2 Z7 x- h# B5 t/ H# q. u ),输出 a + b + c + d a+b+c+da+b+c+d 的值。
    6 [$ x0 B0 J( V% C5 [; b
    2 n8 h& b# f. Y% N

    : r, s2 M, D: e  a- h6 [6 K二、解题思路
      X5 S- |; q9 N, x: l& e难度:&#128308;&#128308;⚪⚪⚪
    ' {2 }  |  Y# C2 @& ]
    ' S  g% F( s$ J; I: f3 f

    * ^1 f9 R& `$ H0 F. [$ F8 {$ D这个问题考察的是对补码的理解。
    " S: {" n. d: w. ?( Q仔细观察题目给出的四个数的范围:[ 0 , 2 62 ] [0, 2^{62}][0,2 3 `5 i5 M$ K/ F
    62. b) @9 s) `- r& O2 s
    ],这四个数加起来的和最大值为 2 64 2^{64}2
    $ [% U7 j' E  I64
    , e$ T( l. s- q* l8 q( L- G3 u" e 。而C语言中,long long的最大值为:2 63 − 1 2^{63}-12
    - r3 k  Z; v; X63' Z* |6 w5 X& \* w* T4 O: ^
    −1,就算是unsigned long long,最大值也只有2 64 − 1 2^{64}-12 4 a! Q' W, l9 c! a- T) ?8 }
    64
    ! `, {# S0 h# ^0 G9 `9 W −1。
      n6 ]& t" }" Q% b5 {: X; E但是我们发现,只有当四个数都取得最大值 2 62 2^{62}2 " a3 e: K9 y! }7 {2 }
    62# ?& `4 d5 \9 P- L
      时,结果才为 2 64 2^{64}2 ' A; X# v" i5 s" p" {
    64
      [% i- r, ^  b7 D: ~+ M ,所以可以对这一种情况进行特殊判断,具体参考代码详解。
    # M0 Z  J  x% X三、代码详解
    2 u! m! T/ E0 }% o#include <stdio.h>6 B& V9 }) ?$ v; L
    typedef unsigned long long ull;                           // (1)
    9 N# H/ [, M) ?3 F: zconst ull MAX = (((ull)1)<<62);                           // (2)
    & q( _0 d  E8 r9 Q6 |' z9 p& x; t9 t% Q3 J  w# p/ q
    8 L. z4 T$ n9 |) O
    int main() {) }& G" G! S' G# Q+ R' r
            int t;
    * e) e# I) I/ H8 }; f3 a        ull a, b, c, d;' q! c  r$ \8 B
            scanf("%d", &t);
    $ ?& P& m" ]: ?# @  G* O1 c' Y$ X        while (t--) {# ~5 ?: P) L4 `9 I- T2 f9 {( _( I" I( V
                    scanf("%llu %llu %llu %llu", &a, &b, &c, &d);     // (3)& ^4 z/ }& b7 x9 m
                    if (a == MAX && b == MAX && c == MAX && d == MAX) // (4): h; |' ]* ~; _# ^5 Z8 T
                            printf("18446744073709551616\n");             // (5)
    - _2 L7 P3 ]- R6 r9 h$ r4 Q( F                else+ W4 x3 N! g  k) C
                            printf("%llu\n", a + b + c + d);              // (6)4 z( ~- f- g  i9 d* b1 p
            }" h' y. l- q0 @2 g/ r
            return 0;2 W2 N/ x9 G3 }& @
    }- a" U+ G! q. R- `8 U0 u
    1, g4 e6 p2 O+ j( @- }
    2
    0 {2 B5 P( B6 w; D3
    & J6 ^% z3 a# i41 b$ a/ L+ Z9 ]
    55 l$ u: b7 r: ?- Z
    66 P: D' o  Z8 e0 G  `  B9 ]: A9 ~
    7; ?& ]* \" Y3 a& z- _
    86 w1 @$ J$ \& V6 F6 q  D: f" e7 B
    91 e4 _6 t% w. i$ d4 a
    10
    + r# H5 ]* A; d! T6 n: g5 k11" p5 `+ {0 C: _
    12
    $ P6 ]+ |1 U) @  I# O13  \" W0 z+ c% g' o
    14
    4 m) \+ T/ W, l1 o15$ V/ W" b. i0 `# D0 c
    164 q- D) B+ \& T& Y9 _
    17
    7 D# _: F3 h8 k( 1 ) (1)(1) 由于这题数据量较大,所有数据都需要用64位无符号整型。ull作为unsigned long long的别名;. C+ D" d, x* d3 Q
    ( 2 ) (2)(2) 用常量MAX表示 2 62 2^{62}2
    9 Y7 l" o  E* U$ P- [' u! h+ B62
    ' u7 q' ]9 O5 R  E. Z7 x: _( D2 l4 S ,这里采用左移运算符直接实现 2 22 是幂运算;9 `! r$ I8 m( t6 E- I
    数学        C语言, R6 h: F: n$ N* ^3 H) Q
    2 n 2^n2
    9 K; T7 O& \2 H. F6 U6 Qn
    2 a  E; x4 S$ C4 h( U, H         1<<n
    ' a0 X4 a- s) j. H6 [: s' w% b需要注意的是,由于 1 是int类型,所以需要对 1 进行强制转换。(ull)1等价于(unsigned long long)1;
    ' X6 ~, f4 {0 L# l# Q1 Q( 3 ) (3)(3) %llu是无符号64位整型的输入方式;$ `8 c) Q8 E& X7 k8 |
    ( 4 ) (4)(4) 这里是对所有数都等于最大值的特殊判断,&&运算符的优先级低于==,所以这里不加括号也没事;" f  N7 W: P+ E% Z
    ( 5 ) (5)(5) 由于 2 64 2^{64}2
    6 t, M1 w" k+ j+ z; y) v648 ~' W7 K2 `7 o( Y: C( m1 F
      是无法用数字的形式输出的,所以我们提前计算机算好以后,用字符串的形式进行输出;: ?- C* j( y# J- J+ g
    ( 6 ) (6)(6) 其它情况都在 [ 0 , 2 64 − 1 ] [0, 2^{64}-1][0,2 0 r! e3 k' O9 Q8 i8 F
    64
    0 z" I) x* z  J) w7 S −1] 范围内,直接相加输出即可。. Q% g  m# M0 P& ]
    由于这个专栏是付费专栏,可能对学生党不是很友好,所以作者经过再三思考,打算放出 300 张 一折优惠券, 先到先得。只要拿这个图片来找作者即可享受,仅限前 300 名。
    4 P* y6 [3 t: u5 f8 Q为了适当提高一定门槛,你至少需要学会如何下载图片或者截图并且发送到微信里 &#129315;。
    $ Q8 a4 s4 n# u
    & P0 i% V1 u/ L/ v+ [

    ) T4 y7 e5 `+ H$ O" b3、数据结构; K0 C2 \; T* V! G
    《C语言入门100例》上的例题,如果能理解前面 25 道,那基本C语言的学习就可以告一段落了,接下来就要开始我们的数据结构的学习了。9 L' f; c; I2 Y! a/ ^& L+ Q! q% f; `
    1、什么是数据结构
    3 ]1 k3 w( |5 b" f  p7 V你可能听说过 数组、链表、队列、栈、堆、二叉树、图,没错,这些都是数据结构,但是你要问我什么是数据结构,我突然就一脸懵逼了。
    % D# p& {2 L4 k- ?* |3 E' Z6 m如果一定要给出一个官方的解释,那么它就是:; ~! ], Y* {- q7 J1 C  ^7 Y
    计算机存储、组织数据的方式。相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。往往同高效的检索算法和索引技术有关。: G: L# R& Y/ i7 h
    ) B/ d2 K+ o0 c& l

    # y, P! N+ ~! e( s6 e. o3 K3 i是不是还不如说它是堆,是栈,是队列呢?6 g0 M2 R, u3 A8 T: _( ?/ j9 H7 N7 K
    是这样的,我们学习的过程中,跳过一些不必要的概念,能够节省我们更多的时间,从而达到更好的效果,当你还在理解数据结构是什么的时候,可能人家已经知道了栈有哪些操作了。3 |: z( b6 c# ^* y
    2、数据结构和算法的关系9 ^2 E! O+ N3 M# E
    很多同学搞不明白,数据结构与算法有哪些千丝万缕的关系?甚至有些同学以为算法里本身就包含了数据结构。; o5 ^& \4 t2 Y/ D, ^/ {0 k
    数据结构主要讲解数据的组织形式,比如链表,堆,栈,队列。
    , y( W% Y: q% j# c而算法,则注重的是思想,比如链表的元素怎么插入、删除、查找?堆的元素怎么弹出来的?栈为什么是先进后出?队列又为什么是先进先出?' h( m/ i5 B7 G+ U$ F9 O! R/ ^
    讲得直白一点,数据结构是有实体的,算法是虚拟的;数据结构是物质上的,算法是精神上的。当然,物质和精神 缺一不可。
    " S" h1 M1 p6 a5 U: |3、数据结构概览/ ~# b2 T7 R; _  H3 P2 s
    周末花了一个下午整理的思维导图,数据结构:
    2 ^. `4 Q" u) x6 n: n: G) _6 @$ p9 K
    ( U+ e2 L. [2 E* X- d+ y$ \
    + H  e/ B4 e& f6 u
    常用的一些数据结构,各自有各自的优缺点,总结如下:
    ) G0 \" e" O9 E/ S% na、数组
    : B5 H: l) S8 R内存结构:内存空间连续
    ' Q$ s7 k" o& C  n* N实现难度:简单. m" v0 m& l  W0 |/ c/ b
    下标访问:支持
    * i; B9 F3 S4 _) l- p  G$ R& c- Q分类:静态数组、动态数组% j, S& t! G0 X/ |
    插入时间复杂度:O ( n ) O(n)O(n)' [, A. l9 p) d+ R
    查找时间复杂度:O ( n ) O(n)O(n)3 I  o7 T) u: R0 C# ?. E
    删除时间复杂度:O ( n ) O(n)O(n)  X' H# Z2 X, f' ]4 |
    4 [- }# O* c1 f, i/ f

    9 X  i. t$ V* b5 j+ I% Jb、字符串
    ( W# y) P% U" F5 e& g内存结构:内存空间连续,类似字符数组. ]6 E6 Z# \; M8 k2 y6 b: U
    实现难度:简单,一般系统会提供一些方便的字符串操作函数
    0 N* J: u, O' q7 }下标访问:支持
    % `& P8 A/ B4 @2 h" Y插入时间复杂度:O ( n ) O(n)O(n)
    & i" q7 r" i4 B! R0 }& i5 j查找时间复杂度:O ( n ) O(n)O(n)
    " }1 l. _# Y! L& g& @6 b删除时间复杂度:O ( n ) O(n)O(n)
    $ H. G( M' b: l5 \) O  E: q+ P& C' k. E* m# [: v" l
    9 h) j, e+ {/ I" ]( j, {9 |
    c、链表
    : ~0 e; r6 w; z  C/ s0 e9 E  i! Q8 W内存结构:内存空间连续不连续,看具体实现
    8 i. m. i. M1 W3 O) U/ L实现难度:一般8 u; P' l; W( I. d8 u7 W
    下标访问:不支持- h4 a* g  H: ?7 r
    分类:单向链表、双向链表、循环链表、DancingLinks  I) }; F1 C4 s) M* h8 `$ q& w
    插入时间复杂度:O ( 1 ) O(1)O(1), ]. J  N' o/ x0 c3 X4 g7 o' ?
    查找时间复杂度:O ( n ) O(n)O(n). z" a& A' |/ P$ m9 F$ a) D( |0 p
    删除时间复杂度:O ( 1 ) O(1)O(1)
    7 p4 T/ ?5 w' _* [3 C% v8 b3 z" k# R" S3 E- \
    ) g6 _! c8 @, e  X$ q7 ?- x
    d、哈希表
    3 g' v6 C- _8 j" B8 o0 A! ~3 z2 l内存结构:哈希表本身连续,但是衍生出来的结点逻辑上不连续
    / d. R! E% h2 ~9 t) z实现难度:一般" Q! k' m# v3 S, t( ^
    下标访问:不支持
    1 P1 \& s1 \! i6 K, K9 r! S分类:正数哈希、字符串哈希、滚动哈希8 o5 ~3 E0 k4 ^; @  p8 {
    插入时间复杂度:O ( 1 ) O(1)O(1)3 \8 m# W( R) G, K& P
    查找时间复杂度:O ( 1 ) O(1)O(1)2 x) e4 `8 A; n* B1 d) [
    删除时间复杂度:O ( 1 ) O(1)O(1), U- s. e, ^8 R
    ' v1 e0 U* P$ U: m
    , _1 F+ m$ n, V$ I
    e、队列
    8 s1 C  }; l6 `+ @5 p: o. O内存结构:看用数组实现,还是链表实现: y$ C$ s4 l( H. i* S% m
    实现难度:一般
    5 f! F0 {- \5 x, r下标访问:不支持
    + S0 ~3 {2 h* u9 S分类:FIFO、单调队列、双端队列- @) W. k. e1 b0 N& M' R+ w
    插入时间复杂度:O ( 1 ) O(1)O(1)4 l2 n: r- U% r+ }
    查找时间复杂度:理论上不支持
    # H: a% p' v0 B, {删除时间复杂度:O ( 1 ) O(1)O(1)$ w( b$ M0 r7 u$ E) ], c

    . E8 o$ k/ ?. Y7 Y' O! Z
    $ O. L) G% `8 Y
    f、栈! ]9 k: @5 O1 i
    内存结构:看用数组实现,还是链表实现
    . _1 R0 ^3 J# j$ c" e& e0 Y实现难度:一般8 `  s1 }( J. `3 b% j
    下标访问:不支持; Q& |* ^0 E6 |3 y( U
    分类:FILO、单调栈% j% }6 x0 t: B7 n7 E3 X; j
    插入时间复杂度:O ( 1 ) O(1)O(1)) h+ E. ]+ s5 R
    查找时间复杂度:理论上不支持
    ' F% \6 L, h$ j+ J7 p. w删除时间复杂度:O ( 1 ) O(1)O(1)
    $ @! I* l2 f; q. b' Z
    , _1 t& b# Z8 f5 g, U0 o9 Y4 y- L9 O

    , @& o" |+ r  _2 D5 _% Rg、树
    + s5 ^8 ]& q; Y8 I内存结构:内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续* a; w6 a: ?# S! Z/ c
    实现难度:较难5 D% \  o# k8 L% \8 ]/ K! c
    下标访问:不支持8 F$ l) q0 ^# p
    分类:二叉树 和 多叉树
    " \% J! d  _! {插入时间复杂度:看情况而定
    " |! N6 Y! m% [" t3 l4 ?查找时间复杂度:理论上 O ( l o g 2 n ) O(log_2n)O(log & z+ g$ t+ Y+ g( T5 k2 M& C
    2& _* y& E  C" U( B
    ​       
    , U9 O9 w# c5 { n)
    5 d3 C  m5 D* q' P% k/ i1 j删除时间复杂度:看情况而定
    ) P) W: a8 X1 a# I( W; Q7 T
    0 z' K3 I! t# ]5 q1 w9 t
    6 h; @( v) e, |& C3 K$ W
    1、二叉树
    ) O% n  b( D* a) R' r二叉树的种类较多,比如:二叉搜索树、平衡树。平衡树又可以分为 AVL 树、红黑树、线段树、堆。最平衡的树莫过于满二叉树了。
    , Z8 b( w5 D/ T6 Z其中,堆也是一种二叉树,也就是我们常说的优先队列。3 K9 |6 p. {9 o- B2 |) J$ a: }3 r
    2、多叉树4 P: n) G" k2 `$ O8 i
    B树和B+树是多叉树,当然我们平时学到的并查集其实也是个多叉树,更加严谨一点,应该称之为森林。
    ' P1 e% j. Q3 {h、图
    5 ~7 Y& B; u. X$ H* J: G" B内存结构:不一定
    $ _; W+ L/ u( v% y0 @2 d0 Q& n实现难度:难* h. L- v' a  L' A/ V
    下标访问:不支持1 X0 n9 K2 L- ^3 c
    分类:有向图、无向图; R! z3 G! k6 y, j2 ?# c
    插入时间复杂度:根据算法而定
    ; {2 y7 C& D' g查找时间复杂度:根据算法而定
    ' Q' p/ y' n7 C6 O: o' K3 K删除时间复杂度:根据算法而定  V! ?1 x2 j) H% B- h; S4 y
    5 p8 t1 A0 L- I! @1 v/ q
    6 \8 ]7 H$ ^7 L2 o- ^5 t
    1、图的概念& x9 j  R# u: b* y9 K
    在讲解最短路问题之前,首先需要介绍一下计算机中图(图论)的概念,如下:; U' {) ^# B$ [. v$ @
    图 G GG 是一个有序二元组 ( V , E ) (V,E)(V,E),其中 V VV 称为顶点集合,E EE 称为边集合,E EE 与 V VV 不相交。顶点集合的元素被称为顶点,边集合的元素被称为边。
    & G9 f& Y- F+ H对于无权图,边由二元组 ( 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 为权值,可以是任意类型。
    ' f8 S7 _( V; |: `6 o/ F图分为有向图和无向图,对于有向图, ( 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;: k/ A/ m' ]- T! y. x
    2、图的存储
    / G+ N' U( d9 S- f0 P对于图的存储,程序实现上也有多种方案,根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例,讲解四种存储图的方案。; i/ d4 M# a: `9 O9 ^- L

    7 f' n0 `0 t9 u5 ~
    % e  X7 K  y0 M4 s
    1)邻接矩阵* M/ D0 K9 x! U3 O7 o
    邻接矩阵是直接利用一个二维数组对边的关系进行存储,矩阵的第 i ii 行第 j jj 列的值 表示 i → j i \to ji→j 这条边的权值;特殊的,如果不存在这条边,用一个特殊标记 ∞ \infty∞ 来表示;如果 i = j i = ji=j,则权值为 0 00。
    / l) T0 w: y  Z+ e: b- q$ V它的优点是:实现非常简单,而且很容易理解;缺点也很明显,如果这个图是一个非常稀疏的图,图中边很少,但是点很多,就会造成非常大的内存浪费,点数过大的时候根本就无法存储。
    " C4 X6 j2 z1 x% t2 v; O3 ?( h9 u+ I[ 0 ∞ 3 ∞ 1 0 2 ∞ ∞ ∞ 0 3 9 8 ∞ 0 ] \left[
    5 Z! H8 o! L+ L  b0 N- T3 l9 b01∞9∞0∞8320∞∞∞30  T) P, N4 s  L
    0∞3∞102∞∞∞0398∞01 Z9 R. j% R- x6 h
    \right]
    ; ?, [7 @& b. L$ Y* j4 z, n
    $ e3 k; s' J. a* y
    - k' L, X+ J3 X! B( E$ p9 ?: J# z
    0 Q$ E" z: K( X' y+ [8 K0 j& u; k
    ​       
    7 j$ x) z+ N9 k: Z; B  ! r9 r& l7 V" Q; {9 i
    0, K2 ]: a3 h) f
    1
    : o' k7 ?7 _1 A! {( Q5 b* P: N1 R* e. a2 f; G5 f6 |
    9
    2 s. Y4 [* A2 a​       
    . [" n: u  y7 r/ p1 `  
    , J5 k' b- U" a+ t9 k
    : _! D' @" X! B& _2 w05 ~# L+ Z: y7 ~- U: b* s
    $ y+ E* C( Z5 J4 V1 O: j
    8
    ' e# c- P0 p0 z% h+ ?​       
      u  Z* t" _/ U2 N+ Q. O  7 O( i4 L. p" m& Y9 l1 G, l
    3
    ( Q) Z! {9 i$ x" P* q7 _- M% }2
    8 s* k+ ^' W$ u) e5 A3 ^1 ]0
    9 ~) T0 o% _$ R: o; }0 ~
    & b5 I. T2 c) t: p. a; G, B​        ( Y, Y9 e0 U$ m$ i5 J! k
      
    + o' N& ]0 w" x  D1 y/ V5 v. b; B7 m6 W

    ! l; G) s# @1 S% ^& @: `3( k( E5 x  D. Z* ~
    0) Y3 P$ E! ]0 a) X. N% v
    ​       
      P3 ?+ r4 Z6 l& C, U1 M# F5 D  
    7 Z" Y( R7 u; h9 Z1 O+ ?+ ?* c
    6 Q% O. ^+ R% ]9 u0 t* }8 g/ H' w
    ( c/ t3 a$ h% X2 U" h7 }* i3 l+ r. t  Z3 W4 g- S' B0 w
    ' V# V" d) i, y5 U/ E
    ​        0 k- N$ j; D! ?' ]% x8 h' _

    & h' t# r  f( e2 m1 c5 }7 [& O  t+ o3 m2)邻接表
    4 h& y* o2 B5 O1 A1 |邻接表是图中常用的存储结构之一,采用链表来存储,每个顶点都有一个链表,链表的数据表示和当前顶点直接相邻的顶点的数据( v , w ) (v, w)(v,w),即 顶点 和 边权。
      [( {0 \% W# \7 Q% h) T它的优点是:对于稀疏图不会有数据浪费;缺点就是实现相对邻接矩阵来说较麻烦,需要自己实现链表,动态分配内存。9 q) q9 W, ^3 N# t, e6 S
    如图所示,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) 二元组。9 M7 K  b' x6 G! Y9 g# J: w) i, j

    : b$ d% C( T5 \' K
    8 k# w: Q% I1 d- _4 \
    在 C++ 中,还可以使用 vector 这个容器来代替链表的功能;
    2 l3 |, Z: i) K, S    vector<Edge> edges[maxn];
    4 J2 Y( F( _+ U7 n. c  a17 O: b/ Z! ^! a0 l9 A6 F
    3)前向星5 J: s7 T1 y6 Z9 w2 [+ }' k1 n; c
    前向星是以存储边的方式来存储图,先将边读入并存储在连续的数组中,然后按照边的起点进行排序,这样数组中起点相等的边就能够在数组中进行连续访问了。
    5 T$ d4 e. f- _+ g它的优点是实现简单,容易理解;缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序,带来了时间开销,实用性也较差,只适合离线算法。; ^# E4 K* c; X* K1 c  N
    如图所示,表示的是三元组 ( u , v , w ) (u, v, w)(u,v,w) 的数组,i d x idxidx 代表数组下标。# E/ Y; M% e/ ]( F* L" I

    ( B5 x5 {4 }1 H: s3 H: V3 ~

    ' ]4 L! o. H1 H- x那么用哪种数据结构才能满足所有图的需求呢?
    " A7 |5 f1 J" p/ A3 ]9 l3 X接下来介绍一种新的数据结构 —— 链式前向星。( {  Q% Y, P# B$ q- B5 Y6 {7 X
    4)链式前向星. x& j! I/ Y4 k  f
    链式前向星和邻接表类似,也是链式结构和数组结构的结合,每个结点 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 指向下一条边。
    & J2 B8 E/ g* }具体的,我们需要一个边的结构体数组 edge[maxm],maxm表示边的总数,所有边都存储在这个结构体数组中,并且用head来指向 i ii 结点的第一条边。
    $ v3 r2 l" _" r+ D& V, ^" C' S边的结构体声明如下:5 s* z4 f8 V# U7 E6 F
    struct Edge {6 \" Q* V" L7 {& B0 t0 v
        int u, v, w, next;
    * T; w# n! i1 K4 y    Edge() {}, {8 b5 v  c  w  S
        Edge(int _u, int _v, int _w, int _next) :' R( F6 d8 Z2 w& ?
            u(_u), v(_v), w(_w), next(_next) $ U. @8 r4 b8 o( }
        {
    0 \# M0 U: I/ t  {    }
    * L! ^3 J; i4 \8 x! Y) D}edge[maxm];* t; S4 |# F- q$ _2 N
    1
    $ q& z& a; P# `2
    ' @, e5 g% E; K6 \9 ^2 c! O& h: s3
    / O5 k( Y( b' p" d. |4/ f2 s2 m1 I$ s+ R
    58 Q% u0 l+ H( ~* N3 d, C
    6) r, f; G! s) D2 s# H" [4 ?: z
    7. |1 I" f- Z6 l
    8
    % K+ O1 Q7 o$ U% H- |0 R, X- S7 X初始化所有的head = -1,当前边总数 edgeCount = 0;
    ) j- A- q$ A1 S0 w- U4 y每读入一条 u → v u \to vu→v 的边,调用 addEdge(u, v, w),具体函数的实现如下:- M/ U( u% F9 `2 A8 A
    void addEdge(int u, int v, int w) {
    8 z# r# X6 y4 [$ t4 z7 n3 H6 N    edge[edgeCount] = Edge(u, v, w, head);
    8 g1 Y' N0 s) h9 i0 l* H( G    head = edgeCount++;
    4 [/ D9 M. J+ F, q3 x% s# C$ c}
    4 h3 U! c+ O' [. w1
    3 A! f, {3 j2 B2
    7 F* j- h0 s; h$ b37 T* q, \3 `# W) f" V2 D% X9 W! ?
    4
    0 A6 g: d4 q6 }3 B/ c这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w)(u,v,w),就在原有的链表结构的首部插入这条边,使得每次插入的时间复杂度为 O ( 1 ) O(1)O(1),所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现,空间上没有浪费,时间上也是最小开销。
    + z/ ]- V- z4 F) y调用的时候只要通过head就能访问到由 i ii 出发的第一条边的编号,通过编号到edge数组进行索引可以得到边的具体信息,然后根据这条边的next域可以得到第二条边的编号,以此类推,直到 next域为 -1 为止。" J9 f( ?, V* f1 E7 |
    for (int e = head; ~e; e = edges[e].next) {/ l$ Y) X* A4 g7 f
        int v = edges[e].v;
    2 Q7 U" c% Q" `+ m; r% L    ValueType w = edges[e].w;& ^3 [7 o( F; q8 @' }
        ...1 f) N7 v8 H2 P! d$ w' j9 I' s
    }) u) A" Z% U! _: L/ ~' ?
    1
    7 J% {; k/ H8 J. D2
    6 P) ^' f- c' K& o* B# b, \, M3
    . b8 n$ V* Z% u42 R* W/ q5 I2 |. M* _
    5# X# `  R3 Q4 F* G2 B0 y9 f
    文中的 ~e等价于 e != -1,是对e进行二进制取反的操作(-1 的的补码二进制全是 1,取反后变成全 0,这样就使得条件不满足跳出循环)。
    7 a1 w3 E! l) l4、算法入门
    ' o0 i5 i5 C. o. T算法入门,其实就是要开始我们的刷题之旅了。先给出思维导图,然后一一介绍入门十大算法。
    & i# H+ n# O* |. n- M" D. N) g
    5 I+ W( A: {+ L% ^

    . u! ^) P  o0 E3 @7 M" ?4 A: X$ ]( s+ Y; L入门十大算法是 枚举、排序、模拟、二分、双指针、差分法、位运算、贪心、迭代、分治。$ C7 {& M- g" Y8 Q! a( D
    对于这十大算法,我会逐步更新道这个专栏里面:《LeetCode算法全集》。
    # e: Q: x* T0 |2 P1、枚举
    - T' n) O0 f, r3 I1 _7 t枚举可以简单理解成for循环,从一个数组中遍历查找一个值,就是枚举;从一个数组中找到一个最大值,就是枚举;求数组所有数的和,也是枚举。2 j' A9 S# O! G0 b# K
    对于枚举而言,基本就是循环语句的语法学会,这个算法就算学会了。: ?% x, g9 j( s3 J) B$ I7 v
    2、排序
    6 W, E& H' r; r% x既然是入门,千万不要去看快排、希尔排序这种冷门排序。9 a) I- ]9 z7 G5 s
    冒泡排序、选择排序、简单插入排序 原理好懂,先看懂再说,其他不管。因为这三者都是基于枚举的。# ]/ P$ B* _7 d- O
    C中有现成qsort排序函数,C++中有现成 sort排序函数,直接拿来用,等算法进阶时再回头来看快速排序的算法实现。
    % x: _9 f# e: [% ^# a1 _3、模拟
    . b7 H: |: c- ~# ^( C+ y) {/ ^. e' i4 t模拟就是要求做什么,你就做什么,完全不要去考虑效率问题。8 Q; i9 I: L& F8 s* C' u
    不管时间复杂度 和 空间复杂度,放手去做!
    7 f0 j" f$ t* m( c5 o: v但是,有时候模拟题需要一些复杂的数据结构,所以模拟题难起来也可以很男,难上加难。& N9 g+ j. m: |) T* E) z8 g
    4、二分* t* B& y4 \* b7 B# K
    二分一般指二分查找,当然有时候也指代二分枚举。7 u9 Z, G: e. K/ T
    例如,在一个有序数组中查找值,我们一般这个干:
    ) z7 \1 W7 l( U* m  p0 g1)令初始情况下,数组下标从 0 开始,且数组长度为 n nn,则定义一个区间,它的左端点是 l = 0 l=0l=0,右端点是 r = n − 1 r = n-1r=n−1;
    8 m/ [! `; {# s: z; j) R: x2 n9 S& Z2)生成一个区间中点 m i d = ( l + r ) / 2 mid = (l + r) / 2mid=(l+r)/2,并且判断 m i d midmid 对应的数组元素和给定的目标值的大小关系,主要有三种:
    ; d) A6 z, A4 Q/ o, `* B% a" x  2.a)目标值 等于 数组元素,直接返回 m i d midmid;
    4 Y, S2 u+ A6 T3 H1 }8 i  2.b)目标值 大于 数组元素,则代表目标值应该出现在区间 [ m i d + 1 , r ] [mid+1, r][mid+1,r],迭代左区间端点:l = m i d + 1 l = mid + 1l=mid+1;
    7 S8 w0 Q+ J# t3 ?, b' b$ a! P  2.c)目标值 小于 数组元素,则代表目标值应该出现在区间 [ l , m i d − 1 ] [l, mid-1][l,mid−1],迭代右区间端点:r = m i d − 1 r = mid - 1r=mid−1;2 k8 D/ h, v9 V) ~* a& ?
    3)如果这时候 l > r l > rl>r,则说明没有找到目标值,返回 − 1 -1−1;否则,回到 2)继续迭代。
    + W& Z  J- w2 {2 w; D+ ]" D5、双指针% f+ ^( G1 W5 u' J1 X
    双指针,主要是利用两个下标在一个数组上,根据问题的单调性,进行指针偏移,由于每个指针只往后偏移,所以时间复杂度可以达到 O ( n ) O(n)O(n),由于思想非常简单,所以出题时,热度不低。
    $ M% P; r5 U: D( T1 j+ p  ?2 M1 Z6 X8 }* U4 Q
    : k! Q7 \! K. ?1 F6 B/ i
    6、差分法  y& q) r% f; f0 |
    差分法一般配合前缀和。' l' e( h8 O& X* K
    对于区间 [ l , r ] [l, r][l,r] 内求满足数量的数,可以利用差分法分解问题;+ n  k4 D0 ?+ Y' v7 V
    假设 [ 0 , x ] [0, x][0,x] 内的 g o o d   n u m b e r good \ numbergood number 数量为 g x g_xg
    $ @4 o; q, A  s) t  Y7 Lx* Q/ v! Y) O  W9 |& u8 T
    ​       
    * F$ N* m2 L4 B- J4 O ,那么区间 [ l , r ] [l, r][l,r] 内的数量就是 g r − g l − 1 g_r - g_{l-1}g 7 }. }. T/ U* |' F7 t8 w2 O
    r2 ]8 H4 m# Z, U+ u
    ​       
    2 w" z! Q# E* Y$ j9 b% q9 K: R# c −g
    ' _/ F/ l4 p: @. x) q, [) [4 zl−1& U' ?. t% L" `3 f4 G0 D
    ​       
    ! v! E( t* G/ Z! ~  L( t6 n+ V ;分别用同样的方法求出 g r g_rg , q+ r- O" a1 p  Y- e
    r& V3 Y* C( `" T
    ​        2 E, z# I8 D' }7 a3 K
      和 g l − 1 g_{l-1}g $ t  j4 e' o1 d- d5 ?
    l−1
    ) D8 t; h: \2 ?​       
    6 Z% w& G5 ^5 `7 S) M& o3 j ,再相减即可;
    9 d5 L: d4 U- R/ P4 |4 L0 O- c; [
    . H! ]; }2 h7 r# s2 b
    7、位运算+ H4 h4 a  f+ l+ V0 Y
    位运算可以理解成对二进制数字上的每一个位进行操作的运算。4 ~8 @% k9 T! B/ A* M
    位运算分为 布尔位运算符 和 移位位运算符。
    5 x, I' [, i) Q布尔位运算符又分为 位与(&)、位或(|)、异或(^)、按位取反(~);移位位运算符分为 左移(<<) 和 右移(>>)。
    7 {# `) w/ q) ?! E如图所示:
    # X# H' m" u% A& ^+ \( l
    2 j* [4 H* s8 U0 `$ Q8 H# t
    ; |2 s( n- _) U2 N7 O4 n6 q
    位运算的特点是语句短,但是可以干大事!
    7 ^, S1 m6 D1 ?7 m4 Y比如,请用一句话来判断一个数是否是2的幂,代码如下:4 p7 _) u. u8 d, i9 i
    !(x & (x - 1))$ S* E* C- _$ F# x
    1
    % l3 e* o; j, A- d2 f: l8、贪心
    4 @7 A& g/ c) I9 K0 {贪心,一般就是按照当前最优解,去推算全局最优解。
    & ^8 d: \/ i( ], |0 q( i所以,只有当当前最优解和全局最优解一致时才能用贪心算法。贪心算法的证明是比较难的,但是一些简单的贪心问题会比较直观,很容易看出来这个能够这么贪。  N% S* ^* @3 Y/ K
    9、迭代" V( J3 f* r8 P: @& F: e, }) T, j
    每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值,周而复始,直到问题全部解决。
    * D" `( Q1 j1 s$ D10、分治+ M; k' C/ f9 t. t4 W6 N9 R) t
    分治,就是把问题分成若干子问题求解,子问题解决后,问题就解决了。一般利用递归实现。属于初学者比较头疼的内容。递归一开始学习的时候,一定要注意全局变量和局部变量的关系。5 z. k4 r7 C, o$ D# \; N
    5、算法进阶
    6 G& S0 n7 W/ X( o$ `6 r算法进阶这块是我打算规划自己未来十年去完成的一个项目,囊括了 大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法 的算法全集,也就是之前网络上比较有名的 《夜深人静写算法》 系列,这可以说是我自己对自己的一个要求和目标吧。
    " y/ A# y1 O; [+ k& N$ J如果只是想进大厂,那么 算法入门 已经足够了,不需要再来看算法进阶了,当然如果对算法有浓厚兴趣,也欢迎和我一起打卡。由于内容较难,工作也比较忙,所以学的也比较慢,一周基本也只能更新一篇。
    + T9 S7 h, z6 S+ R' K这个系列主要分为以下几个大块内容:
    ) N$ s- n( b/ G0 e/ `9 k" Q  1)图论
    1 c& O( W: p6 E. ?7 R  2)动态规划- B$ y- \0 Y4 B
      3)计算几何4 A: y. N- r0 _
      4)数论
    + ?. {; n$ ~# u1 f  5)字符串匹配: m$ n7 N+ k* r) l+ C
      6)高级数据结构(课本上学不到的)) E3 Q2 k4 O7 d0 m& J
      7)杂项算法  s0 b+ E) t' m2 M% `  g/ @, g

    & ~3 z; g3 ~, {7 p+ r

    2 |. w  D9 z" e  D; k  ~先来看下思维导图,然后我大致讲一下每一类算法各自的特点,以及学习方式:' Z) l* o& ^' k" A: {( H

    8 q* W' [2 ^' W: Y, j

    ( d6 f- s; q0 [3 K  ]7 e) u7 i; n. H7 b" B

    9 `+ c; c: Z$ u& W1)图论* g- C  C5 s% m
    1、搜索概览
    ' r$ M" N' p, q图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能,给出人类制定好的规则,枚举出所有可行的情况,找到可行解或者最优解。9 D# E& h' V; J

    * W* D- X, @" c4 V

    , }: [( W# K$ G8 n; U+ u" r  m比较常见的搜索算法是 深度优先搜索(又叫深度优先遍历) 和 广度优先搜索(又叫广度优先遍历 或者 宽度优先遍历)。各种图论的算法基本都是依靠这两者进行展开的。* U4 [0 w- d; f
    2、深度优先搜索, p7 ~; C- Z8 Y+ l5 W
    深度优先搜索一般用来求可行解,利用剪枝进行优化,在树形结构的图上用处较多;而广度优先搜索一般用来求最优解,配合哈希表进行状态空间的标记,从而避免重复状态的计算;
    $ a* C4 T# ?$ q: i% J2 y原则上,天下万物皆可搜,只是时间已惘然。搜索会有大量的重复状态出现,这里的状态和动态规划的状态是同一个概念,所以有时候很难分清到底是用搜索还是动态规划。
    & ]0 u5 u9 _* W" Z) u但是,大体上还是有迹可循的,如果这个状态不能映射到数组被缓存下来,那么大概率就是需要用搜索来求解的。/ _0 R; ?, v- n9 V& e6 P, T
    如图所示,代表的是一个深度优先搜索的例子,红色实箭头表示搜索路径,蓝色虚箭头表示回溯路径。
    6 p* \6 F% J" u+ p1 j( h$ B# c$ `2 k- K  ]% Y4 v4 A6 X  M
    - Y, i* J1 F2 ?: G
    红色块表示往下搜索,蓝色块表示往上回溯,遍历序列为:7 l& N6 h( l' r1 x, m7 s9 z
            0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 69 ~  e/ P3 N9 U9 N1 `3 f
    1
    4 g' f) Q% x: I) _1 H/ q! X同样,搜索的例子还有:
    & [) k. T$ D! f  F$ ^2 q, k5 r- w2 M

    # G' U1 m+ t4 I  f. o7 h$ K: |计算的是利用递归实现的 n nn 的阶乘。2 @* y$ K6 {$ K3 I7 {& ~
    3、记忆化搜索  _' A* t9 y' z
    对于斐波那契函数的求解,如下所示:
    3 n! C( y. i* v- v& A/ Q% f9 Uf ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n − 1 ) + f ( n − 2 ) ( n > 2 ) f(n) =0 B( W( V! F% L
    ⎧⎩⎨11f(n−1)+f(n−2)(n=0)(n=1)(n>2)# V. A: Y$ S- _' l1 J$ W
    {1(n=0)1(n=1)f(n−1)+f(n−2)(n>2)( L$ p9 O9 N. F2 _5 G7 Q
    f(n)= ) U4 ]$ W' w- J/ Z* A- n0 z
    ; v& e, O2 {; Z+ K
    / ]6 r+ w1 U$ G- {
    1 L& b/ D  S( M8 F# Z; }& ]

    " z/ O  Q' e; V! g+ O3 A
    1 q) F( k* j9 ^​        1 e% @* o1 N! [- v' [# ?& [' M1 a. ~
      0 c9 z# ~0 K+ s9 n1 b3 v
    1
    9 _1 a" F5 N# Q( E6 u' m2 n1
    , X2 m! o' m5 t( r! Pf(n−1)+f(n−2)' b1 |  t, a( R" v/ a* G; B/ W
    ​       
    # M( w1 J3 ]0 m0 f  
    % j$ L  B2 ]7 U0 `3 o& W; a3 E(n=0): q- X* V! M9 u  N
    (n=1): D  X3 G6 D9 t/ s  I- b
    (n>2)/ |) G6 h6 u1 P. ?3 _8 f4 h
    ​       
    " Q( ^" y6 c/ C4 Y! z! k# |
    5 g6 ]) }$ L; }2 u! Z7 ~4 j对于 f ( 5 ) f(5)f(5) 的求解,程序调用如下:7 K8 n) ]/ E% B3 n, i9 [

    & v, v% X6 R  X2 w& w. n& I
    ! z. l3 k5 K" f6 ]+ H7 {3 B0 U. u
    这个过程用到了很多重复状态的搜索,我们需要将它优化,一般将一些状态缓存起来。3 T& \' b) f0 i; D$ p/ R  W
    我们通过一个动图来感受一下:
    . b+ ]( I% h; z9 ~/ ]' E( I$ s
    * K& H2 N0 A: q" q1 p5 g# m; H; x

    , T! r$ d' W0 Z当第二次需要计算 f ( 2 ) f(2)f(2) 和 f ( 3 ) f(3)f(3) 时,由于结果已经计算出来并且存储在 h [ 2 ] h[2]h[2] 和 h [ 3 ] h[3]h[3] 中,所以上面这段代码的fib != inf表达式为真,直接返回,不再需要往下递归计算,这样就把原本的 “递归二叉树” 转换成了 “递归链”, 从而将原本指数级的算法变成了多项式级别。5 R4 k6 {, N3 D0 c
    这就是记忆化搜索,像这种把状态缓存起来的方法,就是动态规划的思想了。6 W# F& B" u* ]% Q; }5 h" s2 a
    4、广度优先搜索1 w9 G8 Q4 Q8 f9 U2 L6 S
    单向广搜就是最简化情况下的广度优先搜索(Breadth First Search),以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路,就是广搜的加强版。* [# c- c- g6 ]9 A
    我们通过一个动图来对广搜有一个初步的印象。$ S" d- l, M7 U9 \. e

    0 r" ]' s  R+ x" E: N# o( x7 x
    5 b1 f/ z3 t$ M- S
    6 W0 T1 z9 N" e6 z1 L8 T

    8 @! q6 K6 U6 u& Z$ _$ S/ `从图中可以看出,广搜的本质还是暴力枚举。即对于每个当前位置,枚举四个相邻可以行走的方向进行不断尝试,直到找到目的地。有点像洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水灌溉,所以我们也把这种算法称为 FloodFill。7 G2 I. N5 g; J; c2 H8 h
    那么,如何把它描述成程序的语言呢?这里需要用到一种数据结构 —— 队列。# ]( F3 n- x: O  M+ [+ s
    这时候,算法和数据结构就完美结合了。
    + w& J* T% g3 G( M2 }3 C, t& b2)动态规划
    + w4 |! T* @9 l$ x0 }. x# x动态规划算法三要素:
    * \  g7 ^  G1 _3 i  ①所有不同的子问题组成的表;# K7 b$ N  L5 e) a
      ②解决问题的依赖关系可以看成是一个图;* j" E' K# E3 B8 l' n3 V
      ③填充子问题的顺序(即对②的图进行拓扑排序,填充的过程称为状态转移);
    ! v/ N# M  ]* W0 x' [# \5 j9 B/ v# E% D5 h, f( e$ t

    9 g: |1 u5 m% @. T如果子问题的数目为 O ( n t ) O(n^t)O(n 1 z2 `7 |% z# [4 \$ w8 J
    t
    * w- o: P, e9 B8 o ),每个子问题需要用到 O ( n e ) O(n^e)O(n
    7 h) F/ B- ]/ \, X4 R/ ue% b! R3 L1 S+ [
    ) 个子问题的结果,那么我们称它为 tD/eD 的问题,于是可以总结出四类常用的动态规划方程:(下面会把opt作为取最优值的函数(一般取 m i n minmin 或 m a x maxmax ), w ( j , i ) w(j, i)w(j,i)为一个实函数,其它变量都可以在常数时间计算出来)。6 l  y" D* C% m- T
    1、1D/1D$ ^* S) i3 C9 R% @- l
    d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d = opt( d[j] + w(j, i) | 0 <= i < j )
    ' R# C9 L3 j! A2 S1 ~# `d=opt(d[j]+w(j,i)∣0<=i<j)
    " D& [1 V9 t* o' n4 m- [) j, Z状态转移如图四所示(黄色块代表d [ i ] dd,绿色块代表d [ j ] d[j]d[j]):, L& F$ L' R6 d# L

    2 l6 ?* z# Z& j1 g" ]4 q7 Y
    . G; ~* j' [4 L% W
    这类状态转移方程一般出现在线性模型中。
    7 M9 \7 \0 C6 J' m5 {: q( W  X+ i2、2D/0D" x/ V" o$ y* ?$ W! M' _5 L
    d [ i ] [ j ] = o p t ( d [ i − 1 ] [ j ] + x i , d [ i ] [ j − 1 ] + y j , d [ i − 1 ] [ j − 1 ] + z i j ) d[j] = opt( d[i-1][j] + x_i, d[j-1] + y_j, d[i-1][j-1] + z_{ij} )
    9 c. J& V' n" @d[j]=opt(d[i−1][j]+x " O2 N* ^" E& @3 d# ]3 m: S9 T
    i1 C  L- Z% I2 B" Q6 @
    ​        0 a4 x7 @2 ^( o' X& V
    ,d[j−1]+y
    . `/ R7 T! [7 j' h7 g9 Hj" q, o9 @; w$ j  j* N  s. q7 N
    ​       
    % X: U% K- o7 B ,d[i−1][j−1]+z * [  m! F6 @! @" T- `$ ?: i  l
    ij% E3 L5 @! v9 h7 d/ W' Z
    ​       
    ) }  [" |9 c& o, t ); o$ G$ Q; F+ ]# m0 l8 t  v
    状态转移如图四所示:
    # D5 F: Y( |3 u: J4 T0 X; |. o' C- r; ^7 v+ ]
    7 e! `" d; V# a( Z8 \5 y* N
    比较经典的问题是最长公共子序列、最小编辑距离。; |% J5 a. i0 @3 n% y1 I/ X
    有关最长公共子序列的问题,可以参考以下文章:夜深人静写算法(二十一)- 最长公共子序列: m8 E" }: K3 c+ e5 }+ E! b
    有关最小编辑距离的问题,可以参考以下文章:夜深人静写算法(二十二)- 最小编辑距离. g6 d) w4 G& S# r) \. D4 M
    3、2D/1D
    1 m4 |+ n! H) A& p0 Dd [ i ] [ j ] = w ( i , j ) + o p t ( d [ i ] [ k − 1 ] + d [ k ] [ j ] ) d[j] = w(i, j) + opt( d[k-1] + d[k][j] )+ a' y/ f" o& A
    d[j]=w(i,j)+opt(d[k−1]+d[k][j])9 v  d3 A; S, r5 y, }
    区间模型常用方程,如图所示:% [% W' N/ B& R/ [2 u
    $ Z! Q' y" ?) J) w: \

    5 s9 g" p' y" t: l5 Z3 F& j另外一种常用的 2D/1D 的方程为:
    ( s5 s* m7 E: w, f# ~5 k5 Ed [ i ] [ j ] = o p t ( d [ i − 1 ] [ k ] + w ( i , j , k ) ∣ k < j ) d[j] = opt( d[i-1][k] + w(i, j, k) | k < j )4 D# M8 O6 `/ h; ]
    d[j]=opt(d[i−1][k]+w(i,j,k)∣k<j)
    3 E. F% n$ ~  Y* o区间模型的详细内容可以参考以下这篇文章:夜深人静写算法(二十七)- 区间DP
    & b3 w  ]/ c  ~6 V" C6 N4、2D/2D# t$ m, e, j! s$ u7 ]# V' d, o: |
    d [ i ] [ j ] = o p t ( d [ i ′ ] [ j ′ ] + w ( i ′ , j ′ , i , j ) ∣ 0 < = i ′ < i , 0 < = j ′ < j ) d[j] = opt( d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j)
    9 u8 Q  X# i+ p& M# o$ Rd[j]=opt(d[i
      s2 X/ Y4 M/ j4 }# `) a% B/ h+ {7 E  v7 [* ]. a5 I% O; r( F* S  B
    ][j
    / f0 x. P8 E9 c7 X/ ~" X4 X( {: O6 x
    ]+w(i
    * g6 l$ J$ {" B
    % {1 Y5 M0 f( A0 K$ j6 E  m) @ ,j ) N* _. r! H/ R$ a! {" ~9 r

    : X) `" f& J- d ,i,j)∣0<=i 7 N8 F) W/ P1 Q% G. f/ y! z8 P

    ) A! T. @2 m( Y+ p <i,0<=j % G1 h$ g% ?+ y4 d. T4 B6 J
    3 ?! Q1 q* X5 Z  K0 P4 F" x5 b
    <j)
    8 v% i) b/ N- q. Z* l( f如图所示:2 k- P  w7 M1 z
    ; b/ o6 y0 B" B" d
    : k. t' R' E8 {
    常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等。1 p- j: l" P8 P) _* w, Z  y6 Q
    对于一个tD/eD 的动态规划问题,在不经过任何优化的情况下,可以粗略得到一个时间复杂度是O ( n t + e ) O(n^ {t+e})O(n
    ' r' [; }3 B( o0 x% U' x, ^t+e
    ; y4 P, L, X8 ?& q* Z3 }: { ),空间复杂度是O ( n t ) O(n^t)O(n
    ' q" I  {( p6 ?7 j3 Ft
    $ U. y7 W: i6 @) P8 N, w ) 的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度,后续章节将详细讲解各种情况下的动态规划优化算法。& o! P+ _: p( J* _9 w
    3)计算几何! y! S6 q! e; R% a& I* `2 P7 h
    计算几何的问题是代码量最大的。它是计算机科学的一个分支,以往的解析几何,是用代数的方法,建立坐标系去解决问题,但是很多时候需要付出一些代价,比如精度误差,而计算几何更多的是从几何角度,用向量的方法来尽量减少精度误差,例如:将除法转化为乘法、避免三角函数等近似运算 等等。
    ) ~$ h5 f- J3 w7 A* P如果一个比赛中,有一道计算几何的题,那么至少,它不会是一道水题。
    % n# a# f2 M6 B1 [1、double 代替 float
    : j& T( ?9 g/ }. P- g1 J! bc++ 中 double 的精度高于 float,对精度要求较高的问题,务必采用 double;
    3 n$ v; w' K8 G+ p8 P) f' N& u& t, P2、浮点数判定) y. X. N' q' R  Y2 A' B1 Z7 O
    由于浮点数(小数)中是有无理数的,即无限不循环小数,也就是小数点后的位数是无限的,在计算机存储的时候不可能全部存下来,一定是近似的存储的,所以浮点数一定是存在精度误差的(实际上,就算是有理数,也是存在误差的,这和计算机存储机制有关,这里不再展开,有兴趣可以参见我博客的文章:C++ 浮点数精度判定);
    2 e0 A0 P! q0 g/ \& K& s, Q两个浮点数是否相等,可以采用两数相减的绝对值小于某个精度来实现:
    ( t8 v0 o( z" |const double eps = 1e-8;2 G3 V& s, u4 r) \
    bool EQ(double a, double b) {1 h2 K" w) z8 B+ P$ Q  A
        return fabs(a - b) < eps;0 f& |" r. k; h. p
    }
    / h4 k* s+ }: k+ {; l1
    " F, \% f& T" e/ }2
    , w' ~5 X& U: ~/ N39 Y0 b/ q! K* B
    4
    4 K" D/ [/ }' y5 U  q并且可以用一个三值函数来确定某个数是零、大于零还是小于零:
    ( |- J5 f3 v) G$ W; pint threeValue(double d) {& O: L4 h! t2 ]- p
        if (fabs(d) < eps)# c% C8 w/ v8 H: F0 C* s! @
            return 0;7 G8 z1 @# B0 M+ G8 ^
        return d > 0 ? 1 : -1;
    6 i6 U1 w2 I% ^8 e* Y}
    , a4 \+ R; u. d# Q$ l* [6 Q, F9 r% ?1& A% L7 W' T! k) N7 ~( b( d
    2; G2 @  `# z  Y; Q1 H
    3
    ' K) s9 `: E: ?& M: W' G4$ x8 L! ~9 V+ \1 E5 R' |; T. p) Z
    5; V: Y( N9 @: }3 J  B, E7 W0 N& @2 A
    3、负零判定
    # N" h  G- S0 ]因为精度误差的存在,所以在输出的时候一定要注意,避免输出 -0.00:+ ?$ h4 I9 V* M: R+ S' m8 J# @
        double v = -0.0000000001;
      H9 G6 O/ j7 Q% S, ^) M8 g; a! h6 Y    printf("%.2lf\n", v);* p5 i, k8 w. i# W3 t
    1
    ) O  `+ D% }3 @6 w; n) |2. x4 ]5 \& p- l' A
    避免方法是先通过三值函数确定实际值是否为0,如果是0,则需要取完绝对值后再输出:
    " h* P+ S5 z) |% `    double v = -0.0000000001;; z4 T+ O# M3 B0 i
        if(threeValue(v) == 0) {' k% Y& h7 k: o7 K1 E
            v = fabs(v);: O% e6 u" l% Y/ n4 ^
        }* M' C0 @, H6 _4 T1 ~& g
        printf("%.2lf\n", v);
    2 R  ?! F7 [& ?, _4 G1/ ?2 |% b" {+ y( r* d' L! G
    2) n% f- C$ q; r0 L4 o4 e7 h) \. ^6 h
    37 S7 C+ U, @& D+ U
    40 T1 ^6 ]4 d) P8 G4 K
    5, k0 h# c7 M, Q) e' I2 ]
    4、避免三角函数、对数、开方、除法等1 a% B" ?0 E- _2 L: K) p+ {8 P
    c++ 三角函数运算方法采用的是 CORDIC算法,一种利用迭代的方式进行求解的算法,其中还用到了开方运算,所以实际的算力消耗还是很大的,在实际求解问题的过程中,能够避免不用就尽量不用。0 f$ Q3 y) Q1 e
    除法运算会带来精度误差,所以能够转换成乘法的也尽量转换为乘法运算。
    # k) u, ~/ H0 ~( n$ l% X3 h/ F5、系统性的学习3 I2 i4 r* v9 r* I7 J3 F/ @$ |
    基础知识:点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积;
    # S* ~9 `* {- t1 d8 n7 k( H0 F进阶知识:多边形面积、凸多边形判定、点在多边形内判定;
    , B& |/ Q: D' |* e! F相关算法:二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。
    7 b' Y, M' r: |- x
    8 ^6 z$ O, C. R- w

    % |0 z/ H0 E/ V& w) C( G学习计算几何,最好是系统性的,刷题的过程中不断提炼出自己的模板。: p5 B2 P) _" t& U: t: A# d" N
    4)数论
    / K# f2 z7 ^0 A# K0 y刷题的时候遇到不会的数论题,真的是很揪心,从头学起吧,内容实在是太多了,每个知识点都要证明吃透,不然下次遇到还是不会;不学吧,又不甘心,就是单纯的想把这个题过了,真是进退两难!
    : t7 X# E# r9 w) `数论对一个人的数学思维要求较高,但是一般也是一些固定的模式,所以把模板整理出来很重要。
    / i( }$ s0 N4 f- m, ~" Y当然,数论也有简单问题,一般先做一些入门题提升信心。' B1 x' z4 W9 B2 q1 p4 ]9 i  `& S
    1、数论入门0 j6 J8 J. _# U4 F$ O
    主要是一些基本概念,诸如:" ]. t$ ~" F% S& I  a
    整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和 最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节;
    # o: X' `! t5 N. \( F# H% c2、数论四大定理
    ' m9 w! n6 M4 a' c3 }8 o这四个定理学完,可以KO很多题:4 G" h# L% i/ z
    欧拉定理、中国剩余定理、费马小定理、威尔逊定理
    . o2 f: p1 O: M& G8 u; Y3、数论进阶
    ( A7 ~7 _( q% \% r; H( e8 u系统性的学习,基本也就这些内容了:2 b' D7 E  z2 A5 I
    扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。
    2 F7 j" m) i" U9 {5)字符串匹配/ k4 \, U; D$ f, {
    字符串匹配学习路线比较明确。
    ! n0 ^: C! @' ~+ m' v先学习前缀匹配:字典树。
    - a5 S: u- X! H4 Q然后可以简单看一下回文串判定算法:Manacher。4 N, U* ^: G  y: ?7 W1 @+ u6 p
    以及经典的单字符串匹配算法:KMP。
    ( }/ J% h) n9 |- l+ E实际上平时最常用的还是 BM 算法,而ACM中基本不考察。# m7 c( [' ~5 t7 D
    然后就是较为高阶的 前缀自动机、后缀数组、后缀树、后缀自动机了。% m% {& W8 }0 ~# C7 ^
    关于 算法学习路线 的内容到这里就结束了。% U. Z! J" ~+ J5 w" Z
    如果还有不懂的问题,可以 想方设法 找到作者的微信进行在线咨询。
    . d. |& I6 v0 ~参考资料& z& G& D5 f1 i. h8 A2 e1 I4 f* Z3 Z
    【阶段一】C语言学习资料:《光天化日学C语言》(日更)- {4 o" A9 v. n& j4 `( A
    【阶段二】C语言例题:《C语言入门100例》(日更)
    3 o9 t- X/ [& I  q1 S【阶段三】算法入门题集:《LeetCode算法全集》(日更); j" {: `; q$ W4 G! t* i+ Y
    【阶段四】算法进阶:《夜深人静写算法》(周更)% B! b2 C+ D" \4 a( R2 h* d
    ————————————————
    . L) p( \5 K, ]0 z( B* Q# b! K版权声明:本文为CSDN博主「英雄哪里出来」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。5 h- }4 c8 r" t" U0 q% s: V
    原文链接:https://blog.csdn.net/WhereIsHeroFrom/article/details/118382228
    0 o/ F6 y6 L7 y% O& ^1 P3 T9 R! F) ^8 B) y) ~7 N( a
    . H+ ~+ J$ d  d/ G' Z& i: ^0 a3 c0 Q
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    0

    主题

    10

    听众

    299

    积分

    升级  99.5%

  • TA的每日心情
    开心
    2023-10-14 10:28
  • 签到天数: 28 天

    [LV.4]偶尔看看III

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-15 05:04 , Processed in 0.486588 second(s), 56 queries .

    回顶部