Leetcode 300题我学到了什么?

4.1
(7)

从一个算法小白,以C++作为自己的入门语言,回首起来,从刚开始一道题琢磨两天到现在稳步一天4题左右,实打实的感觉自己有所提高,虽然感觉在面试的时候还是有些慌……


Python很火热,但是我实在不太喜欢用Python来编程,因为每次在看到题解的时候,有些算法实在是过于Pythonic, 好像刷题的初心变成了学习API而不是对算法的理解与掌握上。


不过话说回来Python操作字符串真香,尤其是java python用split就能解决的时候,使用C++真的让人感觉很心累。
但是企业招聘机试的时候却并不看这个,在机试中AC比用什么样的算法往往更重要,所以为了备战牛客网,Pythonic还是要多多学习呀!不能为了坚持自己所谓的原则就放弃了工作面试的机会,嗯!
在这300题中我掌握的方法与技巧有:


* 搜索:DFS BFS 记忆化 剪枝 回溯 二分 two-pointers 归并
* 数据结构:线段树 树状数组 数组  
* 字符串:正则表达式 Trie树
* C++高级用法:Lambda表达式 智能指针 set map等数据结构 sort next_permutation等
* 图:拓扑排序 最大流 最短路径
* 树:递归思想
* 知悉动态规划
* 位运算

链表部分的题,主要考察的是细心,一旦把指针操作逻辑梳理好了再加上掌握一些题目(双指针找环路、指针逆序等)并不是特别复杂。


而对于树的部分,主要考察的是树的递归思想,在解决树的问题的时候,需要把自己的思想聚焦到一个最小子树中,对于这个问题,采取要先获取哪一部分的信息(根节点,左节点,右节点?)再对局部的问题进行处理,剩下的扔给递归来解决。虽然先序后序中序遍历也是递归,但是这种出发点还是一个线性思维,而对于树的问题要摆脱遍历的思想,从小问题入手解决大问题。


对于图的部分,除了掌握拓扑排序、最短路等基本的图论算法外,一个很常见的考点就是搜索啦,搜索是一个较大的考察点(但是在面试中动态规划考的比较多),什么时候用回溯(回溯的时间复杂度较高,这个问题是否有必要一定要用到回溯呢?),如何降低时间复杂度(引入记忆化搜索?或者直接找到状态转移方程使用动态规划来解决这个问题?)


对于位运算部分,这一类的题往往比较取巧,需要掌握计算机组成原理的一些知识,只有掌握了位运算才能深刻理解某些算法(比如树状数组中lowbit(x)函数为什么是(x & (-x)),如果是一个数是unsigned int, lowbit(x)函数是否能够继续使用?)。位运算一个比较经典的问题是:只需要遍历一次不需要额外空间找出数组中重复出现2次的数字。这一类问题尽管给出Solution比较简单,但是还是不要死记硬背,要在理解的基础上掌握其中的思想。


还有一个感觉就是现在能够从数据规模和问题返回的类型来推断考察的问题点啦,如果范围是20以内的,这个问题复杂度往往是指数级,解决这一类问题的方法往往是搜索或DP(比如TSP旅行商问题)。如果问题规模比较大1000 10000,这个时候往往不适合使用搜索算法,要考虑贪心等其他思路。如果问题要求返回最值(Max值或Min值)这一类问题往往是动态规划,如果问题需要返回具体的方案,这一类问题往往是搜索或回溯问题。此外,如果一个给出的数组是有序的,这往往暗示我们使用二分搜索或者Two-pointers这一类对数组顺序有要求的算法。倘若我们忽略掉这些信息,那就实在是太可惜了


此外,我能够在一些题中逐渐理解了递推 搜索 动态规划 贪心,从问题规模上找到他们之间的的区别和联系,可是对于动态规划部分我还是有些捉襟见肘…,遇到没有见过的题型还是无法自己手动退出状态转移方程,希望自己在300题、400题的时候多加练习,之后再多刷一遍,逐渐加深自己对状态转移方程之间的理解吧。


最后一个体会是,从0-100题的时候是最头疼的时候,但是一旦数量上来了,刷题的效率会越来越高,因为很多题背后的思想其实都是一样的,天道酬勤,我还是一个小渣渣,继续努力!

这篇文章是否对您有帮助?

请您为我打分吧!

平均分数 4.1 / 5. 投票数量: 7

发表评论

电子邮件地址不会被公开。 必填项已用*标注