此为 拉勾教育算法训练营 学习笔记
如老师所说，学习任何知识之前，都要先有知识体系的概念，要先找到知识之间的联系
知识体系比知识本身更重要，如果对知识体系掌握不全，就会在某个维度上缺少对知识的认知，形成漏洞或短板
数据结构与算法 知识体系
算法训练的最终目标：真正 掌握 数据结构与算法
- 数据结构有哪些？怎么实现的？
- 算法思维有哪些？怎么实现的？
只有“胸有成竹”，才能“张口就来”！
数据结构
数据结构的核心任务是存数据
计算机中，数据的存储方式只有两种：顺序存储 和 链式存储
数组 => 顺序存储
链表 => 链式存储（离散存储）
数组和链表是最基础的数据结构，其他数据结构的底层实现要么基于数组，要么基于链表，要么基于数组+链表
算法思维
算法的核心任务是操作数据
算法决定程序的效率
程序效率的衡量 包括 两个维度：时间复杂度 & 空间复杂度（内存）
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】
网友评论