精华内容
下载资源
问答
  • 刷了 3333 题 算法题 后的一点点经验总结 —— 题不是这么刷的!

    1️⃣前言:追忆我的刷题经历

      学习算法最好的方法就是刷题了,上大学的时候刷过一些,最近开始转战 LeetCode。

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

    C语言免费动漫教程,和我一起打卡!
    🌞《光天化日学C语言》🌞

    入门级C语言真题汇总
    🧡《C语言入门100例》🧡

    几张动图学会一种数据结构
    🌳《画解数据结构》🌳

    组团学习,抱团生长
    🌌《算法入门指引》🌌

    竞赛选手金典图文教程
    💜《夜深人静写算法》💜

    在这里插入图片描述

    2️⃣算法和数据结构的重要性

    👪1、适用人群

    • 这篇文章会从 「算法和数据结构」 零基础开始讲,所以,如果你是算法大神,可以尽情在评论区嘲讽我哈哈,目的当然是帮助想要涉足算法领域,或者正在找工作的朋友,以及将要找工作的大学生,更加有效快速的掌握算法思维,能够在职场面试和笔试中一展身手。
    • 这篇文章中,我会着重讲解一些常见的 「算法和数据结构」 的设计思想,并且配上动图。主要针对面试中常见的问题和新手朋友们比较难理解的点进行解析。当然,后面也会给出面向算法竞赛的提纲,如果有兴趣深入学习的欢迎在评论区留言,一起成长交流。
    • 零基础学算法的最好方法,莫过于刷题了。任何事情都是需要坚持的,刷题也一样,没有刷够足够的题,就很难做出系统性的总结。所以上大学的时候,我花了三年的时间来刷题, 工作以后还是会抽点时间出来刷题。

    千万不要用工作忙来找借口,时间挤一挤总是有的。

    • 我现在上班地铁上一个小时,下班地铁又是一个小时。比如这篇文章的起草,就是在 地铁 上完成的。如何利用这两个小时的时间,做一些有建设性的事情,才是最重要的。刷抖音一个小时过得很快,刷题也是同样的道理。
    • 当然,每天不需要花太多时间在这个上面,把这个事情做成一个规划,按照长期去推进。反正也没有 KPI 压力,就当成是工作之余的一种消遣,还能够提升思维能力。

    所以,无论你是 小学生中学生高中OIer大学ACMer职场人士,只要想开始,一切都不会太晚!

    🎾2、有何作用

    • 我们平常使用的 智能手机、搜索引擎、网站、操作系统、游戏、软件、人工智能,都大量地应用了 「算法与数据结构」 的知识,以及平时你用到的各种库的底层实现,也是通过各种算法和数据结构组合出来的,所以可以说,有程序的地方,就有江湖 算法,有算法就一定会有对应的数据结构。
    • 如果你只是想学会写代码,或许 「算法与数据结构」 并不是那么重要,但是想要往更深一步发展,「算法与数据结构」 是必不可少的。

      现在一些主流的大厂,在面试快结束的时候都会 奉上一道算法题,如果你敲不出来,可能你的 offer 年包就打了 七折,或者直接与 offer 失之交臂,都是有可能的(因为我自己也是万恶的面试官,看到候选人的算法题写不出来我也是操碎了心,但是我一般会给足容错,比如给三个算法题,挑一个写,任意写出一个都行)。

    • 当然,它不能完全代表你的编码能力,因为有些算法确实是很巧妙,加上紧张的面试氛围,想不出来其实也是正常的,但是你能确保面试官是这么想的吗?我们要做的是十足的准备,既然决定出来,offer 当然是越高越好,毕竟大家都要养家糊口,房价又这么贵,如果能够在算法这一块取得先机,也不失为一个捷径。

    所以,你问我算法和数据结构有什么用?我可以很明确的说,和你的年薪息息相关。

    • 当然,面试中 「算法与数据结构」 知识的考察只是面试内容的一部分。其它还有很多面试要考察的内容,当然不是本文主要核心内容,这里就不做展开了。

    📜3、算法简介

    • 算法是什么东西?
    • 它是一种方法,一种解决问题的方案。
    • 举个例子,你现在要去上班,可以选择 走路、跑步、坐公交、坐地铁、自己开车 等等,这些都是解决方案。但是它们都会有一些衡量指标,让你有一个权衡,最后选择你认为最优的策略去做。
    • 而衡量的指标诸如:时间消耗、金钱消耗、是否需要转车、是否可达 等等。

    时间消耗就对应了:时间复杂度
    金钱消耗就对应了:空间复杂度
    是否可达就对应了:算法可行性

    • 当然,是否需要转车,从某种程度上都会影响 时间复杂度 或者 空间复杂度

    🌲4、数据结构

    • 对于实现某个算法,我们往往会用到一些数据结构。
    • 因为我们通常不能一下子把数据处理完,更多的时候需要先把它们放在一个容器或者说缓存里面,等到一定的时刻再把它们拿出来。
    • 这其实是一种 「空间换时间」 思想的体现, 恰当使用数据结构可以帮助我们高效地处理数据。
    • 常用的一些数据结构如下:
    数据结构应用场景
    数组线性存储、元素为任意相同类型、随机访问
    字符串线性存储、元素为字符、结尾字符、随机访问
    链表链式存储、快速删除
    先进后出
    队列先进先出
    哈希表随机存储、快速增删改查
    二叉树对数时间增删改查,二叉查找树、线段树
    多叉树B/B+树 硬盘树、字典树 字符串前缀匹配
    森林并查集 快速合并数据
    树状数组单点更新,成段求和
    • 为什么需要引入这么多数据结构呢?

      答案是:任何一种数据结构是不是 完美的。所以我们需要根据对应的场景,来采用对应的数据结构,具体用哪种数据结构,需要通过刷题不断刷新经验,才能总结出来。

    3️⃣如何开始持续的刷题

    • 有朋友告诉我,题目太难了,根本不会做,每次都是看别人的解题报告。

    📑1、立军令状

    • 所谓 「军令状」,其实就是给自己定一个目标,给自己树立一个目标是非常重要的,有 「目标才会有方向,有目标才会有动力,有目标才会有人生的意义」 。而军令状是贬义的,如果不达成就会有各种惩罚,所以其实你是心不甘情不愿的,于是这件事情其实是无法持久下去的。

    事实证明,立军令状是不可取的。

    • 啊这……所以我们还是要采用一些能够持久下去的方法。

    👩‍❤️‍👩2、培养兴趣

    • 为了让这件事情能够持久下去,一定要培养出兴趣,适时的给自己一些正反馈。正反馈的作用就是每过一个周期,如果效果好,就要有奖励,这个奖励机制可以自己设定,但是 「不能作弊」 ,一旦作弊就像单机游戏修改数值,流失是迟早的事。
    • 举个例子,我们可以给每天制定一些 「不一样的目标和奖励」 ,比如下图所示:
    刷题的第?天目标题数是否完成完成奖励
    11攻击力 + 10
    21防御力 + 10
    32出去吃顿好的
    42攻击力 + 29
    53防御力 + 60
    61攻击力 + 20
    74出去吃顿好的
    81防御力 + 50
    • 当然,这个完成奖励你可以自己定,总而言之,要是对你有诱惑的奖励才是有意义的。

    🚿3、狂切水题

    • 刚开始刷的 300 题一定都是 「水题」 ,刷 「水题」 的目的是让你养成一个每天刷题的习惯。久而久之,不刷题的日子会变得无比煎熬。当然,刷着刷着,你会发现,水题会越来越多,因为刷题的过程中,你已经无形中不断成长起来了。
    • 至少这个方法我用过,非常灵验!推荐刷题从水题开始。

    如果不知道哪里有水题,推荐:
       C语言入门水题:《C语言入门100例》
      C语言算法水题:《LeetCode算法全集》

    💪🏻4、养成习惯

    • 相信如果切了 300 个 「水题」 以后,刷题自然而然就成了习惯,想放弃都难。这个专业上讲,其实叫 沉没成本。有兴趣的可以自行百度,这里就不再累述了。

    🈵5、一周出师

    • 基本上如果能够按照这样的计划去执行,一周以后,一定会有收获,没有收获的话,可以来找我。

    4️⃣简单数据结构的掌握

    🚂1、数组

    内存结构:内存空间连续
    实现难度:简单
    下标访问:支持
    分类:静态数组、动态数组
    插入时间复杂度 O ( n ) O(n) O(n)
    查找时间复杂度 O ( n ) O(n) O(n)
    删除时间复杂度 O ( n ) O(n) O(n)

    🎫2、字符串

    内存结构:内存空间连续,类似字符数组
    实现难度:简单,一般系统会提供一些方便的字符串操作函数
    下标访问:支持
    插入时间复杂度 O ( n ) O(n) O(n)
    查找时间复杂度 O ( n ) O(n) O(n)
    删除时间复杂度 O ( n ) O(n) O(n)

    🎇3、链表

    内存结构:内存空间连续不连续,看具体实现
    实现难度:一般
    下标访问:不支持
    分类:单向链表、双向链表、循环链表、DancingLinks
    插入时间复杂度 O ( 1 ) O(1) O(1)
    查找时间复杂度 O ( n ) O(n) O(n)
    删除时间复杂度 O ( 1 ) O(1) O(1)

    🌝4、哈希表

    内存结构:哈希表本身连续,但是衍生出来的结点逻辑上不连续
    实现难度:一般
    下标访问:不支持
    分类:正数哈希、字符串哈希、滚动哈希
    插入时间复杂度 O ( 1 ) O(1) O(1)
    查找时间复杂度 O ( 1 ) O(1) O(1)
    删除时间复杂度 O ( 1 ) O(1) O(1)

    👨‍👩‍👧5、队列

    内存结构:看用数组实现,还是链表实现
    实现难度:一般
    下标访问:不支持
    分类:FIFO、单调队列、双端队列
    插入时间复杂度 O ( 1 ) O(1) O(1)
    查找时间复杂度:理论上不支持
    删除时间复杂度 O ( 1 ) O(1) O(1)

    👩‍👩‍👦‍👦6、栈

    内存结构:看用数组实现,还是链表实现
    实现难度:一般
    下标访问:不支持
    分类:FILO、单调栈
    插入时间复杂度 O ( 1 ) O(1) O(1)
    查找时间复杂度:理论上不支持
    删除时间复杂度 O ( 1 ) O(1) O(1)

    🌵7、二叉树

    优先队列 是 堆实现的,所以也属于 二叉树 范畴。它和队列不同,不属于线性表。
    内存结构:内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续
    实现难度:较难
    下标访问:不支持
    分类:二叉树 和 多叉树
    插入时间复杂度:看情况而定
    查找时间复杂度:理论上 O ( l o g 2 n ) O(log_2n) O(log2n)
    删除时间复杂度:看情况而定

    🌳8、多叉树

    内存结构:内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续
    实现难度:较难
    下标访问:不支持
    分类:二叉树 和 多叉树
    插入时间复杂度:看情况而定
    查找时间复杂度:理论上 O ( l o g 2 n ) O(log_2n) O(log2n)
    删除时间复杂度:看情况而定

    🌲9、森林

    🍀10、树状数组

    🌍11、图

    内存结构:不一定
    实现难度:难
    下标访问:不支持
    分类:有向图、无向图
    插入时间复杂度:根据算法而定
    查找时间复杂度:根据算法而定
    删除时间复杂度:根据算法而定

    1、图的概念

    • 在讲解最短路问题之前,首先需要介绍一下计算机中图(图论)的概念,如下:
    • G G G 是一个有序二元组 ( V , E ) (V,E) (V,E),其中 V V V 称为顶点集合, E E E 称为边集合, E E E V V V 不相交。顶点集合的元素被称为顶点,边集合的元素被称为边。
    • 对于无权图,边由二元组 ( u , v ) (u,v) (u,v) 表示,其中 u , v ∈ V u, v \in V u,vV。对于带权图,边由三元组 ( u , v , w ) (u,v, w) (u,v,w) 表示,其中 u , v ∈ V u, v \in V u,vV w w w 为权值,可以是任意类型。
    • 图分为有向图和无向图,对于有向图, ( u , v ) (u, v) (u,v) 表示的是 从顶点 u u u 到 顶点 v v v 的边,即 u → v u \to v uv;对于无向图, ( u , v ) (u, v) (u,v) 可以理解成两条边,一条是 从顶点 u u u 到 顶点 v v v 的边,即 u → v u \to v uv,另一条是从顶点 v v v 到 顶点 u u u 的边,即 v → u v \to u vu

    2、图的存储

    • 对于图的存储,程序实现上也有多种方案,根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例,讲解四种存储图的方案。

    1)邻接矩阵

    • 邻接矩阵是直接利用一个二维数组对边的关系进行存储,矩阵的第 i i i 行第 j j j 列的值 表示 i → j i \to j ij 这条边的权值;特殊的,如果不存在这条边,用一个特殊标记 ∞ \infty 来表示;如果 i = j i = j i=j,则权值为 0 0 0
    • 它的优点是:实现非常简单,而且很容易理解;缺点也很明显,如果这个图是一个非常稀疏的图,图中边很少,但是点很多,就会造成非常大的内存浪费,点数过大的时候根本就无法存储。
    • [ 0 ∞ 3 ∞ 1 0 2 ∞ ∞ ∞ 0 3 9 8 ∞ 0 ] \left[ \begin{matrix} 0 & \infty & 3 & \infty \\ 1 & 0 & 2 & \infty \\ \infty & \infty & 0 & 3 \\ 9 & 8 & \infty & 0 \end{matrix} \right] 0190832030

    2)邻接表

    • 邻接表是图中常用的存储结构之一,采用链表来存储,每个顶点都有一个链表,链表的数据表示和当前顶点直接相邻的顶点的数据 ( v , w ) (v, w) (v,w),即 顶点 和 边权。
    • 它的优点是:对于稀疏图不会有数据浪费;缺点就是实现相对邻接矩阵来说较麻烦,需要自己实现链表,动态分配内存。
    • 如图所示, d a t a data data ( v , w ) (v, w) (v,w) 二元组,代表和对应顶点 u u u 直接相连的顶点数据, w w w 代表 u → v u \to v uv 的边权, n e x t next next 是一个指针,指向下一个 ( v , w ) (v, w) (v,w) 二元组。
    • 在 C++ 中,还可以使用 vector 这个容器来代替链表的功能;
        vector<Edge> edges[maxn];
    

    3)前向星

    • 前向星是以存储边的方式来存储图,先将边读入并存储在连续的数组中,然后按照边的起点进行排序,这样数组中起点相等的边就能够在数组中进行连续访问了。
    • 它的优点是实现简单,容易理解;缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序,带来了时间开销,实用性也较差,只适合离线算法。
    • 如图所示,表示的是三元组 ( u , v , w ) (u, v, w) (u,v,w) 的数组, i d x idx idx 代表数组下标。
      在这里插入图片描述
    • 那么用哪种数据结构才能满足所有图的需求呢?
    • 接下来介绍一种新的数据结构 —— 链式前向星。

    4)链式前向星

    • 链式前向星和邻接表类似,也是链式结构和数组结构的结合,每个结点 i i i 都有一个链表,链表的所有数据是从 i i i 出发的所有边的集合(对比邻接表存的是顶点集合),边的表示为一个四元组 ( 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 v uv w w w 代表边上的权值, n e x t next next 指向下一条边。
    • 具体的,我们需要一个边的结构体数组 edge[maxm]maxm表示边的总数,所有边都存储在这个结构体数组中,并且用head[i]来指向 i i i 结点的第一条边。
    • 边的结构体声明如下:
    struct Edge {
        int u, v, w, next;
        Edge() {}
        Edge(int _u, int _v, int _w, int _next) :
            u(_u), v(_v), w(_w), next(_next) 
        {
        }
    }edge[maxm];
    
    • 初始化所有的head[i] = -1,当前边总数 edgeCount = 0
    • 每读入一条 u → v u \to v uv 的边,调用 addEdge(u, v, w),具体函数的实现如下:
    void addEdge(int u, int v, int w) {
        edge[edgeCount] = Edge(u, v, w, head[u]);
        head[u] = edgeCount++;
    }
    
    • 这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w) (u,v,w),就在原有的链表结构的首部插入这条边,使得每次插入的时间复杂度为 O ( 1 ) O(1) O(1),所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现,空间上没有浪费,时间上也是最小开销。
    • 调用的时候只要通过head[i]就能访问到由 i i i 出发的第一条边的编号,通过编号到edge数组进行索引可以得到边的具体信息,然后根据这条边的next域可以得到第二条边的编号,以此类推,直到 next域为 -1 为止。
    for (int e = head[u]; ~e; e = edges[e].next) {
        int v = edges[e].v;
        ValueType w = edges[e].w;
        ...
    }
    
    • 文中的 ~e等价于 e != -1,是对e进行二进制取反的操作(-1 的的补码二进制全是 1,取反后变成全 0,这样就使得条件不满足跳出循环)。

    5️⃣简单算法的入门

    • 入门十大算法是 线性枚举、线性迭代、简单排序、二分枚举、双指针、差分法、位运算、贪心、分治递归、简单动态规划。
    • 对于这十大算法,我会逐步更新道这个专栏里面:《LeetCode算法全集》
    • 浓缩版可参考如下文章:《十大入门算法》

    🚊10、简单动态规划

    LeetCode 746. 使用最小花费爬楼梯

      数组的每个下标作为一个阶梯,第 i i i 个阶梯对应着一个非负数的体力花费值 c o s t [ i ] cost[i] cost[i](下标从 0 开始)。每当爬上一个阶梯,都要花费对应的体力值,一旦支付了相应的体力值,就可以选择 向上爬一个阶梯 或者 爬两个阶梯。求找出达到楼层顶部的最低花费。在开始时,可以选择从下标为 0 或 1 的元素作为初始阶梯。
      样例输入: c o s t = [ 1 , 99 , 1 , 1 , 1 , 99 , 1 , 1 , 99 , 1 ] cost = [1, 99, 1, 1, 1, 99, 1, 1, 99, 1] cost=[1,99,1,1,1,99,1,1,99,1]
      样例输出: 6 6 6
    如图所以,蓝色的代表消耗为 1 的楼梯,红色的代表消耗 99 的楼梯。

    a、思路分析

    • 令走到第 i i i 层的最小消耗为 f [ i ] f[i] f[i]
    • 假设当前的位置在 i i i 层楼梯,那么只可能从 i − 1 i-1 i1 层过来,或者 i − 2 i-2 i2 层过来;
    • 如果从 i − 1 i-1 i1 层过来,则需要消耗体力值: f [ i − 1 ] + c o s t [ i − 1 ] f[i-1] + cost[i-1] f[i1]+cost[i1]
    • 如果从 i − 2 i-2 i2 层过来,则需要消耗体力值: f [ i − 2 ] + c o s t [ i − 2 ] f[i-2] + cost[i-2] f[i2]+cost[i2]
    • 起点可以在第 0 或者 第 1 层,于是有状态转移方程:
    • f [ i ] = { 0 i = 0 , 1 min ⁡ ( f [ i − 1 ] + c o s t [ i − 1 ] , f [ i − 2 ] + c o s t [ i − 2 ] ) i > 1 f[i] = \begin{cases} 0 & i=0,1\\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases} f[i]={0min(f[i1]+cost[i1],f[i2]+cost[i2])i=0,1i>1

    b. 时间复杂度

    • 状态数: O ( n ) O(n) O(n)
    • 状态转移: O ( 1 ) O(1) O(1)
    • 时间复杂度: O ( n ) O(n) O(n)

    c. 代码详解

    class Solution {
        int f[1100];                                                   // (1)
    public:
        int minCostClimbingStairs(vector<int>& cost) {
            f[0] = 0, f[1] = 0;                                        // (2)
            for(int i = 2; i <= cost.size(); ++i) {
                f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);    // (3)
            }
            return f[cost.size()];
        }
    };
    
    • ( 1 ) (1) (1)f[i]代表到达第 i i i 层的消耗的最小体力值。
    • ( 2 ) (2) (2) 初始化;
    • ( 3 ) (3) (3) 状态转移;

    有没有发现,这个问题和斐波那契数列很像,只不过斐波那契数列是求和,这里是求最小值。


    6️⃣刷题顺序的建议

      然后介绍一下刷题顺序的问题,我们刷题的时候千万不要想着一步到位,一开始,没有刷满三百题,姿态放低,都把自己当成小白来处理。
      这里以刷 LeetCode 为例,我目前只刷了不到 50 题,所以我是小白。
      当我是小白时,我只刷入门题,也就是下面这几个专题。先把上面所有的题目刷完,在考虑下一步要做什么。

    👨‍👦1、入门算法

    种类链接
    算法算法入门
    数据结构数据结构入门
    数组字符串专题数组和字符串
    动态规划专题动态规划入门DP路径问题

      当入门的题刷完了,并且都能讲述出来自己刷题的过程以后,我们再来看初级的一些算法和简单的数据结构,简单的数据结构就是线性表了,包含:数组、字符串、链表、栈、队列 等等,即下面这些专题。

    👩‍👧‍👦2、初级算法

    种类链接
    算法初级算法
    栈和队列专题队列 & 栈

      上面的题刷完以后,其实已经算是基本入门了,然后就可以开始系统性的学习了。
      当然,基本如果真的到了这一步,说明你的确已经爱上了刷题了,那么我们可以尝试挑战一下 LeetCode 上的一些热门题,毕竟热门题才是现在面试的主流,能够有更好的结果,这样刷题的时候也会有更加强劲的动力不是吗!

    👩‍👩‍👧‍👦3、中级算法

    种类链接
    算法中极算法
    二叉树专题二叉树
    热门题热门题 TOP 100

    7️⃣系统学习算法和数据结构

    🚍1、进阶动态规划

    文章链接难度等级推荐阅读
    夜深人静写算法(二)- 动态规划入门★☆☆☆☆★★★★★
    夜深人静写算法(二十六)- 记忆化搜索★☆☆☆☆★★★★★
    夜深人静写算法(十九)- 背包总览★☆☆☆☆★★★★★
    夜深人静写算法(二十)- 最长单调子序列★☆☆☆☆★★★★★
    夜深人静写算法(二十一)- 最长公共子序列★☆☆☆☆★★★★★
    夜深人静写算法(二十二)- 最小编辑距离★★☆☆☆★★★★☆
    夜深人静写算法(十四)- 0/1 背包★☆☆☆☆★★★★☆
    夜深人静写算法(十五)- 完全背包★★☆☆☆★★★★☆
    夜深人静写算法(十六)- 多重背包★★☆☆☆★★★★☆
    夜深人静写算法(二十七)- 区间DP★★★☆☆★★★★☆
    夜深人静写算法(二十九)- 数位DP★★★☆☆★★★★★
    夜深人静写算法(十七)- 分组背包★★★☆☆★★★☆☆
    夜深人静写算法(十八)- 依赖背包★★★★☆★★☆☆☆
    夜深人静写算法(六)- RMQ★★★☆☆★★☆☆☆
    树形DP待更新
    组合博弈待更新
    组合计数DP待更新
    四边形不等式待更新
    状态压缩DP/TSP待更新
    斜率优化的动态规划待更新
    插头DP待更新

    🪐2、强劲图论搜索


    1、深度优先搜索

    文章链接难度等级推荐阅读
    夜深人静写算法(一)- 搜索入门★☆☆☆☆★★★☆☆
    夜深人静写算法(八)- 二分图最大匹配★★☆☆☆★★☆☆☆
    最大团待更新
    最小生成树待更新
    树的分治待更新
    迭代加深 IDA*待更新
    有向图强连通分量和2-sat待更新
    无向图割边割点待更新
    带权图的二分图匹配待更新
    哈密尔顿回路待更新
    最近公共祖先待更新
    欧拉回路圈套圈待更新
    最小费用最大流待更新
    最小树形图待更新

    2、广度优先搜索

    文章链接难度等级推荐阅读
    夜深人静写算法(十)- 单向广搜★★☆☆☆★★★★☆
    夜深人静写算法(二十三)- 最短路★★★☆☆★★★★☆
    夜深人静写算法(二十五)- 稳定婚姻★★☆☆☆★★☆☆☆
    夜深人静写算法(二十四)- 最短路径树★★★☆☆★☆☆☆☆
    K 短路待更新
    差分约束待更新
    拓扑排序待更新
    A*待更新
    双向广搜待更新
    最大流 最小割待更新

    0️⃣3、进阶初等数论

    文章链接难度等级推荐阅读
    夜深人静写算法(三)- 初等数论入门★★☆☆☆★★★★☆
    夜深人静写算法(三十)- 二分快速幂★☆☆☆☆★★★★★
    夜深人静写算法(三十一)- 欧拉函数★★★☆☆★★★★★
    夜深人静写算法(三十二)- 费马小定理★★☆☆☆★★★☆☆
    夜深人静写算法(三十三)- 扩展欧拉定理★★★☆☆★★★★☆
    夜深人静写算法(三十四)- 逆元★★★☆☆★★★★☆
    夜深人静写算法(三十五)- RSA 加密解密★★★☆☆★★★★★
    夜深人静写算法(三十六)- 中国剩余定理★★☆☆☆★★★☆☆
    夜深人静写算法(三十七)- 威尔逊定理★★☆☆☆★★★☆☆
    夜深人静写算法(三十八)- 整数分块★★☆☆☆★★★★☆
    卢卡斯定理待更新
    狄利克雷卷积待更新
    莫比乌斯反演待更新
    容斥原理待更新
    拉宾米勒待更新
    Pollard rho待更新
    莫队待更新
    原根待更新
    大步小步算法待更新
    二次剩余待更新
    矩阵二分快速幂待更新
    Polya环形计数待更新

    🛑4、进阶计算几何

    📏5、字符串的匹配

    🎄6、高級数据结构


    🙉饭不食,水不饮,题必须刷🙉

    C语言免费动漫教程,和我一起打卡!
    🌞《光天化日学C语言》🌞

    LeetCode 太难?先看简单题!
    🧡《C语言入门100例》🧡

    数据结构难?不存在的!
    🌳《画解数据结构》🌳

    LeetCode 太简单?算法学起来!
    🌌《夜深人静写算法》🌌

    展开全文
  • 常见算法题代码c++ 常见算法题代码c++ 常见算法题代码c++ 常见算法题代码c++ 常见算法题代码c++ 常见算法题代码c++
  • 然而我是谁,我可是死狗中的战斗鸡,智力不够那刷题来凑,开始了夜以继日哼哧哼哧刷题的日子,从此"读与提交齐飞, AC 与 WA 一色 ",我惊喜的发现被虐既刺激又有快感,那一刻我泪流满面。这么好的事儿作为一个...

    遥想当年,机缘巧合入了 ACM 的坑,周边巨擘林立,从此过上了"天天被虐似死狗"的生活…


    在这里插入图片描述


    然而我是谁,我可是死狗中的战斗鸡,智力不够那刷题来凑,开始了夜以继日哼哧哼哧刷题的日子,从此"读题与提交齐飞, AC 与 WA 一色 ",我惊喜的发现被题虐既刺激又有快感,那一刻我泪流满面。这么好的事儿作为一个正直的人绝不能自己独享,经过激烈的颅内斗争,我决定把我私藏的十几个 T 的,阿不,十几个刷题网站放出来,让我们一起爽!

    刷题,是这个世界上最有意思的事儿!

    在这里插入图片描述


    当然刷题不能乱爽,你要知道刷题要干嘛,是找工作面试、研究生复试机试,是参加程序设计竞赛还是为了提高自己,在这里我将这些分为三类:收割 offer 版、ACM 竞赛版和提高版。



    0x00 收割 offer 版


    不管是找工作笔试面试白板试进大厂,还是研究生参加初试复试机试,数据结构和算法都是绕不过去的坎,刷题就成了很多人的需求,快来看看下面这些网站,变身刷题机器,收割 offer 吧!


    1、leetcode


    英文网址:https://leetcode.com/
    中文网址:https://leetcode-cn.com/


    估计 leetcode(力扣)大家都很熟悉了,都被推荐烂了,很多国内外的程序员在上面刷题,难度从 Easy、Medium 至 Hard 都有,据说很多面试官都会从中挑选各种题目,号称大厂的筛码工。


    我很早就知道 leetcode,但是直到准备复试闲来无事的时候才在它上面刷了点儿题找感觉,发现上面的题型覆盖很广,像线段树、滑动数组、博弈论、扫描线等都应有具有,但是好像有的测试数据有点弱?有的题好像可以悄咪咪的水过去…

    在这里插入图片描述


    当然题目都是英文的,现在也有了中文社区,两个网址我都放出来了,还是建议大家首刷英文的,锻炼一下,一举两得,毕竟如果是搞 ACM 的话,题目都是英文的…


    在这里插入图片描述


    2、hihoCoder


    网址:https://hihocoder.com


    网站的技术团队来自于原北大 POJ 的开发团队,至于 POJ 会在后面的篇章中介绍,反正膜拜就完事了。一些知名的大厂比如微软、百度、腾讯、网易等会在上面举办在线编程比赛,风格倒是和 ACM 比赛类似。


    如果仅止步于此还不至于让我推荐,当初与它的结缘是因为 hihoCoder 每周有周赛,每月有月赛。周赛是一道题,题目比较难但是极有意思,可以很好的拓宽自己的解题思路,月赛就更厉害了,题目均出自北大等一流高校玩 ACM 的菊苣出题,通过这个的检验可以迅速定位到自己真实的水平,同时了解自身在解决问题过程中的不足。


    这将是展示自我真实水平的绝佳机会。


    在这里插入图片描述


    3、牛客网


    网址:https://www.nowcoder.com/


    牛客网作为国内内容超级丰富的 IT 题库,各种东西看的我眼花缭乱,题库+面试+学习+求职+讨论 360 度无死角服务,堪称"互联网求职神器"。它好就好在不只是一个刷题的平台,还是一个交流学习的平台,发个问题贴总有热心的大佬帮助,别问我怎么知道,我才不要说我也给人回答过问题…


    说句题外话,我与牛客网的结缘还是因为…它上面有考研真题,我刷来着…


    在这里插入图片描述


    在这里插入图片描述


    4、计蒜客


    网址:https://www.jisuanke.com/


    计蒜客这个网站可能很多人不知道,他也有可以刷题的题库,也会定期举办比赛,当年和计蒜客有的交集也就是参加计蒜客举办的"计蒜之道"的线上比赛,还赢得过 T 恤,现在好像还在我家放着…


    这么多年还记得这个网站的原因,是因为当年在某乎上关注了他们的 CEO,然后竟然被反关,着实把当年的我惊着了…


    在这里插入图片描述


    0x01 ACM 竞赛版


    PS:虽然这一部分的标题为 ACM 竞赛版,也只是因为这些在学校搞 ACM 的同学用的比较多,实际上所有的人都可以在下面这些网站上刷题,题目的质量和广度都是顶呱呱的,男女老少咸宜。

    搞 ACM 的时候知道了很多 OJ(Online Judge),比如下图(当然实际的数量肯定远远多于图中所展示的这些):


    在这里插入图片描述


    5、HDU


    网址:http://acm.hdu.edu.cn/


    杭电(杭州电子科技大学)的 OJ 大概是国内最火的几个 OJ 之一了,大多数 ACMer 应该都知道(其实我想说所有来着),勿需多说,非常多比赛都在上面,比如每年暑假的多校联赛,朝鲜、外蒙等学校的队伍都会参加,想不知道都不可能。


    现在上面大概有接近 6k 的题量,网上有很多的刷题顺序,刷题指南,感兴趣的玩玩儿…


    在这里插入图片描述

    6、POJ


    网址:http://poj.org/


    这个就是我在介绍 hihocoder 的时候提到过的 POJ(Peking University Online Judge),同样作为国内最火的几大 OJ 之一,它的建立时间更早,一些上古时期的题目也能在上面找到,同样 POJ 也很出名,也是我最早刷题的 OJ 之一。


    现在上面有 3k+ 的题量,关于 POJ 的刷题指南网上更是很多,同样欢迎去玩儿…


    在这里插入图片描述


    7、SDUT


    网址:https://acm.sdut.edu.cn/


    这个是我打开次数最多,刷题次数最多的 OJ,是我刷题之路开始的地方 – 我本科母校 SDUT 的 OJ 平台。虽然我们学校不出名,但是我们集训队做东西是认真的,上面有接近 3k 的题量,并且在逐渐增多,简单题多一些,很适合刷题。


    欢迎大家注册,多多刷题,我们集训队多年一直秉持开放的态度,欢迎多多交流…


    在这里插入图片描述


    8、其它 OJ

    最后附带一些其它同样优秀的 OJ 平台:


    国内:

    ZJU(浙大): https://zoj.pintia.cn/home
    USTC(中科大):http://acm.ustc.edu.cn/ustcoj/
    FZU(福大):http://acm.fzu.edu.cn/
    HIT(哈工大):http://acm.hit.edu.cn/


    国外:

    URAL:http://acm.timus.ru/
    SPOJ:https://www.spoj.com/



    0x02 提高版


    这一部分推荐的网站,非常有意思,如果想提高自己,体验比赛的快感,非常建议尝试。

    9、Codeforces


    网址:https://codeforces.com/


    Codeforces 又被戏称为 CF,是一家俄罗斯的网站,当然还是用英文食用。这里的很好的比赛,很好的题目,很好的选手,简称"三好"。


    CF 最吸引人的地方在于它那超级牛批的比赛系统,CF 上每个用户都拥有 Rating,也就是比赛积分,新用户默认为 1500 分,每次比赛就会在你的积分上加加减减,上面的比赛一般分为四种:Div1、Div2、Div3、Educational Codeforces Round。Div 的比赛一般是根据积分来的,每个积分段只能参加对应的 Div 的比赛,Div1的比赛是里面最难的,大佬基本都在这里。Educational Codeforces Round 则是类似 ACM 的比赛,提交之后立马出结果。


    但是如果仅限这些也算不上超级,还有一个更有意思的是,CF 的比赛还提供一个 hack 功能,通俗点说就是你去看别人提交的代码,然后通过提交你想出的特殊测试用例然后找出别人代码的 bug,hack 成功则加积分,比赛更多了很多乐趣,在 hack 和反 hack 中斗智斗勇。


    不过对国内来说,和俄罗斯存在时差,一般想参加比赛的话大多数要在晚上 11 点以后,按照基础的 2 个小时比赛时间,再加上 hack 和测评反馈的过程,然后再刺激一下,差不多一宿就这么交待了,不过其中的乐趣不足为外人道。如果没有时间,上面的题目还是可以自己拿来做的,题目质量超级好,很能锻炼自己。


    在这里插入图片描述

    10、Topcoder


    网址:https://www.topcoder.com/


    Topcoder 据说是世界上规模最大的编程网站,如果这样的话那这个 Top 就可以理解了,Top 的 coder 丫,这个我基本上没用过,可能是因为我不 Top,只能仰望…


    想起它来的原因还是因为现在每次有比赛的时候都会给我发邮箱,搞得我想忘了它都不成…


    在这里插入图片描述



    0x03 写在之后


    虽然想写的尽量轻松些,不要让文章看起来太无聊,但在最后还是想认真的说一句:


    刷题不要单纯的为了追求做题的数量
    还是要以学会为目的
    并且学以致用

    希望大家永远记住你的目的是什么,关于如何刷题以后我会认真的再出篇文章,敬请期待!

    在这里插入图片描述

    另外本蒟蒻把公众号的高分原创文章整理成了一本电子书,取名《Python修炼之道》,一共 400 页!

    具体内容请戳:熬夜爆肝整理 400 页 《Python 修炼之道》,一本高分原创高清电子书送给你!

    目录如下:


    在这里插入图片描述

    现在免费送给大家,在我的公众号Python空间(微信搜 Devtogether) 回复 修炼之道即可获取。


    ❤️ 看完有所收获?希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~


    ❤️可以关注我的原创公众号:「Python空间」,更多优质的技术文章第一时间更新。最后送你新人大礼包一份,关注微信公众号,后台回复:“CSDN” 即可获取!

    作者Info:

    【作者】:Rocky0429
    【原创公众号】:Python空间。
    【简介】:CSDN 博客专家, 985 计算机在读研究生,ACM 退役狗 & 亚洲区域赛银奖划水选手。这是一个坚持原创的技术公众号,专注Python 编程,每天坚持推送各种 Python 基础/进阶文章,数据分析,爬虫实战,数据结构与算法,不定期分享各类资源。
    【转载说明】:转载请说明出处,谢谢合作!~

    展开全文
  • 经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题
  • 算法题 算法题

    2007-07-13 23:02:27
    算法题算法题算法题算法题
  • 算法 ,简单 入门 LeetCode网站开放的简单算法题,用于平时检验自己的算法能力,程序设计.
  • 当然是折腾一些算法题了,下面给大家讲几道一行代码就能解决的算法题,当然,我相信这些算法题你都做过,不过就算做过,也是可以看一看滴,毕竟,你当初大概率不是一行代码解决的。 学会了一行代码解决,以后遇到...

    春节假期这么长,干啥最好?当然是折腾一些算法题了,下面给大家讲几道一行代码就能解决的算法题,当然,我相信这些算法题你都做过,不过就算做过,也是可以看一看滴,毕竟,你当初大概率不是一行代码解决的。

    学会了一行代码解决,以后遇到面试官问起的话,就可以装逼了。

    一、2 的幂次方

    问题描述:判断一个整数 n 是否为 2 的幂次方

    对于这道题,常规操作是不断这把这个数除以 2,然后判断是否有余数,直到 n 被整除成 1 。

    我们可以把 n 拆成二进制看待处理的,如果 n 是 2 的幂次方的话,那么 n 的二进制数的最高位是 1,后面的都是 0,例如对于 16 这个数,它的二进制表示为 10000。

    如果我们把它减 1,则会导致最高位变成 0,其余全部变成 1,例如 10000 - 1 = 01111。

    然后我们把 n 和 (n - 1)进行操作,结果就会是 0,例如(假设 n 是 16)

    n & (n-1) = 10000 & (10000 - 1) = 10000 & 01111 = 0

    也就是说,n 如果是 2 的幂次方,则 n & (n-1) 的结果是 0,否则就不是,所以代码如下

    int isPow(n){
    	return (n & (n - 1)) == 0;
    }
    

    二、一行代码搞定经典的约瑟夫环

    约瑟夫环问题,我相信大家在大一大二的时候就接触过了,很多人也都会拿来作为环形链表的一个应用,然而环形链表并非最优的解决方法,今天我就用一行代码干掉它,并且几乎算是最优解了。

    鉴于有些人把这道题忘了,我还是把这道题的描述贴出来一下吧

    问题描述:编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈,从编号为 1 的士兵开始依次报数(1,2,3…这样依次报),数到 m 的 士兵会被杀死出列,之后的士兵再从 1 开始报数。直到最后剩下一士兵,求这个士兵的编号。

    先给出代码,后面在解释。

    int f(int n, int m){
        return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
    }
    

    原理是这样的:

    如果我们把士兵删除后,重新给这些士兵编号的话,那么删除前和删除后,这些编号存在某种数学关系,我们只需要找出这个关系即可。

    我们定义递归函数 f(n,m) 的返回结果是存活士兵的编号,显然当 n = 1 时,f(n, m) = 1。假如我们能够找出 f(n,m) 和 f(n-1,m) 之间的关系的话,我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为


    1

    m - 2

    m - 1

    m

    m + 1

    m + 2

    n

    进行了一次删除之后,删除了编号为 m 的节点。删除之后,就只剩下 n - 1 个节点了,删除前和删除之后的编号转换关系为:

    删除前 — 删除后

    … — …

    m - 2 — n - 2

    m - 1 — n - 1

    m ---- 无(因为编号被删除了)

    m + 1 — 1(因为下次就从这里报数了)

    m + 2 ---- 2

    … ---- …

    新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1, 2, 3 的节点。

    假设 old 为删除之前的节点编号, new 为删除了一个节点之后的编号,则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

    这样,我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了,而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下:

    注:有些人可能会疑惑为什么不是 old = (new + m ) % n 呢?主要是因为编号是从 1 开始的,而不是从 0 开始的。如果 new + m == n的话,会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

    int f(int n, int m){
        if(n == 1)   return n;
        return (f(n - 1, m) + m - 1) % n + 1;
    }
    

    怎么不是一行而是两行?如果你经常刷题,那肯定希望自己的代码看起来越短越简介越好,至于会不会变的更难理解?我懒的理,所以代码如下

    int f(int n, int m){
        return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
    }
    

    当然,我之前写过一篇文章,用了三种方法来解决约瑟夫环,感兴趣的也可以看:记一道阿里笔试题:我是如何用一行代码解决约瑟夫环问题的

    只出现一次是数

    问题描述:给你一个整型数组,数组中有一个数只出现过一次,其他数都出现了两次,求这个只出现了一次的数。

    这道题可能很多人会用一个哈希表来存储,每次存储的时候,记录 某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为 O(n),空间复杂度也为 O(n)了。

    然而这道题其实可以采用异或运算来解决,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,并且异或运算支持交换律,基于这个特点,我们只需要把这一组整型全部异或一下,最后的结果就是我们要找的数了。

    例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下:

    由于异或支持交换律和结合律,所以:

    123451234 = (11)(22)(33)(44)5= 00005 = 5。

    通过这种方法,可以把空间复杂度降低到 O(1),而时间复杂度不变,相应的代码如下

    int find(int[] arr){
        int tmp = arr[0];
        for(int i = 1;i < arr.length; i++){
            tmp = tmp ^ arr[i];
        }
        return tmp;
    }
    

    说好的一行代码的呢?

    这不是为了先让你看的懂吗?一行代码解决方案如下:

    // 例如使用这个函数的时候,我们最开始传给 i 的值是 1,传给 result 的是 arr[0]
    //例如 find(arr, 1, arr[0])
    int find(int[] arr,int i, int result){
    	return arr.length <= i ? result : find(arr, i + 1, result ^ arr[i]);
    }
    

    实不相瞒,这道题用了一行代码之后,更加复杂 + 难懂了,,,,,,不好意思,我错了,不该把简单的问题搞复杂了再扔给面试题的。

    四、n 的阶乘

    问题描述:给定一个整数 N,那么 N 的阶乘 N! 末尾有多少个 0?例如: N = 10,则 N!= 3628800,那么 N! 的末尾有两个0。

    我先给出个代码让大家品尝一下,在细细讲解

    int f(n){
    	return n == 0 ? 0 : n / 5 + f(n / 5);
    }
    

    对于这道题,常规操作是直接算 N!的值再来除以 10 判断多少个 0 ,然而这样肯定会出现溢出问题,并且时间复杂度还大,我们不妨从另一个思路下手:一个数乘以 10 就一定会在末尾产生一个零,那么,我们是否可以从哪些数相乘能够得到 10 入手呢?

    答是可以的,并且只有 2 * 5 才会产生 10。

    注意,4 * 5 = 20 也能产生 0 啊,不过我们也可以把 20 进行分解啊,20 = 10 * 2。

    于是,问题转化为 N! 种能够分解成多少对 2*5,再一步分析会发现,在 N!中能够被 2 整除的数一定比能够被 5 整除的数多,于是问题近似转化为求 1…n 这 n 个数中能够被 5 整除的数有多少个

    注意,像 25 能够被 5整除两次,所以25是能够产生 2 对 2 * 5滴。有了这个思路,代码如下:

    int f(int n){
        int sum = 0;
        for(int i = 1; i <= n; i++){
            int j = i;
            while(j % 5 == 0){
                sum++;
                j = j / 5;
            }
        }
        return sum;
    }
    

    然而进一步拆解,我们发现

    当 N = 20 时,1~20 可以产生几个 5 ?答是 4 个,此时有 N / 5 = 4。

    当 N = 24 时,1~24 可以产生几个 5 ?答是 4 个,此时有 N / 5 = 4。

    当 N = 25 时,1~25 可以产生几个 5?答是 6 个,主要是因为 25 贡献了两个 5,此时有 N / 5 + N / 5^2 = 6。

    可以发现 产生 5 的个数为 sum = N/5 + N/5^2 + N/5^3+….

    于是,一行代码就可以搞定它了

    int f(n){
    	return n == 0 ? 0 : n / 5 + f(n / 5);
    }
    

    总结

    有木觉得很牛逼?以后面试官问你这些题,你就把这行代码扔给他!!!

    当然,想要一直保持牛逼,还得多看一些算法书,我也有整理了一些
    在这里插入图片描述

    在此贡献给大家,都是一些值得看的算法书

    大家可以在我的公众号『帅地玩编程』获取『我要学算法』获取下载链接。

    老铁,要不点个赞再走可好?么么哒

    1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    2、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。

    保存让你看完有所收获,不信你打我。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书。

    作者简洁

    作者:大家好,我是帅地,从大学、校招一路走来,深知算法计算机基础知识的重要性,所以申请了一个微星公众号『帅地玩编程』,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习。 转载说明:未获得授权,禁止转载

    展开全文
  • 算法刷到最后,最后记在脑子里的不是代码,是思路,如果你有思路,那你一定能把代码写出来,你不可能记住所有的代码,唯一可以记住的是解题思路,所以怎么码代码不是一个问题,怎么解题才是一个问题,建议刷题的...

    作者 | Rocky0429
    来源 | Python空间


    大家好,我是 Rocky0429,一个曾经在 ACM 界划水多年的蒟蒻


    在“刷了几千道算法题,这些我私藏的刷题网站都在这里了!”这篇文章中,我有说过要写一篇如何刷题的文章,然而好几个月过去了,我实在没法舔着脸继续拖下去了…


    所以,我来交作业了…


    在这里插入图片描述

    我好多次在想要如何写这篇文章,试图去回想我刷题的时光,当时的种种感觉拼接起来,一次次动笔,又一次次的放弃。


    其实诸多纠结,我试图遵循常规,将这种刷题经验公式化,列个一二三四,期间穿插一些算法题来 give an example,这样好像才是真正像是经验的样子,但我总觉的哪里奇怪。


    我问自己,当年还是个小白,对刷题一无所知的我是否想要去看这样的文章,我想答案应该是不会…


    在这里插入图片描述

    所以这篇文章我可能会写成自己想写的样子,它不会教你速成,没有捷径,单纯是一个当年机缘巧合入了 ACM 的混子,有一段很长的(三年)连续刷题的时间,恰好有一点自己感想的碎碎念。


    以下仅代表个人想法…


    在这里插入图片描述


    很多人开始他的刷题之路因为各种各样的原因:进大厂、研究生复试或者参加竞赛拿牌,当然也可能是因为喜欢。其实不管你抱着何种目的开始,我希望你能一直在刷题这条路上走下去,毕竟除了提高自己解决问题和写代码的能力这种显而易见的好处,也能当作无聊时候的一种消遣…


    在这里插入图片描述


    其实随着刷题的深入,我发现刷题其实就是分为两步,第一步有思路,即知道用哪种姿势怎么解题;第二步是实现,即将你的思路转化为代码。接下来我所有的废话都是围绕这两步来展开。


    在这里插入图片描述



    0x01 有思路


    先说第一步:有思路。


    算法题刷多了,你就会发现,最后其实在你脑子里记住的不是实现这道题的代码,而是解这道题的思路。


    当我们刷了几百道几千道算法题的时候,你不可能记住每道题的代码,但是你可能知道这道题的思路,也就是出现类似“这道题我见过,我知道用这样那样的方法可以做出来”。有了思路,其实把它实现出来就是自然而然的事儿了,当然可能有人说知道了思路也不知道怎么实现,现在我先不说,这是我们下一步要讲的问题。


    在这里插入图片描述


    上面说的是我们要走到的目的地,那如何走上这条路,从而到刷题刷到思路“泉涌”呢?其实很简单,我们从小到大一直在被动习惯的四个字:题海战术。


    在这里插入图片描述


    题海战术,说白了就是多刷题,见多才能识广。


    但这里的多刷题,不是指多瞎刷题,而是有方法的去刷。至于刷题的网站我已经在文章的开头放链接了,不知道去哪找题的可以看一下。


    首先说什么是瞎刷题,就是看到一道刷一道,这是很多刚开始刷题的同学容易犯的毛病。


    有的追求数量,刷了一堆简单题,沉迷在 AC 的快感中不能自拔,在深深的自我感动中依然菜的扣脚;

    有的追求无脑,看到一道题就去网上搜答案,以为会解决问题,实则搜到了还看不懂,正好一劳永逸,给自己下了不是这块料的断言,成功的做到了开始即结束。


    别问我为什么知道,我才不会告诉你当年我就是这样…


    在这里插入图片描述


    其实怎么用正确的题海战术,在我看来,其实也还是两步,第一步多题一解,第二步一题多解。


    当然在此之前,我觉得你得先搞明白什么是时间复杂度和空间复杂度,不然不懂这些指标,你也不知道算法对于你当前题目的优劣。之前写过一篇旧文,有兴趣的可以看一下。


    循序渐进带你学习时间复杂度和空间复杂度。


    0x01-1 多题一解


    多题一解,就是把多种同类型的题先放在一起来做,也就是俗称的刷专题。下面是我当年刷题的一部分分类的截图:

    在这里插入图片描述
    在这里插入图片描述


    很多大佬说做题要追求完美,一道题来 N 种姿势,但是对于刚开始起步的同学来说,一道题带着多解的思想包袱去刷,本身就是一种负担。你很难指望初学者能一上来就一题多解,没那么多见识,脑阔里没储备那么多的算法类型,能够暴力破解且跑通就已经是烧高香了。


    在这里插入图片描述


    这里再多提一嘴,关于网上搜答案这件事,答案可以搜,但是不要上来一看题,感觉自己不会就立马搜答案,要尝试思考,多在草稿纸上写写画画,实在想不出来再去搜。


    在这里插入图片描述


    搜到的答案我不希望你去看别人的代码,按照别人的代码一步步的写出来其实本身没有多大意义,真正有意义的是别人的思路,通过别人的思路来自己实现出现,这才是最应该做的。


    这样做的好处是,你可以很快了解一种类型题目的做题方法,加深对某类算法的理解,总结出做题的套路,这算是一种抽象的概括能力。很多时候你就会发现,题目不过是在某类解决办法方面做加法减法。


    在这里插入图片描述



    0x01-2 一题多解


    其实这个不用刻意去追求一题多解的能力,刷的专题多了,碰到的题目多了,自然而然你碰到一道题的时候脑袋里就会有想法,觉的可以这样做,也可以那样做,这个时候你就可以对比不同的时间复杂度和空间复杂度,选择当前的最优解法。


    说一题多解,其实就是希望你在碰到一个问题的时候能够多想一步,一步一步再一步,不同维度不同姿势都尝试一下。刚开始这可能比较难,毕竟这涉及到一个改变,因为人都是有惰性的,毕竟只求一解比自找麻烦的求多解舒服多了…


    在这里插入图片描述


    题目见的多了你就会发现,很多时候你会碰到这种情况:A 题你有 5 种方法去解决它,改变它的某一个条件变成 B 题,作为 A 题的相似题 B,可能这个时候你照搬 A 的解法来解决 B,你只剩下 3 种或者更少的解法可以解决 B 题,如果你只会 1 种解法,刚好这种解法失效,那你就只能再另想它法。


    所以一题多解的好处也是显而易见的,就相当于你的手里多了很多的选项,选项多了不管你在面试或是其它时候,都能手里有牌可打。


    在这里插入图片描述


    在这里我又要多提一嘴,追求一题多解并不意味着“不择手段”的追求题解数量的堆叠,也就是不要过分追求所谓奇淫技巧的解法,而这恰恰是许多同学容易犯的毛病,错误的认为了奇淫技巧等于水平高超,在我看来这个除了能引来别人一句卧槽的惊讶,从而带来一点内心虚荣心的满足以外,其余的用处不大,看个热闹就得了。毕竟鲁迅先生曾经说过:“Use your best judgement”。


    在这里插入图片描述


    当然我也不是全盘否定技巧,但是你连个两三百道题都没刷完,你就在这给我讲你要技巧,我会认为你是在耍流氓…



    0x02 实现


    一道题有了思路,其实这道题的 90% 你已经解决了,把它实现出来按理来说就是自然而然的事儿了。


    在这里插入图片描述


    当然可能有同学知道了思路,但是就卡在这 10% 不知道怎么实现上,那这就是你写代码的能力问题,其实一样的,这就是不熟练,不熟练的原因就是练少了。


    其实这个问题的唯一解还是所谓的“题海战术”,多练习,唯手熟尔。


    在这里插入图片描述


    刚开始的时候不管是书上的例题,一些简单的水题或者你想实现的一个简单的东西,按照你的想法写出来或者看一遍别人怎么写的,自己再一步一步的默敲,不要怕麻烦,一定要自己动手,不要看会了,我们都知道看会了其实不是真正的会。但是慢慢当你习惯了这种方式,你的代码能力会潜移默化的变强。


    在这里插入图片描述


    别问我为什么知道,我难道要说作为一个当年上了大学半年还没写过一次超过 20 行的代码的男人,经过一个寒假以后,能切百十行代码的题?


    也太丢面儿了吧,说好的整个学霸人设呢…


    在这里插入图片描述



    0x03 第三步


    咦?不是只有两步嘛,哪来的第三步?


    嘿嘿,总得给能坚持看我说废话看到这里的同学开个小小灶不是…


    在这里插入图片描述

    其实还有两点是我想说的,而且这两点是我觉得在整个过程中最重要的。


    0x03-1 做总结


    怎么说呢,做总结这件事的好处,谁做谁知道,不信你就试试…


    在这里插入图片描述


    每道题有每道题的总结,每种类型的题有某类题的总结,千万不要怕麻烦,虽然刚开始的时候确实会很麻烦…


    每每回想起来,我最后悔的就是在我刚开始刷题的时候没有做总结。当年集训队老师告诉我们每道题做完都要把题解发布到 CSDN 上,记录自己的思路,解题方式和代码。这件事乍一听我觉得太麻烦,觉得“有这个时间我多刷道题它不香嘛”,一直当作耳旁风。


    在这里插入图片描述


    后来真正开始在 CSDN 上发题解,并不是我突然顿悟,而是集训队老师看我们太懒,强制执行,然而这个强制,在经过初期的不适以后,慢慢的让我形成了做什么都要总结记录的习惯,一下子就写了 6 年。下面是刚开始的一些截图:


    在这里插入图片描述


    习惯性梳理总结,在这个过程中重新产生更多的认识,理解更深,有更多的想法,无论后来成为 CSDN 的博客专家(Rocky0429)或者后来开始写公众号(Python空间,id:Devtogether),都是因为这种积累,我因此而获益,对我们老师感激一生。


    0x03-2 保持热情


    保持热情,不仅仅是能坚持,而要在坚持上最好能带有一点兴趣。刷题真的是一个很漫长的过程,如何在这个过程中能坚持下去真的很难做到…


    在这里插入图片描述


    我觉得你最好有一个最终的目标,这个很多开始刷题的同学肯定都有,不然没人闲着没事找事去刷题,有了最终的目标朝着这个方向去努力,同时把这个过程分成一部分一部分,比如拿刷专题来说,我这段时间刷链表,下段时间刷贪心,再下段时间刷 dp…


    将目标量化为可衡量的每一段,自己有了掌控感,一步一步的向着最终的目标前进,知道自己离着还有多远,不至于半途而废。


    拿我自己来说,当年搞 ACM,半年以后我已经准备放弃了,那段时间完全迷茫,觉得自己水平很差,没有机会去参加比赛,不可能拿到奖牌。那段时间我开始去寻找别的出路,去参加 Python 的社团,准备转去做项目。


    浑浑噩噩了一圈,最后还是回去做 ACM,一方面是不想让自己半年的努力付诸东流,对拿牌子的执念,更多的是我发现坐在那写项目和做题比起来,我更喜欢 AC 的快感。


    在这里插入图片描述



    0x04 写在之后


    以上就是我的一点点经验,其实没有什么新鲜的,有点啰嗦,也不一定能让你有什么进步。我一直觉的只要我们付出了时间和努力,开始向更好的方向迈出第一步,我们解决问题和写代码的能力就会潜移默化的提高。


    在这个过程中,收获的远比去解决问题更有成就感,当然这种感同身受更多的需要你自己在这个过程中去体验。


    可能末了整篇文章最有价值的只有四个字 - 题海战术。


    希望你在变好的路上越走越远…


    在这里插入图片描述


    另外本蒟蒻把公众号的高分原创文章整理成了一本电子书,取名《Python修炼之道》,一共 400 页!

    具体内容请戳:熬夜爆肝整理 400 页 《Python 修炼之道》,一本高分原创高清电子书送给你!

    目录如下:


    在这里插入图片描述

    现在免费送给大家,在我的公众号Python空间(微信搜 Devtogether) 回复 修炼之道即可获取。



    作者Info:

    【作者】:Rocky0429
    【原创公众号】:Python空间。
    【简介】:CSDN 博客专家, 985 计算机在读研究生,ACM 退役狗 & 亚洲区域赛银奖划水选手。这是一个坚持原创的技术公众号,每天坚持推送各种 Python 基础/进阶文章,数据分析,爬虫实战,数据结构与算法,不定期分享各类资源。
    【福利】:送你新人大礼包一份,关注微信公众号,后台回复:“CSDN” 即可获取!
    【转载说明】:转载请说明出处,谢谢合作!~

    展开全文
  • 程序员算法题汇总

    2017-05-27 10:09:24
    PHP程序员算法题汇总,经典算法题仅供学习研究。
  • 面试算法题总结
  • 算法题的五种解法

    万次阅读 2021-04-15 21:46:11
  • 面试常见的js算法题

    2020-10-20 03:41:10
    本文主要介绍了面试常见的js算法题。具有很好的参考价值。下面跟着小编一起来看下吧
  • 面试常见算法题

    2018-05-17 17:20:12
    这是在面试中遇到的一些常见算法题,笔试面试经常遇到,所以总结了一下,方面以后查看,分享给大家。
  • leetcode算法题答案PDF

    2016-10-14 22:53:10
    leetcode算法题的答案PDF,C++编写的,有详细的算法逻辑分析。
  • java算法题(五)

    2009-10-12 10:14:35
    java算法题java算法题java算法题java算法题java算法题java算法题java算法题java算法题java算法题java算法题
  • 目前 需要去面试 据说面试前需要做一道算法题 所以搜集了一些leetcode的算法题共享
  • ------------------------------------------------------------- 经典算法题:大数据处理常见算法题 --------------------------------------------------------------
  • java算法题(四)

    2009-10-12 10:13:20
    java算法题 java算法题 java算法题 java算法题java算法题
  • 用Java刷算法题的常用API一览,适用于准备求职时刷leetcode、lintcode等算法题,或面试白板编程。
  • java算法题(七)

    2009-10-12 10:17:15
    java算法题java算法题java算法题java算法题
  • java算法题(六)

    2009-10-12 10:16:06
    java算法题java算法题java算法题java算法题
  • Android面试算法题

    2012-03-12 18:06:40
    该资源为Android开发工程师面试算法题,为基础知识具备比较好的人提供。
  • java算法题(三)

    2009-10-12 10:12:34
    很不错的java算法题 很不错的java算法题 很不错的java算法题 很不错的java算法题 很不错的java算法题
  • Leetcode算法题之数组(简单)

    万次阅读 2020-04-10 16:37:26
    这篇博客主要记录自己LeetCode上面做过的数组相关的算法题。当然,目前为止,我做过的算法题不是很多。因此,这篇文章我主要记录简单的算法题。后面也会有专门的文章去记录中等难度的算法题。当然,可能目前而言,我...
  • java算法题(二)

    2009-10-12 10:11:25
    共有7个 很不错的java算法题 共有7个 很不错的java算法题 共有7个 很不错的java算法题 共有7个 很不错的java算法题 共有7个 很不错的java算法题 共有7个 很不错的java算法题
  • 电梯算法题

    千次阅读 2016-11-08 09:46:18
    电梯算法题:  高志大厦因等电梯人数太多,现规定电梯上升只能停一层,大家下电梯再各个步行到自己楼层,求停哪一层所有人步行层数总和最少。input: int[] floorPersonCount = [ 0, 0, 2, 5, 3, 0 ]; //各楼层...
  • 字节跳动算法题

    千次阅读 2019-08-31 10:10:04
    前几天有个朋友去面试字节跳动,面试官问了他一道链表相关的算法题,不过他一时之间没做出来,就来问了我一下,感觉这道题还不错,拿来讲一讲。 题目 这其实是一道变形的链表反转题,大致描述如下 给定一个单链表的...
  • ACM国际大学生软件大赛,主要是考的些算法题,一些相关的软件比赛都是考的算法题,这些题目可以看看
  • 收藏!90 个名企笔试题 + 算法题

    万次阅读 多人点赞 2018-01-14 00:00:00
    (点击上方公众号,可快速关注)节选自「算法爱好者」微信公号的精选算法题和名企笔试题。长按上图,弹出“识别二维码”后关注提示:点击下方目录,即可查看题目详情,并查看网友的讨论交流。名企笔试名企笔试:美团...
  • 一道广联达秋招算法题

    千次阅读 2020-07-22 21:33:52
    今天下午师兄在教研室群里发了一道热乎的广联达算法题,乍一看完全没有思路,于是实验室的小伙伴们饶有兴致地开始讨论起了这道题。 先给大家看一下题目: 题目描述 有一种排序算法定义如下,该排序算法每次把一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 754,616
精华内容 301,846
关键字:

算法题