LeetCode刷题回顾与总结

2020.5.27记

截止 5.27日，leetcode总刷题数到达200，写一篇文章以回顾，总结。

起因

非计算机专业出身的程序员, 经历过很多因为数据结构算法能力薄弱, 而错失了机会的情况。

几个面试遇到算法，一脸懵逼的经历.

  • 贝壳, 二叉树反转 毫无思路,..

  • 百度, 堆排序, 心里在想 堆 是什么鬼…

  • 美团, 合并两个有序数组 , 只想出了数组插入, 而被吐槽时间复杂度高,…

  • 新氧, 字符串匹配只写出了暴力法, 面试官提醒下, 仍然不知道什么是KMP..

  • 新东方, 面试官 : 假设你们房天下有海量数据的楼盘数据, 如何选出其中价格最低的 10 条? 我 : 遍历？或者排序？ 面试官 : 哦, 那可能数据量小时还可以…

  • …

没有数据结构和算法的基础, 深感技术路线寸步难行。

遂决定, 学习数据结构与算法

学习

可以说是学习, 也可以说是扫盲。 之前确实都是知识盲区。

Objective-C用久了, 其中的数据结构用的很6, 例如NSArray,NSMutableArray,NSString,NSDictionary, NSMutableDictionary,NSSet 等。

但是如果说 NSMutableArray 为什么能实现动态添加/删除元素？NSDictionary 实现原理？ NSSet实现原理？ 真心不懂.

语言环境

学习数据结构使用的Java , 开发工具使用的IntelliJ IDEA。

为什么使用Java?

  • Java开源, 并且java.util中有各种数据结构的开源代码,例如 ArrayList;LinkedList;TreeSet; TreeMap; HashSet;HashMap;PriorityQueue等, 可以查看自己写的代码跟库代码的差距。
  • leetcode刷题, 使用Java很方便。

正式开始

在2019.07 正式开始了Java + 数据结构算法的学习之路.

从基础的开始, 跟着李明杰的课程将 动态数组 , 链表, 队列, 栈, 集合, 二叉树, BST, AVLTree RedBlackTree, 堆等常用数据结构 用Java实现了一遍。

在实现完以上各种常见数据结构以后, 开始学习高级一些的数据结构如,图,跳表,并查集。 以及排序, 递归，动态规划，贪心策略，分治，KMP等。

学习某种数据结构或者算法时, 同步刷一些leetcode相关题目, 把题解以及逐步优化的思路整理，写到博客上，方便以后复习。

感想

  • 解决同一道题目, 使用不同的思路解决, 效率相差又何止数倍.

    • e.g. 求斐波那契数列第N项时，使用递归 和 递推(简单动态规划)在时间复杂度上的差别。

    • 递归存在大量重复调用, 时间复杂度 O(2 ^ N), 指数级,

    • 递推, 从小值逐步推到出大的值, 时间复杂度为 O(N). 常数级.

  • 实现同样的功能,使用不同的数据结构, 效率也是天壤之别.

    • e.g. LinkedList / ArrayList在查询是否存在某元素时, 时间复杂度 : O(N).
    • 使用二叉搜索树呢？ 因为BST, 因为左子树 < 父节点的值 < 右子树, 可以将时间复杂度降低至 O (log N).
    • BST, 在极端情况，如插入顺序如果为升序时, 有可能退化为链表(只有右子树，无左子树)的情况.
    • 所以引入了BBST, 在每次插入/删除元素后, 恢复树的平衡. 来提高检索效率.

  • 深深感觉到数据结构和算法对程序执行效率的巨大影响.

    • 以后写业务或者解题过程中, 一定要注重使用最合适的数据结构, 找到最优的算法。
    • 多思考, 多学习他人的思路, 有更优的思路记录下来复习, 下次碰到类似的，能活学活用, 转换成自己的东西。

阶段性小成果

现在面试如果被问到以前的知识盲区? 可以轻松的回答出来.

  • 二叉树反转 ?

其实是考的二叉树遍历，可以用递归/迭代的前序遍历/中序遍历/后序遍历， 和迭代的层序遍历写出来.

  • 堆排序 ?

可以写出来 原地建堆heaptify, 下滤 siftDown 操作，知道其 O(N * logN)的时间复杂度。

  • 合并两个有序数组?

归并排序了解一下, 先divide, 再merge， merge不就是合并两个有序数组吗。

  • KMP, 即使手写不出next表的构建, 也能大致说出其中原理。

选出价格最低的10个楼盘? 这不就是Top K问题?

排序的话，用最优的快排，平均时间复杂度 : O(N * log N).

而使用二叉堆, 新建一个大顶堆，堆的size为10, 海量数据依次入堆, 遍历完毕，堆中剩下的元素就是最小的10个元素。 平均时间复杂度 : O(N * logK).

…

LeetCode

屏幕快照 2020-05-28 下午2.13.17

到昨天为止, 整整200题，其中也有重复的.

  • 从一开始跟着李明杰的课程刷题。
  • 到独立刷题, 很少能有思路，基本都是去题解看人家的思路，理解了自己再写一遍。
  • 再到偶尔碰到一些题，能想到解题思路, 能独立写出来。

能感受到自己这大半年以来的进步, 但仍然是个小学生。 还有大量的知识等着去学习, 大量的题目等着去刷…

2020.06.30记录

截止 2020.6.30日, 刷题数量达到300，更新下回顾与总结.

截屏2020-06-30下午11.29.11

200-300题感想

  • 200 - 300题，沉浸在提交后 Accept 的感觉，希望尽快达到这个节点。

  • 依然有很多知识盲区：

    • 回溯算法，理解思路，但是写的时候还是写不出来？
    • 位运算，碰到这类题目，就碰到了盲区，心里想，下次学习并整理一篇位运算的知识，题目。到现在也没整理
    • 动态规划, 各类 dp 问题，都能搞定吗？ 我想大部分的还是搞不定的。
    • 滑动窗口 ，别的不提，接雨水的经典问题 都拖延了多久没碰了。
    • …
    • 类似这种 在舒适区外，就躲避的例子还有很多…

  • 看起来，好像 200 - 300题的阶段，一直在自己的舒适区里，刷题刷题刷题。

  • 缺乏总结与复习，往前冲的做法，看上去做的题目数量多了。

  • 又有多少真正转化为了自己的东西了呢？ 好像也并不多，各类算法掌握的也不扎实。

后续计划