算法训练 -- 前言
此为 拉勾教育算法训练营 学习笔记
如老师所说,学习任何知识之前,都要先有知识体系的概念,要先找到知识之间的联系
知识体系比知识本身更重要,如果对知识体系掌握不全,就会在某个维度上缺少对知识的认知,形成漏洞或短板
数据结构与算法 知识体系
算法训练的最终目标:真正 掌握 数据结构与算法
- 数据结构有哪些?怎么实现的?
- 算法思维有哪些?怎么实现的?
只有“胸有成竹”,才能“张口就来”!
数据结构
数据结构的核心任务是存数据
计算机中,数据的存储方式只有两种:顺序存储 和 链式存储
数组 => 顺序存储
链表 => 链式存储(离散存储)
数组和链表是最基础的数据结构,其他数据结构的底层实现要么基于数组,要么基于链表,要么基于数组+链表
算法思维
算法的核心任务是操作数据
算法决定程序的效率
程序效率的衡量 包括 两个维度:时间复杂度 & 空间复杂度(内存)
6C 解题方法论
1. Comprehend 理解题意
关键点:分析问题根源,寻找解题思路,构建可行方案
具体做法:尝试将问题提炼成模型,如:“这道题可以看做一个典型的xxxx问题!”
2. Choose 选择数据结构与算法
根据需求:选择数据结构,选择算法思维
3. Code 编码实现基本解法
使用注释,记录和梳理解题流程
先编写主体代码(按照解题流程一步一步编写),并本地测试
再处理边界问题,考虑特殊情况,并本地测试
4. Consider 思考更优解
寻找更好的 数据结构
剔除无效代码,优化空间消耗
删除不必要的操作、多余的变量、多余的数据结构,从而提高代码性能
寻找更好的 算法思维
例如:遇到数字相关的问题应该优先尝试使用数学方法实现功能
参考和借鉴 其他算法
5. Code 编码实现最优解
6. Change 变形与延伸
参考其他相关题目,或者思考改变本题的某个条件(操作对象的类型、范围等)后,该如何解决?
刷题方法论
学会立Flag,从少到多,从易到难,循序渐进
笔记目录
-
第一章 线性表
1.1 数组:实现整数的数字反转【leetcode 7】
1.1.1 整型字符串转换整数 atoi【leetcode 8】
1.1.2 颠倒二进制位【leetcode 190】
1.2 链表 + 数学:两数(大数)相加 【leetcode 2】
1.2.1 二进制求和 【leetcode 67】
1.2.2 两整数之和(不使用“+”)【leetcode 371】
1.3 栈:删除最外层括号【leetcode 1021】
1.3.1 最小栈 【leetcode 155】
1.3.2 栈的压入弹出序列 【leetcode 946】(剑指 offer 31)
1.4 队列:最近的请求次数【leetcode 933】
1.4.1 用栈实现队列【leetcode 232】
1.4.3 用队列实现栈【leetcode 225】
1.5 链表 + 快慢指针:环形链表【leetcode 141】
1.5.1 环形链表 II【leetcode 142】
1.5.2 反转链表【leetcode 206】
1.6 跳表:Redis 中如何实现有序集合?【leetcode 1206】
1.7 双指针:删除排序数组的重复项【leetcode 26】
1.7.1 删除排序链表中的重复元素【leetcode 83】
1.7.2 删除排序链表中的重复元素 II【leetcode 82】
1.8 无重复字符的最长子串【leetcode 3】
1.8.2 至多包含两个不同字符的最长子串【leetcode 159】
1.8.3 至多包含 K 个不同字符的最长子串【leetcode 340】
1.9 双端队列:翻转字符串里的单词【leetcode 151】
1.9.1 反转字符串中的单词 III【leetcode 557】
1.9.2 翻转字符串里的单词 II【leetcode 186】 -
第二章 递归、分治与贪心算法
2.1 递归:求汉诺塔问题
2.1.1 数字阶乘的计算
2.1.2 斐波那契数【leetcode 509】
2.2 排序 + 递归:特殊的二进制序列【leetcode 761】
2.2.1 按奇偶排序数组 II【leetcode 922】
2.2.2 数组的相对排序【leetcode 1122】
2.3 分治算法:排序矩阵查找
2.3.1 多数元素【leetcode 169】
2.3.2 最大子序和【leetcode 53】
2.4 归并排序 + 二分查找:寻找两个正序数组的中位数【leetcode 4】
2.4.1 二分查找【leetcode 704】
2.4.2 搜索二维矩阵【leetcode 74】
2.5 贪心算法:行相等的最少多米诺旋转【leetcode 1007】
2.5.1 分发饼干【leetcode 455】
2.5.2 买卖股票的最佳时机 II【leetcode 122】
2.6 栈 + 贪心:去除重复字母【leetcode 316】