《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解《算法和数据结构》学习路线总纲

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用


本文已收录于专栏


?《夜深人静写算法》?

前言

  看到太多爆肝熬夜整合的内容,又是几万字,又是爆肝,我也来试试看能不能扛得住。试完后发现,果然还是扛不住啊。但是既然整理完了,那就把我的 算法学习路线 发出来吧,我把整个算法学习的阶段总结成了五个步骤,分别为: 「 基础语法 」 「 语法练习 」 「 数据结构 」 「 算法入门 」 「 算法进阶 」。本文梳理了这五个大项的思维导图,在下文会有详细介绍。
  希望各位能够找到自己的定位,通过自己的努力在算法这条路上越走越远。
  刚开始切勿心浮气躁,说一定要把这么多东西都学会。就算你的精力旺盛,日夜操劳,时间也是有限的。所以,首先是明确我们要做什么,然后制定好一个合理的 「 目标 」 ,然后再将目标进行逐渐拆解,再一点一点将要学习的内容逐步付诸实践才是最重要的。

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
点击我跳转末尾 获取 粉丝专属 《算法和数据结构》源码。


1、基础语法

  算法是以编程语言为基础的,所以选择一门编程语言来学习是必须的。因为作者本身是C/C++技术栈的,所以就拿C语言来举例子吧。如果是 Java、Python 技术栈,可以跳过 C语言相关的内容。这一小节,先给出学习路线图,然后我再来讲,每部分应该如何去学。
《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

1)第一个程序

  无论是 Java、Python、C/C++,想要上手一门语言,第一步一定是 HelloWorld,先不要急着去配环境。如果环境配了几个小时,可能一开始的雄心壮志就被配环境的过程消磨殆尽,更加不要谈日后的丰功伟业了。来看第一个 C 语言程序:

#include <stdio.h> // (1)
int main()                       // (2)
{ 
   
   /* 我的第一个 C 程序 */       // (3)
   printf("Hello, World! \n");   // (4)
   return 0;                     // (5)
}

这段代码只做了一件事情,就是向屏幕上输出一行字:Hello, World!
( 1 ) (1) (1) stdio.h是一个头文件 (标准输入输出头文件) , #include是一个预处理命令,用来引入头文件。当编译器遇到 printf()函数时,如果没有找到 stdio.h头文件,就会发生编译错误。
( 2 ) (2) (2) main()作为这个程序的入口函数,代码都是从这个函数开始执行的。
( 3 ) (3) (3)/**/包围起来的代表注释,是给人看到,不进行代码的解析和执行。
( 4 ) (4) (4) printf代表将内容输出到控制台上。其中\n代表换行符。
( 5 ) (5) (5) 作为函数的返回值。

2)热爱编程

  所以,我们需要让这件事情从一开始就变得 有趣,这样才能坚持下去。比如找一个相对较为有趣的教程,这里我会推荐这个:《光天化日学C语言》。听名字就比较搞笑,可能作者本身也不是什么正经人,哈哈哈!虽然不能作为一个严谨的教程去学,起码可以对搞笑的内容先产生兴趣。从而对于语言本身有学习下去的动力。
  刚才提到的这个系列,可以先收藏起来。回头再去看,它讲述的是 对白式C语言教学,从最简单的输出 HelloWorld 这个字符串开始讲起,逐渐让读者产生对C语言的兴趣。这个系列的作者是前 WorldFinal 退役选手,一直致力于 将困难的问题讲明白 。我看了他的大部分教程,基本都能一遍看懂。

3)制定目录

  然后,我们大致看下你选择的教程的前几个章节,那些标题是否有你认知以外的名词出现,比如以这个思维导图为例,前几个章节为:

1、第一个C语言程序
2、搭建本地环境
3、变量
4、标准输出
5、标准输入
6、进制转换入门
7、ASCII字符
8、常量

  如果你觉得这些名词中有 五六个是没有什么概念的。那么,可能需要补齐一些数学、计算机方面的基础知识。反之,我们就可以继续下一步了。

4)勤于思考

  只要对一件事情养成习惯以后,你就会发现,再难的事情,都只是一点一点积累的过程。重要的是,每天学习的过程一定要吃透,养成主动思考的好习惯。因为,越到后面肯定是越难的,如果前期不养成习惯,后面很可能心有余而力不足。
  就像刷题,一旦不会做就去找解题报告,最后就养成了看解题报告才会做题的习惯。当然这也是一种习惯,只不过不是一种好习惯罢了。

5)事必躬亲

  光看教程肯定是不行的,写代码肯定还是要动手的,因为有些语法你看一遍,必定忘记。但是写了几遍,永世难忘。这或许就是写代码的魅力所在吧。所以,记得多写代码实践。

6)坚持到底

  每天把教程上的内容,自己在键盘上敲一遍,坚持一天,两天,三天。你会发现,第四天就变成了习惯。所以坚持就是今天做了这件事情,明天继续做。

7)正反馈

  然而,就算再有趣的教程,看多了都会乏味,这是人性决定的,你我都逃不了。能够让你坚持下去的只有你自己,这时候,适当给予自己一些正反馈就显得尤为重要。比如,可以用一张表格将自己的学习计划记录下来,然后每天都去分析一下自己的数据。
  当然,你也可以和我一样,创建一个博客,然后每天更新博文,就算没有内容,也坚持日更,久而久之,你会发现,下笔如有神,键盘任我行!更新的内容,可以是自己的学习笔记,心路历程 等等。
  看着每天的粉丝量呈指数级增长,这是全网对你的认可,应该没有什么会是比这个更好的正反馈了。

8)仪式感

  那么,至此,不知道屏幕前的你感想如何,反正正在打字的我已经激情澎湃了。已经全然忘记这一章是要讲C语言基础的了!
  介于篇幅,我会把C语言基础的内容,放在这个专栏 《光天化日学C语言》 里面去讲,一天更新一篇,对啊,既然说了要坚持,要养成习惯,我当然也要做到啦~如果你学到了哪一章,可以在评论区评论 “打卡” ,也算是一种全网见证嘛!
  我也很希望大家的学习速度能够超越我的更新速度。

2、语法练习

  学习的过程中,做题当然也是免不了的,还是应征那句话:实践是检验真理的唯一标准。
  而这里的题库,是我花了大量时间,搜罗了网上各大C语言教程里的例题,总结出来的思维导图,可以先大致看一眼:

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  从数学基础、输入输出、数据类型、循环、数组、指针、函数、位运算、结构体、排序 等几个方面,总结出的具有概括性的例题 100 道 《C语言入门100例》

  • 这里可以列举几个例子:

1、例题1:整除判定

一、题目描述

  先输入一个 t t t,然后输入 t t t 组数据,对于每组数据,输入两个整数 a a a b b b,如果 a a a 能够被 b b b 整除,则输出 YES,否则输出 NO
《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

二、解题思路

难度:?⚪⚪⚪⚪
  首先,当 b b b 等于 0 时, a a a 是一定不能被 b b b 整除的;然后,就是看 a a a 除上 b b b 的余数是不是零了,这步运算在C语言中表示为a % b

三、代码详解

1、if else 语句

#include <stdio.h>
int main() { 
   
    int a, b, t;
    scanf("%d", &t);             // (1)
    while (t--) { 
                   // (2)
        scanf("%d %d", &a, &b);
        if (b == 0 || a % b)     // (3)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}
  • ( 1 ) (1) (1) 输入 t t t 组数据;
  • ( 2 ) (2) (2) while(t--)等价于while(t-- != 0),当 t = 0 t=0 t=0 的情况下,这个循环就会结束,也就是说整个循环会执行一开始输入的那个t的次数;
  • ( 3 ) (3) (3) 根据本题的题意,用逻辑运算符||(或)对两种情况输出 N O NO NO,一种是 b等于0,另一个中是 a % b不等于0;

2、条件运算符

#include <stdio.h>
int main() { 
   
    int a, b, t;
    scanf("%d", &t);
    while (t--) { 
   
        scanf("%d %d", &a, &b);
        printf("%s\n", (b == 0 || a % b) ? "NO" : "YES"); // (1)
    }
    return 0;
}
  • ( 1 ) (1) (1) 采用条件运算符?:来实现if else语句的功能;

2、例题2:最大的数

一、题目描述

  循环输入。每组数据先输入 n ( n ≤ 10000 ) n(n \le 10000) n(n10000),再输入 n n n 个正整数 a i ( a i ≤ 10000 ) a_i(a_i \le 10000) ai(ai10000),输出其中最大的数。当没有任何输入时,程序结束。

二、解题思路

难度:?⚪⚪⚪⚪
  这个问题的经典思路就是枚举问题,以第一个元素为初始最大值,然后不断和第二个数、第三个数、…、第 n n n 个数进行比较,过程中将最大值存下来,最后输出这个最大值即可。

三、代码详解

#include <stdio.h>
int max(int a, int b) { 
   
    return a > b ? a : b;             // (1)
}
int main() { 
   
    int n, a, i, maxv;
    while(scanf("%d", &n) != EOF) { 
   
        for(i = 0; i < n; ++i) { 
   
            scanf("%d", &a);
            if(i == 0) { 
                 // (2)
                maxv = a;       
            }
            maxv = max(a, maxv);      // (3)
        }
        printf("%d\n", maxv);
    }
    return 0;
}
  • ( 1 ) (1) (1) 首先,实现一个最大值函数:给定两个数,求其中的大者。我们利用三目运算符来实现;
  • ( 2 ) (2) (2) n n n 个数迭代求大者,将最大值存储在maxv中,当输入第一个数的时候因为没有比较,所以我们把第一个输入的数直接赋值给它;
  • ( 3 ) (3) (3) 然后对每个输入的数a,和maxv比大小,迭代求最大值;

  由于这个专栏是付费专栏,可能对学生党不是很友好,所以作者经过再三思考,打算放出 300 张 7 折优惠券, 先到先得。只要拿这个图片来找作者即可享受,仅限前 300 名。
  为了适当提高一定门槛,你至少需要学会如何下载图片或者截图并且发送到微信里 ?。

在这里插入图片描述

3、数据结构

  《C语言入门100例》上的例题,如果能理解前面 35 道,那基本C语言的学习就可以告一段落了,接下来就要开始我们的数据结构的学习了。

1、什么是数据结构

  • 你可能听说过 数组、链表、队列、栈、堆、二叉树、图,没错,这些都是数据结构,但是你要问我什么是数据结构,我突然就一脸懵逼了。
  • 如果一定要给出一个官方的解释,那么它就是:

计算机存储、组织数据的方式。相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。往往同高效的检索算法和索引技术有关。

  • 是不是还不如说它是堆,是栈,是队列呢?
  • 是这样的,我们学习的过程中,跳过一些不必要的概念,能够节省我们更多的时间,从而达到更好的效果,当你还在理解数据结构是什么的时候,可能人家已经知道了栈有哪些操作了。

2、数据结构和算法的关系

  • 很多同学搞不明白,数据结构与算法有哪些千丝万缕的关系?甚至有些同学以为算法里本身就包含了数据结构。
  • 数据结构主要讲解数据的组织形式,比如链表,堆,栈,队列。
  • 而算法,则注重的是思想,比如链表的元素怎么插入、删除、查找?堆的元素怎么弹出来的?栈为什么是先进后出?队列又为什么是先进先出?
  • 讲得直白一点,数据结构是有实体的,算法是虚拟的;数据结构是物质上的,算法是精神上的。当然,物质和精神 缺一不可。

3、数据结构概览


第一章


线性表

1)顺序表


《画解数据结构》(1 – 1)- 顺序表

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


2)链表


《画解数据结构》(1 – 2)- 链表

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


3)栈


《画解数据结构》(1 – 3)- 栈

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


4)队列


《画解数据结构》(1 – 4)- 队列

在这里插入图片描述


5)双端队列


《画解数据结构》(1 – 5)- 双端队列

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


6)哈希表


《画解数据结构》(1 – 6)- 哈希表

在这里插入图片描述


7)树


第二章





(2-1)画解树

、

   更多内容请收看:画解树


8)二叉树


(2-2)画解二叉树

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   为了增加阅读体验,更多内容请收看:画解二叉树


9)二叉搜索树


《画解数据结构》(2 – 3)- 二叉搜索树

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


10)堆


(2-4)画解堆

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   为了增加阅读体验,更多内容请收看:画解堆


11)AVL树


(2-5)画解AVL树

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   本文已超五万字,为了增加阅读体验,更多内容请收看:画解二叉平衡树


12)线段树


(2-6)画解线段树

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   为了增加阅读体验,更多内容请收看:画解线段树


13)字典树


(2-7)画解字典树

在这里插入图片描述

   为了增加阅读体验,更多内容请收看:画解字典树


14)霍夫曼树


(2-8)画解霍夫曼树

在这里插入图片描述

   为了增加阅读体验,更多内容请收看:画解霍夫曼树


15)并查集


(2-9)画解并查集

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   为了增加阅读体验,更多内容请收看:画解并查集


16)图


第三章





(3-1)画解图

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   本文已超五万字,为了增加阅读体验,更多内容请收看:画解图


17)二分匹配


(3-2)画解二分匹配

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   为了增加阅读体验,更多内容请收看:画解二分匹配


18)最短路


(3-3)画解最短路

在这里插入图片描述

   为了增加阅读体验,更多内容请收看:画解最短路


19)最小生成树


(3-4)画解最小生成树

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
   为了增加阅读体验,更多内容请收看:画解最小生成树


20)强连通


(3-5)画解强连通

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

   为了增加阅读体验,更多内容请收看:画解强连通

4、算法入门

  • 算法入门,其实就是要开始我们的刷题之旅了。先给出思维导图,然后一一介绍入门十大算法。
    《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


?《算法入门指引》?

5、算法进阶

  • 算法进阶这块是我打算规划自己未来十年去完成的一个项目,囊括了 大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法 的算法全集,也就是之前网络上比较有名的 《夜深人静写算法》 系列,这可以说是我自己对自己的一个要求和目标吧。
  • 如果只是想进大厂,那么 算法入门 已经足够了,不需要再来看算法进阶了,当然如果对算法有浓厚兴趣,也欢迎和我一起打卡。由于内容较难,工作也比较忙,所以学的也比较慢,一周基本也只能更新一篇。

这个系列主要分为以下几个大块内容:
  1)图论
  2)动态规划
  3)计算几何
  4)数论
  5)字符串匹配
  6)高级数据结构(课本上学不到的)
  7)杂项算法

  • 先来看下思维导图,然后我大致讲一下每一类算法各自的特点,以及学习方式:

在这里插入图片描述

1)图论

1、搜索概览

  • 图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能,给出人类制定好的规则,枚举出所有可行的情况,找到可行解或者最优解。
    《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  • 比较常见的搜索算法是 深度优先搜索(又叫深度优先遍历) 和 广度优先搜索(又叫广度优先遍历 或者 宽度优先遍历)。各种图论的算法基本都是依靠这两者进行展开的。

2、深度优先搜索

  • 深度优先搜索一般用来求可行解,利用剪枝进行优化,在树形结构的图上用处较多;而广度优先搜索一般用来求最优解,配合哈希表进行状态空间的标记,从而避免重复状态的计算;
  • 原则上,天下万物皆可搜,只是时间已惘然。搜索会有大量的重复状态出现,这里的状态和动态规划的状态是同一个概念,所以有时候很难分清到底是用搜索还是动态规划。
  • 但是,大体上还是有迹可循的,如果这个状态不能映射到数组被缓存下来,那么大概率就是需要用搜索来求解的。
  • 如图所示,代表的是一个深度优先搜索的例子,红色实箭头表示搜索路径,蓝色虚箭头表示回溯路径。
    《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  • 红色块表示往下搜索,蓝色块表示往上回溯,遍历序列为:
	0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6
  • 同样,搜索的例子还有:
    《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  • 计算的是利用递归实现的 n n n 的阶乘。

3、记忆化搜索

  • 对于斐波那契函数的求解,如下所示:
  • f ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n − 1 ) + f ( n − 2 ) ( n > 2 ) f(n) = \begin{cases}1 & (n = 0) \\1 & (n = 1) \\f(n-1) + f(n-2) & (n > 2) \end{cases} f(n)=11f(n1)+f(n2)(n=0)(n=1)(n>2)
  • 对于 f ( 5 ) f(5) f(5) 的求解,程序调用如下:
    在这里插入图片描述
  • 这个过程用到了很多重复状态的搜索,我们需要将它优化,一般将一些状态缓存起来。
  • 我们通过一个动图来感受一下:
    在这里插入图片描述
  • 当第二次需要计算 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、广度优先搜索

  • 单向广搜就是最简化情况下的广度优先搜索(Breadth First Search),以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路,就是广搜的加强版。
  • 我们通过一个动图来对广搜有一个初步的印象。

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

  • 从图中可以看出,广搜的本质还是暴力枚举。即对于每个当前位置,枚举四个相邻可以行走的方向进行不断尝试,直到找到目的地。有点像洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水灌溉,所以我们也把这种算法称为 FloodFill。
  • 那么,如何把它描述成程序的语言呢?这里需要用到一种数据结构 —— 队列。
  • 这时候,算法和数据结构就完美结合了。

2)动态规划

动态规划算法三要素:
  ①所有不同的子问题组成的表;
  ②解决问题的依赖关系可以看成是一个图;
  ③填充子问题的顺序(即对②的图进行拓扑排序,填充的过程称为状态转移);

  • 如果子问题的数目为 O ( n t ) O(n^t) O(nt),每个子问题需要用到 O ( n e ) O(n^e) O(ne) 个子问题的结果,那么我们称它为 tD/eD 的问题,于是可以总结出四类常用的动态规划方程:(下面会把opt作为取最优值的函数(一般取 m i n min min m a x max max ), w ( j , i ) w(j, i) w(j,i)为一个实函数,其它变量都可以在常数时间计算出来)。

1、1D/1D

  • d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d[i] = opt( d[j] + w(j, i) | 0 <= i < j ) d[i]=opt(d[j]+w(j,i)0<=i<j)
  • 状态转移如图四所示(黄色块代表 d [ i ] d[i] d[i],绿色块代表 d [ j ] d[j] d[j]):
    《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  • 这类状态转移方程一般出现在线性模型中。

2、2D/0D

  • 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[i][j] = opt( d[i-1][j] + x_i, d[i][j-1] + y_j, d[i-1][j-1] + z_{ij} ) d[i][j]=opt(d[i1][j]+xi,d[i][j1]+yj,d[i1][j1]+zij)
  • 状态转移如图四所示:
    《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  • 比较经典的问题是最长公共子序列、最小编辑距离。
  • 有关最长公共子序列的问题,可以参考以下文章:夜深人静写算法(二十一)- 最长公共子序列
  • 有关最小编辑距离的问题,可以参考以下文章:夜深人静写算法(二十二)- 最小编辑距离

3、2D/1D

  • d [ i ] [ j ] = w ( i , j ) + o p t ( d [ i ] [ k − 1 ] + d [ k ] [ j ] ) d[i][j] = w(i, j) + opt( d[i][k-1] + d[k][j] ) d[i][j]=w(i,j)+opt(d[i][k1]+d[k][j])
  • 区间模型常用方程,如图所示:
    在这里插入图片描述
  • 另外一种常用的 2D/1D 的方程为:
  • d [ i ] [ j ] = o p t ( d [ i − 1 ] [ k ] + w ( i , j , k ) ∣ k < j ) d[i][j] = opt( d[i-1][k] + w(i, j, k) | k < j ) d[i][j]=opt(d[i1][k]+w(i,j,k)k<j)

4、2D/2D

  • d [ i ] [ j ] = o p t ( d [ i ′ ] [ j ′ ] + w ( i ′ , j ′ , i , j ) ∣ 0 < = i ′ < i , 0 < = j ′ < j ) d[i][j] = opt( d[i’][j’] + w(i’, j’, i, j) | 0 <= i’ < i, 0 <= j’ < j) d[i][j]=opt(d[i][j]+w(i,j,i,j)0<=i<i,0<=j<j)
  • 如图所示:
    在这里插入图片描述
  • 常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等。
  • 对于一个tD/eD 的动态规划问题,在不经过任何优化的情况下,可以粗略得到一个时间复杂度是 O ( n t + e ) O(n^ {t+e}) O(nt+e),空间复杂度是 O ( n t ) O(n^t) O(nt) 的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度,后续章节将详细讲解各种情况下的动态规划优化算法。

3)计算几何

  • 计算几何的问题是代码量最大的。它是计算机科学的一个分支,以往的解析几何,是用代数的方法,建立坐标系去解决问题,但是很多时候需要付出一些代价,比如精度误差,而计算几何更多的是从几何角度,用向量的方法来尽量减少精度误差,例如:将除法转化为乘法、避免三角函数等近似运算 等等。
  • 如果一个比赛中,有一道计算几何的题,那么至少,它不会是一道水题。

1、double 代替 float

  • c++ 中 double 的精度高于 float,对精度要求较高的问题,务必采用 double;

2、浮点数判定

  • 由于浮点数(小数)中是有无理数的,即无限不循环小数,也就是小数点后的位数是无限的,在计算机存储的时候不可能全部存下来,一定是近似的存储的,所以浮点数一定是存在精度误差的(实际上,就算是有理数,也是存在误差的,这和计算机存储机制有关,这里不再展开,有兴趣可以参见我博客的文章:C++ 浮点数精度判定);
  • 两个浮点数是否相等,可以采用两数相减的绝对值小于某个精度来实现:
const double eps = 1e-8;
bool EQ(double a, double b) { 
   
    return fabs(a - b) < eps;
}
  • 并且可以用一个三值函数来确定某个数是零、大于零还是小于零:
int threeValue(double d) { 
   
    if (fabs(d) < eps)
        return 0;
    return d > 0 ? 1 : -1;
}

3、负零判定

  • 因为精度误差的存在,所以在输出的时候一定要注意,避免输出 -0.00:
    double v = -0.0000000001;
    printf("%.2lf\n", v);
  • 避免方法是先通过三值函数确定实际值是否为0,如果是0,则需要取完绝对值后再输出:
    double v = -0.0000000001;
    if(threeValue(v) == 0) { 
   
        v = fabs(v);
    }
    printf("%.2lf\n", v);

4、避免三角函数、对数、开方、除法等

  • c++ 三角函数运算方法采用的是 CORDIC算法,一种利用迭代的方式进行求解的算法,其中还用到了开方运算,所以实际的算力消耗还是很大的,在实际求解问题的过程中,能够避免不用就尽量不用。
  • 除法运算会带来精度误差,所以能够转换成乘法的也尽量转换为乘法运算。

5、系统性的学习

基础知识:点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积;
进阶知识:多边形面积、凸多边形判定、点在多边形内判定;
相关算法:二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。

  • 学习计算几何,最好是系统性的,刷题的过程中不断提炼出自己的模板。

4)数论

  • 刷题的时候遇到不会的数论题,真的是很揪心,从头学起吧,内容实在是太多了,每个知识点都要证明吃透,不然下次遇到还是不会;不学吧,又不甘心,就是单纯的想把这个题过了,真是进退两难!
  • 数论对一个人的数学思维要求较高,但是一般也是一些固定的模式,所以把模板整理出来很重要。
  • 当然,数论也有简单问题,一般先做一些入门题提升信心。

1、数论入门

  • 主要是一些基本概念,诸如:
  • 整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和 最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节;

2、数论四大定理

  • 这四个定理学完,可以KO很多题:
  • 欧拉定理、中国剩余定理、费马小定理、威尔逊定理

3、数论进阶

  • 系统性的学习,基本也就这些内容了:
  • 扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。

  • 今天先讲这么多吧。
  • 如果还有不懂的问题,可以 「 想方设法 」找到作者的「 联系方式 」 ,随时线上沟通。

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解
  相信看我文章的大多数都是「 大学生 」,能上大学的都是「 精英 」,那么我们自然要「 精益求精 」,如果你还是「 大一 」,那么太好了,你拥有大把时间,当然你可以选择「 刷剧 」,然而,「 学好算法 」,三年后的你自然「 不能同日而语 」
  那么这里,我整理了「 几十个基础算法 」 的分类,点击开启:


?《算法入门指引》?


  如果链接被屏蔽,或者有权限问题,可以私聊作者解决。

  大致题集一览:


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


在这里插入图片描述


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解


《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

  为了让这件事情变得有趣,以及「 照顾初学者 」,目前题目只开放最简单的算法 「 枚举系列 」 (包括:线性枚举、双指针、前缀和、二分枚举、三分枚举),当有 一半成员刷完 「 枚举系列 」 的所有题以后,会开放下个章节,等这套题全部刷完,你还在群里,那么你就会成为「 夜深人静写算法 」专家团 的一员。
  不要小看这个专家团,三年之后,你将会是别人 望尘莫及 的存在。如果要加入,可以联系我,考虑到大家都是学生, 没有「 主要经济来源 」,在你成为神的路上,「 不会索取任何 」



?让天下没有难学的算法?




C语言免费动漫教程,和我一起打卡!


?《光天化日学C语言》?




入门级C语言真题汇总


?《C语言入门100例》?




几张动图学会一种数据结构


?《画解数据结构》?




组团学习,抱团生长


?《算法入门指引》?




竞赛选手金典图文教程


?《夜深人静写算法》?
  这篇文章的主要目的是讲解二叉搜索树的一些基础概念,以及和二叉搜索树相关的一些经典算法。但是实际学习过程还是需要看个人的毅力和坚持。下图代表的是 LeetCode 经典的二叉搜索树的题集,其中树是很重要的一个章节,涉及了诸多算法,希望可以供读者参考和学习。

《算法和数据结构》从语言到算法的过渡篇缩写_对数据结构和算法的理解

粉丝专属福利

语言入门《光天化日学C语言》(示例代码)
语言训练《C语言入门100例》试用版
数据结构《画解数据结构》源码
算法入门《算法入门》指引
算法进阶《夜深人静写算法》算法模板

  


??
验证码 可通过搜索下方
公众号 获取??

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/186528.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • java -jar没有主清单属性_idea怎么导入jar

    java -jar没有主清单属性_idea怎么导入jar使用idea2018打包了一个springboot项目(打包为jar)启动是报错如下:错误原因打包后的jar文件中的MANIFEST.MF缺少项目启动项,即没有Main-Class和Start-Class如下:解决方案如下指定MANIFEST.MF路径项目打包前第一步file–&gt;projectstructure弹框后选中Atifacts—&gt…

  • stl库,基本操作代码

    stl库,基本操作代码

  • linux查看硬盘smart信息_检查中ctl是检查什么

    linux查看硬盘smart信息_检查中ctl是检查什么知识介绍SMART是一种磁盘自我分析检测技术,早在90年代末就基本得到了普及每一块硬盘(包括IDE、SCSI)在运行的时候,都会将自身的若干参数记录下来这些参数包括型号、容量、温度、密度、扇区、寻道时间、传输、误码率等硬盘运行了几千小时后,很多内在的物理参数都会发生变化某一参数超过报警阈值,则说明硬盘接近损坏此时硬盘依然在工作,如果用户不理睬这个报警继续使用那么硬盘将变得非常不可靠,随时可能故障启用SMARTSMART是和主板BIOS上相应功能配合的要使用SMART,必须先进入到主板

  • JVM内存结构图解

    JVM内存结构图解一 真实系统中的概念  JVM(JavaVirtualMachine),顾名思义是对真实计算机系统的模拟,正因如此才能屏蔽物理机器的变化,从而实现“一次编译,到处运行”。  相信很多Java程序员经常听到堆、栈等概念,也会进行设置调优以让Java应用能够更好地运行,但对于JVM与真实计算机系统之间的关系并没有特别清晰的认识。因此,这里先简单介绍下真实计算机系统中的一

  • git查看本地分支对应的远程分支_git 查看远程分支地址

    git查看本地分支对应的远程分支_git 查看远程分支地址在项目目录下右键GitBashHere输入如下命令:$gitbranch*master效果如下:本地只有一个master分支

  • vCenter用户和组管理

    vCenter用户和组管理

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号