- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 557335 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 172573
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
# x$ n* a: E0 J; P' A% X
❤️两万字《算法 + 数据结构》全套路线❤️(建议收藏)
" v2 x# V% j+ S6 I: G
c4 ?: I$ b; p+ f- ^/ F* x前言$ b8 R+ L; j a
所谓活到老,学到老,虽然我感觉自己已经学了很多算法了,但是昨天熬夜整理完以后发现,自己还是个弟弟,实在忍不住了,打算把 算法学习路线 发出来,我把整个算法学习的阶段总结成了五个步骤,分别为: 基础语法学习(重要)、语法配套练习、数据结构、算法入门、算法进阶。本文梳理了这五个大项的思维导图,在下文会有详细介绍。
4 C3 x9 O" @, Y4 |+ V) r 希望各位能够找到自己的定位,通过自己的努力在算法这条路上越走越远。/ P0 r9 s h0 t c! Q
刚开始切勿心浮气躁,千万不要给自己立 flag,说一定要把这么多东西都学会。就算你的精力旺盛,日夜操劳,时间也是有限的。所以,首先是明确我们要做什么,然后制定好一个合理的 目标 ,再一点一点将要学习的内容逐步付诸实践才是最重要的。! C( F8 J j5 D, v Z4 k
每日一篇C语言打卡,目前更新到:光天化日学C语言(20)- 赋值运算符与赋值表达式 | 让代码变得更加简介(建议收藏)。9 U) @2 }; N' w$ M% `7 r
! V5 w0 b. N/ U" m( ~) z6 X
# p' P0 ?; g+ r0 R) \
" F9 J* Q7 a0 }& g; C
! w2 S* d6 Z; ^% |
2 A; V" `, u# K% ~: }
# J P5 j1 P/ t4 j d; l/ Y
; a% Q- ~7 \: b/ c9 A" b* X
2 |& Y1 L: M% ~1 ], K图片较大,文章中有拆解,需要原图可以留言找我要哈
6 o3 V. m9 B/ c1、基础语法学习
* ^' R8 h( P. J5 z) |1 f4 |算法是以编程语言为基础的,所以选择一门编程语言来学习是必须的。
/ `* e6 k; a( g$ i; D" ^因为作者本身是C/C++技术栈的,所以就拿C语言来举例子吧。如果是 Java、Python 技术栈,可以跳过 C语言相关的内容。这一小节,先给出学习路线图,然后我再来讲,每部分应该如何去学。$ P. o, C0 O8 m! c5 C) L% C
# {- V, U2 ?/ b8 J3 c/ z8 l6 r
\: f g2 g5 C
0 {. \' \3 \# S0 D2 q5 B, q. X& d& V' h+ \. _
1)HelloWorld
' c+ D9 }* U/ R! O& @; f无论是 Java、Python、C/C++,想要上手一门语言,第一步一定是 HelloWorld,先不要急着去配环境。如果环境配了几个小时,可能一开始的雄心壮志就被配环境的过程消磨殆尽,更加不要谈日后的丰功伟业了。6 f- U2 {$ W+ C$ z( k
2)让自己产生兴趣
3 ?* F' R! p' M7 L3 w0 G% K所以,我们需要让这件事情从一开始就变得 有趣,这样才能坚持下去。比如找一个相对较为有趣的教程,这里我会推荐这个:《光天化日学C语言》。听名字就比较搞笑,可能作者本身也不是什么正经人,哈哈哈!虽然不能作为一个严谨的教程去学,起码可以对搞笑的内容先产生兴趣。从而对于语言本身有学习下去的动力。
( w) t2 R% e5 w! {- A刚才提到的这个系列,可以先收藏起来。回头再去看,它讲述的是 对白式 的 C语言教学,从最简单的输出 HelloWorld 这个字符串开始讲起,逐渐让读者产生对C语言的兴趣。这个系列的作者是前 WorldFinal 退役选手,一直致力于 将困难的问题讲明白 。我看了他的大部分教程,基本都能一遍看懂。算了,不装了,摊牌了,因为我就是这个作者。
1 L% n- G b E: a. O3)目录是精髓+ H9 y( [9 i7 F m
然后,我们大致看下你选择的教程的前几个章节,那些标题是否有你认知以外的名词出现,比如以这个思维导图为例,前几个章节为:
2 l7 p4 E& y E3 |1、第一个C语言程序
8 v3 j: L p( h2 W0 t2、搭建本地环境
) F" F8 c y+ R2 O7 }3、变量
1 f4 N6 \4 h$ `4 z5 t2 Y/ _4、标准输出
+ w: {, c$ Y8 u: J2 D5、标准输入8 C# h- f+ y0 M% v: J$ X
6、进制转换入门
# w7 f/ a5 k! _1 m% r, |8 \* @$ z8 O7、ASCII字符
4 S1 L$ h% V8 {. `2 R. f0 j8、常量' N7 b0 j% ~2 l; k! S6 A; C
' X4 l% @" u% A* }1 A( `& q# T9 q) ]8 o& O1 K
如果你觉得这些名词中有 3 / 4 以上是没有什么概念的。那么,可能需要补齐一些数学、计算机方面的基础知识。反之,我们就可以继续下一步了。
; \8 s [ T8 v. `# R! ?4)习惯思考并爱上它) N2 I; F7 I H, E
只要对一件事情养成习惯以后,你就会发现,再难的事情,都只是一点一点积累的过程。重要的是,每天学习的过程一定要吃透,养成主动思考的好习惯。因为,越到后面肯定是越难的,如果前期不养成习惯,后面很可能心有余而力不足。
8 L- [9 C: S% w就像刷题,一旦不会做就去找解题报告,最后就养成了看解题报告才会做题的习惯。当然这也是一种习惯,只不过不是一种好习惯罢了。
8 R' D+ ~2 T4 W: y5 |/ C% r6 _" m5)实践是检验真理的唯一标准
% ?2 u: Q) k4 t$ Y( J9 W" Q( C光看教程肯定是不行的,写代码肯定还是要动手的,因为有些语法你看一遍,必定忘记。但是写了几遍,永世难忘。这或许就是写代码的魅力所在吧。7 a9 b0 ?$ Q; f& {
所以,记得多写代码实践哟 (^U^)ノ~YO
) S% Q/ l3 l5 S; q' ?' H6)坚持其实并没有那么难3 z: A- Z* f; E+ l9 ?$ \
每天把教程上的内容,自己在键盘上敲一遍,坚持一天,两天,三天。你会发现,第四天就变成了习惯。所以坚持就是今天做了这件事情,明天继续做。' q& S# K) U/ w* c y' M
7)适当给予正反馈1 X# |8 r" M3 L7 g5 k! d
然而,就算再有趣的教程,看多了都会乏味,这是人性决定的,你我都逃不了。能够让你坚持下去的只有你自己,这时候,适当给予自己一些正反馈就显得尤为重要。比如,可以用一张表格将自己的学习计划记录下来,然后每天都去分析一下自己的数据。
* O8 A3 p5 ]0 A* ?! m o当然,你也可以和我一样,创建一个博客,然后每天更新博文,就算没有内容,也坚持日更,久而久之,你会发现,下笔如有神,键盘任我行!更新的内容,可以是自己的学习笔记,心路历程 等等。- q# K3 x$ C1 A4 ^% V
看着每天的粉丝量呈指数级增长,这是全网对你的认可,应该没有什么会是比这个更好的正反馈了。
' z2 c( Z3 C% S8 ?. D; |' a' H; `8)学习需要有仪式感1 ~7 X- i# J; n% Z- ]9 L
那么,至此,不知道屏幕前的你感想如何,反正正在打字的我已经激情澎湃了。已经全然忘记这一章是要讲C语言基础的了!
3 o9 h, P! R: B0 w介于篇幅,我会把C语言基础的内容,放在这个专栏 《光天化日学C语言》 里面去讲,一天更新一篇,对啊,既然说了要坚持,要养成习惯,我当然也要做到啦~如果你学到了哪一章,可以在评论区评论 “打卡” ,也算是一种全网见证嘛!* C- z* P3 Q7 i3 R* W
我也很希望大家的学习速度能够超越我的更新速度。' j e: T# v7 B! f6 b& ]- D
2、语法配套练习3 M0 q$ P2 v6 o# x
学习的过程中,做题当然也是免不了的,还是应征那句话:实践是检验真理的唯一标准。
2 n# z4 Z$ F1 E3 x而这里的题库,是我花了大量时间,搜罗了网上各大C语言教程里的例题,总结出来的思维导图,可以先大致看一眼:
% V M) J* L2 y4 \
8 P4 {$ ?1 j5 ^& J& t- a' I2 R
C- ^* P3 d( j5 V3 N% ~8 u) P% S/ n
% h' [0 Z; F" H) W" n
从数学基础、输入输出、数据类型、循环、数组、指针、函数、位运算、结构体、排序 等几个方面,总结出的具有概括性的例题 100 道 《C语言入门100例》,目前还在更新中。0 l1 a6 x1 k- U6 ]) w% N
这里可以列举几个例子:- {6 {& z E& C" u
1、例题1:交换变量的值
2 r5 P, Q1 V i. H一、题目描述9 D7 r2 x& ~! j5 w, c
循环输入,每输入两个数 a aa 和 b bb,交换两者的值后输出 a aa 和 b bb。当没有任何输入时,结束程序。: z1 r, u8 O4 Y
9 ^1 v( k# _$ t; Z4 a
6 l% r3 _: M: }: Q6 { j
& D4 F( X0 I: u' {5 B% e0 P* \& ?# A& m/ n
二、解题思路
. Z+ h$ X) y/ f9 b/ g: B难度:🔴⚪⚪⚪⚪
+ s) _: D% A9 g( s
; o) g% N( m$ w9 O6 M* {8 D% R o R9 W3 `5 |6 ~* ]
这个题的核心是考察如何交换两个变量的值,不像 python,我们可以直接写出下面这样的代码就实现了变量的交换。0 @7 L& K; @' w, g" ?
a, b = b, a
0 a8 a6 R7 D0 A3 A/ A d# Y1
8 a+ }/ I, S: r% H# Q在C语言里,这个语法是错误的。
5 u8 ~' P4 a, K5 p6 g {我们可以这么理解,你有两个杯子 a aa 和 b bb,两个杯子里都盛满了水,现在想把两个杯子里的水交换一下,那么第一个想到的方法是什么?0 m$ l: @+ L) D; H6 Y
当然是再找来一个临时杯子:
% Z k* F4 Y) K( B( M9 p6 v- ^ 1)先把 a aa 杯子的水倒进这个临时的杯子里;
: y$ c' ~% }' x: _ 2)再把 b bb 杯子的水倒进 a aa 杯子里;
' k7 X7 f+ M7 |( p' M$ w 3)最后把临时杯子里的水倒进 b bb 杯子;
2 O, b& @/ ?2 W- _1 R! H9 J
4 }- b6 A; x! @" i
* G! I. U5 \& L3 R# q0 l3 W这种就是临时变量法,那么当然,还有很多很多的方法,接下来就让我们来见识一下吧。
" O- {$ G' U8 `2 i; N) C* ?; P$ R* M% F
, n3 f2 R: B- Q6 Z1 B/ u三、代码详解& G; n/ N5 V; c: C( |' I
1、正确解法1:引入临时变量
: k: a' @2 }0 _; T+ ~#include <stdio.h>
" q- e1 q# k; \0 ~, j( T fint main() {
9 L$ H+ }0 M1 n1 w6 x5 \0 _/ b O int a, b, tmp;
r, @0 E0 U6 l8 t: A2 ~ o- S while (scanf("%d %d", &a, &b) != EOF) {7 S* g6 J* ?& I, o+ l
tmp = a; // (1)9 N/ |: ^/ N2 B s4 b
a = b; // (2)/ ?& H+ i& W3 X
b = tmp; // (3)
+ c0 o8 x. n3 F+ F& z# ` printf("%d %d\n", a, b);3 B- H) z$ p" Q* s0 d
}9 S+ Y4 q( b: c
return 0;
6 g; ]+ h6 L! n+ \6 u, D" U}
3 _- w$ q1 F/ w. T+ K# P- y1
5 F3 H( l) q* p$ z$ ]! O+ P24 P( E; [: C( x
3
( B P: f4 h! O; H! H7 Q A4
8 C4 E9 C7 ?6 \+ J1 M3 r2 v% H5
/ I7 s2 M) W& w2 J- K( n X9 w6" `$ Y2 K1 p+ v) D: z+ G o
7
+ s, u" I5 \& O: G8 M7 F# l8
3 \" [% }/ P: c2 q* v+ t4 l* S1 r9
3 l+ E+ @2 _) Y; D10: y! R+ u9 n2 b) g0 C2 B
11 u4 ^: K& p! r. q
( 1 ) (1)(1) tmp = a;表示把 a aa 杯子的水倒进这个临时的杯子里;
" w1 J6 t5 M% a7 d; v7 N) w. X( 2 ) (2)(2) a = b;表示把 b bb 杯子的水倒进 a aa 杯子里;- X1 e: L( W( _# P$ _4 a
( 3 ) (3)(3) b = tmp;表示把临时杯子里的水倒进 b bb 杯子里;
* A7 f- {3 z% q, ?这三步,就实现了变量 a aa 和 b bb 的交换。6 V* D: N8 W3 D4 s i4 y9 B$ k
2、正确解法2:引入算术运算
) Z7 d( W& ^ X7 A#include <stdio.h>+ N5 Q2 I) ^& l6 {9 p) D7 W- r* H
int main() {* c$ v9 u/ v/ `9 L3 R; V+ m2 F
int a, b;: a9 O9 z0 K& t6 D! j; S
while (scanf("%d %d", &a, &b) != EOF) {
; K0 o- i, Q/ w9 \3 z1 W a = a + b; // (1)
; d+ L4 a( r7 {- \/ o7 s9 X: N0 Y6 C b = a - b; // (2)
^$ v2 ^* T# d0 f) N, \: J a = a - b; // (3)8 x4 x# p# p5 s# i. X9 d
printf("%d %d\n", a, b);
7 b# ]! {" b7 N: w }/ c9 `$ D7 A( ^' l3 @ g
return 0;
7 ]# x1 R& V+ w! U; w, I- F}% a1 ^" ?% O7 @/ ^8 U
1
( d7 r0 b% m& M# F, ?5 C2
. d; i5 a- a& N2 c; I8 w3: M [! i- q; ?" U$ S9 l" z0 g
4
0 H4 K* S b8 s% Y% n# J7 q9 S5 a) B5/ u6 S" Q' p9 q2 \
6
$ ^% h* e. d( p9 L# V8 N7
2 \4 E' Z7 b8 n0 w& o8
- u8 l* ^! ~" y; N- g; b, C91 p2 Z4 d' j/ J; y
10
! L( I7 w. w5 M* ^" d# B: h8 k110 p2 ^6 N9 p' n5 K; H
( 1 ) (1)(1) a = a + b;执行完毕后,现在最新的a的值变成原先的a + b的值;7 l: G+ w7 A% ~
( 2 ) (2)(2) b = a - b;执行完毕后,相当于b的值变成了a + b - b,即原先a的值;
5 Q f# c, n3 F- ?( q! l( 3 ) (3)(3) a = a - b;执行完毕后,相当于a的值变成了a + b - a,即原先b的值;
|% V, t" P9 v' Y: D从而实现了变量a和b的交换。7 O4 q0 P' t+ W2 J
3、正确解法3:引入异或运算0 X3 F* j, ^0 S* Z# ~$ y
首先,介绍一下C语言中的^符号,代表的是异或。1 L4 ?% r' k! r3 n4 o
二进制的异或,就是两个数转换成二进制表示后,按照位进行以下运算:
4 T% R8 o/ w1 P( M. T左操作数 右操作数 异或结果
& _( g0 P2 B$ L6 x& n& U0 0 0
" @4 s, x1 i% s+ i. F. ^5 v& m9 s% [1 1 0. Y: R, X9 e. c2 U
0 1 1; y2 W' B7 D' ~6 N
1 0 1% p$ p+ e0 y- v: r9 P0 `
也就是对于 0 和 1,相同的数异或为 0,不同的数异或为 1。- M M: U/ P' L5 ^
这样就有了三个比较清晰的性质:
# U M4 ?- p/ ~. L1)两个相同的十进制数异或的结果一定位零。
( F% Y6 v2 E# l9 s& w1 A2)任何一个数和 0 的异或结果一定是它本身。
3 L9 _6 ?% Q J) o3)异或运算满足结合律和交换律。
0 z& x8 R# O. M) Y#include <stdio.h>
3 \" @5 q" L& a- `# |int main() {
- n# T6 W( u- A2 q8 `; C int a, b;4 ?4 x& t6 u2 b0 k2 I
while (scanf("%d %d", &a, &b) != EOF) {" w2 \9 ~% O I' S
a = a ^ b; // (1)6 Y* q: C: B! H: v
b = a ^ b; // (2)
5 \3 K- j, b6 k# d/ i1 h. j a = a ^ b; // (3)% {! g6 B; U% \! b$ K$ h( R
printf("%d %d\n", a, b);
3 A* i- X2 r' _6 Q* \! J }
5 q8 A5 W9 N4 @ return 0;
: ^' f1 a' `+ d3 E/ e: k: d}- A4 U( k, E5 {1 j3 L0 B8 E
18 D2 b% m! n8 N& x- E [: |
2( N! h1 q5 @- D2 ]% z0 y, J3 @; P
3
5 r k( e3 m! { ~4
. [ ~/ f( `4 A5% d- W0 p3 C7 j
6
v8 r( {! Q" y( d# a$ F( h& V( e7
- _: ]0 l; q3 s" X }% J8
* i% @1 \8 m, I2 ^) f9
7 r3 U& f' U ^- o/ a4 n9 }10
% {4 c" \- c1 _# m11& o6 f1 Q" b p
我们直接来看 ( 1 ) (1)(1) 和 ( 2 ) (2)(2) 这两句话,相当于b等于a ^ b ^ b,根据异或的几个性质,我们知道,这时候的b的值已经变成原先a的值了。/ f9 ^: I; T- A5 c- Z/ H/ b$ @
而再来看最后一句话,相当于a等于a ^ b ^ a,还是根据异或的几个性质,这时候,a的值已经变成了原先b的值。* ?3 j. f" j$ p1 d a
从而实现了变量a和b的交换。1 b0 n' `+ v. q5 G- Z$ _
3 I9 U8 C" x; A/ F: [. @
7 M- ~- Y3 n% j1 r/ F1 k4、正确解法4:奇淫技巧8 x2 x3 r: N3 T3 X) u: k5 R
当然,由于这个题目问的是交换变量后的输出,所以它是没办法知道我程序中是否真的进行了交换,所以可以干一些神奇的事情。比如这么写:
2 L9 j P, ~! z# b8 ?. g/ s#include <stdio.h>$ g: F5 a; i. B+ f0 r* z
int main() {
' R/ {+ n+ i( `3 o" V int a, b;* d# G3 t8 C: `3 S
while (scanf("%d %d", &a, &b) != EOF) {
; u; c; K. b* f$ w" W printf("%d %d\n", b, a);
r* l( U6 `) O/ I0 L }
7 I# P9 {! F; M# i return 0;
: @6 }8 \- _: T7 H: R* H. X}
8 a- d2 I7 e# a; i! g) m A7 k1 p7 ]1
1 d7 d8 h/ t3 S4 Y2
% u7 D! [0 _! J3 I. U: E38 L0 B4 p5 v2 E3 J
4* j8 k9 p4 {8 _2 c
5
]" v2 W, {) H! T6
0 ~& L( s7 G& G; _- `; {) R8 u) e70 Q& U3 Z! H3 \- ^0 Z2 }; F
8
: }6 `, [: W: f; i- n你学废了吗 🤣?
0 S. Z, A8 h. |# n; P2、例题2:整数溢出
E+ T: V4 N5 p) P9 o一、题目描述% y( H& w' G8 n9 i- _: r' Y
先输入一个 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
8 B3 ^: q1 n- L7 v R( q+ [62
, O3 o7 K6 J- _ d! t ),输出 a + b + c + d a+b+c+da+b+c+d 的值。
+ n5 k7 W' V% G- B/ _; U% ]
7 U! `& W r/ p3 i @$ S9 z
- `" }# D9 F) {/ n' N二、解题思路9 g4 j+ J7 ?, D# o
难度:🔴🔴⚪⚪⚪# i* O( M% O T' z2 j f
, B# ?3 x8 ~: I9 S( H0 G) Q
1 A) F% I2 E9 F3 o* K这个问题考察的是对补码的理解。' \% l+ X, @1 n0 J- ?' C$ A
仔细观察题目给出的四个数的范围:[ 0 , 2 62 ] [0, 2^{62}][0,2
% Y% T4 G7 H+ d9 u6 t! i/ c62# V: x4 f3 t" R2 o6 |' ^
],这四个数加起来的和最大值为 2 64 2^{64}2
0 Z6 Z* ?9 h. B# N' }- Q64
0 T* c. t; z2 W9 k) u- p4 v 。而C语言中,long long的最大值为:2 63 − 1 2^{63}-12
5 r; R* w3 G6 O7 Q. K635 ?7 U0 }( L/ T' `6 m! e
−1,就算是unsigned long long,最大值也只有2 64 − 1 2^{64}-12
/ n8 Z8 l$ F* V5 l) n. q641 b3 V# X6 v- ?& _* w
−1。5 j1 u# q8 T1 v3 }6 k) N5 m
但是我们发现,只有当四个数都取得最大值 2 62 2^{62}2 + w! B) t8 I. g" R% N1 ]& p( y; k& n+ S
628 w6 u3 L, `7 B, j: a1 s, |
时,结果才为 2 64 2^{64}2 ; A' }" E! V+ w5 X- w5 Q& U
64& T/ y! K2 {$ v& V2 q
,所以可以对这一种情况进行特殊判断,具体参考代码详解。" H- G/ c' L8 F
三、代码详解% V/ o: N* L& C5 ]) F
#include <stdio.h>6 E6 C1 i# f+ ]% R8 o
typedef unsigned long long ull; // (1)
0 A9 |# J* p; S: [' `( |1 Gconst ull MAX = (((ull)1)<<62); // (2) h' R& m! |( D( c0 h4 u
/ ~$ v" L# ~/ [ u+ x
. y; s. W. j3 }6 J! n# Dint main() {
$ n* Y. B {- K0 }+ ?$ L5 L9 J2 D int t;
5 N3 Y" a5 B: Z ull a, b, c, d;$ n" O5 w, Q) ]5 l5 }! G
scanf("%d", &t);' \ n3 K6 W9 \2 w- M+ z: y4 \
while (t--) {
9 K2 i7 X0 B, `" S* d9 u" S scanf("%llu %llu %llu %llu", &a, &b, &c, &d); // (3)
2 T D5 x' L. ~ if (a == MAX && b == MAX && c == MAX && d == MAX) // (4)
+ {# V7 ~' a; q% E2 _+ H% D printf("18446744073709551616\n"); // (5)
! \( n( B; I" A3 d4 L; {3 b/ v else
5 G/ [1 F, F4 E, E printf("%llu\n", a + b + c + d); // (6): f' `. H9 n4 Q
} Z! l/ l# G) r2 k5 v9 t
return 0;
3 {" b4 n0 o! \3 S/ Z- F) K5 N}
; J8 ]4 l; m4 N' j& S14 p, Y7 g9 e1 ^! |. K
2
0 i( K" L2 N' J8 C7 v) D3
/ M& R) x: B9 d7 T1 ?1 W; l& r4
8 S0 Q( v( \2 r53 p" x: l' N% o2 I: { J% `
6
6 G9 d/ Z3 x" c' |0 o6 k7
* b: C; \- @' M; E+ ~8
8 D+ R9 s( S- R. n9& b; g7 T6 [; S, j% P3 x
103 _2 u ]/ k: H% K, Y' }: D) |
11
* c! U5 q- ~ k" t, [12* Z2 q! y+ V4 ?1 i4 ^9 P1 W
13
; O9 \/ w x! L& e; l14
6 ]! c0 s4 L' X: j0 a+ B- V15; Q% R, G8 ]" d9 C
16/ F5 n6 u7 E. }1 s- A
17) T$ W# ` a/ U# R
( 1 ) (1)(1) 由于这题数据量较大,所有数据都需要用64位无符号整型。ull作为unsigned long long的别名;) H3 `( `2 r) |* P. V5 L) Q7 \: ^8 i
( 2 ) (2)(2) 用常量MAX表示 2 62 2^{62}2 , u4 _% E7 S3 x
62
# }& t# i, D8 h* F$ u) B: y& V ,这里采用左移运算符直接实现 2 22 是幂运算;
, w0 Q; D& y( @, p' W* N数学 C语言; `9 L" y0 K. a8 J* x6 U: \
2 n 2^n2 - Y7 G( `0 y; ?$ I I& g
n1 J# K4 E6 B; A
1<<n
% y7 B1 L' J3 ~- u0 j4 B0 s需要注意的是,由于 1 是int类型,所以需要对 1 进行强制转换。(ull)1等价于(unsigned long long)1;) o0 d5 w: C$ v& c: C
( 3 ) (3)(3) %llu是无符号64位整型的输入方式;1 y$ U* K9 u$ g
( 4 ) (4)(4) 这里是对所有数都等于最大值的特殊判断,&&运算符的优先级低于==,所以这里不加括号也没事;
- @$ c5 C8 c% u* Y( 5 ) (5)(5) 由于 2 64 2^{64}2
- y3 o' N+ y0 R5 d% a640 Y& q% v! C5 h
是无法用数字的形式输出的,所以我们提前计算机算好以后,用字符串的形式进行输出;2 k# |7 k. g" q* W G" b: C
( 6 ) (6)(6) 其它情况都在 [ 0 , 2 64 − 1 ] [0, 2^{64}-1][0,2 , Z! l4 T3 N. }9 u& d3 v
64
- K4 T f. D8 |/ D/ h! g −1] 范围内,直接相加输出即可。
7 c5 `+ Y( `' N' |! X由于这个专栏是付费专栏,可能对学生党不是很友好,所以作者经过再三思考,打算放出 300 张 一折优惠券, 先到先得。只要拿这个图片来找作者即可享受,仅限前 300 名。
" p) q3 r# ^7 H9 W为了适当提高一定门槛,你至少需要学会如何下载图片或者截图并且发送到微信里 🤣。
d$ W2 C9 t+ H3 M' e* a+ c2 K0 [
4 d9 W% ]" S$ q) \. g
3、数据结构. Z7 G1 P7 K, W" B7 X# f
《C语言入门100例》上的例题,如果能理解前面 25 道,那基本C语言的学习就可以告一段落了,接下来就要开始我们的数据结构的学习了。1 z" t) _( l- `% W0 C. M. r5 D2 x
1、什么是数据结构3 y' C( b" i( R" {; r
你可能听说过 数组、链表、队列、栈、堆、二叉树、图,没错,这些都是数据结构,但是你要问我什么是数据结构,我突然就一脸懵逼了。
& R3 r6 ~; z1 B) \如果一定要给出一个官方的解释,那么它就是:1 i1 B; f# B( H: P3 o4 Z0 B& p
计算机存储、组织数据的方式。相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。往往同高效的检索算法和索引技术有关。
8 G% ~* z, T6 |% z0 i* |, N' Q
8 ?! L0 g% v) q' V H
; a# E7 |5 H% u/ u是不是还不如说它是堆,是栈,是队列呢?
( e! {/ M) }7 L$ L是这样的,我们学习的过程中,跳过一些不必要的概念,能够节省我们更多的时间,从而达到更好的效果,当你还在理解数据结构是什么的时候,可能人家已经知道了栈有哪些操作了。
* Z( U+ C$ G: k% L2、数据结构和算法的关系
9 S O9 Q4 c( }- F I很多同学搞不明白,数据结构与算法有哪些千丝万缕的关系?甚至有些同学以为算法里本身就包含了数据结构。8 k; `: w* r3 k: f% T% B
数据结构主要讲解数据的组织形式,比如链表,堆,栈,队列。9 C. f% h, S( x+ e9 Q8 g
而算法,则注重的是思想,比如链表的元素怎么插入、删除、查找?堆的元素怎么弹出来的?栈为什么是先进后出?队列又为什么是先进先出?, `$ ^, g9 t: g+ E; m
讲得直白一点,数据结构是有实体的,算法是虚拟的;数据结构是物质上的,算法是精神上的。当然,物质和精神 缺一不可。
9 _+ S$ Q6 y1 N* c+ I3、数据结构概览
! i+ B6 F8 a, @3 N, z" A/ j3 {# U: D周末花了一个下午整理的思维导图,数据结构:7 d6 H, {4 v C f1 u6 \
- p# m- p; L' t/ G1 ]3 N( @. L( E' i; y! c' B. d T
常用的一些数据结构,各自有各自的优缺点,总结如下:
" o6 Z' u, k: m6 Z& Ea、数组
+ J1 ~/ x) s* J5 R内存结构:内存空间连续
. z- p8 s. E" e y) F% m. `, P' b实现难度:简单. e" G0 P* n9 N$ t2 {
下标访问:支持7 U/ Y: ?: d3 P7 C/ k7 n Y
分类:静态数组、动态数组0 X( `) k. K- n
插入时间复杂度:O ( n ) O(n)O(n)
; U; `' U, D4 S; V/ P# G查找时间复杂度:O ( n ) O(n)O(n)
" F7 a9 I8 g% \! G. g$ t! u: k2 E删除时间复杂度:O ( n ) O(n)O(n)' U8 Z" n0 D, F9 ]* e" }: ~1 z4 Q
# T% G; U9 F9 l' S) ?' {& Y
! ^( W8 G) N2 a, Gb、字符串- }% M3 {6 B) u. U3 x& I0 r7 w
内存结构:内存空间连续,类似字符数组( y" K( {" F( S* F& Y5 ]
实现难度:简单,一般系统会提供一些方便的字符串操作函数
' k* {5 c5 T" a' q. n/ }" `下标访问:支持# \5 @6 k3 P% h
插入时间复杂度:O ( n ) O(n)O(n)& f1 R$ \4 C! [
查找时间复杂度:O ( n ) O(n)O(n)
( N, m6 z! a# }. V删除时间复杂度:O ( n ) O(n)O(n)* |2 T8 e5 D" ?
& G6 f5 t ~% D
, @" N) {( J9 G" B9 X) C( } }1 h* D9 ]c、链表
& }* v/ C' H9 J. m O- i内存结构:内存空间连续不连续,看具体实现
2 i, Q& E. E' N6 Z' n5 u- l实现难度:一般) G: I9 h+ I* b2 \$ r8 c
下标访问:不支持
/ X+ N7 x# ^# Z& _分类:单向链表、双向链表、循环链表、DancingLinks2 L; Z7 V& k- A, C( e8 Z2 ^
插入时间复杂度:O ( 1 ) O(1)O(1): h, _9 a* _. X0 @
查找时间复杂度:O ( n ) O(n)O(n)0 R* \: _( ~7 Q6 ~0 i/ Q
删除时间复杂度:O ( 1 ) O(1)O(1)
" [( M1 O. k0 s5 [% Z" M
' O8 Y4 S/ L( P7 s
0 N9 M0 a6 H3 M2 h Y2 jd、哈希表
, |: N0 h8 V* M: I+ H7 j8 N内存结构:哈希表本身连续,但是衍生出来的结点逻辑上不连续9 o( b+ D& a' v3 S9 {' h
实现难度:一般- [1 F- Y9 D% q- i
下标访问:不支持) w! m! j5 C0 y6 U$ O0 ^
分类:正数哈希、字符串哈希、滚动哈希
4 d) |& R& @- q% N8 S插入时间复杂度:O ( 1 ) O(1)O(1)8 U# x+ p$ k0 B W
查找时间复杂度:O ( 1 ) O(1)O(1): y5 z c& [. A% r/ ]/ `
删除时间复杂度:O ( 1 ) O(1)O(1)9 D) V- f; c3 j
! }/ M. K2 A) ^8 A9 V% @; K. Z0 B7 y ^1 l4 |. _
e、队列( r2 ~- m& S+ k
内存结构:看用数组实现,还是链表实现
" |& {, u4 H3 r& M! ^4 L实现难度:一般 m" y, {- |, ?+ q: Y* V& W
下标访问:不支持
& [% d* S' S2 [# u分类:FIFO、单调队列、双端队列
% h) a% r5 P, U9 L L8 i. Y6 m/ b插入时间复杂度:O ( 1 ) O(1)O(1)
& y+ W( U- o Q$ w查找时间复杂度:理论上不支持
5 L+ f5 ]) A, k* ?! a删除时间复杂度:O ( 1 ) O(1)O(1)8 c+ k# N4 \4 Q1 U9 [1 V
5 K7 J9 A* T$ f1 F; ~& u! `. {; H- i) ^% s1 S% S
f、栈! B0 x+ B& _/ v
内存结构:看用数组实现,还是链表实现
1 O1 e% L0 W3 W# J1 p$ p1 {# i实现难度:一般4 `% o$ B+ f/ B7 v- _. Z
下标访问:不支持! M# G+ k ?, ?
分类:FILO、单调栈4 X1 H8 w: R" L( n
插入时间复杂度:O ( 1 ) O(1)O(1)+ V0 u m) ^, m& S6 O
查找时间复杂度:理论上不支持
u% X8 U3 h) ^/ q+ X- O" S删除时间复杂度:O ( 1 ) O(1)O(1)9 @& |9 S/ T* z W8 I2 v
+ }- m* g# @$ B; ?9 F! O. T: `
: N6 M' o3 [0 ]$ ?3 ig、树$ e& v; T+ w: R5 t
内存结构:内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续3 @- A8 d) P v* l- J
实现难度:较难9 o! Y. v, {( g4 B5 i& K
下标访问:不支持3 h# q$ Z0 \1 L) h
分类:二叉树 和 多叉树$ n6 ~# ^2 D! Y9 \+ u$ n
插入时间复杂度:看情况而定' I6 X6 w& k0 ?9 y
查找时间复杂度:理论上 O ( l o g 2 n ) O(log_2n)O(log 2 H5 d0 T9 P2 l/ s" n
2" F- A2 k9 U. t3 T
% u8 i# Q! Y" d& Q n)% X, j$ ~4 b$ Y) [
删除时间复杂度:看情况而定% e. F8 h0 P9 s( F* i3 V
& ?( e; r% O2 G# q
# J$ j6 Y% E t$ M5 R' T1、二叉树
- B1 u( {7 Y* y) v# m. Q二叉树的种类较多,比如:二叉搜索树、平衡树。平衡树又可以分为 AVL 树、红黑树、线段树、堆。最平衡的树莫过于满二叉树了。
3 F% {% ^8 p0 D% I9 k8 n6 |5 z其中,堆也是一种二叉树,也就是我们常说的优先队列。* l+ O& Y/ N+ }; O! y
2、多叉树
" P2 N) K( N* K. X/ `6 \3 VB树和B+树是多叉树,当然我们平时学到的并查集其实也是个多叉树,更加严谨一点,应该称之为森林。
$ o0 [) I% S6 j9 Fh、图& |0 Y: g* k0 x. _
内存结构:不一定
! x& h" w9 l& W) O+ f5 q实现难度:难+ k8 J: F( x7 {2 S* o+ ^
下标访问:不支持
( i1 A |5 M# [5 \! B, m5 ~2 W5 }分类:有向图、无向图
6 d6 i: z' C, }, d, u插入时间复杂度:根据算法而定* c h, P- B7 i0 ~
查找时间复杂度:根据算法而定
7 r' H5 }) u% a8 p( Q0 y; E删除时间复杂度:根据算法而定- r4 E. H3 M( o, S' a
# ]' ?+ e# m) B" k1 c" D/ M# U6 x: a* a
1、图的概念0 @# T8 b( ?: n7 \
在讲解最短路问题之前,首先需要介绍一下计算机中图(图论)的概念,如下:
5 I8 `; Y/ |0 M7 [图 G GG 是一个有序二元组 ( V , E ) (V,E)(V,E),其中 V VV 称为顶点集合,E EE 称为边集合,E EE 与 V VV 不相交。顶点集合的元素被称为顶点,边集合的元素被称为边。9 _% [, T& n+ D; g( w
对于无权图,边由二元组 ( 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 为权值,可以是任意类型。% w( e+ ], w, |7 S$ H
图分为有向图和无向图,对于有向图, ( 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;7 y! O/ V2 a4 B. @) r
2、图的存储
4 z- ]4 `- p" a) ?, M+ }5 f对于图的存储,程序实现上也有多种方案,根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例,讲解四种存储图的方案。
/ {% ?1 [& {- c0 F) _$ g% f/ `! S: }& l. S' V3 a/ w
2 l& P" o6 g9 F7 g
1)邻接矩阵
7 ~& @9 W8 R/ z5 S- [4 Z' n邻接矩阵是直接利用一个二维数组对边的关系进行存储,矩阵的第 i ii 行第 j jj 列的值 表示 i → j i \to ji→j 这条边的权值;特殊的,如果不存在这条边,用一个特殊标记 ∞ \infty∞ 来表示;如果 i = j i = ji=j,则权值为 0 00。
# F. s7 u) [1 T1 \1 A0 d3 N7 P它的优点是:实现非常简单,而且很容易理解;缺点也很明显,如果这个图是一个非常稀疏的图,图中边很少,但是点很多,就会造成非常大的内存浪费,点数过大的时候根本就无法存储。
% t5 o( l9 m- K) B/ e[ 0 ∞ 3 ∞ 1 0 2 ∞ ∞ ∞ 0 3 9 8 ∞ 0 ] \left[
2 I. g/ e: l) @& \1 C01∞9∞0∞8320∞∞∞30
2 ~$ s5 U! v* ~: h! n0∞3∞102∞∞∞0398∞0. @6 k4 ]& b8 I
\right]
) h6 p# h8 ?( R: {⎣
, D) C6 l) @, g) ~' S⎢
9 f f0 p- `( {; y. o. D0 J⎢( r: g E$ x) W# ^( C( ~1 }) [8 t5 N
⎡
4 W- v5 r2 n# Y3 o2 X3 \( k ( w: y+ h' ~3 r) b: e; n" C
! {! T1 [ D0 [" ?; v: a0 J# V2 w+ _; q2 Y3 \' m$ f$ k
1
2 [7 H0 C. I: E∞
9 Q* `% A6 E! U95 r" J: Z+ h8 U$ w. a, l9 n7 L
3 ~" M. d( V* u) |2 I2 u/ d
5 r& z* h; @, |, Q
∞! o% u% f3 L* |
0
. ^* s% v, d. e5 {( L# B, S. J" W9 ~∞( e& ~- q# [+ o9 y/ {* p
8$ _2 y3 l. S5 ~. S, E. B: X
4 S) C6 h, R7 X( t0 L 1 k2 ]8 n( w5 o9 m
3! b5 T* u. {$ C9 j4 b V/ L: m
2. F* e" y: ?3 }( n( B2 s5 ]2 D
0
- \; L4 I5 h1 k0 v: o∞
6 j% i$ V% ]: V& V" z 5 @2 s4 S, D5 e7 L; }5 Z. T
1 B6 }1 Z2 f1 ]( |; r∞
3 _6 `4 p, K5 Z5 K∞
?4 ^7 k* w4 W3 f0 K8 {2 H3( ^) G8 w# f" o* R$ Y" M/ q
0" z0 {* G1 A: @4 o4 ]" s2 U/ b
' V' K, R: h [* t, f, A+ H
5 p! g$ x3 {$ [, h _⎦. x5 ]9 n, U8 O4 Y; r) D1 _
⎥
( t7 S( }& d6 `+ _0 \⎥
?) f' @9 L6 Z* c. s⎤1 W( P" k4 S5 e z2 G1 r
3 m7 b- s, x8 E6 `1 J* S% R
% L/ H; G8 w" m4 i! F) n- e1 j2)邻接表
! f( b/ I( `1 F) A: w邻接表是图中常用的存储结构之一,采用链表来存储,每个顶点都有一个链表,链表的数据表示和当前顶点直接相邻的顶点的数据( v , w ) (v, w)(v,w),即 顶点 和 边权。
. U, H) g+ L1 I+ l# G它的优点是:对于稀疏图不会有数据浪费;缺点就是实现相对邻接矩阵来说较麻烦,需要自己实现链表,动态分配内存。
" f* F" C5 `6 O6 H6 i如图所示,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) 二元组。
1 a( j; |/ u! y8 K. }( @; n, k4 _5 R( I( M% i4 o$ C. t( {
; b. l# J+ V }
在 C++ 中,还可以使用 vector 这个容器来代替链表的功能;/ j9 W- l) Y8 i1 ]7 ?5 l' m: i
vector<Edge> edges[maxn];
) w* I. s2 i4 S1
0 d) @1 @0 O" i* ~& ?3 r O3)前向星
; y. I' y7 g) ^9 d4 c1 ^前向星是以存储边的方式来存储图,先将边读入并存储在连续的数组中,然后按照边的起点进行排序,这样数组中起点相等的边就能够在数组中进行连续访问了。" v( Z. [* [1 A7 g1 ^' M7 C
它的优点是实现简单,容易理解;缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序,带来了时间开销,实用性也较差,只适合离线算法。% o9 F; H7 A- `! F" \# B9 ]! y h' O R" ^
如图所示,表示的是三元组 ( u , v , w ) (u, v, w)(u,v,w) 的数组,i d x idxidx 代表数组下标。
' K0 R) \" Q, Q8 k- B) t: D; C9 I- e4 }% |1 y4 @2 R
$ f9 W7 X% M' i那么用哪种数据结构才能满足所有图的需求呢?
: Y3 m1 A8 v7 H- k) x% S接下来介绍一种新的数据结构 —— 链式前向星。; P4 P% W, R. F+ d" g/ n
4)链式前向星" K, |: E6 w5 D, ~# @
链式前向星和邻接表类似,也是链式结构和数组结构的结合,每个结点 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 指向下一条边。
( _' |4 l$ d0 P7 h, w- z具体的,我们需要一个边的结构体数组 edge[maxm],maxm表示边的总数,所有边都存储在这个结构体数组中,并且用head来指向 i ii 结点的第一条边。 E3 ]6 U/ L* ]' Y5 m2 O6 h
边的结构体声明如下:
8 Z+ {9 w, [8 F) pstruct Edge {
: _0 l2 r; ^/ u4 p% B int u, v, w, next;& m- W1 V; @) P7 r1 U
Edge() {}1 ]- P: v" n, q) R' ]5 S
Edge(int _u, int _v, int _w, int _next) :
# K Y" [1 N# n8 i1 _ u(_u), v(_v), w(_w), next(_next) , ?; n% s4 l. ]. n S2 e
{
# i1 H: X5 i: M) R, R" h. ^! } }# K& H# }5 u) X/ z0 C8 L+ g* `5 k
}edge[maxm];; R7 o) T, h/ g: @- i s( f. P
1
# x9 _" \- o# Q0 @* e2
% j# z8 q" N$ R9 j3
' i, z) f0 y2 a/ o9 Z, u! s4
# e: G8 o% D- K6 Z) X( r/ D55 l" W( l9 n) A% r( I
63 d2 L( K' l p
7
: u+ F- p! Q$ A& `. j8 M8
$ @3 t- B9 H2 O1 b% m: e; \/ t) R初始化所有的head = -1,当前边总数 edgeCount = 0;
8 Y D. D' `0 B8 g5 Y每读入一条 u → v u \to vu→v 的边,调用 addEdge(u, v, w),具体函数的实现如下:
, Q S }' [4 E! rvoid addEdge(int u, int v, int w) {
* X) P8 [* W4 u edge[edgeCount] = Edge(u, v, w, head);
* K) Q, x2 |0 S) x2 i3 P) ^ head = edgeCount++;
! K/ q; D" t$ _9 @+ o9 i}
3 m/ N% X+ Q7 Y( R1% h% P/ g! B1 P* a0 _5 x& S
2
9 g9 n; {$ W: n5 W, }# C- x L30 j: }& ~; t4 o) `0 J5 j
4
7 j5 J0 P' v5 C+ Y6 F& M+ \6 C这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w)(u,v,w),就在原有的链表结构的首部插入这条边,使得每次插入的时间复杂度为 O ( 1 ) O(1)O(1),所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现,空间上没有浪费,时间上也是最小开销。
# e0 {& [: X7 q: _- T2 c$ C调用的时候只要通过head就能访问到由 i ii 出发的第一条边的编号,通过编号到edge数组进行索引可以得到边的具体信息,然后根据这条边的next域可以得到第二条边的编号,以此类推,直到 next域为 -1 为止。
9 \% q4 P) f0 V& s; ifor (int e = head; ~e; e = edges[e].next) {! w% A& r p1 M
int v = edges[e].v;
; `( l3 u3 J$ W \/ x- O, O" O' R ValueType w = edges[e].w;
7 x- B. @3 M+ d3 x ...
3 V/ z3 l( a. Q}
" E, K! v: t; G1
& \5 T8 T8 u! d* a( M! M27 i( G8 u1 ~: ]: h9 I5 q) y4 D
3
" M: k( u0 b. P4 m$ V. {4 c, q4( b# j2 V( P3 o7 l
5/ K! I! L: J# w
文中的 ~e等价于 e != -1,是对e进行二进制取反的操作(-1 的的补码二进制全是 1,取反后变成全 0,这样就使得条件不满足跳出循环)。" ^7 r: o/ @4 r( T3 c# V
4、算法入门' E% G# s0 {8 j& W' K6 t! y# L
算法入门,其实就是要开始我们的刷题之旅了。先给出思维导图,然后一一介绍入门十大算法。! z8 o& O" M2 _* S. l) y
2 K& | K1 o& N4 t# M9 @0 @
9 ~( d7 {( i& y* \$ W入门十大算法是 枚举、排序、模拟、二分、双指针、差分法、位运算、贪心、迭代、分治。$ {( a- { `, @ C" y6 r
对于这十大算法,我会逐步更新道这个专栏里面:《LeetCode算法全集》。
' F5 J# u, p; O. k/ x1、枚举
$ x2 {7 D* y q9 i W4 _$ B5 a枚举可以简单理解成for循环,从一个数组中遍历查找一个值,就是枚举;从一个数组中找到一个最大值,就是枚举;求数组所有数的和,也是枚举。
7 l& i& j" A8 o. V# A: ~6 h' D对于枚举而言,基本就是循环语句的语法学会,这个算法就算学会了。
# [$ N( g0 _( [5 @& P9 C- p2、排序5 O% O1 a, ]# ^" r
既然是入门,千万不要去看快排、希尔排序这种冷门排序。$ ?' k" P4 a: ]3 N6 c1 M0 v( u
冒泡排序、选择排序、简单插入排序 原理好懂,先看懂再说,其他不管。因为这三者都是基于枚举的。
2 Z9 F4 [& l' f, `, NC中有现成qsort排序函数,C++中有现成 sort排序函数,直接拿来用,等算法进阶时再回头来看快速排序的算法实现。
7 B' u& R- w% g4 L ~- P3、模拟% Q8 l- Z2 d0 {- }
模拟就是要求做什么,你就做什么,完全不要去考虑效率问题。
- Q( T! F& f: k' F, Q4 o不管时间复杂度 和 空间复杂度,放手去做!! p C, Y8 Y2 s
但是,有时候模拟题需要一些复杂的数据结构,所以模拟题难起来也可以很男,难上加难。9 B, ^) m; Z8 N4 }
4、二分3 N; D* A: t6 |8 G, U9 x
二分一般指二分查找,当然有时候也指代二分枚举。
% }' l* L; L. u& y' Y7 P例如,在一个有序数组中查找值,我们一般这个干:- X2 t0 W- @- B$ \+ l
1)令初始情况下,数组下标从 0 开始,且数组长度为 n nn,则定义一个区间,它的左端点是 l = 0 l=0l=0,右端点是 r = n − 1 r = n-1r=n−1;
$ A2 `" a" U6 h, d/ Q# T! u" q2)生成一个区间中点 m i d = ( l + r ) / 2 mid = (l + r) / 2mid=(l+r)/2,并且判断 m i d midmid 对应的数组元素和给定的目标值的大小关系,主要有三种:. l0 s4 e& s H9 d4 n
2.a)目标值 等于 数组元素,直接返回 m i d midmid;! T9 t% h* @, O# F# c
2.b)目标值 大于 数组元素,则代表目标值应该出现在区间 [ m i d + 1 , r ] [mid+1, r][mid+1,r],迭代左区间端点:l = m i d + 1 l = mid + 1l=mid+1;. T3 P$ F! p& S ]" S
2.c)目标值 小于 数组元素,则代表目标值应该出现在区间 [ l , m i d − 1 ] [l, mid-1][l,mid−1],迭代右区间端点:r = m i d − 1 r = mid - 1r=mid−1;
. n# a5 p* e4 h9 G: I9 Y; _/ k3)如果这时候 l > r l > rl>r,则说明没有找到目标值,返回 − 1 -1−1;否则,回到 2)继续迭代。
+ ]- S: ], g. T& Q2 y4 W5、双指针/ n4 ~3 r2 k# q" p+ O4 a
双指针,主要是利用两个下标在一个数组上,根据问题的单调性,进行指针偏移,由于每个指针只往后偏移,所以时间复杂度可以达到 O ( n ) O(n)O(n),由于思想非常简单,所以出题时,热度不低。
9 y- W8 O* ?7 N8 G! Q& [
: J. H; j; E4 j/ e
% s' V A1 B* C% O1 x6、差分法
* t% q7 q4 a: D" V+ g差分法一般配合前缀和。/ d2 ^: D' X% p! P5 z! B+ I
对于区间 [ l , r ] [l, r][l,r] 内求满足数量的数,可以利用差分法分解问题;
' h! ~% C% z8 V6 x9 T/ d$ [4 I; S假设 [ 0 , x ] [0, x][0,x] 内的 g o o d n u m b e r good \ numbergood number 数量为 g x g_xg " l- n' G) {/ H6 l. ]7 V& G
x) V( n: S( t3 B$ [# t/ @& ]
6 p: z/ ^" e7 ^; a ,那么区间 [ l , r ] [l, r][l,r] 内的数量就是 g r − g l − 1 g_r - g_{l-1}g
$ ` c* W3 T% l9 cr( o8 O( w" G* n( ]
. O. P$ X7 [5 s −g 0 j7 v0 k! G% G+ A0 P
l−1
3 A4 e! f# U9 M, z
+ Y7 Y0 j, E: ~2 m0 n, L ;分别用同样的方法求出 g r g_rg 5 ^, i$ o$ j9 S9 i: A4 P- U1 i
r$ f/ V) \' S" j6 I; E
3 P V0 u' L0 v9 Z0 z* R
和 g l − 1 g_{l-1}g
( Z4 [" ?9 U; g/ j+ |9 Ol−1
4 a7 h4 m: M* S, R ! t Q. K/ ?5 U0 D$ P! }! B; t( m
,再相减即可;) V4 s( x1 h1 _4 V% X8 F0 ~
Z" M$ C( Z1 T; Z7 K/ @* w
' x& F0 {4 c- m9 ^; ~! O7、位运算, L$ D1 c1 G6 B A$ m! F7 C* n) ?2 }- z
位运算可以理解成对二进制数字上的每一个位进行操作的运算。
1 {9 ~; N, p3 p! r, J! E位运算分为 布尔位运算符 和 移位位运算符。
( z* \8 p/ C5 F3 X布尔位运算符又分为 位与(&)、位或(|)、异或(^)、按位取反(~);移位位运算符分为 左移(<<) 和 右移(>>)。 \ e2 B* `9 l( g( I& M: J+ m9 }
如图所示:" q$ M3 _- Y' U3 w/ n
4 p8 p+ R4 ~$ @5 U2 Y: | D. f1 K u/ i2 w
位运算的特点是语句短,但是可以干大事!/ b" a+ P9 Z: j5 l; u! r
比如,请用一句话来判断一个数是否是2的幂,代码如下:
3 q& S$ S6 I8 @0 f!(x & (x - 1)), e: ^0 g2 ^/ n, {0 x
1
, L- k2 H. L$ |/ T- _8、贪心
" a2 C% [4 R5 Y6 B. d* G! Z, M贪心,一般就是按照当前最优解,去推算全局最优解。2 j& h' v# X) l/ \, ]5 W A( u$ Y
所以,只有当当前最优解和全局最优解一致时才能用贪心算法。贪心算法的证明是比较难的,但是一些简单的贪心问题会比较直观,很容易看出来这个能够这么贪。
6 B0 d3 G& c/ v% K2 ], }9、迭代
+ g* ]3 l: o2 G$ E! J! {每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值,周而复始,直到问题全部解决。" m4 {, E; ?8 `0 ? T* \2 ]: U
10、分治
2 S& b: j% K$ c* _# l6 h分治,就是把问题分成若干子问题求解,子问题解决后,问题就解决了。一般利用递归实现。属于初学者比较头疼的内容。递归一开始学习的时候,一定要注意全局变量和局部变量的关系。 M, w/ s6 V. e. s7 J) H0 S
5、算法进阶
! k( l: ~) _& X4 K算法进阶这块是我打算规划自己未来十年去完成的一个项目,囊括了 大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法 的算法全集,也就是之前网络上比较有名的 《夜深人静写算法》 系列,这可以说是我自己对自己的一个要求和目标吧。 n1 Y8 X7 [3 _) I. }0 M
如果只是想进大厂,那么 算法入门 已经足够了,不需要再来看算法进阶了,当然如果对算法有浓厚兴趣,也欢迎和我一起打卡。由于内容较难,工作也比较忙,所以学的也比较慢,一周基本也只能更新一篇。6 Z6 }0 i1 _1 @1 {% b! k
这个系列主要分为以下几个大块内容:! F _- }( E: I% T8 z- S+ ?
1)图论
- J1 p: N; h, n! _ 2)动态规划
! L" t8 B! L/ l5 }% j 3)计算几何1 V' P# p0 \2 N
4)数论& w9 `: [7 F- J( l
5)字符串匹配" z' ^# y" V: W$ E6 H% H
6)高级数据结构(课本上学不到的)! [5 C; j" ^: _ |+ w1 L% M \2 X C! L
7)杂项算法8 @5 P& T' ^' }- a, Y8 _/ o) y
_* n& e0 p8 p& a
; {! v1 j% q. w# p' J先来看下思维导图,然后我大致讲一下每一类算法各自的特点,以及学习方式:
& i8 j3 ]- k) p$ W+ g/ I
7 A' G2 G) V1 K0 J
) x1 U' _* ?: p" K {: B
+ J& G" {, B/ N) n
: G/ \/ y; a ]5 O1)图论
; i4 M, S3 e3 z" B1、搜索概览
& Y- o: z& ]) E/ s, X图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能,给出人类制定好的规则,枚举出所有可行的情况,找到可行解或者最优解。
8 O" w* m9 W* A8 q
8 U% Y* O5 k1 A# t
5 W4 B4 P# e6 p+ K比较常见的搜索算法是 深度优先搜索(又叫深度优先遍历) 和 广度优先搜索(又叫广度优先遍历 或者 宽度优先遍历)。各种图论的算法基本都是依靠这两者进行展开的。
9 v0 M" H4 J0 O7 w1 _0 e2、深度优先搜索
' d( F4 S8 Z' D( }- L: |深度优先搜索一般用来求可行解,利用剪枝进行优化,在树形结构的图上用处较多;而广度优先搜索一般用来求最优解,配合哈希表进行状态空间的标记,从而避免重复状态的计算;) @4 j3 x0 m; L+ \+ ~% f
原则上,天下万物皆可搜,只是时间已惘然。搜索会有大量的重复状态出现,这里的状态和动态规划的状态是同一个概念,所以有时候很难分清到底是用搜索还是动态规划。
5 g$ a% K+ j% B( [+ i1 p但是,大体上还是有迹可循的,如果这个状态不能映射到数组被缓存下来,那么大概率就是需要用搜索来求解的。6 j3 P# r' V* w% ]% D/ B: f
如图所示,代表的是一个深度优先搜索的例子,红色实箭头表示搜索路径,蓝色虚箭头表示回溯路径。
1 {( l5 ~* f3 {$ w$ b' a7 @' [- n4 H
+ k% A6 U4 x4 i
红色块表示往下搜索,蓝色块表示往上回溯,遍历序列为:
0 c3 b0 S& ~* g7 z4 z/ l- F" O+ k) d 0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6
+ A: \* ]) M @1
7 Y: u4 L) e0 q4 i$ g, [& j) b同样,搜索的例子还有:
' F5 N! w! m- c- _' L) j* Q9 X/ r% d) k
2 r5 h. ]- { c* `' Z+ g计算的是利用递归实现的 n nn 的阶乘。
/ t0 A+ a9 d: E3、记忆化搜索- O9 y/ H$ z* U7 o( \3 i3 F
对于斐波那契函数的求解,如下所示:
# v3 t3 Q! W3 e2 Of ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n − 1 ) + f ( n − 2 ) ( n > 2 ) f(n) =! E1 U) l' E/ E1 a; {9 A b) i
⎧⎩⎨11f(n−1)+f(n−2)(n=0)(n=1)(n>2)2 \# w* \8 O2 Q6 b& E* X6 w/ ^
{1(n=0)1(n=1)f(n−1)+f(n−2)(n>2)5 G# C; R+ l) y. S* [ S3 C j
f(n)=
( {* k! O/ t4 R4 `5 M⎩9 \/ R# O5 e& t0 T9 P
⎪
4 f( ? o5 D( T- [⎨
( A# d% ^: u# D3 H( v. Q⎪, S5 f+ K: e3 l0 Q* G& ]: E' |
⎧
+ V9 Q3 G. b* }4 j) @ / m( y: z! p- C" f/ E
: A2 {) Q s s9 A9 e; G/ U% r1
8 @; `1 b. @$ k# S' X* E% B1- Q8 X1 u9 B- ^: M! ?) ?" ?
f(n−1)+f(n−2)
: W6 s- F7 s: {3 V
) u* X3 y; ?6 r9 H) j4 a" S5 z- Z$ v, R
$ M, b+ `. ?5 c+ C- d) r9 v3 a(n=0)
- Q& a1 P: c' f: P M(n=1)6 _5 [2 V# l9 u5 p, @ T. f
(n>2)3 Z1 U. `2 e9 j
+ k3 y* h4 O0 h( n( c& C) Z$ B
+ ^- J. Z: H# ^对于 f ( 5 ) f(5)f(5) 的求解,程序调用如下:. k; C2 v0 b s1 T, U" t/ }" R7 O
3 q* z6 q: z' |4 }! g; {9 \# a
y8 ~$ Q9 Z; o* [& a! ~
这个过程用到了很多重复状态的搜索,我们需要将它优化,一般将一些状态缓存起来。
3 U1 R' {' q- c' z' h0 \我们通过一个动图来感受一下:
& }! H, _7 e+ N1 }5 o! J* t4 m- ^' Y) @7 f" i4 D0 ?
5 H8 A; q" `- {) _8 X' c; X& N
当第二次需要计算 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表达式为真,直接返回,不再需要往下递归计算,这样就把原本的 “递归二叉树” 转换成了 “递归链”, 从而将原本指数级的算法变成了多项式级别。
4 V- m" v: U2 x4 P% S2 c1 N% c% L这就是记忆化搜索,像这种把状态缓存起来的方法,就是动态规划的思想了。
) U# E9 p- W" U4、广度优先搜索3 \. u9 G, z1 p* h0 N
单向广搜就是最简化情况下的广度优先搜索(Breadth First Search),以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路,就是广搜的加强版。
8 `1 ?" V1 C% \) ~8 Z我们通过一个动图来对广搜有一个初步的印象。" `, h! _. ]& g T. w- R( v9 Q
4 O5 r M7 \( [! \8 k7 k: p) x- B3 f
; V/ o" x" i6 ^1 i( o
8 F# B. [# b S1 k* [3 ]( s
从图中可以看出,广搜的本质还是暴力枚举。即对于每个当前位置,枚举四个相邻可以行走的方向进行不断尝试,直到找到目的地。有点像洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水灌溉,所以我们也把这种算法称为 FloodFill。
6 _# B; d7 o$ P, X' n3 l那么,如何把它描述成程序的语言呢?这里需要用到一种数据结构 —— 队列。5 t6 n+ U, E' d! ?9 X# { y! i* a
这时候,算法和数据结构就完美结合了。' e: N0 X/ P. X( M3 y. E
2)动态规划
; |3 E, X+ Z& I" ]( h( ^& a7 [动态规划算法三要素:
2 I d! M- P' V, g% S ①所有不同的子问题组成的表;
0 s! S8 P2 z$ W ?! r ②解决问题的依赖关系可以看成是一个图;2 k( R' d8 \, P6 J! f
③填充子问题的顺序(即对②的图进行拓扑排序,填充的过程称为状态转移);
2 [) A Q: m( H! | z# o- a1 K3 Z: n. d( \0 g( A
, B0 k; |8 C1 z0 p/ G如果子问题的数目为 O ( n t ) O(n^t)O(n ) q0 ^* t3 @; w9 w! @" H
t
8 Z8 _' J* d' n5 Q1 A$ u ),每个子问题需要用到 O ( n e ) O(n^e)O(n
3 e9 g' n4 o! u0 q+ ~& Pe
a- X: |( I$ K/ g) g' e ) 个子问题的结果,那么我们称它为 tD/eD 的问题,于是可以总结出四类常用的动态规划方程:(下面会把opt作为取最优值的函数(一般取 m i n minmin 或 m a x maxmax ), w ( j , i ) w(j, i)w(j,i)为一个实函数,其它变量都可以在常数时间计算出来)。( P' w: `/ E& A0 B, D
1、1D/1D
9 T# j# L$ i" C- Fd [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d = opt( d[j] + w(j, i) | 0 <= i < j )
( `" v0 y+ A" fd=opt(d[j]+w(j,i)∣0<=i<j)2 b$ q5 }/ n+ D6 N J/ @: ^8 d
状态转移如图四所示(黄色块代表d [ i ] dd,绿色块代表d [ j ] d[j]d[j]):
! ^0 N2 F* X# ?. o
' y4 T7 r9 G8 p
. a: u3 V) N# J @这类状态转移方程一般出现在线性模型中。& H0 }" m0 x! y+ [$ ?$ m! [4 u
2、2D/0D' I" k& I" i& L2 r9 T: y7 Z
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} )
$ g" r" J8 a9 _/ _$ X" ld[j]=opt(d[i−1][j]+x
1 l: ?& Z% }9 y4 a9 Vi; X# g, K) {$ z6 V0 e3 |& Q
4 g2 R/ R# p# N$ K. @
,d[j−1]+y
" [( @! W7 O' b8 ~j
# D7 c* o4 ?! e6 t1 U8 a r! z % H# a% T; V7 s# t& @% e
,d[i−1][j−1]+z
3 r( C3 H; ]; ]! w3 g& |ij
) u8 G1 `2 @5 _9 E1 Z0 d- O' G b . o' D. f/ C" r( r4 ^* S& ~
)7 Y' l5 q1 ?7 A2 p2 m/ W
状态转移如图四所示:
' x4 I8 K6 L. e; l b' g* U; j0 z( S% ?7 Q
& U8 j1 B+ t# @3 N9 w v- C比较经典的问题是最长公共子序列、最小编辑距离。% f& d; f1 y$ O2 q( B
有关最长公共子序列的问题,可以参考以下文章:夜深人静写算法(二十一)- 最长公共子序列
& ~5 K. i6 T' b; j/ |$ v; ?: `3 p有关最小编辑距离的问题,可以参考以下文章:夜深人静写算法(二十二)- 最小编辑距离
. O# r" [% i6 t( e# l8 I4 Q) s+ N3、2D/1D
) q; F% g9 n8 \8 Cd [ 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] )
" ~+ S& G& v9 k; \d[j]=w(i,j)+opt(d[k−1]+d[k][j])
# l$ c e& g! v区间模型常用方程,如图所示:
" E Q& m% t! i- B6 E# @# U% P0 c" \, o, k) i' |$ S
6 U9 x. \! B) _另外一种常用的 2D/1D 的方程为:1 } i- t/ v" c7 Z
d [ 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 )
* G; d: S7 J a# Y. n- ~9 Ud[j]=opt(d[i−1][k]+w(i,j,k)∣k<j) y6 J6 c9 W, j Z- J
区间模型的详细内容可以参考以下这篇文章:夜深人静写算法(二十七)- 区间DP, l% c6 H! W: U/ k- [- d, K' Q2 l
4、2D/2D1 ^6 m! C* `5 `
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)
! T" s1 Y) H% W0 q( g( z" u6 Kd[j]=opt(d[i % r' R7 C; Q2 s: b
′2 y4 `3 [. ^1 W' ^& L
][j
" z: \" [( |0 b0 i a/ N′7 w) u! q( H: s( L% y
]+w(i + x' T& k2 n1 z# d4 b; A+ m
′ D/ k. A z$ E( V
,j ( N: L( {8 z+ }9 |6 U
′
: o8 j% Q3 x0 }5 I5 ]. i# Z/ ^ ,i,j)∣0<=i ; p8 H$ J# H7 x7 j$ Z$ e4 P
′& \. B! c. x7 W9 ^/ G, K
<i,0<=j
9 u( G# I2 |% M. ~* I0 e4 J′2 t8 y6 c4 p N+ r5 U R
<j)
( s* F; n% g1 k5 d" E7 q如图所示:
4 d0 o8 f; N) M
1 F& ^9 y! `9 J# \3 h, T( w
; H+ Z. X% N8 K( C常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等。" k# l/ ?6 Q6 w2 i/ f# C! L7 c
对于一个tD/eD 的动态规划问题,在不经过任何优化的情况下,可以粗略得到一个时间复杂度是O ( n t + e ) O(n^ {t+e})O(n
; g) c) b1 }! T! N" rt+e
& f; l4 C" I1 u9 J ),空间复杂度是O ( n t ) O(n^t)O(n
& G2 s$ H7 [: R0 ~t
- ~# N# E$ i# f9 U/ c ) 的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度,后续章节将详细讲解各种情况下的动态规划优化算法。, l: h! x: m, n8 [& E% N
3)计算几何0 e& E, F7 t/ \6 L/ q- w9 v" T5 ]
计算几何的问题是代码量最大的。它是计算机科学的一个分支,以往的解析几何,是用代数的方法,建立坐标系去解决问题,但是很多时候需要付出一些代价,比如精度误差,而计算几何更多的是从几何角度,用向量的方法来尽量减少精度误差,例如:将除法转化为乘法、避免三角函数等近似运算 等等。1 i2 i \, F/ |; k- G4 o) h
如果一个比赛中,有一道计算几何的题,那么至少,它不会是一道水题。9 s0 i- q: L! q/ `9 K6 J
1、double 代替 float" Y' B! s$ l2 E$ p% @. C
c++ 中 double 的精度高于 float,对精度要求较高的问题,务必采用 double;
0 p0 Y* B( F* o. k8 U2 c0 X2、浮点数判定
* J" n$ z1 n6 m( k8 ^5 T* v7 M# c由于浮点数(小数)中是有无理数的,即无限不循环小数,也就是小数点后的位数是无限的,在计算机存储的时候不可能全部存下来,一定是近似的存储的,所以浮点数一定是存在精度误差的(实际上,就算是有理数,也是存在误差的,这和计算机存储机制有关,这里不再展开,有兴趣可以参见我博客的文章:C++ 浮点数精度判定);
/ @& `4 j( A7 E3 E8 s6 u0 [两个浮点数是否相等,可以采用两数相减的绝对值小于某个精度来实现:2 U+ z% V4 T5 ^4 U! h
const double eps = 1e-8;! `& ^/ `) m# v
bool EQ(double a, double b) {
6 D/ i% v8 S2 p: t# ]0 m. F return fabs(a - b) < eps;! o9 C: g6 f6 T, Q+ E2 q
}
) o" @- `, T8 N1: M1 v5 _6 X4 L, l. k# I
2
. m0 @6 @2 b) ?6 e; z/ G' I3
0 @; P0 j3 O! V0 @6 l4
4 t* w3 Y4 B9 i! `1 I并且可以用一个三值函数来确定某个数是零、大于零还是小于零:
) \4 v5 D7 W8 B+ y0 Kint threeValue(double d) {2 \3 D3 q! }# ]. I
if (fabs(d) < eps)
H) t; q* V" \: v* p return 0;
; R, V) Q) n' ^! n return d > 0 ? 1 : -1;
( M3 y: ]* J0 f2 d- m. U}$ R8 V/ S p0 L8 y2 c. b2 |
1
; C( d5 I" f6 R2 p9 F5 V# {21 b& ~' Y$ _4 W! L
3
6 A! {; L/ P" d4) y9 O. Z: |0 J/ h0 C7 p9 G
5
0 u. J& P0 q; N9 K3、负零判定6 |. `8 @" c, @' Z! }( R
因为精度误差的存在,所以在输出的时候一定要注意,避免输出 -0.00:" w! p. d+ D" K" R# ~8 V# Q
double v = -0.0000000001;
& E5 Q4 a$ `) s! @; d0 G1 A9 | printf("%.2lf\n", v);) g, V/ A+ d k! S9 S6 l
1
/ m9 V$ O1 I) }/ d, t" @' j, V }2( _1 C R. x% l: t+ P
避免方法是先通过三值函数确定实际值是否为0,如果是0,则需要取完绝对值后再输出:
) I5 H' O% t- M8 Q+ Q double v = -0.0000000001;1 A1 n- m, z6 B9 Q. I
if(threeValue(v) == 0) {
( ^8 Q% y. u. n3 F v = fabs(v);/ ^% {& I" f; L, {# z
}0 g3 ^* Y, G& h& u! V( j
printf("%.2lf\n", v);( a+ o; ?- U, S( z M4 A* _
1# [- J1 x, v( X% X& s
2
& m. i( A1 v/ F3 o/ e7 P3
( R) w' x4 r) y0 @: S8 Z4
9 Z& R, T/ U% l0 d# B50 w( T! Y( e2 i( p8 F- m
4、避免三角函数、对数、开方、除法等
7 t5 U( h y: q. n% R) @+ jc++ 三角函数运算方法采用的是 CORDIC算法,一种利用迭代的方式进行求解的算法,其中还用到了开方运算,所以实际的算力消耗还是很大的,在实际求解问题的过程中,能够避免不用就尽量不用。
' R# t! v0 v9 B. {( Y( o7 n除法运算会带来精度误差,所以能够转换成乘法的也尽量转换为乘法运算。' M, v; \0 u! u
5、系统性的学习
+ ? @9 F: C, P8 }+ K* A基础知识:点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积;' k; d( F3 Q7 H+ o+ N
进阶知识:多边形面积、凸多边形判定、点在多边形内判定;/ s5 X4 _$ ]2 ^
相关算法:二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。
- R" Q2 x: ^& s& T) N# X. G( @
7 L+ S2 E4 g. P- L8 ~' w+ {$ z+ d6 X
H8 l% ~ c2 }+ A/ _学习计算几何,最好是系统性的,刷题的过程中不断提炼出自己的模板。
+ J7 Y) s% X5 u6 V1 R h' \/ Z8 n; g4)数论$ l8 u& V: `8 x: n0 G
刷题的时候遇到不会的数论题,真的是很揪心,从头学起吧,内容实在是太多了,每个知识点都要证明吃透,不然下次遇到还是不会;不学吧,又不甘心,就是单纯的想把这个题过了,真是进退两难!
, D T; k- s `3 Z9 ~数论对一个人的数学思维要求较高,但是一般也是一些固定的模式,所以把模板整理出来很重要。3 @/ B( |# I/ L* ?( w
当然,数论也有简单问题,一般先做一些入门题提升信心。% @/ L* w" W e1 t$ S
1、数论入门
8 s- b" L. R* q5 s _主要是一些基本概念,诸如:
. b$ [4 F$ O+ D8 q% ^* n3 n整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和 最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节;; B8 R3 h3 h1 V. z+ @, n
2、数论四大定理
+ L' \2 e' D! p4 K9 H7 T2 r这四个定理学完,可以KO很多题:( f7 V5 f z, }4 x
欧拉定理、中国剩余定理、费马小定理、威尔逊定理* V) n& X1 B5 h# s2 W: q( W
3、数论进阶, {" R5 G% _6 w# T# y9 `2 B4 }
系统性的学习,基本也就这些内容了:
8 C j l" O2 D! e扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。
# f5 U$ I: ]! o$ ~, Q+ z5)字符串匹配
' i! c3 S1 _* p6 S字符串匹配学习路线比较明确。2 ]1 g9 w5 ^0 k3 ?4 T
先学习前缀匹配:字典树。! u+ a4 d# V% i+ q: T+ R) {3 M
然后可以简单看一下回文串判定算法:Manacher。, Q2 L M) k' t2 K7 ~. n3 \
以及经典的单字符串匹配算法:KMP。
* j3 B! v# D8 j) `* X% Q: [6 X* n实际上平时最常用的还是 BM 算法,而ACM中基本不考察。5 A5 U7 o/ v+ c. r2 R
然后就是较为高阶的 前缀自动机、后缀数组、后缀树、后缀自动机了。
5 y0 x5 ^8 H! l+ t2 t5 ]0 ~% _关于 算法学习路线 的内容到这里就结束了。" V$ o' w {: b1 x# C. }
如果还有不懂的问题,可以 想方设法 找到作者的微信进行在线咨询。
$ G: o: S4 I5 a! }. ~参考资料/ g7 u5 e0 u% l! J+ E# o1 X3 o
【阶段一】C语言学习资料:《光天化日学C语言》(日更)& \% ~+ f: }3 F e' C
【阶段二】C语言例题:《C语言入门100例》(日更)
; n. h4 [* ^5 v- h* y+ r【阶段三】算法入门题集:《LeetCode算法全集》(日更)( n3 k- e4 I9 Z: I; p: `2 a9 F4 h
【阶段四】算法进阶:《夜深人静写算法》(周更)
+ u% s# L2 r6 m————————————————
8 v* ~: R, N+ Q2 }7 N# Y版权声明:本文为CSDN博主「英雄哪里出来」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
2 R& e+ S8 G1 l x6 _原文链接:https://blog.csdn.net/WhereIsHeroFrom/article/details/118382228
8 @( ?% e1 |1 t5 w5 r8 c W5 p- k; |( s" W- I8 l4 d
# D1 _3 r% m& X0 n
|
zan
|