【038-week1】总结

[jianghaoyuan2007]

本周算法学习总结

本周没有对哪个具体的技术进行深入的思考。所以，以下内容均为对本周学习到的内容进行总结。

链表

链表相关问题的汇总如下：

• 判断链表是否有环

  使用快慢指针 —— 快指针每次走两步，慢指针每次走一步，如果最后两指针相遇，那么表示链表含有环。

• 计算含环链表中环的大小

  找到环中任意一结点后，继续遍历并累加其循环次数，再次回到该结点时候，则计算出环的大小。

• 计算有环链表中入环的结点

  使用两个指针。指针p先走l步（环的大小），指针p再与指针p同速前行。两指针相遇的点就是链表中入环的结点。

• 链表插入和删除相关的技巧

  在链表中删除和添加结点的时候，非常容易出错。为此可以构造一个带头的链表，头结点的next指向要修改的链表的第一个结点。

递归

递归相关问题汇总如下：

• 使用递归求解‌划分 k 个相等子集的问题

  依次尝试将数组中的元素放入到 k 个子集当中。

测试用例

当编写测试用例发愁的时候，可以朝着这三个方面来编写：

1. 功能测试

2. 边界条件测试

3. 特殊输入测试

解题过程的分解与优化

面对一个复杂的问题，有效的办法就是将其进行分解成子任务。所以，将过去的编码和测试改成了以下的过程：

1. 明确问题
2. 输出相关的边界条件
3. 绘制相关的图表
4. 为测试用例编写辅助的函数
5. 编写测试用例
6. 方案汇总（时间复杂度和空间复杂度）
7. 确定执行方案
8. 伪代码设计
9. 编写代码
10. 执行测试用例
11. 重构优化
12. 提交代码
13. 相关总结（知识点 & 技巧）