青蛙过河leetcode algorithm:刷题记录

青蛙过河leetcode切题Clarification：明确题目要求

Possible solutions：所有可能解法

Compare (time/space)：比较解法的时间和空间复杂度

Optimal：选择最优解法

Coding Test cases：编写测试用例

五遍刷题

第一遍（5-10分钟）：读题+思考

• 有思路：开始做和写代码

• 无思路：直接看解法，学习多种解法，比较优劣，尝试默写和背诵

第二遍：立即自己写→ LeetCode提交，比较多种解法并优化

第三遍（24小时后）：重复做题，掌握不同解法，进行专项练习

第四遍（一周后）：反复练习相同的题目，巩固解法

第五遍（面试前一周）：恢复性训练，强化记忆

时间复杂度分析

• 树的遍历：前、中、后序遍历 O(n)

• 图的遍历：O(n)

• 搜索算法：DFS、BFS O(n)

• 二分查找：O(logn)

• 跳表：升维思想，空间换时间，多级索引，增加log2n个级索引，时间复杂度logn，但维护成本较高

常见题目

1. 两数和

2. 盛水最多的容器

3. 三数和

4. 合并两个有序链表

5. 删除有序数组中的重复项

6. 加一

7. 爬楼梯

8. 合并两个有序数组

9. 环形链表

10. 旋转数组