数学建模社区-数学中国

标题: 算法越学越扎心，有没啥破解之法？ [打印本页]

作者: 杨利霞 时间: 2020-4-24 17:58
标题: 算法越学越扎心，有没啥破解之法？

算法越学越扎心，有没啥破解之法？
算法越学越扎心，有没啥破解之法？

对于算法的学习，我也是从一个小白一步步走来，当然，现在仍然很菜，，，不过，鉴于我觉得还有一些人比我更菜了，我决定谈谈我算法学习过程走过的坑，以及自己总结的一些经验。

切勿盲目刷题：刷题前的知识积累

说实话，想要提高自己的算法，真的没啥捷径，我觉得最好的捷径就是脚踏实地着多动手去刷题，多刷题。

但是，我必须提醒的是，如果你是小白，也就是说，你连常见的数据结构，如链表、树以及常见的算法思想，如递归、枚举、动态规划这些都没学过，那么，我不建议你盲目疯狂着去刷题的。而是先去找本书先去学习这些必要的知识，然后再去刷题。

因为，如果这些基础都不懂的话，估计一道题做了几个小时，然后看答案都看不懂，做题没有任何思路，这是很难受的。久而久之，估计没啥动力了，我刚开始就是这样，一道题答案看一天，然而还是不大懂，什么回溯啊，暴力啊，还不知道是啥意思。

也就是说，假如你要去诸如leetcode这些网站刷题，那么，你要先具备一定的基础，这些基础包括：

1、常见数据结构：链表、树(如二叉树)。（是的，链表和二叉树是重点，图这些可以先放着）

2、常见算法思想：贪婪法、分治法、穷举法、动态规划，回溯法。（贪婪、穷举、分治是基础，动态规划有难度，可以先放着）

以上列出来的算是最基本的吧。就是说你刷题之前，要把这些过一遍再去刷题。如果你连这些最基本的都不知道的话，那么你再刷题的过程中，会很难受的，思路也会相对比较少。

总之，千万不要急，先把这些基本的过一遍，力求理解，再去刷题。

在这里，我推荐基本我大一时看过的书籍吧，感觉还是非常不错的，如果对于数据结构时零基础的话，那么我建议你可以看《数据结构与算法分析：C语言描述版》这本书，这本书自认为真的很 nice，当时我把这本书里面的全部都看了，并且 coding 了一遍，感觉整个人有了质的飞跃。

后面我时在一些学校的OJ刷题，当时看的一本书叫做《挑战程序设计大赛》，日本作家写的，我觉得这本书也很nice，里面有分初级，中级和高级三个模块，基础比较差的可以从初级开始看起。

当然，这两本书，你可以在这个Github上找到：https://github.com/iamshuaidi/CS-Book
总结下：

提高数据结构与算法没啥捷径，最好的捷径就是多刷题。但是，刷题的前提是你要先学会一些基本的数据结构与算法思想。

AC不是目的，我们要追求完美

如何刷题？如何对待一道算法题？

我觉得，在做题的时候，一定要追求完美，千万不要把一道题做出来之后，提交通过，然后就赶紧下一道。我认为这意义不大，因为一道题的解法太多了，有些解法态粗糙了，我们应该要寻找最优的方法。

算法能力的提升和做题的数量是有一定的关系，但并不是线性关系。也就是说，在做题的时候，要力求一题多解，如果自己实在想不出来其他办法了，可以去看看别人是怎么做的，千万不要觉得模仿别人的做法是件丢人的事。

我做题的时候，我一看到一道题，可能第一想法就是用很粗糙的方式做，因为很多题采用暴力法都会很容易做，就是时间复杂度很高。之后，我就会慢慢思考，看看有没其他方法来降低时间复杂度或空间复杂度。最后，我会去看一下别人的做法，当然，并不是每道题都会这样执行。

衡量一道算法题的好坏无非就是时间复杂度和空间复杂度，所以我们要力求完美，就要把这两个降到最低，令他们相辅相成。

我举道例题吧：

问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

这道题我在以前的分章分析过，不懂的可以先看下之前写的：递归与动态规划—基础篇1

方法1：：暴力递归

这道题不难，或许你会采取下面的做法：

public int solve(int n){
if(n <= 2){
      return n;
}else{
      return solve(n-1) + solve(n-2);
}
}
1
2
3
4
5
6
7
这种做法的时间复杂度很高，指数级别了。但是如果你提交之后侥幸通过了，然后你就接着下一道题了，那么你就要好好想想了。

方法二：空间换时间

力求完美，我们可以考虑用空间换时间：这道题如何你去仔细想一想，会发现有很多是重复执行了。不行你可以画个图

所以可以采取下面的方法：

//用一个HashMap来保存已经计算过的状态
static Map<Integer,Integer> map = new HashMap();
public static int solve(int n){
   if(n <= 2){
      return n;
}else{//是否计算过
      if(map.containsKey(n)){
         return map.get(n);
      }else{
         int m = solve(n-1) + solve(n-2);
         map.put(n, m);
         return m;
      }
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
这样，可以大大缩短时间。也就是说，当一道题你做了之后，发现时间复杂度很高，那么可以考虑下，是否有更好的方法，是否可以用空间换时间。

方法三：斐波那契数列

实际上，我们可以把空间复杂度弄的更小，不需要HashMap来保存状态：

public static int solve(int n){
if(n <= 2){
      return n;
}
int f1 = 0;
int f2 = 1;
int sum = 0;
for(int i = 1; i<= n; i++){
      sum = f1 + f2;
      f1 = f2;
      f2 = sum;
}
return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
我弄这道题给你们看，并不是在教你们这道题怎么做，而是有以下目的：

1、在刷题的时候，我们要力求完美。

2、我想不到这些方法啊，怎么办？那么你就可以去看别人的做法，之后，遇到类似的题，你就会更有思路，更知道往哪个方向想。

3、可以从简单暴力入手做一道题，在考虑空间与时间之间的衡量，一点点去优化。

挑战自己，跳出舒适区

什么叫舒适区？在刷题的时候，可能有一类题是你比较懂的，你每次一看就有思路，然后半个小时就撸好代码，提交代码，然后通过了，然后，哇，又多刷了一道题，心里很舒服。

但是，记住，前期你可以多刷这种题练手，提升自己的乐趣，但，我还是建议你慢慢跳出舒适区，去做一些自己不擅长的题，并且找段时间一直刷这种题。例如，我觉得我在递归方面的题还是挺强的，
但是，我对动态规划的题，很菜，每次都要想好久，每次遇到这种题都有点害怕，没什么信心。不过有段时间我觉得只刷动态规划的题，直接在 leetcode 选定专题，连续做了四五十道，刚开始很难受，后来就慢慢知道了套路了，一道题从两三个小时最后缩到半小时，简单的十几分钟就搞定。感觉自己对这类型的题也不惧怕的。

当然，对于动态规划的学习，大家也可以看我这篇广受好评的文章：为什么你学不过动态规划？告别动态规划，谈谈我的经验

所以，建议你，一定要学好跳出自己的舒适区。

一定要学会分类总结

有些人以为 leetcode 的题刷的越多，就一定能越厉害，其实不然，leetcode 虽然有 1000 多道题，但题型就那么几类，我们前期在刷的时候，我是建议按照题型分类刷题的，例如我这整理刷二叉树相关，然后刷链表相关，然后二分法，然后递归等等，每刷一种题型，都要研究他们的套路，如果你愿意去总结，那么 leetcode 的题，其实你刷几百道，有目的、挑选的刷，我觉得就差不多了。

我看过一本书，叫做《程序员代码面试指南：IT 名企算法与数据结构题目最优解》，这本书就非常不错，里面按照栈，队列，链表，二叉树，字符串等一个专题一个专题来刷的，并且每道题都给出了最优解，而且里面的题有一定的难度，感兴趣的，真心不错，如果你把这本书的题全部搞定，并且总结相关套路，那么你的算法一定有很大的提升。

推荐一些刷题网站

我一般是在leetcode和牛客网刷题，感觉挺不错，题目难度不是很大。

在牛客网那里，我主要刷剑指Offer,不过那里也有个在线刷leetcode，不过里面的题量比较少。牛客网刷题有个非常方便的地方就是有个讨论区，那里会有很多大佬分享他们的解题方法，不用我们去百度找题解。所以你做完后，实在想不出，可以很方便着去看别人是怎么做的。

至于leetcode，也是大部分题目官方都有给出答案，也是个不错的刷题网站。你们可以两个挑选一个，或者两个都刷。

当然，还有其他刷题的网站，不过，其他网站没刷过，不大清除如何。

至于leetcode，有中文版和英文版

leetcode有中文版

英文版

根据自己的兴趣选。

学习一些解题技巧

说实话，有些题在你没看别人的解法前，你好不知道有这么美妙优雅的解法，看了之后，卧槽，居然还可以这样。而我们在刷题的过程中，就要不断累积这些技巧，当你累计多了，你就会形成一种
神经反应，一下子就想到了某种方法。解题技巧很多，例如数组下标法、位图法、双指针等等，我自己也分享过一篇总结一些算法技巧的文章

推荐阅读：一些常用的算法技巧总结

例如在刷题的时候，我们要学会巧用双指针、数组下标法、位运算等等技巧来解决问题，可能会有意想不到的效果。我给你再找点我之前写文章的一些例子吧：

分享一道解法巧妙的算法题

【算法技巧】位运算装逼指南

这是个长期累积的过程，我自己也精彩在我的公众号里分享一些解题的文章，感兴趣的可以关注我的公众号：帅地玩编程。

再说数据结构发重要性

前面我主要是说了我平时都是怎么学习算法的。在数据结构方法，我只是列举了你们一定要学习链表和树(二叉堆)，但这是最基本的，刷题之前要掌握的，对于数据结构，我列举下一些比较重要的：

1、链表（如单向链表、双向链表）。

2、树（如二叉树、平衡树、红黑树）。

3、图（如最短路径的几种算法）。

4、队列、栈、矩阵。

对于这些，自己一定要动手实现一遍。你可以看书，也可以看视频，新手可以先看视频，不过前期可以看视频，之后我建议是一定要看书。

例如对于平衡树，可能你跟着书本的代码实现之后，过阵子你就忘记，不过这不要紧，虽然你忘记了，但是如果你之前用代码实现过，理解过，那么当你再次看到的时候，会很快就记起来，很快就知道思路,而且你的抽象能力等等会在不知不觉中提升起来。之后再学习红黑树啊，什么数据结构啊，都会学的很快。

对于有哪些值得学习的算法，我之前也总结过，这里推荐给大家程序员必须掌握的核心算法有哪些？，这篇文章居然 40多万阅读量了，有点受宠若惊。

最最重要

动手去做，动手去做，动手去做。重要的话说三遍。

千万不要找了一堆资源，订好了学习计划，我要留到某某天就来去做…

千万不要这样，而是当你激情来的时候，就马上去干，千万不要留到某个放假日啊什么鬼了，很多这种想法的人，最后会啥也没做的。

也不要觉得要学习的有好多啊，不知道从哪学习起。我上面说了，可以先学习最基本的，然后刷题，刷题是一个需要长期坚持的事情，一年，两年。在刷题的过程中，可以穿插和学习其他数据结构。

总结一下吧

所以我给大家的建议就是，先学习基本的数据结构以及算法思想，不要盲目刷题，接着刷题的过程中，不能得过且过，尽量追求最优解，还有就是要跳出舒适区，逼自己成长，刷题的过程中，要学会分类总结。

当然，最重要的，就是你去动手了，不然，一切免谈！

看在熬夜写过的份上，送我个赞呗，嘻嘻。
————————————————
版权声明：本文为CSDN博主「帅地」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_37907797/article/details/104765116

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)