请选择 进入手机版 | 继续访问电脑版

马悦凌健康养生网-马悦凌粉丝乐园-马悦凌博客专注-爱久养身园专注各种中医养生知识

搜索
热门搜索: 健康 瑜伽 养生
 找回密码
 立即注册
热图推荐
  • 亲民双门跑车,起步301马力+8AT,5.7秒破百
  • 专家称,房价下跌也不一定是好事,难道说是
  • 为什么猫在7楼左右跳下最危险,而超过7楼反
  • 瑜伽中,为什么做反祈祷式双手无法合十?肩
  • 怎么不按套路出牌呢!你这是亲脚毁了教练的
  • 小小一枚,孩子喉管被腐蚀!再说一遍,这些
  • 上课溜号,小动作多,过度活跃,很聪明但成
  • 丁彦雨航伤了!以这种方式受伤,在篮球比赛
  • 什么叫Shell Cordovan呢?马臀皮鞋子,牛仔
  • 最新数据!做不到这3件事,9400多万人可能
查看: 950|回复: 0

君生我未生全文 程序员如何学好算法? 超级大蟒蛇

[复制链接]

1359

主题

3692

帖子

5695

积分

论坛元老

Rank: 8Rank: 8

积分
5695
发表于 2019-7-11 23:25 | 显示全部楼层 |阅读模式


王国维师长在《人世词话》中写道:古今之成大奇迹、大学问者,必经过三种境界:“昨夜西风凋碧树。独上高楼,望尽天涯路!贝说谝痪骋!耙麓タ碇詹换,为伊消得人憔悴!贝说诙骋!爸诶镅八О俣,蓦地回首,那人却在,灯火衰退处!贝说谌骋。算法的进修之道也是如此。


<h1 class="ql-align-center">夯实根底

在最初的阶段,算法天下的大门刚刚翻开,这个时辰苍茫是一般的,处理苍茫的要诀在于少想多做,勇往直前。怀着一颗"千磨万击还坚固,任尔工具南北风"的恒心,爬上算法的高楼,做到"望尽天涯路"。
从一个算法萌新入门,第一步便在于打牢根底。保举阅念书籍:
1.《算法第 4 版》- Robert Sedgewick
2.《鬼话数据结构》- 程杰
3.《算法图解》- Aditya Bhargava
4.《算法导论》- Cormen,T.H.
《算法第 4 版》合适初学者入门、《鬼话数据结构》和《算法图解》这两本书的特点是风趣、易了解,也很是合适初学者!端惴ǖ悸邸返奶氐闶侵苋,它是一本算法的百科全书,侧重在于坦荡算法视野,合适有一定算法根本后再去进修。
入门阶段是看一些天赋的,花费时候一视同仁,大约在 3~6 月之间,将上述提到的书籍挑选其中一本看完根基就能入门了。在这个阶段中,需方法会几类常用的算法:


其中,暴力列举、贪心算法轻易了解,可以很快上手。数论相关的算法需要用到一些数学技能,包括位运算、幂函数、求模等等性质。二分算法和深度优先搜索算法相对有些技能性,幸亏他们都有牢固的模板。别的,不能不提的是,深度优先搜索算法的思惟很是重要,而且深度优先搜索是静态计划、分治和回溯的基,需要重点把握。
在此进程中,可以辅以力扣(LeetCode)中的简单题目,它们常常都代表了一类典范算法,如:
70. 爬楼梯
假定你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有几多种分歧的方式可以爬到楼顶呢?
静态计划 算法的典范题目,经过此题目可以领会状态、鸿沟条件、状态转移方程等根基概念。
112. 途径总和
给定一个二叉树和一个方针和,判定该树中能否存在根节点到叶子节点的途径,这条途径上一切节点值相加即是方针和。
深度优先算法 的入门题目,递归实现和迭代实现都不难,可以进修到深度优先算法的层层嵌套搜索、找到答案或到达鸿沟停止的根基解题思绪。
35. 搜索插入位置
给定一个排序数组和一个方针值,在数组中找到方针值,并返回其索引。假如方针值不存在于数组中,返回它将会被按顺序插入的位置。
二分算法 的典型题目,利用二分算法的解题模板可以轻松处理,二分算法的算法思惟清楚明白,一通百通。
169. 求众数
给定一个巨细为 n 的数组,找到其中的众数。众数是指在数组中出现次数 大于 ? n/2 ? 的元素。你可以假定数组是非空的,而且给定的数组总是存在众数。
分治算法 的简单题目,假如我们晓得数组左侧一半和右侧一半的众数,我们便可以用线性时候晓得全局的众数是哪个。这道题妙就妙在可以有多种解题方式,让初学者最少可以写出暴力列举算法 AC 题目,然后再慢慢深入,优化算法。
944. 删列造序
给定由 N 个小写字母字符串组成的数组 A,其中每个字符串长度相称。拔取一个删除索引序列,对于 A 中的每个字符串,删除对应每个索引处的字符。所余下的字符串行从上往下读构成列。假定,我们挑选了一组删除索引 D,那末在履行删除操纵以后,A 中所残剩的每一列都必须是 非降序 排列的,然后请你返回 D.length 的最小能够值。
这是一道 贪心算法 的简单题目,贪心算法了解简单,上手轻易,合适作为初学者把握的第一个算法。






<h1 class="ql-align-center">交融贯通

进修算法理论如同阅读了一本武功秘籍,但是仅仅把握理论是不够的,接下来就要进入到现实练习阶段。
实战练习很是重要,不经过实战练习,理论仅仅是纸上谈兵。比如,不经过大量练习,永久不会晓得二分算法是何等轻易出现死循环。一个鸿沟条件控制欠好,法式就会显现无情的"Time Limit Exceeded"。在 20 分钟的调试后,也许仅仅是将 while (left <= right) 改成了 while (left < right) 。法式员说到底也是技术人,这一个字符的修改,正是"台上一分钟,台下十年功"的表现,需要在大量的练习中才能了解两者之间的分歧感化。
再比如,静态计划算法中,递归的函数就像是《盗梦空间》中的"梦中梦",一层套一层,又渐次展开,很难整体把控。在不竭的练习后,才会晓得,静态计划算法的重点是捉住静态转移方程,只处置两个状态之间的过渡和鸿沟条件,渐渐"大事化,小事化了"。


这一阶段花费的时候将会很长很长,陪伴着不竭地跌倒、爬起,你会对每类算法逐步交融贯通。幸亏这一阶段是不看天赋只看勤恳的,每次从坑里爬起,都是献给长大的一份气力。
保举的进阶书籍有《编程珠玑》,本书探讨了法式设想职员面临一系列的现实题目以及处理题目标办法(处理计划的代码以 C/C++ 说话编写)。书中拔取了很多具有典型意义的复杂编程和算法题目,并论述和总结了很多怪异精巧的设想原则、思考息争决题目标方式以及适用的法式设想技能。
在这个阶段,可以尝试练习力扣上的中等题目,中等题目根基上也只会利用一种算法,加上一些特别的限制,比如让你在进修了直拳的理论后衍生出左勾拳和右勾拳。保举练习题目有:
1048. 最长字符串链
给出一个单词列表,其中每个单词都由小写英笔墨母组成。假如我们可以在 word1 的任何地方增加一个字母使其酿成 word2,那末我们以为 word1 是 word2 的前身。例如,"abc" 是 "abac" 的前身。词链是单词 [word_1, word_2, ..., word_k] 组成的序列,k >= 1,其中 word_1 是 word_2 的前身,word_2 是 word_3 的前身,依此类推。从给定单词列表 words 当挑选单词组成词链,返回词链的最长能够长度。
分析题目可知,要求出答案必须遍历一切能够的词链,静态计划算法在其中起备忘录的感化,用于记录已经算过的答案,削减计较次数。
47. 全排列 II
给定一个可包括反复数字的序列,返回一切不反复的全排列。
这道题是 46. 全排列 的增强版,全排列 I 的题目是:
给定一个 没有反复 数字的序列,返回其一切能够的全排列。(利用深度优先搜索算法即可处理。)
本题在其根本上增强了难度,有两种方式可解。第一种方式最简单,间接用全排列 I 的答案去重即可,第二种方式是先将数组排序,全排列时碰到反复数字则跳过,这样的剪枝优化可以削减遍历次数,进步算法效力。
40. 组合总和 II
给定一个数组 candidates 和一个方针数 target ,找出 candidates 中一切可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能利用一次。
深度优先搜索算法衍生出来的 回溯算法,一样用到 47 题的剪枝优化思惟:不异数字只答应递归第一个。
89. 格雷编码
格雷编码是一个二进制数字系统,在该系统中,两个持续的数值唯一一个位数的差别。给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开首。
静态计划 算法的现实利用之一。
79. 单词搜索
给定一个二维网格和一个单词,找出该单词能否存在于网格中。单词必须依照字母顺序,经过相邻的单元格内的字母组成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不答应被反复利用。
深度优先搜索 的中级利用,利用零丁数组标志已利用过的元素,这也是 DFS 中较为常见的做法,难点在于将标志数组复原的机会,需要频频练习,熟练把握。
当你把每一类算法的中等题目刷起来驾轻就熟时,无妨起头尝试困困难目标练习。困困难目总是融合两种或两种以上算法,或是加深难度的典范算法,如二维甚至三维静态计划。练习困困难目比如同时用上左勾拳和扫堂腿,不但让思维畅快淋漓,在每次 AC 以后还会带来无与伦比的成就感。保举练习题目有:
679. 24 点游戏
你有 4 张写有 1 到 9 数字的牌。你需要判定能否能经过 *,/,+,-,(,)的运算获得 24。
只要 4 张牌,且只能履行 4 种操纵。即使一切运算符都不停止交换,最多也只要 12 * 6 * 2 * 4 * 4 * 4 = 9216 种能够性,这使得我们可以尝试一切这些能够,假如用深度优先搜索算法例需要费一番功夫。
124. 二叉树中的最亨衢径和
给定一个 非空 二叉树,返回其最亨衢径和。本题中,途径被界说为一条从树中肆意节点动身,到达肆意节点的序列。该途径 最少包括一个 节点,且纷歧定经过根节点。
首先,斟酌实现一个简化的函数:计较每个节点及其子树对途径和的最大进献。再斟酌第二点:最亨衢径纷歧定包括根节点。这意味着我们在每一步都检查哪类挑选更好:是继续当前途径大概以当前节点作为最高节点计较新的途径。
410. 朋分数组的最大值
给定一个非负整数数组和一个整数 m,你需要将这个数组分红 m 个非空的持续子数组。设想一个算法使得这 m 个子数组各自和的最大值最小。
二分算法 贪心算法 的综合练习,仔细分析可知其单调关系:数组和的最大值越,分组数越大。而且数组和的范围是可以肯定的。按照此特征,可以将题目转换为:当子数组的和最大为 maxSum 时,最少需要分几多组,能否在最多 m 组的限制范围内完成份割。在每次朋分时,采用贪心战略,尽能够多的放置元素,直到一组放不下,再另起一组。假如满足朋分条件,记录当前值,操纵二分法,缩小子数组总和。否则扩大子数组总和,直到找到最好答案。






<h1 class="ql-align-center">推陈出新

究竟上,大量法式员逗留在第二重境界就没法再进一步。当提到某一类算法时,你可以说:"我晓得"、"我会用"、"踩过坑",但能说出"我完全了解其思惟"、甚至"我能想法子改良"的人却很少很少。这一步恍如武学中的攻守之道,当你把握到这一层,即可不再拘泥于一刀一!⒁徽幸皇,如金书中所说:飞花摘叶皆可伤人、草木竹石都可为剑。
开创算法的进程是艰难又孤独的。每一个典范算法的诞生都陪伴着"一将功成万骨枯"。比如现在我们在很多说话中都可以间接挪用 Collection.sort() 实现快速排序,而在快速排序算法出现之前,曾有一段时候唯一冒泡、挑选、插入三种排序算法。直到 1959 年,希尔提出"希尔排序"算法,也许现在晓得此算法的人已经很少了。但它是首个冲破 O(n^2)复杂度的排序算法,它的根基算法思惟以下:
挑选一个增量序列 t1,t2,…,tk,其中 ti > tj, tk = 1;按增量序列个数 k,对序列停止 k 趟排序;每趟排序,按照对应的增量ti,将待排序列朋分红多少长度为 m 的子序列,别离对各子表停止间接插入排序。仅增量因子为 1 时,全部序列作为一个表来处置,表长度即为全部序列的长度。
动图演示以下:


希尔排序算法较为艰涩难明,而且并不是最优的排序算法,现在已经被后来的快速排序算法给淘汰了。但是不成否认希尔对排序算法的演进具有开创性进献,在攀越算法高峰的路上,每一步都走得小心翼翼,我们只要铭刻这些巨大的带路人,以此激励自己不竭前行。
算法天下不尽完善。不但有典范算法在前奠基,后起之秀遗传算法、深度进修算法也熠熠生辉。算法天下还有很多"所罗门王的宝藏",一向静静地等待在"灯火衰退处",期待着人们去挖掘。






<h1 class="ql-align-center">进修方式

我给大师整理了一个进修计划,可以保存下图停止进修:


现在网上有很多资本、博客、论坛可供我们更方便地进修常识片断。但是这类类似兵来将挡、水来土掩般的进修方式虽然有用,却并不特此外好。这里保举大师在网上寻觅一些系统的进修教程,以帮助自己由浅入深,一路长大。


算法进修之道非一日之功,在技术提升的路上,力扣会一向助你前行。


本文作者:Alpinist Wang
声明:本文归 “力扣” 版权一切,如需转载请联系。
文中部分图片来历于收集,为非贸易用处利用,若有侵权联系删除。
感谢您的阅读
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

    联系我们
  • 咨询电话:0000 - 12345678 9999888877
  • 邮箱:123456789@qq . com
  • 地址:北京市海定区通州路群芳园二园1号楼9号
    移动客户端:
    关注我们:
  • 微信公众号:
  • 123cwyy
  • 扫描二维码加关注

快速回复 返回顶部 返回列表